On Upper-Confidence Bound Policies for Switching Bandit Problems

By Aurélien Garivier, Eric Moulines. International Conference on Algorithmic Learning Theory, 2011

591 citations recorded by the source corpus.

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

View Paper: https://www.semanticscholar.org/paper/2b9c08bc8b18358c074d6f8c105ad6158e97e489

How researchers see this paper

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

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Introduction to Multi-Armed Bandits (2019, background): “For a fixed S, any algorithm suffers regret Ω( √ SKT ) in the worst case (Garivier and Moulines, 2011).”
Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism (2020, methodology): “This has been proved to work well in stationary and non-stationary bandit settings (Auer et al., 2002a; Garivier & Moulines, 2011b; Cheung et al., 2019b;a).”
Dynamic Pricing and Learning: Historical Origins, Current Research, and New Directions (2013, unknown): “3, is related to the non-stationary multiarmed bandit problem [304,305].”
Continuous Meta-Learning without Tasks (2019, methodology): “We use the notion of regret defined in [14], in which the chosen action is compared to the action with the best mean reward at each time, with perfect knowledge of switches.”
An exploration strategy for non-stationary opponents (2017, methodology): “In particular, two algorithms are based the upper confidence bounds (UCB) algorithm [1] to detect changes: one relies on the discounted UCB and the other one adopts a sliding window approach [21].”
Stochastic Multi-Armed-Bandit Problem with Non-stationary Rewards (2014, background): “, [25] and references therein (see also [26] in the adversarial context).”
A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity (2017, background): “Garivier and Moulines (2011) proposed two methods: the discounted UCB (D-UCB) whose policy averages past rewards with a discount factor giving more weight to recent observations; and the sliding-window approach (SW-UCB) which relies on a local empirical information of the last τ plays (τ being a…”
Tracking the Best Expert in Non-stationary Stochastic Environments (2017, methodology): “Let us remark that although an Ω( √ ΓT ) lower bound was also given in [9], it was achieved by distributions with Λ ≥ Ω(T ).”
Near-Optimal Model-Free Reinforcement Learning in Non-Stationary Episodic MDPs (2021, methodology): “Within different non-stationary multi-armed bandit (MAB) settings, various methods have been proposed, including decaying memory and sliding windows (Garivier & Moulines, 2011; Keskin & Zeevi, 2017), as well as restart-based strategies (Auer et al., 2002; Besbes et al., 2014; Alle-siardo et al.,…”
Sequential Transfer in Multi-armed Bandit with Finite Set of Models (2013, background): “Garivier and Moulines (2011) introduces a modifiedv rsion of UCB using either a sliding window or discounting totrack the changing distributions and they show, when optimally tuned w.r.t. the number of switchesR, it achieves a (worst-case) expected regret of orderO( √ TR) over a total number of…”
A Meta-MDP Approach to Exploration for Lifelong Reinforcement Learning (2019, background): “In this paper, however, we focus on one aspect of lifelong learning: when faced with a sequence of MDPs sampled from a distribution over MDPs, how can a reinforcement learning agent learn an optimal policy for exploration? Specifically, we do not consider the question of when an agent should explore”
A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces (2020, methodology): “…in particular recover previously studied forgetting mechanisms to tackle non-stationarity in bandits and RL: sliding windows (Gajane et al., 2018) and exponential discounting (Kocsis and Szepesvári, 2006; Garivier and Moulines, 2011; Russac et al., 2019), and allow for combinations between those.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, unknown): “An apparently similar problem was studied by Garivier and Moulines [2011], where they assume that the reward distributions can abruptly change at unknown time instants (and there is a small number of such change-points). Within this model, the authors prove that the best possible regret is of order ”
Bandit Algorithms (2020, background): “Hazan and Kale [2011] gave an algorithm for which Rn = O(k2 √ Qt), which can be better than the worst-case bound of Exp3 or Exp3-IX when the quadratic variation is very small.”