Tracking the Best Expert in Non-stationary Stochastic Environments

Abstract

We study the dynamic regret of multi-armed bandit and experts problem in non-stationary stochastic environments. We introduce a new parameter $\Lambda$, 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 $\Lambda$ and $\Gamma$, which counts the number of times the distributions change, as well as $\Lambda$ and $V$, which measures how far the distributions deviates over time. One striking result we find is that even when $\Gamma$, $V$, and $\Lambda$ 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 $\Gamma$ and $\Lambda$, as it can be made independent of $T$, while with constant $V$ and $\Lambda$, 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.

References in corpus (2)

• Empirical Bernstein Bounds and Sample Variance Penalization
• A Second-order Bound with Excess Losses

Cited by in corpus (18)

• A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
• Hedging the Drift: Learning to Optimize under Non-Stationarity
• Decentralized Online Learning: Take Benefits from Others' Data without Sharing Your Own to Track Global Trend
• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem
• Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions
• Bandit Convex Optimization in Non-stationary Environments
• Proximal Online Gradient is Optimum for Dynamic Regret
• Combinatorial Semi-Bandit in the Non-Stationary Environment
• Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications
• Improved Path-length Regret Bounds for Bandits
• Taking a hint: How to leverage loss predictors in contextual bandits?
• Online Second Price Auction with Semi-bandit Feedback Under the Non-Stationary Setting
• Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits
• Distribution-dependent and Time-uniform Bounds for Piecewise i.i.d Bandits
• Adaptive and Efficient Algorithms for Tracking the Best Expert
• Online estimation and control with optimal pathlength regret
• Online Learning with Automata-based Expert Sequences