Replicable Constrained Bandits

Matteo Bollini; Gianmarco Genalti; Francesco Emanuele Stradi; Matteo Castiglioni; Alberto Marchesi

cs.LGFeb 16, 2026

Replicable Constrained Bandits

Authors: Matteo Bollini, Gianmarco Genalti, Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi

Organizations: Politecnico di Milano

Abstract

Algorithmic replicability has recently been introduced to address the need for reproducible experiments in machine learning. A replicable online learning algorithm is one that takes the same sequence of decisions across different executions in the same environment, with high probability. We initiate the study of algorithmic replicability in constrained MAB problems, where a learner interacts with an unknown stochastic environment for $T$ rounds, seeking not only to maximize reward but also to satisfy multiple constraints. Our main result is that replicability can be achieved in constrained MABs. Specifically, we design replicable algorithms whose regret and constraint violation match those of non-replicable ones in terms of $T$ . As a key step toward these guarantees, we develop the first replicable UCB-like algorithm for unconstrained MABs, showing that algorithms that employ the optimism in-the-face-of-uncertainty principle can be replicable, a result that we believe is of independent interest.

Figures & tables

Panel of Figure 1 — Algorithm 3 DEBORA-S

Panel of Figure 2 — Algorithm 4 DEBORA-H

Explore similar work

Replicable Bandits with UCB based Exploration
Apr 21, 2026Rohan Deb, Udaya Ghai, Karan Singh +1Multi-Armed Bandits Contextual Bandits
University of Illinois Urbana-Champaign · Amazon · Carnegie Mellon University
Replicability is Asymptotically Free in Multi-armed Bandits
Feb 12, 2024Junpei Komiyama, Shinji Ito, Yuichi Yoshida +1Multi-Armed Bandits ML Reproducibility
New York University · Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) · RIKEN AIP +2
Truly Adapting to Adversarial Constraints in Constrained MABs
Feb 16, 2026Francesco Emanuele Stradi, Kalana Kalupahana, Matteo Castiglioni +2Constrained Optimization Adversarial Bandits
Politecnico di Milano

Apr 21, 2026J/K move · Enter open · S save

Replicable Bandits with UCB based Exploration

Rohan Deb, Udaya Ghai, Karan Singh, Arindam Banerjee

University of Illinois Urbana-Champaign · Amazon · Carnegie Mellon University

Multi-Armed Bandits Contextual Bandits ML Reproducibility UCB Algorithms Generalized Linear Bandits

Open paper AskPDF 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(\frac{K^2\log^2 T}{ρ^2}\sum_{a:Δ_a>0}\left(Δ_a+\frac{\log(KT\log T)}{Δ_a}\right)\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

\widetilde{O}\!\big(\big(d+\frac{d^3}ρ\big)\sqrt{T}\big)

. 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.

Abstract

Explore similar work

Replicable Bandits with UCB based Exploration

Replicability is Asymptotically Free in Multi-armed Bandits

Truly Adapting to Adversarial Constraints in Constrained MABs