Replicable Linear Bandits with UCB based Exploration

We study replicable algorithms for stochastic linear bandits with optimism-based exploration. A bandit algorithm is $\rho$-replicable if two executions using shared internal randomness but independent reward realizations produce the same action sequence with probability at least $1-\rho$. For linear bandits with infinitely many actions, existing replicable algorithms are elimination-based and rely on discretizing the action space, leading to suboptimal dependence on the dimension $d$ and on $\rho$. We first introduce RepRidge, a replicable ridge regression estimator that satisfies a self-normalized confidence bound whose radius is inflated by a factor of $(1+d/\rho )$. We believe this estimator is of independent interest. Building on it, we design RepLinUCB, a replicable optimistic algorithm that combines determinant-triggered batching with RepRidge, and show that its regret is $\tilde{\mathcal{O}}(d^3\sqrt{T}/\rho )$. This improves the state-of-the-art by a factor of $d/\rho$ and gives the first linear bandit algorithm with optimal dependence on $\rho$ for large action sets. Because our approach does not rely on action-space discretization, it also applies to time-varying action sets, which existing results could not handle. Finally, we extend our approach to generalized linear bandits via a replicable penalized GLM estimator, RepGLM, and a corresponding optimistic algorithm, RepGLMUCB. In synthetic experiments, RepLinUCB achieves substantially lower regret than existing elimination-based algorithms.