Regret-Optimal List Replicable Bandit Learning: Matching Upper and Lower Bounds
Authors: Michael Chen
A. Pavan
N. V. Vinodchandran
Ruosong Wang
Lin Yang
Venue: ICLR 2025 Poster (2025)
Keywords: Replicability
Regret Bound
Bandit
Primary area: learning theory

Abstract: This paper investigates *list replicability* [Dixon et al., 2023] in the context of multi-armed (also linear) bandits (MAB). We define an algorithm $A$ for MAB to be $(\ell,\delta)$-list replicable if with probability at least $1-\delta$, $A$ has at most $\ell$ 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 $\Omega(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},\delta)$-list replicable algorithm with near-optimal regret, $\widetilde{O}({\sqrt{kT}})$, (2) a $(O(k/\delta),\delta)$-list replicable algorithm with regret $\widetilde{O}\left(\frac{k}{\delta}\sqrt{kT}\right)$, (3) a $((k+1)^{B-1}, \delta)$-list replicable algorithm with regret $\widetilde{O}(k^{\frac{3}{2}}T^{{\frac{1}{2}}+2^{-(B+1)}})$ 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 $\ell$). We prove that there is no $(k-1,\delta)$-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 $\widetilde{O}(d^2T^{1/2+2^{-(B+1)}})$-regret algorithm with $((2d+1)^{B-1},\delta)$-list replicability, for $B>1$, even when the number of possible arms can be infinite.

Published as a conference paper at ICLR 2025
REGRET-OPTIMAL LIST REPLICABLE BANDIT LEARN- ING: MATCHING UPPER AND LOWER BOUNDS
Michael Chen
A. Pavan
N. V. Vinodchandran University of Nebraska - -I Lincoln vi nodêunl .edu
lowa State University mgychen i astate. edu
lowa State University
pavan@iastate.ed
Ruosong Wang
Lin F. Yang
Peking University
University of California, Los Angeles linyang@ee. ucla. edu
ruosongwangg@pku..eok edu. on
ABSTRACT
This paper investigates list replicability Dixon al. (2033 in the context of multi- armed (also linear) bandits (MAB). We deline an algorithm A for MAB to be (e, - replicable if with probability at least 1 8, A has most & traces in independent executions even with different random bits. where a trace means se- quence of arms played during an execution. For k-armed bandits, although the total number of traces can be ?(A-²)) for time horizon T, we present several sur- prising upper bounds that either independent of or logarithmic T:: (1) (2 8)- list replicable algorithm with near-optimal regret, OVVKT) (2) a (O(k/o), - replicable algorithm with regret Ō ( V+TT.:: (3) a ((k: + 1) B - replicable
algorithm with regret Ö(k T +2 (2+))) 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 E). We prove that there is no (k: 1, 8-1istt replicable algorithm with rrerre. This is optimal in list complexity in the sub-lineat regret regime as there is (k, 0)-list replicable algorithm with O(T2/3) We further show that for linear bandits with d-dimensional features, there is a ((d2T1/242- (m++), }-regret algorithm with ((2d + 1) 5)-list replicability, for >> 1, even when the number of possible arms can be infinite.
INTRODUCTION
The issue of replicability and reproducibility in science has become a significant concern attract- ing substantial attention from the broader scientific community [Begley & Ellis] (2012): [oannidis] (2005); [Baker] (2016); jof Sciences et al.] (2019). Recently the machine learning community also started addressing this issue. Inspired by reproducibility workshops at ICML/ICLR, the ML com- munity has created a dedicated online conference, the ML Reproducibility Challenge (MLRC) Sinha et al. (003),, to encourage the publishing and sharing of scientific results that are reliable and repro- ducible. In machine learning, a common approach to ensure replicability and reproducibility is to make datasets and code publicly available. However, is unclear if such approach is sufficient, as machine learning algorithms draw samples from data distributions and are usually randomized. This inherent randomness results in non-replicability. Therefore, it more desirable to design machine learning algorithms that are replicable. i.c., algorithms that return the same result over multiple runs, even when different runs observe different sets of samples from the data distribution. The aforemen- tioned requirement has recently led to theoretical studies and rigorous definitions of replicability Impaglizzoo et al. (2022): ; Dixon al. (2023). with various notions of replicability being proposed.
In this work, we study bandit algorithms with replicability guarantees. The Multi-Armed Bandit (MAB) is a learning task in which a learner interacts with an environment consisting of a set of fixed & distributions (called arms) in discrete time steps. In each of the T steps, the learner selects
Here Ō(-) omits log ki log log T, log 4-

---

Published as a conference paper at ICLR 2025
an arm and receives an i.i.d. sample from that arm, called the reward. The goal of the learner is to maximize the cumulative expected reward, equivalently minimizing the "regret" (defined formally later), which characterizes the total sub-optimality of the actions played over the learning course.
Ideally, an MAB algorithm with perfect replicability should always select exactly the same trace (i.e., sequence of arms) over multiple runs, even if the algorithm receives different set of samples from the data distribution for each run. However, as shown later in the paper (and discussed in Dixon al. (2023). ). is impossible for MAB algorithms with perfect replicability guarantees have non-trivial regret bound, as algorithms need to adapt to the randomness from the history to learn effectively. Therefore, we ask, what is the strongest notion of replicability of bandit algorithm without suffering significant regret loss?
Inspired by recent study Dixon al. (2023) that investigates replicability in the supervised learning setting, we propose notion of list replicability for bandit learning. In this setting, we require that the trace (sequence of actions) produced by the algorithm during the entire learning course be predictable to a certain extent. That is, no matter how many times we repeat the algorithm for the bandit instance, the resulting sequence of actions comes from a small finite list. Note that in general, T horizon MAB algorithm with k arms can have k²' possible traces. Such a guarantee would be useful for bandit learning in safety-critical applications, as one can be prepared for the action sequence being played. Bandit algorithms and more general reinforcement learning algorithms are increasingly used in clinical trials and social experiments to personalize treatment decisions for individuals /Zang al. (2024). In such domains, it is highly desirable to limit the possible sequence of actions and limit uncertainty.
The formalization of the concept of replicability in various computational settings is significant and emerging area of research. This work takes an important step toward understanding the foundational principles of replicability in the context of bandit problems.
PRELIMINARIES
For E N, we use [n] to denote the set (1...., n) and for o, b E lR we use [a, (a, b). [a, b), and (a, b] to represent the closed, open intervals, and their corresponding half-open intervals respectively. We use Ó() to subsume log k, log log T, and log g- In this paper, we consider the following Multi- Armed Bandit (MAB) instance.
Assumption 2.1. An MAB instance is a tuple (D, where D = (Di..... D2) is a collection of distributions and T N is the horizon such tha D, is supported on [0, 1] and has a mean pi. For any t E [T] if action a₂ E [k] is played, the reward Tt is an i.i.d. sample drawn from Da.-
Here, we use l denote the number of arms and T denote the horizon. For a collection of means , H4g we use '² = max {Pa} } to denote the highest mean and for each E [k]] A, = 1r¹ - μ4 to denote its reward gap. An arm with A, = 0 is called an optimal arm; otherwise, is called sub aub-optimal arm. Let M be an algorithm for MAB. The algorithm M defines probability distribution PM on traces [k]]" in the following sense: Given a trace a E [K]"", probability of a, de- noted (a) is the probability that M takes trace a. For set S of traces, (M((S) = Eaes PM (a). Definition 2.2 ((e, 6)-MAB Replicability). An algorithm M for MAB is (E, (f.8)-list replicable if for every MAB instance (D,T), there exists a set of traces Sp. C [k]] such that 1SD.T| S E and (M(SD.T) 2 8.
When 0, then we just say that M E-list replicable. We call E the list complexity of M. Definition 2.3 (Regret). We measure the performance of an algorithm by the regret, which is Rr
IL max, Ma par, where a' is the action played at time t. An MAB algorithm is effective if the regret is sublinear in T: in this case, the average regret per round is approaching 0 as T + 0o.
Trivially, any MAB algorithm is T -list replicable because trace must be element of TT] and an algorithm playing the same action all the time is 1-list replicable algorithm, yet with regret T. We aim create MAB algorithms that have both low regret and are ( replicable with small l and 6.
For presentation simplicity, we restrict to the [0, 1] setting. Our results generalize to aub-Gaussian distri- butions straightforwardly.
2

---

Published as a conference paper at ICLR 2025
For the linear bandits, assume that the rewards rt satisfy linear structure. Specifically, Assumption 2.4. For any E A, we assume ||al|z I 1 and hence A is compact set. For any time i, if action at is played, the reward vt satisfies Tt = (ar, 0*) ) + nt where 0 unknown with [|0~|e 12 & vd, and nee is an history independent mean-O Ø-sub- Gaussian random variable that satisfies E(me] 0 and (Vx 0). [[mel] x] eexp
We denote Pa (a.0* 0²) [0, as the unknown true mean of an arm a, and let a" arg ( 0*), which is the unknown optimal action. For presentation simplicity, we assume
3 OUR CONTRIBUTIONS
In this work, we introduce viable notion of replicability which is called list replicability in the context of Multi-Armed Bandit algorithms. We summarize technical results below.
In Section 5.1
we present a (2*, 8)-list replicable MAB algorithm with npar-optimal regret, Õ(VKT). Importantly, the total number of possible traces is completely independent of T.
we present (O(k/8). 5)-lit replicable MAB algorithm with (kk/6VkT) re- gret. When constant, the total number of possible traces is O(k), while the regret bound is Ō( polpoly)))
In Section 5.2
we present ((k: + 1)B-118)-liss replicable algorithm with regret bound ( for any B > 1. By setting B to be constant, the total number of possible traces is polynomial in k, while the regret bound sublinear k. By setting total number of possible traces is OOolg log T), while the regret bound O(k3/2 (T).
In Section 5.3
log log T, the
In Section 6 we further show that the guarantees of our third algorithm are nearly tight by establish- ing a (k- - lower bound for any list replicable algorithm with failure probability at most 1/(k 1/(k+]] +) and regret o(T), almost exactly matching the k-list replicable upper bound for B = 2. Interstingly, we use a cubical version of Spemer/KKM lemma for establishing the lower bound.
Finally, in Section
third algorithm to the linear bandit setting. For d- dimensional linear bandit instance, we present a ((2d + (18-116)-IB replicable algorithm with regret Ö(PT +2-((+))) for any B >> 1.
generalize
4 RELATED WORK
Bandit algorithms have been extensively studied in the general setting Lattimore & Szepesvári 2020
Slivkins et al.] (2019) Bubeck et al. (2012): Auer et al. (2002): Cesa-Bianchi & Fischer
Kaufmann al. (0022. In the MAB setting, Thomson sampling and UCB achieve op- timal regret of Ö(VkT) Agrawal & Goyal (017)); Auer et al. (2002). In the d-dimensional linear bandit setting, Contextual Thomson sampling and LinUCB achieve regret of ((dTT)) Lattimore & Szepesvári (2020). There is extensive work in other bandit variants, and interested readers are referred Lattimore Szepesvári (2020).
1998
Several works Impagliazzo et al. 2022), Dixon et al. (203)); Bun et al. 2020); Ghazi et al. (2021)
studied various notions of replicability in the context learning tasks. Bun et al. (2020). no- tion called stability is introduced. The work of [Impagliazzo et al. (2022). defined the notion of p-replicability. In Dixon et al. (2023), the authors introduce list replicability and certificate replica- bility. The work of Ghazi et al. (2021) studied list-global stability and pscudo-global stability. The works of EEsfandiari et al. (2023) ; Karbasi et al. (2024); Eaton et al. (2023) studied replicability in the context of reinforcement learning and Bandits.
The work that is closely related to our work is the work of Esfandiari et al. 2023) in the con- text of MAB. Their definition of replicability for MAB is inspired by the notion of p-replicability of Impagliazzo et al.] (2022). Informally, their definition requires that an algorithm for MAB p- replicable if multiple of algorithm, where all the runs share the internal random seed, will
3

---

Published as a conference paper at ICLR 2025
result in the same trace, with probability greater than 1 - p. Their goal was design p-replicable algorithms for MAB with (near) optimal regret. Our definition of replicability inspired by the list replicability notion of Dixon et al. (2023). In our work, the goal is to design list-replicable algorithms with small list size with (near) optimal regret. In this context, the notions of p and list replicability different they do not imply each other. Thus our results are significantly different from that of Esfandiari et al. (2023). Since their algorithm's 's replicability depends on the random seeds/certificates, which could be exponentially many, their algorithm can have bad (exponential) list replicability when applied in our setting. Hence, different techniques are required to bound the list size.
MULTI-ARM BANDITS: UPPER BOUND
In this section, we introduce several list-replicable algorithms for the finite-arm setting. We first present an algorithm with no dependence yet with less ideal dependence on k. We will then attempt to improve the dependence on k by sacrificing the dependence on other parameters.
5.1 A (2*, 6)-LIST REPLICABLE ALGORITHM
This algorithm a standard phase-elimination type algorithm (yet our analysis for list-replicability is novel). For completeness, we present the full algorithm in Algorithm The algorithm proceeds in batches (or rounds) and maintains a of "good" arms. In each batch, the good arms are played uniformly in lexicographic order to refine the estimation of their estimated means. At the com- pletion of the batch, the arms whose estimated means are deemed non-optimal (even considering the estimation uncertainty) are removed. The batch length grows geometrically to provide more accurate estimates of the arms compared to the previous batch. The total number of batches is bounded by Oloog 7'). Furthermore, the arms being played at every batch are guaranteed to satisfy certain optimality guarantees, and therefore, the overall regret per batch can be bounded with high probability.
Algorithm 1: (2*,8)= 50-List Replicable for MAB
Input: Horizon T, Actions [k), Failure probability 8
Number of batches: B +- [log2s TJ, Initial good arm set: Ai +- [k]
for b do
Denote error parameter: 66 +
V Set deletion criteria: Ds t- 3еp
ck 526
log 8
kB for some constant e > 0,
For each arm E As, play for algorithm if T arms have been played)
2 A
times, and obtain an empirical mean (s,(8) (halt the
For all E A₁; let (0,00) max (b) (4,(0) Eliminate bad arms: Ab+1 <- (i E As Å,,()) S Dr).
end
5.1.1 ANALYSIS
Our analysis for replicability relies on the novel observation that the total number of traces is deter- mined by the number of possible batches for sub-optimal arm be eliminated. If each sub-optimal is eliminated in at most 2 different batches with high probability, then the overall list complexity is most 2* In particular, sub-optimal arm is always eliminated one of two consecutive batches, with high probability. More formally, the guarantee of the algorithm is presented as follows.
Theorem 5.1. For every 8 (0. 1]. Algorithm [ is (2 8'-list replicable, and for every imput bandit instance satisfying Assumption 2 the algorithu enjoys regret bound of O (v (VTT log & loo T with probability at least 1-
We provide the proof of the theorem, which built on a sequence of lemmas and observations. Before make analysis formal, recall our definition of the parameters. Note that B
4

---

Published as a conference paper at ICLR 2025
1log25 T is the number of batches. For E [B], note that No =
is the number of pulls cach
[
arm in the batch. Then each batch has length of T. | No 2 520. For V
ck 5th 5 and
log
kn
(b) be the empirical mean the arm i, we denote the following event Eg {(vé E As). 14 cb S
(s,(0) S Pt + 66). Define the "good" event = NEEB Es. Then, by Hoeffding bound and
union bound, we have that Pr[E] 2 5. Conditioned on E, we immediately have, 4h E [B].
4 - cb I maXaeA, Pa.(b) S ue" + c and A, 2c, I A., - A + 2cg.
We now define partition (TI..... . TB-1) 1) on [0, 1]. Let co = 1 and cB1 O. For each m E [B] define I. (Cm: 6m-1] and /B+1 = ( Note for each arm E [k], there exists a unique
m E [B + 1] such that A, E m. We use m, denote this unique partition number.
For E [t]]. let X, be the random variable that denotes which batch arm is eliminated; we claim that conditioned on E, X; can take at most one of two values, namely my or m, 1. This follows because of the geometric nature of Eb. The proof of the following can be found at the Appendix A.T
Lemma 5.2. For all i E [k: Pr(m:: S X; S m. + 1 =
To conclude that the algorithm is ( 0))list replicable, consider the vectors of deletion sequences (X1...., Xs). with high probability see exactly these 2 such vectors, each vector corresponds to single unique trace. The proof of the following can be found in Appendix A.1 Thus concludes the proof of Theorem 5.1
Lemma 5.3. On E, the regret of Algorithm satisfies Ry S 5o VATToo &logT
5.2 A (O(k/8), 8))/0) REPLICABLE ALGORITHM
In this section, we present novel modification to Algorithm D to further boost the list replicablility. For the above (2h, l'ist replicablility, we obtained 2c, esttemmtte of A and eliminated those that were 3e, away. The algorithm guarantees w.h.p. that each arm will be deleted randomly in one of two rounds. We shall now show that we perturb the deletion criteria by random shift picked at the start of the algorithm (while simultaneously getting better approximations for A, by drawing more samples each batch), then the arm will deleted exactly round. Crucially, we show that if we pick at most C' = 12k such perturbations, it results in at most C many traces. The algorithm is formally presented in Algorithm 2
Algorithm 2: (12k/8,8) List Replicable for MAB
Input: Horizon 7", Actions [k], Failure probability 8
Number of shifts: C +- 12k Number of batches: B + log25 [
T
Initial good arm set:
A + [k), Random shift: r ~ UnC)
for b= B do
ck Denote error parameters: Eb C
log
2kB To 3(v2-1) 3( mm)
4Ccr.
Set deletion criteria: D3 t Dr.r 3rp + (r 1).
C2 A
For each arm i As, play for
times, and obtain empirical mean (r,(6) (halt the algorithm if T arms have been played)
For all E AA: let Á,,0) + maxac.A, (a. (44(0))
Eliminate bad arms: Ab+1 < (i E As )s,()) Dr).
end
5.2.1 ANALYSIS
Similar to the analysis of Algorithm I our new algorithm shares a similar structure of bounding the regret: the estimates of arms get increasingly improved, and only arms with better error guarantees will be played per batch. The challenging part is to show that the algorithm can only produce a small number of traces. The following theorem presents the formal guarantee.
5

---

Published as a conference paper at ICLR 2025
11,1
2a,2
Db,C-1
Db.c
Db-1,1
3m,
A
2eb
A + 2cb
37
Figure 1: The deletion criteria D6 is randomly chosen from D Db,1.-.., Db.
Theorem 5.4. For every 8 E
(0. 1. Algorithm 2
replicable, and for every input bandit & klog T 8
instance satisfying Assumption 2.1 with probability at least 1 5.
the algorithm enjoys a regret bound o
kT //Tlog
We now present a proof of the theorem. Recall that C = o the number of shifts, B = [log2s ]- Let T, = C2 and Ng- = [' we draw T, samples each round, each arm gets 2 No. samples. Let 6 5 each round is co-accurate with probability at least - 5. For b E [B]. and for E [C], consider the deletion criterias in the algorithm: D,,- 3n, + (r 1r--1 3(%, -_ For a randomly picked [C), the deletion criteria at round b, denoted by the random variable DE is uniformly picked from Db.1,..., Dbb... Note that the same r shared across all rounds.
4Cc, and thus the estimate dk log 2 (for some > 0) and ть 3( 3(v2-1)
5
Unlike in Algorithm | the decision boundary, Do x (Ces) is much larger than the estimation error tb. Hence, suppose an arm has gap A, E [D,, D--1] and is more than ( from the boundary of the interval, the algorithm will eliminate it with high probability in batch b. Only the "bad" arms whose gaps are within ((e)) to the boundary has the possibilities to be not eliminated in batch b. We will show that for the C we choose, with certain probability bad arms exists and thus there is unique trace from the algorithm. Below, we make this intuition more formal.
Observation 5.5. For all b [B] and [C], 3rb S Da.r < 3- In parficular, this always holds for the random variable Db. 3TD S Db < 37.-1.
Analogous the analysis of Algorithm [ for b [B]. we define the event as Eg : (Vi As). b S. (b.(bb) S + and the "good" event E' = [be[ Eg. Via Hoeffding and a union bound, we have for all b E [B] Pr E,) 2 1 2 and Pr(E) on [0, 1]. Let
1 3. Define the partition {I,...., In+1]
[TB+1; TB. For each and TB+1 = O. For each m E [B] define Im (Tm, Tm- and J =
E [k:]. there exists a unique E B such that A, T We m, to denote this unique partition number.
We now claim that each arm i will be eliminated in one of three batches, namely mi, m, + 1, m, + instead of the two in the case of the previous algorithm. Intuitively, an arm that was supposed to be deleted in the second round might be delayed to the third round because of the perturbation in the deletion criteria. The full proof can be found in Appendix A.2
Lemma 5.6. For all E [A:]. Pr(m: S X; S m, + E)
Referring to Figure T observe that if r C' C-1 1 were picked, it would be "bad" because even conditioned on E, sometimes the estimate A; lies on the left of the deletion criteria, Dù and other times A lies the right of the Ds. i.e., the round the arm is deleted is inconsistent even when estimates are good. The other rs are "good" because the arm consistently either gets eliminated this round its deletion gets postponed to future round.
Definition 5.7. Let i E [k], E [C], and b E [B]. We say.
1. r b-bad for Db. IA 20,, A; + 2cg].
2. r bad for if is b-bad for i for some b m,, m, + 1, m, 2.
3. r bad if is bad for i for some [k)]. Otherwise, r is said to be good.
D S were carefully chosen so that every batch b [B] the length of the approximation interval of A; at round exactly equal to the distance between consecutive shifts of the same round brr and D1 As consequence, there can only be at most two Dr contained in the interval

---

Published as a conference paper at ICLR 2025
[A; 2cc, A, + 2co]. With some rudimentary counting, the following lemma holds whose full proof can be found in Appendix A.2
Lemma 5.8. There are at most 6k bad rs.
When good r is chosen, we see exactly one trace (conditioned on E), because the deletion criteria always outside the estimation interval for all arms. Thus if we uniformly at random pick an r ~ Unif(C], then with probability at most 6k 5 is bad. Therefore, the number of traces is C = 2
at most C = 12k when both these events occur. The probability that both estimates are good and &
r is good are independent and bounded by: Pr(E n riss is good) 2 (1 5)² 2 1 - ó. The proof
of the following lemma is similar to the regret analysis of the previous section and can be found in Appendix A.2 Thus concludes the proof of Theorem 5.4
Lemma 5.9. On E and the event that r is good, the regret of Algorithm satisfies, R -
kT log ll
5.3 A (1)(1), 8I-LTST REPLICABLE ALGORITHM WITH 13/221//24000 REGRET
In this section, we refine the tradeoff between list-eeplicability and the regret bound. We rely on the following critical routine proposed in Dixon et al. (2023).
Theorem 5.10
(ixonn al. 2023), Replicable Mean Estimation). Let c, (0, 1] and k N. For any random vector V E R² suppose there exists an algoritim takes samples from V and produces an estimator V such, that [[[]]] Vl S 2k with probability at least 5. Then there exists an algorithm, ReplicableMeans. which takes V as an input and output a (),,))))--- replicable estimator V. which satisfies [[[]] Vl S e, with probability at least 8.
We shall argue about replicability based the subset of arms that are eliminated. Let B > be an integer, denoting the number of batches, and 8 E (0, 1]. Let s शशंं with a + v. (
We shall demonstrate how to create a ((k + 1) 5) -list replicable algorithm with ( regret. The algorithm is constant batched algorithm where B is the number of batches. In each batch, bad arms are deleted in a replicable manner with the help of Theorem 5.10 thus, in each batch, only (k + 1) possible subset of arms are deleted (instead of the naive 2*). Via rule of product, over batches (A: + B)B-1 traces are observed. Note that the eliminations batch B does not affect the replicability. Therefore the replicability is (k + 1)8-1. The algorithm is formally presented in Algorithm 3
-
Algorithm 3: ((k 1-) 8)-List Replicable for MAB
Input: Horizon T, Actions [k], Number of Batches B > 1, Failure probability 5
Regret paramter: v + 20 a + + v, Initial good arm set: Ar + [A]]
for b= do
For each arm As, play for No, ( pp/ times and obtain an empirical
mean (4,(0) (the algorithm halts if it has played T arms)
Use Theorem 5.10 (Di,())) ReplicableMeans (P..))))EAA)
For all E As; let Ár,)) + maxag.A, Aa.(b) (44(())
Let T, = As be the total steps of batch
Denote error parameters: 6b +
cka 75
log kB
Abt1 +- {i E A, ALCO 2cx).
end
7

---

Published as a conference paper at ICLR 2025
5.3.1 ANALYSIS
Theorem 5.11. For every ò E (0,1), and integer B 1, Algorithm is (k++1) (1+1))-11 - 8)--ist replicable, and for every input bandit instance satisfying Assumption 2.1
the algorithm enjoys
regret bound of
kT /TTVV
with probubility least 6, where v 2-
Remark 5.12. We note that when B = 2, the algorithm is (k: + 1, -iiss replicable while en- joys regret bound of (133122213) For B loglogT, the algorithms enjoys regret bound of 0(3//2/T) while with klog gloglog' log list-complexity Cesa-Bianchi al. 2013).
We present the proof of Theorem 5.11 For b E [B]. let Tn = @(T TT) be the batch length. Note that if v = 2-+1-2 then TB T. Therefore
2--1-2 sufficient to guar-
antee ΣiE[B] To ~ T. Let 6b V T,
cka
log kB for some Therefore, for each b [B]. with 8
probability at least 1 - B, for each i E Ab. (Ar,0) - pul S 2 Therefore, by Theorem 5.10 RelicableMeans outputs a (I + 1, B) means with error at most 6, to each arm.
We now argue Algorithm is (kk+))B-1 (0)-1,))-liss - replicable. Due to the list replicability of the mean estimators, we see at most (k + 1) possible subset deletions at each b = =1.... B 1 with high probability. Therefore, following lemma similar to the previous regret analysis, and the proof can be found in Appendix A.3 Thus concludes the proof of Theorem|5.1
see at most (I: + 1)8-1 traces with probability 2 6. The proof of the
Lemma 5.13. The regret of Algorithm with probability at least 1 5 is bounded by Rr S
O kT v
kB KT log 8
MULTI-ARM BANDITS: LOWER BOUND
In this section, we prove that any algorithm for k-MAB that has a regret o(T) with high probability can not be (k 1) list replicable.
Theorem 6.1. There is no (k: 1, f-iss replicable algorithm for k-MAB that has o(T) regret with I
probability 5, for I+I
The proof this lower bound theorem makes use of a cubical version of Sperner/KKM lemma De Loera et al. (2002). Informally, Sperner/KKM lemma says the following: if we "properly color" dimensional cube with d + colors, then there a point p in the cube so that any arbitrary small neighborhood of contains + points with different colors.
We prove Theorem 6. in two steps. Step (I): we establish that any (A: - 1l-t replicable algorithm with (T)) regret yields a (A-1) ) list replicable algorithm for problem known as (k: e, -ARMTAR... Step (2): we establish that (ks, e, 6) -BESTARM does not admit (k 1)-list replicable algorithm.
We provide proof sketch after stating relevant definitions and necessary results. The detailed proof's are given in Appendix [1.441 We say an arm a is an e-best arm if μ³ Ha <.
Definition 6.2 ((k: c, 5) BESTARR)), Let
and c, (0, 1). The (k, (,))-BTTTARRM follow- ing problem: given k arms with unknown means pi,..., Pk- Output an c-best arm. with probability 2 8. The algorithm can sample from the distribution of the arms.
Definition 6.3 (List replicable algorithms). An algorithm A for (ks e, (),,,,))BESTAARM
-)--TEAAAAMM is l-list repli-
cable if there is a list L C [k]] of size so that (1) for every i E L, 1r" 4s < (2)
Pr[A outputs a arm from L) 1-18.
Lemma 6.4. If there is an (1list replicable algorithm for k-MAB that has o(T) regret with probability 2 1 - 8 then there is a E-list replicable algorithm for (k, e, 28)STAA for any constant e and 8.
The above Lemma formalizes Step (1). The proof of the lemma is based on the observation that any oregrregret algorithm for k-MAB should not play a bad arm too frequently. Thus, we could use k-MAB algorithm with o(T) regret tell us approximate best by simply looking the
8

---

Published as a conference paper at ICLR 2025
most frequently played arm. Therefore, to prove Theorem 6.1 suffices show that there is no (A: 1, x --isst replicable algorithm for (k, e, -)-BETAARM (Step (2)).
Following is a sketch of the proof. Suppose there is a (A: - 1, -iist replicable algorithm .A for (k, (k,c,6)-BESTE -))-BSTTRRMM. Let be a (k-1) -immensdiaai cuboid. For each point (a) (a....... 04--1) C, 1: 2) Each point 17 E C is assigned color from [k] follows: Consider the behavior of the algorithm A on the arms associated with the point p. If arm i E [k] is the most likely output of A, then color the point P with color i.
we associate arms with means (ak)...,, -k-1:
Spemer/KKM coloring of C. Thus by KPerner/KKM lemma, there exists a point p E C. such that for every V > O, the p-neighborhood of p (points that are close in &o -nrm sense) contains points pi..... Ple with distinct colors. Without loss of generality, let the most likely output of A on the arms associated with the point be i. The crucial observation that since A (k 1, d replicable, the probability of the most likely output is least T-T- On the other hand, since the points pi,.... Ph are arbitrarily close, by data processing inequality, can be argued that the behavior of the algorithm must be very similar on each of these inputs. This would imply that the algorithm A on instance associated with p1 must output each arm in k] with probability at least more than for the choice of k- This leads contradictions as the sum of these probabilities is
can be shown that the above coloring
Remark. Consider Algorithm with B = 2. With slight modification (play the best estimate arm in the second batch), this is (k;, 0)-list replicable algorithm with regret ((T2/3). Thus, by Theorem 6. in the sub-linear regret regime, the list size of optimal. We also point out that 6 S KII necessary due to the following: Consider the (k, 0)-list replicable algorithm as discussed.
Since there are only k traces, there is trace with probability S t The remaining k traces have probability at least (1 - t). Thus this is (I: 1, 1t) list-replicable algorithm.
7 LINEAR BANDITS
In this section, we provide the algorithm for list-replicable linear bandit. In the linear bandit setting, are given set of actions A C Rdd for some dimension d. Similar to the MAB setting, agent is allowed to take one action a, from .A at each time t and receive a reward rt. The assumption is that rr satisfies linear structure.
7.1 ALGORITIIM
The algorithm takes phase-eliminen elimmintiiiini batched structure, in each batch b, the algorithm maintains a set of surviving actions An such that for a E A,, pa- S Pa + 4h-1 for some 6 depending on the previous batch. Given a target regret bound Rr, we choose the current batch size, Th, so that 6-17% Ry and ΣØ To S T.
Similar to the MAB analysis, B is either constant or log- logarithai in T. The critical component to maintain the regret bound is that need to eliminate the arms with errors smaller than the previous batch. We first choose small set of arms from the survival set As. These arms are chosen such that they can be "good" representatives (in terms of linear regression) of the survival set. More specifically, we choose the G-optimal design (specified shortly), which contains 2d arms. Our algorithm plays each arm a specific number of times to obtain a sufficient number of samples about its mean. With these samples, we call the deplicabs laableMenns (Theorem 5. estimator to produce (2d + reppe-eeeele for their means. We then solve linear regression for these estimated means to obtain 0* for this batch and eliminate the arms with sub-optimality below the accuracy level. We will show that the algorithm halts in at most batches and achieves the desired regret bound. The list-complexity is therefore (2d + B-1
7.2 ANALYSIS
Definition 7.1. For any compact set A C Rd, let ग. A [0, be a distribution on A. Denote ((x) = E. <(a)aa" and g( suPaEa lim ||a|| (Ar+(()))))))) is a c-G-optimal design for A. if g(T)) ed.

---

Published as a conference paper at ICLR 2025
Algorithm 4: ((2d + 1)8-1 1))=-1,6--Liss 8)--isst Replicable Linear Bandit Algorithm
Input: Horizon T' Number of batches B >> 1, Failure probability å > 0
Initialize: A = 6o = 1, 1/ + 20t1 a f- 2 +
for b= do
Find a -2-G-optimal design To for A, using Corollary 7.3 with d' = |supp( s 2d. For sT)p(T)). play for No + [ / /d1 times and obtain empirical mean M(u) = (Ha,()) (e.ppp)))sspp(..) (halt the algorithm if '"' arms are played)
Let (()) < ReplicableMeanse
Let 4b [a] (eldssup((r)) be the matrix of stacking all actions in supp(m.)
Solve for estimated mean by: Ô (Φ, 2b))
D, P(b)
cal log "'
Denote emror parameter: cb V 2h
where T. (supp( |No
Eliminate actions Ab, with sub- sub-optimality below the accuracy level:
end Ab+1 - {a As maxa'eAs (a', (a, 0) I ea/2]
Theorem 7.2 (G-optimal design Kiefer Wolfowitz 1960)). For any compact subset A C Rdd there exists I-G-optimal design ग,, G C. A such that (sup((T) T)] = d.
Corollary 7.3. For any compact subset A R.d, there exists a /2-G-optimal design म,, GCA. such that [supp(T)] < 2d and is uniform distribution over supp(*).
Theorem 7.4 (Guarantee of Algorithm 4. For every ô (0, 1}, and integer B 1, Algorithm is ((2d B-B -)lsstt replicable, and for every input bandit instance satisfying Assumption 2.4
enjoys regret bound of dPTVV (T dB with probability least 1 ō, where 2011-
CONCLUSION
This work introduces and initiates the study of list replicability for the Multi-Armed Bandits prob- lem. We designed various list-replicable algorithms for k-MAB with near-optimal regret in and list-complexity linear/polynomial in k. To complement these results, show that to design (k- 1)-list replicable algorithms with sublinear regret. An open question is to close the gap between upper and lower bounds on the list complexity. For example, Theorem 5.4 if chose = .. then the list size is (A*)). Can we prove that list complexity is ((kk)? A general question investigate trade-offs between list complexity and regret.
not hope
algorithms is exponentially dependent on T. Consider the case when & 2 and both arms have identical distributions. Let UCB, and UCB2 represent the UCB estimates of arm and arm 2, respectively. Let assume that at some time f, UCB, < UCB2. UCB algorithm dictates that we shall play arm till the estimate of arm I is larger. However, because the samples random, the time which start playing arm probabilistic. For each time step where switch is possible results a new trace. This trait makes the list complexity of JCCB-based algorithms exponentially dependent on T. Note that the list complexities of our algorithms are independent of T. We leave it as an open question about what changes need to be made to UCB to guarantee list replicability.
Remark about UCB. The list complexity of
Acknowledgements. Pavan and Michael's work partly supported by NSF grants 2130536 and 234225. Vinod's work is partly supported by NSF grants 2130608 and 2342244.
REFERENCES
Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5):1-24, 2017.
10

---

Published as a conference paper at ICLR 2025
Peter Auer, Nicolo Cesa-Bianchi and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 11-235-256. 2002.
Monya Baker. 1,500 scientists lift the lid on reproducibility. Nature, 533(7604), 2016.
C Glenn Begley and Lee M Ellis. Raise standards for preclinical cancer research. Nature, 483 (7391):531-533,22) 2012.
Sébastien Bubeck, Nicolo Cesa-Bianchi, el. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In Sandy Irani (ed.), 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19. 2020, pp. 389-402. IEEE, 2020.
Nicolo Cesa-Bianchi and Paul Fischer. Finite-time regret bounds for the multiarmed bandit problem. In ICML, volume 98, pp. 100-108. Citeseer, 1998.
Nicolo Cesa- Basa-Bianchi, Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. Advances in Neural Information Processing Systems, 26, 2013.
Jesus A. De Loera, Elisha Peterson, and Francis Edward Su. A polytopal generalization of sperner's lemma. Journal of Combinatorial Theory, Series A, 100(1):1-26, 2002. ISSN 0097-3165. doi:
URL https: www. www.:eeseeincciceeeeeee com/
sci
Peter Dixon, A. Pavan, Jason Vander Woude, and N. V. Vinodchandran. List and cer- tificate complexities in replicable learning. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Pro- cessing Systems, volume 36. pp. 30784-30806. Curran Associates, Inc., 2023. URL
Eric Eaton, Marcel Hussing, Michael Kearns, and Jessica Sorrell. Replicable reinforcement learning. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas. Replicable bandits. In The Eleventh International Conference Learning Represen- tations, 2023. htttttts:t:////t httpttss://openreiee...tt net./
Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. User-level differentially private learning via cor- related sampling. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang. and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 20172-20184 2021.
Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 818-831, 2022.
John PA loannidis. Why most published research findings are false. PLoS medicine, 2(8) 2005.
Amin Karbasi, Grigoris Velegkas, Lin Yang, and Felix Zhou. Replicability in reinforcement learn- ing, Advances in Neural Information Processing Systems, 36. 2024.
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On bayesian upper confidence bounds for bandit problems. In Artificial intelligence and statistics, pp. 592--000 PMLR, 2012.
Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
11

---

Published as a conference paper at ICLR 2025
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
National Academies of Sciences, Policy, Global Affairs, Board on Research Data, Information, Division on Engineering, Physical Sciences, Committee on Applied, Theoretical Statisties, Board on Mathematical Sciences, et al. Reproducibility and replicability in science. National Academies Press, 2019.
Koustuv Sinha, Jessica Zosa Forde, Mandana Samiei, Arna Ghosh, Lintang Sutawika, and Siba Smarak Panigrahi. Machine learning reproducibility challenge 2023https: //tpttoo::/reprom... reproml. org/ 2023. URL.
Aleksandrs Slivkins al. Introduction multi-armed bandits. Foundations and Trendy@ in Ma- chine Learning, 12(1-2):1-286, 2019.
Kelly W. Zhang, Nowell Closser, Anna L. Trella, and Susan A Murphy, Replicable bandits for digital health interventions. 2024. URL http:///....eemttoo..ooooorrrrrr
271329265
A APPENDIX / SUPPLEMENTAL MATERIAL
A.1 PROOFS OF SECTION 5.1
We first note the following observation about Algorithm
Observation A.I. 66-1 5eg and 6B+1 < < <... < <6b+1 <6h < <6-1- <1 < 60
Proof of Lemma 5.2 We first prove for all E [k]. Pr(X; 2 m; E))
Let i E [b), for each S m, 1, A.,00) S A, + 2c S fm:-1 + 2cg S 6 + 2cg = Db- This is to
say that for rounds b such that b S m; 1, the highest estimate of A is more than the deletion criteria Dr. Thus, will not be deleted.
We now prove for all i E [k], Pr(X, S m, + 1 =
Let i [k]] and b m, + 1, we have A 2 A; 2c, C.. 2c, 6--1 1 2cb to say that the lowest estimate A, at round m, + 1, is strictly more than the deletion criteria Do, therefore i will be eliminated the latest by round m: + 1.
3c Dr. This
Observe that the regret in each round b E (2..... ....... B} is at most 7,Db-1 and for round 1 the expected regret is at most Ti
Proof of Lemma 5.3
B
B
ck
Rr < Ti
1+
TiD
25 + 3
Σ 52
log
52 15
0
2=
b=
25 + 3/
23ck log
25ch
1
Σ
56
< 25 + 3/
25ck 25cklog log
1
.25
0
b=2
= =0 (0(1 kTT
k log T
8
A.2 PROOFS OF SECTION 5.2
Proof of Lemma 5.6 Following a similar analysis for the proof of Lemma 5.2
We first prove, for all E [k]. Pr(X, 2 my E) = 1. Let i [k],
for for each b m4
3(v2 -
) < A + 2ed S Tm, -1 + 2eg < Tb
Tb
3mb < Dr
2C
12

---

Published as a conference paper at ICLR 2025
We now prove, For all i E [k], Pr(X; m; + 2|E) = 1.
Note that Eb < To. Let E [kt]. for b = m, +
A,(0) 2 A 2ca Tm; 2no = 57h - -2 7b-1
> 35- > Db
5
Proof of Lemma 5.9
Ignoring constants.
B
B Σ
h
h
k log T
Rr S Ti ++
Σ
12
C2
log
25
KT
log
526
0
2=
b=
A.3 PROOFS SECTION 5.3
Proof of Lemma 5.8 We first prove
Claim A.2. LetiE E [k] and my, m, + 1,m, there are at most two b-bad rs for i.
Proof. Let b m, m, + 1, m. + 2. Firstly, observe that the decision boundaries Do,1, Di......, D are spaced by 4eg- The estimate interval [A, 2cg, A + 2cp] has length 4еş and can contain most two Do,r, 2rr+11 See Figure
Let E [k]. Fix b = or m, + 1 or m, + 2, the number of b-bad r's for at most 2 via Claim A.2 In the worst case, there 2 bad rs for each of m,, m Therefore, there can be at most 3 x 2 6 for i. Therefore, there can be at most l x 6 bad rs.
and m, + 2, and all of them are different.
Proof of Lemma
5.13
Let 0 B3 we have, ignoring constants
B
B
1
h
B
To
Ry < Ti 1+
To = T +
Tb
log
T +
3
log
T
0
TTb-1
b=
b=2
2=
h
BB 8
= +
3.3 log
T
T
+ BTa
133 log
b=2
kB
= 0 KTT KT
log
8
A.4 PROOFS OF SECTION 6
Proof of Lemma 6.4 Let M be a dl-iss replicable algorithm for k-MAB that has a regret ((T) with probability 2 1 - 5. We design a ê-list replicable algorithm A for (k, e, 26) us- ing M. A works follows: Simulate M for T steps and let N, be the number of times was played. Output the arm that is most frequently played: That is, output arg max, No, breaking ties by outputting the smallest numbered arm. The list replicability of A follows due to the é-list replicability M. It suffices to show that A outputs an arm r-close to the best arm with probability
Let Ω be the sample space of the algorithm M. Each sample point w E Ωs sequence of alternating actions and rewards. We say that a sample point w good if the regret of M along w o(T) and the trace associated with w is in the list. By union, it follows that Pr[w is good] 2 1 28.
Consider good E Ω Let a A(w) be the output in this sample point. We now claim the p > μr c. Assume for contradiction's 's sake, that the output N4a < p² c. We know that N₂ Na (w) 2
because A outputs most frequently played arm. Hence the regret along w is 2 N, 2 Tz. Since and k are constants, this is contradiction. Thus Pr[AA outputs e-best arm] 2 8.
E.
13

---

Published as a conference paper at ICLR 2025
A.4.1 LOWERBOUND ON THE LIST COMPLEXITY OF e, (,,,,,)-BETTARM
In this section, we will prove that there is no (k: - 1, स+T) -liss replicable algorithm for (k, e, 0)- BESTARM. We first introduce the necessary definitions and notation and then state Sperner/KKM Lemma.
Definition A.3 (Sperner/KKM Coloring). Let E N and let be a d-dimensional cuboid and let V be the verlex sei (corners) of C. For a face F of C (of any dimension) let Vr be the set of vertices of F. A coloring function color : =C - [d + +] of C is called a Sperner/KKM coloring if (1) {color(v) u E V} [d + 1] (intuitively, all colors are used the corners) (2) for any face F of C, for any point p E F, it holds that color(p) (p) = color(v) (v) for some U E V (informally, the color of p is color of one of the vertices in the face F).
Theorem A.4 (Cubical Sperner/KKM lemma De Loera et al. 2002)) ) Let d N and let C be d-dimensional cuboid. Let color C + [d + I] be Sperner/KKM coloring of C. Then there is point p such that for every distinct colors.
v-neighbourhood of p. B (p) that contains d + points with
Theorem A.S. Let S BESTARM.
L and 8 S K+I There is no (k - 1)-list replicable algorithm for (k, e, 5)- 2I
Proof of Theorem A.5 Let A be a (k- - 1)-sist replicable algorithm for the (ki, 0)-ESTAR where the total number of times arms are played is n.
We will use Sperner/KKM Lemma on the (k- - d)-dimensia cuboid to arrive at a contradiction.
The cuboid C is defined [0, [0, c] x (0, 26] x x [0, (1 (k 2)c)]- For each point p = (a1. --. ag- E C, associate an instance
(p) = (a1. 02: ... -4-1, +) of the (k, e, BESTARM. We assign color from [k] to each point of the cuboid C follows: Color of a point p
the arm whose output probability is the largest when the algorithm A is run on input [(p) (breaking
the ties arbitrarily). More formally, color(p) arg max (Pr[A(I(p) a]}. We first claim that the above coloring is valid SpemnerKKKM coloring.
Coloring of the vertices of C. A vertex (cornrr) of C is specified by (an, 02,,..,, ak-1) where a; either 0 or (1 - (i - 1)e). Let i" be the first index where a is non-zero if such an exists otherwise (when all ats are 0) '" = k. Note that the color(v) it. This is because for any i & i", ag a, 2 6 and A should output the arm i" with probability 2 1 - 5. Note that all l colors are used while coloring the vertices of C. Figure 2 for the case 3.
Coloring of any face F. For an (0 < < < 2), consider (k- - 1 E) dimensional face F of C. Face specified specifying coordinates in < ig < ... < ig and fixing them to be Oişz where ar, is either 0 or (ij 1)e). We claim that the color of any point on F is one of the colors of VF.
Case 1. All a&s are in F: In this case the color(Vs) = [b] fir..... 4.) This is because of the following. Fix i E [k] \ (i1.-.. iej. Consider a point p whose ith co-ordinate is (1 (i 1)c) and all other co-ordinates are zero. This point belongs to Vr and gets color Note that the kth- coordinate of T(p) is 1/2 for every p. Thus the color of point p can not belong to {úr i2, de). By a very similar reasoning, it follows that for any point p on F' cannot have color from ( it and hence the coloring is proper.
Case 2. At least one at, is mon--zzre zero: Let j be the smallest index such that among {1,-... . such ai,- # In this case, we claim that the color(V))) {L, ... iz. . , -1
Fix a vertex e V(P). Color of this vertex cannot be any of i., , - as all these co-ordinates in ((v) are zero Let i > ig., note that 0iy, a 2 e. Thus can not be the color of v. We can apply very similar reasoning to conclude that for any point on F, its color belongs to (1.---i54 iz- {ōi, -1.-
To finish the proof, we need the following distance lemma that can be proved by Data Processing inequality.
Lemma A.6 (Distance Lemma), Let p and q be the two points of the cuboid C such that 1plg S Then, for any a E [b]. [Pr[A(T(p)) a) 1 Pr(A(T(()) a) S k.
14

---

Published as a conference paper at ICLR 2025
Now ready to complete the proof. Let ba By the Spemer/KKKM Lemma, there is v- neighborhood in (in lx-- -nomm) with points p1. Pk such that each point gets a distinct color. Let a, arg [e[k (Pr(A(I(p:)) al}. Note that all a, 's are distinct as colors of pi are distinct.
By definition of list replicability Pr[A([(p:) = a. 2 1- k-1 Z (k-1)(k+1) = --r 1 S k.
We have the following Pr[A([(pi) = ai] 2 -ं and for 2 S i S h. Pr(A(1(pi) = =a,] Z
P-I n k V
F by distance lemma.
Thus, the following leads to contradiction, Pr(A(T(p:)) E (ai, a g=-1 k=-l
k(k-1) k-1
k4
1.
A.5 PROOFS OF SECTION
Proof of Corollary 7.3 Let qinit be I-G-optimal design whose existence guaranteed by Theo- rem 7.2 For each a E supp(rimit), we add (drini(a)) copies of a into the support of т. Note that this implies supp(rt (T) is multiset. We define be the uniform distribution over all actions on its support.
Clearly,
(supp(T)]
<
Σ
[dr S (supp(Tinn) + d
Σ aEsupp(rinit)
π init (a) = 2d.
aEsupp(rinit)
Moreover,
((=) [supp(T) (T)
Σ
aa
Σ aEsupp(m)
aa
T
2
Σ
a init
iniit(a (d')aa" 2 (irinit).
2d
(Esupp(a)
('aupp(rrinit)
Therefore, π is a V2-G-optimal design.
Proof of Theorem 7.4 We first show correctness. For each batch let μ (Ma)oesupo(TL)) By Hoeffding bound and union bound, for each batch b, with probability at least 1 6/B. B.
Va E supp(To) Im(_(o) -Mal S O
Eb
VB
where n² is the empirical mean and c is error parameter defined Algorithm 4 Thus, by The- orem 5.10 have that with probability at least 1 5/B, the estimated mean (() satisfies
(|supp( Tb 1) list replicablity and
Va E supp(To):
|Pa,(b) Hal 0
ch Vd
Let V E Eessupp(rL) 00 We have
Va E Ab: (a, (0 01) < (a(Vt)1/2 (1,1))1/2111(000 (1/2(0-0))
s Vata.a V 1(0- (0) ( 0))
Vg(Too//supp((l /0- TT 0)
O(eb)
where we use
| 0)1 ( - Hella S O(E)).
Hence, the overall regret of the algorithm with probability at least 8 bounded by.
B
B
d
dB
dB
B Tb
RT Ti 1+
To Eb = T
+
Tb
log
T
de log
To-i
v T
b
b=
h
dB
B
dB
= + +v
vaa vdttlgg
log 5
Ta
T
+
BTa v
d log
8
b=2
=ō =0 (
15

---

Published as a conference paper at ICLR 2025
where we ignore constant factors and v. We also note that TB T and Ei= Tb T
Thus, with probability at least 6, the list complexity is bounded by (2d 1) 1)
0,1-0
(0,0)
(1,0)
Figure 2: Coloring of 2-dimensional cuboid for k = 3. Colors blue, red, and green are identified with coloring with arms 1,2, and 3 respectively. Point (Ir y) associated with instance (æ, y, 1/2).
16


Reviews:
[{"review_id": "rxYhY8GDrV", "reviewer": "Reviewer_ujbd", "summary": "This paper studies list replicability in multi-armed bandits (MAB), defining an algorithm as list replicable if it limits the distinct arm sequences (traces) across independent executions with high probability. Further, this paper proposes three algorithms with different parameters of list replicability. Finally, this paper investigates a lower bound of bandits with list replicability.\n\n**---After rebuttal---**\n\nMy primary concern pertains to the main claims of the paper, as highlighted in the title: \"Regret-Optimal\" and \"Matching Upper and Lower Bounds.\" Following a detailed discussion with the authors, I have observed that the paper fails to provide any lower bound in terms of regret for their setting, even in Section 6. Consequently, the claims of \"Regret-Optimal\" and \"Matching Upper and Lower Bounds\" appear highly questionable.\n\nIn their latest response, the authors stated that their claim of \"regret-optimality\" is based on achieving a $\\tilde{O}(\\sqrt{T})$ regret. However, to the best of my knowledge in the field of bandits, it is not standard practice to assert optimality of regret solely with respect to the parameter $T$, while disregarding other critical parameters (e.g., $K$). Given this significant issue of overclaim, I am unable to recommend this paper for acceptance.", "questions": "See weaknesses.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The problem setting proposed is both novel and intriguing, characterized by a rigorously defined concept of bandit replicability in Definition 2.2.\n2. The theoretical analysis provided is exhaustive, introducing three distinct algorithms tailored to various parameters of replicability.", "weaknesses": "1. Algorithms 1 and 2 exhibit considerable similarities. Could there be a method to consolidate these two algorithms into a unified framework?\n\n2. In Theorem 6.1, the designation \"lower bound\" appears misapplied as it does not seem to correspond to the lower bounds of any algorithms discussed previously. Notably, in Theorem 6.1 we have $l \\approx k$, whereas in prior algorithms $l \\gg k$ in most cases. In my humble opinion, a valid lower bound should be able to explain whether the proposed algorithms can be further optimized in general.\nFurthermore, why the authors said \"We show that result (3) is nearly tight for B=2\" in the abstract. What's the hidden constant behind $\\Omega(B) $ in (3). Do you mean the regret of (3) is $O(T)$ for $B=2$?\n\n3. Would it be more accurate to describe what is currently referred to as \"lower bounds\" in Theorem 6.1 as \"impossibility results\"? I think Theorem 6.1 is quite trivial because any pair of traces should share more than two arms if the total number of traces is less than $K$.\n\n4. The absence of experimental validation in this paper is notable. Including even preliminary numerical simulations or toy experiments could significantly enhance the validity and impact of the proposed algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "edMa2CY3RP", "reviewer": "Reviewer_ksHy", "summary": "This paper studies list replicability in multi-armed bandits and linear bandits. It comes up with the notion of $(\\ell, \\delta)$-list replicability, and proved various trade-off between replicability and regret dependency on number of arms and on time horizon. Furthermore, the paper extends the results to linear bandits setting.", "questions": "1. Line 18, $\\widetilde O \\sqrt{kT}$ missing parentheses.\n2. The notion of $O(\\cdot)$ and $\\Omega(\\cdot)$ was a little abused. The paper contains regret bound like $\\widetilde O (k^{\\frac32} T^{\\frac12 + 2^{-\\Omega(B)}})$. Here, it's inappropriate to use $\\Omega(\\cdot)$ in $\\widetilde O(T^{2^{-\\Omega(B)}})$, because the constant before $B$ cannot be ignored, e.g., $T^{2^{-B}}$ and $T^{2^{-2B}}$ have very different order.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper proposes a definition of reproducibility in bandits problems.\n2. The paper proves tight trade-off between replicability and regret dependency on $T$. \n3. The proof to the lower bound is quite insightful.", "weaknesses": "1. The algorithms are generally based on successive elimination, so it contains less insight on more widely used bandits algorithms like UCB.\n2. The proofs to the upper bounds are quite simple and lack enough novelty given their similarity to successive elimination.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HA5leaoK96", "reviewer": "Reviewer_jzZs", "summary": "The paper introduces replicability to the multi-armed bandit area through the concept of list replicability and proposes algorithms for both k-armed and linear bandits. Notably, for k-armed bandits, the authors provide a lower bound demonstrating that one proposed algorithm is nearly optimal.", "questions": "- While it seems that replicability papers often omit experiments, bandit experiments are generally straightforward to conduct. Did the authors consider demonstrating some experimental results?\n- Most of the algorithms appear to be adaptations of standard elimination-based bandit algorithms for both k-armed and linear bandit problems. It would be valuable if the authors could reference each classical elimination algorithm and include a side-by-side comparison showing what aspects of these algorithms break replicability and how the new modifications enable it.\n- Given that the study addresses regret minimization—typically dominated by UCB-type algorithms for stronger instance guarantees—the authors’ choice of elimination-based algorithms is interesting. Could you clarify the rationale behind this choice?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and structured, with a clear motivation. Tho short, it presents a comprehensive set of results for both k-armed and linear bandits, though the linear bandit results appear to be preliminary.", "weaknesses": "- It would be helpful to clarify which variables the hidden logarithmic factors depend on, and whether these factors are consistent throughout the paper.\n- No experiments are presented.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tzB4s1azOW", "reviewer": "Reviewer_m3DX", "summary": "This paper introduces the concept of list replicability to the multi-armed bandit model, where the sequence of arm pulls must lie in a small finite list with high probability. The authors design and analyze three algorithms, each providing different levels of guarantees on list replicability and high-probability regret. Additionally, a nearly matching lower bound is proved for any algorithm with sub-linear regret. The paper also extends the study to linear bandits.", "questions": "1. Could you compare $\\rho$-replicability and list replicability with respect to their potential practical applications, such as in clinical trials?\n2. Why is $C$ referred to as the number of shifts? Do you mean the number of possible shift $r$?\n3. Minor typos: Line 207: Theorem 2.1 -> Assumption 2.1; Line 210: lemma -> lemmas; Line 346: the of -> the number of.\n4. Thomson sampling and UCB are two well-established algorithms in the bandit literature. Thomson sampling is randomized, making it tricky to provide strong list replicability guarantees. Could you discuss the potential challenges in adapting UCB? My intuition is that UCB might achieve good list replicability with appropriate early-stage modifications.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Although the paper is highly theoretical, it is well-presented and clearly conveys the key ideas behind the algorithm designs and proofs.\n\n2. Three algorithms with varying levels of guarantees are introduced, each with its own significance. Notably, the first algorithm achieves near-optimal cumulative regret, and the total number of possible traces is independent of T. The last algorithm is based on a subroutine from Dixon et al. (2023) and is nearly optimal, given the lower bound in Section 6.\n\n3. The theoretical contributions are nontrivial, and the analysis of the phase-elimination algorithm is novel, which should be of interest to the bandit community. It is also interesting that the lower bound is proven using the Sperner/KKM lemma, a combinatorial result in coloring.", "weaknesses": "The main criticism of the paper might lie in its motivation. In the introduction, it is suggested that list replicability might be beneficial for safety-critical applications, as one could be prepared for the action sequence being played. However, although the proposed algorithms can ensure a small number of traces with high probability, these possible traces cannot be known without exact knowledge of the problem instance. Therefore, outside of the theoretical domain, the practical application of list replicability seems limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)