Stochastic Multi-Armed-Bandit Problem with Non-stationary Rewards

By Yonatan Gur, Assaf J. Zeevi, Omar Besbes. Neural Information Processing Systems, 2014

434 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/2295f2034c2a45a39fd1a08605d2a8e0588e7e4d

How researchers see this paper

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

Citations in the corpus

Near-Optimal Model-Free Reinforcement Learning in Non-Stationary Episodic MDPs (2021, methodology): “Our algorithm adopts a simple but effective restarting strategy (Jaksch et al., 2010; Besbes et al., 2014) that resets the memory of the agent according to a calculated schedule.”
Reactive Exploration to Cope with Non-Stationarity in Lifelong Reinforcement Learning (2022, background): “Besbes et al. (2014) characterize the regret in MAB problems with non-stationary rewards such that there is a link between reward variation and minimal achievable regret to factor in a variation budget to allow for temporal changes.”
Online Adaptative Curriculum Learning for GANs (2018, background): “In the non-stationary stochastic bandits (Besbes et al., 2014) case, each action a ∈ A is associated with mean μa,t on time t.”
Markov Decision Processes with Time-varying Transition Probabilities and Rewards (2019, background): “Part i) is common in literature when the problem considered does not have a Markov processe structure, e.g. (Besbes et al., 2014; 2015).”
Optimizing for the Future in Non-Stationary MDPs (2020, background): “In contrast, non-stationary multi-armed bandits (NMAB) capture the setting where the horizon length is one, but the reward distribution changes over time (Moulines, 2008; Besbes et al., 2014).”
Dealing with Non-Stationarity in MARL via Trust-Region Decomposition (2021, methodology): “…the convergence to the best-response from each agent’s perspective, we consider an objective of minimizing the dynamic regret (Jaksch et al., 2010; Besbes et al., 2014; Cheung et al., 2019; Mao et al., 2021) In the oracle =1 ρ ∗ t , the summand ρ ∗ t is the optimal long-term average reward of the…”
Tracking the Best Expert in Non-stationary Stochastic Environments (2017, methodology): “The problem stems from the fact that [9] considers the traditional adversarial setting, while [3] studies the non-stationary stochastic setting.”
Bandit Algorithms (2020, methodology): “The approach based on Brownian motion is due to Slivkins and Upfal [2008] while the variant described in Note 4 is by Besbes et al. [2014]. The idea of discounted UCB was introduced without analysis by Kocsis and Szepesvári [2006]. The analysis of this algorithm and also of Sliding-Window UCB algori”
A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity (2017, methodology): “Besbes et al. (2014) proposed the Rexp3 algorithm (based on Exp3) for this setting and their results highlight a trade-off that exists between retaining and forgetting information, i.e., the fewer past observations to recall, the larger the associated error; the more past observations, the higher th”
A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces (2020, background): “As a sanity-check, we note that in stationary MDPs, for which ∆ = 0 , we recover the regret bound of Kernel-UCBVI 7 (Domingues et al., 2020) , which is optimal for d = 1 in the (stationary) bandit case (Bubeck et al., 2011).”