# Replicable Bandits with UCB based Exploration

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 31 references that are in the map.
- First posted on arXiv 21 Apr 2026.

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

- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Conservative Contextual Linear Bandits](https://mlsanity.com/paper/1611.06426/) (2016)
- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Batched Neural Bandits](https://mlsanity.com/paper/2102.13028/) (2021)
- [Replicable Bandits](https://mlsanity.com/paper/2210.01898/) (2022)
- [Replicable Reinforcement Learning](https://mlsanity.com/paper/2305.15284/) (2023)
- [Replicability in Reinforcement Learning](https://mlsanity.com/paper/2305.19562/) (2023)
- [Replicable Clustering](https://mlsanity.com/paper/2302.10359/) (2023)
- [Replicability in High Dimensional Statistics](https://mlsanity.com/paper/2406.02628/) (2024)
- [Replicable Bandits for Digital Health Interventions](https://mlsanity.com/paper/2407.15377/) (2024)
- [Contextual Bandits with Online Neural Regression](https://mlsanity.com/paper/2312.07145/) (2023)
- [On the Computational Landscape of Replicable Learning](https://mlsanity.com/paper/2405.15599/) (2024)
- [Replicable Online Learning](https://mlsanity.com/paper/2411.13730/) (2024)
- [Conservative Contextual Bandits: Beyond Linear Representations](https://mlsanity.com/paper/2412.06165/) (2024)
- [Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resources](https://mlsanity.com/paper/2312.17229/) (2023)
- [Replicability is Asymptotically Free in Multi-armed Bandits](https://mlsanity.com/paper/2402.07391/) (2024)
- [The Cost of Replicability in Active Learning](https://mlsanity.com/paper/2412.09686/) (2024)
- [Replicable Constrained Bandits](https://mlsanity.com/paper/2602.14580/) (2026)

## Abstract (arXiv)

We study replicable algorithms for stochastic multi-armed bandits (MAB) and linear bandits with UCB (Upper Confidence Bound) based exploration. A bandit algorithm is ρ-replicable if two executions using shared internal randomness but independent reward realizations produce the same action sequence with probability at least 1-ρ. Prior approaches to this problem are elimination-based and, in linear bandits with infinitely many actions, rely on discretization, leading to suboptimal dependence on the dimension d and ρ. We develop optimistic alternatives for both settings. For stochastic multi-armed bandits, we propose RepUCB, a replicable batched UCB algorithm and show that it attains a regret O!left(fracK2log2 Tρ2suma:Deltaa>0left(Deltaa+fraclog(KTlog T)Deltaaright)right). For stochastic linear bandits, we first introduce RepRidge, a replicable ridge regression estimator that satisfies both a confidence guarantee and a ρ-replicability guarantee. Beyond its role in our bandit algorithm, this may also be of independent interest in other statistical estimation settings. We then use RepRidge to design RepLinUCB, a replicable optimistic algorithm for stochastic linear bandits, and show that its regret is bounded by widetildeO!big(big(d+fracd3ρbig)√Tbig). This improves the best prior regret guarantee by a factor of O(d/ρ), showing that our optimistic algorithm can substantially reduce the price of replicability. This is the first linear-bandit algorithm with an optimal dependence on ρ for large number of arms. Finally, we extend our framework to stochastic generalized linear bandits by developing RepGLM, a replicable penalized GLM estimator, and RepGLMUCB, a replicable optimistic algorithm for this setting.