Regret-Optimal List Replicable Bandit Learning: Matching Upper and Lower Bounds
Michael Chen, Aduri Pavan, N. V. Vinodchandran, Ruosong Wang, Lin Yang
Abstract
This paper investigates list replicability Dixon et al. (2023) in the context of multiarmed (also linear) bandits (MAB). We define an algorithm A for MAB to be (ℓ, δ)-list replicable if with probability at least 1 -δ, A has at most ℓ traces in independent executions even with different random bits, where a trace means sequence of arms played during an execution. For k-armed bandits, although the total number of traces can be Ω(k T ) for a time horizon T , we present several surprising upper bounds that either independent of or logarithmic of T : (1) a (2 k , δ)list replicable algorithm with near-optimal regret, O(
) for any integer B > 1. On the other hand, for the sublinear regret regime, we establish a matching lower bound on the list complexity (parameter ℓ). We prove that there is no (k -1, δ)-list replicable algorithm with o(T )-regret. This is optimal in list complexity in the sub-linear regret regime as there is a (k, 0)-list replicable algorithm with O(T 2/3 )-regret. We further show that for linear bandits with d-dimensional features, there is a O(d 2 T 1/2+2 -(B+1) )-regret algorithm with ((2d + 1) B-1 , δ)-list replicability, for B > 1, even when the number of possible arms can be infinite.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
- List and Certificate Complexities in Replicable Learning cites An Equivalence Between Private Classification and Online Prediction
- List and Certificate Complexities in Replicable Learning cites User-Level Differentially Private Learning via Correlated Sampling
- List and Certificate Complexities in Replicable Learning cites Reproducibility in learning
- Replicability in Reinforcement Learning cites List and Certificate Complexities in Replicable Learning
- Replicability in Reinforcement Learning cites Reproducibility in learning
- User-Level Differentially Private Learning via Correlated Sampling cites An Equivalence Between Private Classification and Online Prediction
- Reproducibility in learning cites An Equivalence Between Private Classification and Online Prediction
- Reproducibility in learning cites User-Level Differentially Private Learning via Correlated Sampling
Builds on7
- User-Level Differentially Private Learning via Correlated SamplingBadih Ghazi, Ravi Kumar, Pasin ManurangsiNeurIPS 2021 · 45 citations
- An Equivalence Between Private Classification and Online PredictionMark Bun, Roi Livni, Shay MoranFOCS 2020 · 28 citations
- Replicability in Reinforcement LearningAmin Karbasi, Grigoris Velegkas, Lin Yang, Felix ZhouNeurIPS 2023 · 28 citations
- Reproducibility in learningRussell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica SorrellSTOC 2022 · 20 citations
- List and Certificate Complexities in Replicable LearningPeter Dixon, Aduri Pavan, Jason Vander Woude, N. V. VinodchandranNeurIPS 2023 · 18 citations
Related papers
- Linear Bandits with Partially Observable FeaturesWonyoung Kim, Sungwoo Park, Garud Iyengar, Assaf Zeevi et al.ICML 2025 · 3 citations
- Impact of Representation Learning in Linear BanditsJiaqi Yang, Wei Hu, Jason D. Lee, Simon Shaolei DuICLR 2021 · 58 citations
- Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual BanditsZihan Zhang, Xiangyang Ji, Yuan ZhouICLR 2025
- Distributed Bandit Learning: Near-Optimal Regret with Efficient CommunicationYuanhao Wang, Jiachen Hu, Xiaoyu Chen, Liwei WangICLR 2020 · 115 citations
- Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent ArrivalsJunyan Liu, Arnab Maiti, Artin Tajdini, Kevin Jamieson et al.ICML 2025
