# Bridging Adversarial and Nonstationary Multi-armed Bandit

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 27 references that are in the map.
- First posted on arXiv 5 Jan 2022.

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

- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [A Survey on Practical Applications of Multi-Armed and Contextual Bandits](https://mlsanity.com/paper/1904.10040/) (2019)
- [Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards](https://mlsanity.com/paper/1405.3316/) (2014)
- [Prediction with Corrupted Expert Advice](https://mlsanity.com/paper/2002.10286/) (2020)
- [On Optimal Robustness to Adversarial Corruption in Online Decision Problems](https://mlsanity.com/paper/2109.10963/) (2021)
- [Learning Product Rankings Robust to Fake Users](https://mlsanity.com/paper/2009.05138/) (2020)
- [Regime Switching Bandits](https://mlsanity.com/paper/2001.09390/) (2020)

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

- [Fooling Algorithms in Non-Stationary Bandits using Belief Inertia](https://mlsanity.com/paper/2511.05620/) (2025)
- [Bandits in Flux: Adversarial Constraints in Dynamic Environments](https://mlsanity.com/paper/2601.19867/) (2026)

## Abstract (arXiv)

In the multi-armed bandit framework, there are two formulations that are commonly employed to handle time-varying reward distributions: adversarial bandit and nonstationary bandit. Although their oracles, algorithms, and regret analysis differ significantly, we provide a unified formulation in this paper that smoothly bridges the two as special cases. The formulation uses an oracle that takes the best-fixed arm within time windows. Depending on the window size, it turns into the oracle in hindsight in the adversarial bandit and dynamic oracle in the nonstationary bandit. We provide algorithms that attain the optimal regret with the matching lower bound.