# Randomized Exploration for Non-Stationary Stochastic Linear Bandits

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Dec 2019.

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

- [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)
- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledge](https://mlsanity.com/paper/2205.14775/) (2022)
- [Dynamic Embedding Size Search with Minimum Regret for Streaming Recommender System](https://mlsanity.com/paper/2308.07760/) (2023)
- [Linear Bandits with Memory: from Rotting to Rising](https://mlsanity.com/paper/2302.08345/) (2023)
- [Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs](https://mlsanity.com/paper/2601.01069/) (2026)
- [Variance-Dependent Regret Bounds for Non-stationary Linear Bandits](https://mlsanity.com/paper/2403.10732/) (2024)
- [Optimal Dynamic Regret by Transformers for Non-Stationary Reinforcement Learning](https://mlsanity.com/paper/2508.16027/) (2025)
- [Non-Stationary Contextual Bandit Learning via Neural Predictive Ensemble Sampling](https://mlsanity.com/paper/2310.07786/) (2023)
- [Tracking Most Significant Shifts in Infinite-Armed Bandits](https://mlsanity.com/paper/2502.00108/) (2025)
- [Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits](https://mlsanity.com/paper/2509.15073/) (2025)
- [Bayesian Non-stationary Linear Bandits for Large-Scale Recommender Systems](https://mlsanity.com/paper/2202.03167/) (2022)
- [Revisiting Weighted Strategy for Non-stationary Parametric Bandits](https://mlsanity.com/paper/2303.02691/) (2023)
- [Weighted Sequential Bayesian Inference for Non-Stationary Linear Contextual Bandits](https://mlsanity.com/paper/2307.03587/) (2023)
- [Time-Uniform Self-Normalized Concentration for Discounted Least Squares: Limits and Corrections](https://mlsanity.com/paper/2608.19643/) (2026)
- [Block Optimism for Nonstationary Bandits with Latent Linear Dynamics](https://mlsanity.com/paper/2610.00911/) (2026)

## Abstract (arXiv)

We investigate two perturbation approaches to overcome conservatism that optimism based algorithms chronically suffer from in practice. The first approach replaces optimism with a simple randomization when using confidence sets. The second one adds random perturbations to its current estimate before maximizing the expected reward. For non-stationary linear bandits, where each action is associated with a d-dimensional feature and the unknown parameter is time-varying with total variation BT, we propose two randomized algorithms, Discounted Randomized LinUCB (D-RandLinUCB) and Discounted Linear Thompson Sampling (D-LinTS) via the two perturbation approaches. We highlight the statistical optimality versus computational efficiency trade-off between them in that the former asymptotically achieves the optimal dynamic regret tildeO(d7/8 BT1/4T3/4), but the latter is oracle-efficient with an extra logarithmic factor in the number of arms compared to minimax-optimal dynamic regret. In a simulation study, both algorithms show outstanding performance in tackling conservatism issue that Discounted LinUCB struggles with.