2017

Taming Non-stationary Bandits: A Bayesian Approach

Raj, Vishnu, Kalyani, Sheetal

Understand

We consider the multi armed bandit problem in non-stationary environments.

Based on the Bayesian method, we propose a variant of Thompson Sampling which can be used in both rested and restless bandit scenarios.
Applying discounting to the parameters of prior distribution, we describe a way to systematically reduce the effect of past observations.
Further, we derive the exact expression for the probability of picking sub-optimal arms.

Built on

On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples
William R. Thompson · 1933
Earlier work this paper cites.
Some Aspects of the Sequential Design of Experiments
Robbins Herbert · 1952
Earlier work this paper cites.
Bandit Processes and Dynamic Allocation Indices
J. C. Gittins · 1979
Earlier work this paper cites.
A Dynamic Allocation Index for the Discounted Multiarmed Bandit Problem
J. C. Gittins and D. M. Jones · 1979
Earlier work this paper cites.
Asymptotically Efficient Adaptive Allocation Rules
T.L. Lai and Herbert Robbins · 1985
Earlier work this paper cites.
On The Gittins Index For Multiarmed Bandits
Richard Weber · 1992
Earlier work this paper cites.
Gambling in a rigged casino: The adversarial multi-armed bandit problem
Peter Auer, Nicolo Cesa Bianchi, Yoav Freund, and R.E. Schapire · 1995
Earlier work this paper cites.
Distributions of the ratios of independent beta variables and applications
T Pham-Gia · 2000
Earlier work this paper cites.
Finite time analysis of the multiarmed bandit problem
Peter Auer, Nicolo Cesa Bianchi, and P Fischer · 2002
Earlier work this paper cites.
The Non-Stochastic Multi-Armed bandit problem
Peter Auer, Nicolo Cesa Bianchi, Yoav Freund, and Robert E.Schapire · 2002
Earlier work this paper cites.
Multi-Armed Bandit Algorithms and Empirical Evaluation
Joannes Vermorel and Mehryar Mohri · 2005
Earlier work this paper cites.

Similar

Multi-armed bandit, dynamic environments and meta-bandits, 2006
C Hartland, S Gelly, N Baskiotis, O Teytaud, and M Sebag · 2006
Cited alongside, same era.
Adapting to a Stochastically Changing Environment: The Dynamic Multi-Armed Bandits Problem, 2007
Aleksandrs Slivkins and Eli Upfal · 2007
Cited alongside, same era.
Adapting to a changing environment: The Brownian restless bandits
A. Slivkins and E. Upfal · 2008
Cited alongside, same era.
UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem
Peter Auer and Ronald Ortner · 2010
Cited alongside, same era.
A modern Bayesian look at the multi-armed bandit
Steven L. Scott · 2010
Cited alongside, same era.
An Empirical Evaluation of Thompson Sampling
Olivier Chapelle and Lihong Li · 2011
Cited alongside, same era.
The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond
Aurelien Garivier and Olivier Cappe · 2011
Cited alongside, same era.
On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems
Aurelien Garivier and Eric Moulines · 2011
Cited alongside, same era.
Thompson sampling for dynamic multi-armed bandits
Neha Gupta, Ole Christoffer Granmo, and Ashok Agrawala · 2011
Cited alongside, same era.
Analysis of Thompson Sampling for the multi-armed bandit problem
Shipra Agrawal and Navin Goyal · 2012
Cited alongside, same era.
On Bayesian upper confidence bounds for bandit problems
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier · 2012
Cited alongside, same era.

Then

Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
S Bubeck and Nicolo Cesa Bianchi · 2012
Later among the works it cites.
The Best of Both Worlds: Stochastic and Adversarial bandits
S Bubeck and Aleksandrs Slivkins · 2012
Later among the works it cites.
Optimistic bayesian sampling in contextual-bandit problems
Benedict C. May, Nathan Korda, Anthony Lee, and David S. Leslie · 2012
Later among the works it cites.
Further Optimal Regret Bounds for Thompson Sampling
Shipra Agrawal · 2013
Later among the works it cites.
One practical algorithm for both stochastic and adversarial bandits
Y. Seldin and A. Slivkins · 2014
Later among the works it cites.
Stochastic Multi-Armed-Bandit Problem with Non-stationary Rewards
Omar Besbes, Yonatan Gur, and Assaf Zeevi · 2014
Later among the works it cites.
Explore no more: improved high-probability regret bounds for non-stochastic bandits
Gergely Neu · 2015
Later among the works it cites.
A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit
Giuseppe Burtini, Jason Loeppky, and Ramon Lawrence · 2015
Later among the works it cites.
A Note on Information-Directed Sampling and Thompson Sampling
Li Zhou · 2015
Later among the works it cites.
An Information-Theoretic Analysis of Thompson Sampling
Daniel Russo and Benjamin Van Roy · 2016
Later among the works it cites.
Thompson Sampling is Asymptotically Optimal in General Environments
Jan Leike, Tor Lattimore, Laurent Orseau, and Marcus Hutter · 2016
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…