On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems

By Aurélien Garivier, Eric Moulines. 2008

337 citations recorded by the source corpus.

Multi-armed bandit problems are considered as a paradigm of the trade-off between exploring the environment to find profitable actions and exploiting what is already known. In the stationary case, the distributions of the rewards do not change in time, Upper-Confidence Bound (UCB) policies have been shown to be rate optimal. A challenging variant of the MABP is the non-stationary bandit problem where the gambler must decide which arm to play while facing the possibility of a changing environment. In this paper, we consider the situation where the distributions of rewards remain constant over epochs and change at unknown time instants. We analyze two algorithms: the discounted UCB and the sliding-window UCB. We establish for these two algorithms an upper-bound for the expected regret by upper-bounding the expectation of the number of times a suboptimal arm is played. For that purpose, we derive a Hoeffding type inequality for self normalized deviations with a random number of summands. We establish a lower-bound for the regret in presence of abrupt changes in the arms reward distributions. We show that the discounted UCB and the sliding-window UCB both match the lower-bound up to a logarithmic factor.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/6eb7f22b9329ff77d0bdb6d86f35a7b6e62be1e3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Reactive Exploration to Cope with Non-Stationarity in Lifelong Reinforcement Learning (2022, background): “The latter is often referred to as piecewise stationary (Hartland et al., 2007; Garivier & Moulines, 2008; Cao et al., 2019).”
Optimism in reinforcement learning and Kullback-Leibler divergence (2010, background): “The proof relies on the two following concentration inequalities due to [7, 8]: for all x ∈ X , a ∈ A, any CP > 0, and CR > 0, it holds that”
Agent57: Outperforming the Atari Human Benchmark (2020, methodology): “Inspired by Schaul et al. (2019), we propose using a simple non-stationary multi-armed bandit (Garivier & Moulines, 2008) to directly control the exploration rate and discount factor to maximize the episode return, and then provide this information to the value network of the agent as an input.”
Improved Algorithms for Linear Stochastic Bandits (2011, positive): “…et al. (2008) (when it is used with a ﬁxed , by avoiding union bounds, or the need to know the horizon, or the doubling trick) or to improve the bounds derived by Garivier and Moulines (2008) for UCB for changing environments, or the stopping rules and racing algorithms of Mnih et al. (2008).”
Identifying Unknown Unknowns in the Open World: Representations and Policies for Guided Exploration (2016, methodology): “established a lower bound on the regret in the presence of abrupt changes in the reward distributions of the arms and also showed that discounted UCB matches this lower bound upto a logarithmic factor (Garivier and Moulines 2008).”