# Learning to Optimize under Non-Stationarity

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

## Key facts

- Cited by 85 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Oct 2018.

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

- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [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)
- [Robust Stochastic Linear Contextual Bandits Under Adversarial Attacks](https://mlsanity.com/paper/2106.02978/) (2021)
- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [Tracking Most Significant Arm Switches in Bandits](https://mlsanity.com/paper/2112.13838/) (2021)
- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [The Pareto Frontier of model selection for general Contextual Bandits](https://mlsanity.com/paper/2110.13282/) (2021)
- [Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits](https://mlsanity.com/paper/2202.06151/) (2022)
- [Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2110.12615/) (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)
- [An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledge](https://mlsanity.com/paper/2205.14775/) (2022)
- [Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs](https://mlsanity.com/paper/2110.08984/) (2021)
- [Robust Lipschitz Bandits to Adversarial Corruptions](https://mlsanity.com/paper/2305.18543/) (2023)
- [Multi-channel Autobidding with Budget and ROI Constraints](https://mlsanity.com/paper/2302.01523/) (2023)
- [Regret Bounds for Generalized Linear Bandits under Parameter Drift](https://mlsanity.com/paper/2103.05750/) (2021)
- [Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2301.12366/) (2023)
- [Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift](https://mlsanity.com/paper/2407.18676/) (2024)
- [An Information-Theoretic Analysis of Nonstationary Bandit Learning](https://mlsanity.com/paper/2302.04452/) (2023)
- [Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithms](https://mlsanity.com/paper/2106.02979/) (2021)
- [Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2111.03917/) (2021)
- [Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraints](https://mlsanity.com/paper/2211.14720/) (2022)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [Generalized non-stationary bandits](https://mlsanity.com/paper/2102.00725/) (2021)
- [Adaptive Experimentation in the Presence of Exogenous Nonstationary Variation](https://mlsanity.com/paper/2202.09036/) (2022)
- [An Online Learning Approach to Optimizing Time-Varying Costs of AoI](https://mlsanity.com/paper/2105.13383/) (2021)
- [Linear Bandits with Memory: from Rotting to Rising](https://mlsanity.com/paper/2302.08345/) (2023)
- [Non-stationary Reinforcement Learning under General Function Approximation](https://mlsanity.com/paper/2306.00861/) (2023)
- [Lower Bounds for Time-Varying Kernelized Bandits](https://mlsanity.com/paper/2410.16692/) (2024)

## Abstract (arXiv)

We introduce algorithms that achieve state-of-the-art dynamic regret bounds for non-stationary linear stochastic bandit setting. It captures natural applications such as dynamic pricing and ads allocation in a changing environment. We show how the difficulty posed by the non-stationarity can be overcome by a novel marriage between stochastic and adversarial bandits learning algorithms. Defining d,BT, and T as the problem dimension, the variation budget, and the total time horizon, respectively, our main contributions are the tuned Sliding Window UCB (textttSW-UCB) algorithm with optimal widetildeO(d2/3(BT+1)1/3T2/3) dynamic regret, and the tuning free bandit-over-bandit (textttBOB) framework built on top of the textttSW-UCB algorithm with best widetildeO(d2/3(BT+1)1/4T3/4) dynamic regret.