# Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax Regret

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 37 references that are in the map.
- First posted on arXiv 22 Jan 2021.

## Builds on (most cited first, 7 of 7)

- [Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit](https://mlsanity.com/paper/1802.03692/) (2018)
- [A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem](https://mlsanity.com/paper/1711.03539/) (2017)
- [Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards](https://mlsanity.com/paper/1405.3316/) (2014)
- [Taming Non-stationary Bandits: A Bayesian Approach](https://mlsanity.com/paper/1707.09727/) (2017)
- [On Abruptly-Changing and Slowly-Varying Multiarmed Bandit Problems](https://mlsanity.com/paper/1802.08380/) (2018)
- [Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits](https://mlsanity.com/paper/1902.01575/) (2019)
- [A Reliability-aware Multi-armed Bandit Approach to Learn and Select Users in Demand Response](https://mlsanity.com/paper/2003.09505/) (2020)

## Built on by (most cited first, 6 of 6)

- [Non-Stationary Representation Learning in Sequential Linear Bandits](https://mlsanity.com/paper/2201.04805/) (2022)
- [Improving Few-Shot Generalization by Exploring and Exploiting Auxiliary Data](https://mlsanity.com/paper/2302.00674/) (2023)
- [Stochastic Multi-armed Bandits with Non-stationary Rewards Generated by a Linear Dynamical System](https://mlsanity.com/paper/2204.05782/) (2022)
- [Representation Learning for Context-Dependent Decision-Making](https://mlsanity.com/paper/2205.05820/) (2022)
- [Adapting Foundation Models for Few-Shot Medical Image Segmentation: Actively and Sequentially](https://mlsanity.com/paper/2502.01000/) (2025)
- [Maximizing Success Rate of Payment Routing using Non-stationary Bandits](https://mlsanity.com/paper/2308.01028/) (2023)

## Abstract (arXiv)

We study the nonstationary stochastic Multi-Armed Bandit (MAB) problem in which the distribution of rewards associated with each arm are assumed to be time-varying and the total variation in the expected rewards is subject to a variation budget. The regret of a policy is defined by the difference in the expected cumulative rewards obtained using the policy and using an oracle that selects the arm with the maximum mean reward at each time. We characterize the performance of the proposed policies in terms of the worst-case regret, which is the supremum of the regret over the set of reward distribution sequences satisfying the variation budget. We extend Upper-Confidence Bound (UCB)-based policies with three different approaches, namely, periodic resetting, sliding observation window and discount factor and show that they are order-optimal with respect to the minimax regret, i.e., the minimum worst-case regret achieved by any policy. We also relax the sub-Gaussian assumption on reward distributions and develop robust versions the proposed polices that can handle heavy-tailed reward distributions and maintain their performance guarantees.