# Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards

arXiv: https://arxiv.org/abs/1405.3316 · HTML: https://mlsanity.com/paper/1405.3316/

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2014.

## Built on by (most cited first, 30 of 42)

- [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021)
- [Continual Learning as Computationally Constrained Reinforcement Learning](https://mlsanity.com/paper/2307.04345/) (2023)
- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [Non-Stationary Bandit Learning via Predictive Sampling](https://mlsanity.com/paper/2205.01970/) (2022)
- [No-Regret Algorithms for Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2102.06296/) (2021)
- [Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs](https://mlsanity.com/paper/2110.08984/) (2021)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [Reactive Exploration to Cope with Non-Stationarity in Lifelong Reinforcement Learning](https://mlsanity.com/paper/2207.05742/) (2022)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits](https://mlsanity.com/paper/2107.11419/) (2021)
- [On Slowly-varying Non-stationary Bandits](https://mlsanity.com/paper/2110.12916/) (2021)
- [Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax Regret](https://mlsanity.com/paper/2101.08980/) (2021)
- [An Online Learning Approach to Optimizing Time-Varying Costs of AoI](https://mlsanity.com/paper/2105.13383/) (2021)
- [Stochastic Saddle Point Problems with Decision-Dependent Distributions](https://mlsanity.com/paper/2201.02313/) (2022)
- [Non-stationary Reinforcement Learning under General Function Approximation](https://mlsanity.com/paper/2306.00861/) (2023)
- [Addressing the Long-term Impact of ML Decisions via Policy Regret](https://mlsanity.com/paper/2106.01325/) (2021)
- [Learning to Bid in Non-Stationary Repeated First-Price Auctions](https://mlsanity.com/paper/2501.13358/) (2025)
- [Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directions](https://mlsanity.com/paper/2601.15353/) (2026)
- [Kolmogorov-Smirnov Test-Based Actively-Adaptive Thompson Sampling for Non-Stationary Bandits](https://mlsanity.com/paper/2105.14586/) (2021)
- [Towards Futuristic Autonomous Experimentation--A Surprise-Reacting Sequential Experiment Policy](https://mlsanity.com/paper/2112.00600/) (2021)
- [Adaptive Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2407.08654/) (2024)
- [Competing Bandits in Time Varying Matching Markets](https://mlsanity.com/paper/2210.11692/) (2022)
- [Dynamic Pricing and Learning under the Bass Model](https://mlsanity.com/paper/2103.05199/) (2021)
- [Bridging Adversarial and Nonstationary Multi-armed Bandit](https://mlsanity.com/paper/2201.01628/) (2022)
- [Variance-Dependent Regret Bounds for Non-stationary Linear Bandits](https://mlsanity.com/paper/2403.10732/) (2024)
- [Non-Stationary Dueling Bandits Under a Weighted Borda Criterion](https://mlsanity.com/paper/2403.12950/) (2024)
- [Regression Oracles and Exploration Strategies for Short-Horizon Multi-Armed Bandits](https://mlsanity.com/paper/2102.05263/) (2021)
- [Dynamic neighbourhood optimisation for task allocation using multi-agent](https://mlsanity.com/paper/2102.08307/) (2021)
- [Bayesian adversarial multi-node bandit for optimal smart grid protection against cyber attacks](https://mlsanity.com/paper/2104.02774/) (2021)
- [Periodic-GP: Learning Periodic World with Gaussian Process Bandits](https://mlsanity.com/paper/2105.14422/) (2021)

## Abstract (arXiv)

In a multi-armed bandit (MAB) problem a gambler needs to choose at each round of play one of K arms, each characterized by an unknown reward distribution. Reward realizations are only observed when an arm is selected, and the gambler's objective is to maximize his cumulative expected earnings over some given horizon of play T. To do this, the gambler needs to acquire information about arms (exploration) while simultaneously optimizing immediate rewards (exploitation); the price paid due to this trade off is often referred to as the regret, and the main question is how small can this price be as a function of the horizon length T. This problem has been studied extensively when the reward distributions do not change over time; an assumption that supports a sharp characterization of the regret, yet is often violated in practical settings. In this paper, we focus on a MAB formulation which allows for a broad range of temporal uncertainties in the rewards, while still maintaining mathematical tractability. We fully characterize the (regret) complexity of this class of MAB problems by establishing a direct link between the extent of allowable reward "variation" and the minimal achievable regret. Our analysis draws some connections between two rather disparate strands of literature: the adversarial and the stochastic MAB frameworks.