Tracking the Best Expert in Non-stationary Stochastic Environments
This work addresses the challenge of dynamic regret in online learning for non-stationary environments, which is incremental as it builds on existing bandit and expert problems by introducing new parameters and bounds.
The paper tackles the problem of tracking the best expert in non-stationary stochastic environments by introducing a new parameter Λ to measure total statistical variance and analyzing its interaction with other parameters like Γ and V, finding that regret lower bounds can still grow with T even under constant constraints in bandit settings, while constant regret becomes achievable in full-information settings under certain conditions.
We study the dynamic regret of multi-armed bandit and experts problem in non-stationary stochastic environments. We introduce a new parameter $Λ$, which measures the total statistical variance of the loss distributions over $T$ rounds of the process, and study how this amount affects the regret. We investigate the interaction between $Λ$ and $Γ$, which counts the number of times the distributions change, as well as $Λ$ and $V$, which measures how far the distributions deviates over time. One striking result we find is that even when $Γ$, $V$, and $Λ$ are all restricted to constant, the regret lower bound in the bandit setting still grows with $T$. The other highlight is that in the full-information setting, a constant regret becomes achievable with constant $Γ$ and $Λ$, as it can be made independent of $T$, while with constant $V$ and $Λ$, the regret still has a $T^{1/3}$ dependency. We not only propose algorithms with upper bound guarantee, but prove their matching lower bounds as well.