Replicable Online Learning
Authors: Saba Ahmadi
Siddharth Bhandari
Avrim Blum
Venue: NeurIPS 2025 poster ()
Keywords: Online Learning
Replicability
Primary area: theory
TL;DR: We demonstrate adversarially replicable online learning algorithms for online linear optimization and the experts problem that achieve sub-linear regret.

Abstract: We investigate the concept of algorithmic replicability introduced by Impagliazzo et al.(2022) in an online setting. In our model, the input sequence received by the online learner is generated from time-varying distributions chosen by an adversary (obliviously). Our objective is to design low-regret online algorithms that, with high probability, produce the \emph{exact same sequence} of actions when run on two independently sampled input sequences generated as described above. We refer to such algorithms as adversarially replicable.

Previous works explored replicability in the online setting under inputs generated independently from a fixed distribution; we term this notion as iid-replicability. Our model generalizes to capture both adversarial and iid input sequences, as well as their mixtures, which can be modeled by setting certain distributions as point-masses.

We demonstrate adversarially replicable online learning algorithms for online linear optimization and the experts problem that achieve sub-linear regret. Additionally, we propose a general framework for converting an online learner into an adversarially replicable one within our setting, bounding the new regret in terms of the original algorithm’s regret. We also present a nearly optimal (in terms of regret) iid-replicable online algorithm for the experts problem, highlighting the distinction between the iid and adversarial notions of replicability.

Finally, we establish lower bounds on the regret (in terms of the replicability parameter and time) that any replicable online algorithm must incur.

Replicable Online Learning
Saba Ahmadi"
Toyota Technological Institute at Chicago sabaêttic. edu & Siddharth Bhandari
Toyota Technological Institute Chicago
s wddwarth@tt.i edu
Avrim Blum Toyota Technological Institute at Chicago avrimêttic.ed
Abstract
We investigate the concept of algorithmic replicability introduced by Impagliazzo al. [2022], Ghazi et al. [2021], Ahn et al. [2024] in an online setting. In our model, the input sequence received by the online learner is generated from time- varying distributions chosen by an adversary (obliviously). Our objective is to design low-regret online algorithms that, with high probability, produce the ex- act same sequence of actions when run on two independently sampled input se- quenees generated as described above. We refer to such algorithms adversari- ally replicable.
Previous works (such as Esfandiari et al. [2022]) explored replicability in the on- line setting under inputs generated independently from fixed distribution; we term this notion iid-replicability. Our model generalizes to capture both adver- sarial and iid input sequences, as well their mixtures, which can be modeled by setting certain distributions as point-masses.
We demonstrate adversarially replicable online learning algorithms for online lin- ear optimization and the experts problem that achieve sub-linear regret. Addi- tionally, we propose general framework for converting an online learner into an adversarially replicable one within our setting, bounding the new regret in terms of the original algorithms regret. We also present nearly optimal (in terms of regret) iid-replicable online algorithm for the experts problem. highlighting the distinction between the iid and adversarial notions of replicability.
Finally, we establish lower bounds on the regret (in terms of the replicability pa- rameter and time) that any replicable online algorithm must incur.
Introduction
The replicability crisis, which is pervasive across scientific disciplines, has substantial implications for the integrity and reliability of findings. In survey of 1,500 researchers, it was reported that 70% had attempted failed to replicate another researchers findings [Baker, 2016]. A recent Nature article [Ball, 2023] discusses how the replicability crisis in Al is creating ripple effect across numerous scientific fields, including medicine, due to AIs broad applications. This highlights an urgent need to establish formal framework for assessing the replicability of experiments in machine learning.
Driven by this context, Impagliazzo et al. [2022] (see also Ghazi et al. [2021], Ahn et al. [2024]) initiate the study of reproducibility as a property of algorithms themselves, rather than the process
Authors are ordered alphabstically. The sccond author did this work prior to joining Amazon.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

by which their results are collected and reported. An algorithm ALG drawing samples from an (unknown) distribution D is called p-replicable if, run twice on independent samples and the same randomness R. ALG produces exactly the same answer with probability at least 1 p. For instance, consider the task of estimating the average value of distribution D over IR, say μ4, using n iid sample from D. If we simply use the empirical average, say ùú it won't lead to a p-replicable algorithm. However, replicability can be achieved at the cost of a little accuracy: we overlay a grid on with a fixed width (sufficiently larger than the standard deviation of ji) but random offset, and then round i to the nearest grid point (see Impagliazzo et al. [2022] for more details). this work, we focus on studying and designing replicable online learning algorithms.
In the context of an online learning algorithm, say for instance for the setting of learning with experts advice or online linear optimization, p-replicability means that when the algorithm is run using the same internal randomness on two input sequences sampled iid from an (unknown) distribution D, the entire sequence of actions performed is identical in both the runs with probability at least 1 p. More precisely, suppose the inputs to the an online algorithm, say ALG, arrive one by one, i.c., input c at time t. where C X for some input domain X. For an input sequence S [C1, ....... cr) we let az (S, R) be the action of ALG at time t: since ALG is an online algorithm, at as R) is a function only of the history seen till time t 1 and internal randomness R. We say that ALG is p-replicable for all input distributions D over X we have:
Pr S-D
[tt: (t) =
R)) 21-P.
where S and S' are independent sequences of T iid random variables sampled from D (see Sec- tion 2).
However, we would also like our online algorithm to achieve low regret as compared to the best course of action in hindsight. In the above set-up let the cost incurred by an action E A, where A is the action space, on input be Cost(a, c). For instance, in the case of online linear optimization a, E R" and Cost(a, c) = a-c (the inner product of a and c), and for the experts setting a E [n]] c I" and Cost(a, c) = c(a) the cost of expert a. Then, the regret of ALG on input S = (CI...., Cr) is
Reg(AL (gg((A(())) = E
Cost(at,
min Σ aEA
Cost(a,
Since the notion of replicability is under stochastic iid inputs, first demand on ALG is that while being p-replicable, it has low expected regret when the input sequence is sampled iid from D, for all imput distributions D. In other words, Es.-Dr [Reg(ALG(S))) is low and ALG is p-replicable. Such a setting was explored by Esfandiari et al. [2022] in the case of stochastic multi-arm bandits: see Section A for more works in this setting. A stronger yet natural requirement is that the worst- case regret of ALG remains low; that is, supsey r (Ag(AA((S)) is minimized while maintaining scenario: the algorithm achieves low regret in
p-replicability. This gives a best-of-hoth-wordd the worst case, while remaining replicable for stochastic iid inputs.
Another natural extension is allow the distribution on inputs to vary over time. Since an online algorithm processes inputs indexed by time, it is reasonable to permit their distributions to be time- dependent. For instance, consider online algorithm that recommends stock to invest in daily based on historical performance, or the online shortest path problem in traffic management, where edge weights time represent travel times streets. One could also generalize this requirement to cases where part of the input is stochastic and part is adversarial.
We capture the above points into single concept. We assume that for each time t the ad adversary chooses a distribution D. (in an oblivious fashion) and selects a cost vector e; from that distribution. The distributions D, could be point-masses, reducing the standard adversarial online formulation, but they could also be more general. The goal of the online learner ALG is to (a) achieve low regret with respect the actual sequence cI2 C2,..., ..., CT of cost vectors observed and (b) be replicable:
for any sequence Di, Dr, with probability at least 1 - p the algorithm has the exact same behavior on two different draws S, S' from this sequence when the learning algorithm uses the same randomness R, i.c.,
Pr [Vt: : (s R) = (S R)] 2 1 - p. 8,5' RR
2

---

If this is the case then we say that ALG is adversarially p-replicable. To distinguish it from the previous situation we will say that ALG is iid p-replicable if the replicability guarantees are only against iid inputs. (See Section 2.)
Remark. One could also study a notion of approximate replicability by requiring that, for each time step I,
Pr S.S' RR
1 - D,
meaning that each time step the actions of the algorithm S and S' the same with proba- bility at least 1 - This contrasts with the stronger requirement that the entire sequence of actions on S and S' be identical with probability least
Choosing the stronger notion of replicability of course implies approximate replicability, but also allows the algorithm to be composed with other algorithms, preserving replicability across compo- sitions.
1.1 Our Contributions
We present online learning algorithms for online linear optimization and the experts problem that achieve both sub-linear regret and adversarial p-replicability. Moreover, we introduce a general framework for transforming an online learner for the above problems into an adversarial p-replicable online learner, with a bound on its regret based on the regret of the original algorithm. Furthermore, we also give an almost optimal algorithm (in terms of regret) for the experts problem in the iid- replicability setting.
We also explore how replicability affects the regret of an algorithm by proving lower bounds of the regret of any online p-replicable algorithm in the adversarial and iid settings. Up to lower order terms the upper and lower bounds match for the iidrrppicaabiliy setting while their being gap for the adversarial-replicabbee
setting.
The key ideas are outlined below.
1.1.1 Adversarially p-replicable Online Linear Optimization
We examine the online linear optimization problem which a linear generalization the standard online learning problem. Here, at time t the algorithm taken action a IR" and receive an input C E R", and accrues a cost a, C (see Section 2). In this context, we demonstrate a low regret algorithm that is adversarially p-replicable. Our algorithm leverages two main strategies: a) partitioning the time horizon into blocks and updating its action only at the endpoints blocks (referred to transition points), and b) rounding of cumulative cost vectors the grid points in random grid. Below, we provide a brief overview of these key ideas:
The algorithm partitions the time horizon into blocks of fixed size and only changes its actions at the end of block. Here, for two independent sequences S, S' drawn from the same sequence DI,.. ... , since the sequences are close to each other but not exactly the same, traditional lowrregret algorithm, c.g. "Follow the Perturbed Leader" by Kalai and Vempala [2005], might change its actions in different but relevantly close time steps. Consequently, the idea of blocking allows to argue that this switching behavior of the algorithm happens with high probability within the same block. Hence, when the algorithm only changes its actions at the two different sequences.
Blocking of time steps:
endpoint of block, with high probability it shows the same behavior
Rounding of cumulative cost vectors to the grid points in random grid Here, at the end of each block, the online learner rounds the cumulative cost vectors to the grid points in a grid with random offset, and selects the action that minimizes the total cost pretending the grid point is the cost vector. This idea is inspired by the seminal "Follow the Lazy Leader" (FLL) algorithm of Kalai and Vempala [2005]. Since S, are drawn from the same sequence DI, , Dr, the cumulative cost vectors are within a bounded é distance with high probability, and hence the cost vectors get rounded to the same grid point with high probability. This property helps us argue that the online learner picks the same action at all the block endpoints (and also all the time steps) with high probability.
These two ideas help us achieve replicability guarantees, however, we need to careful when setting the block size and the randomness of the grid; we increase them, it is easier to achieve
3

---

replicability,, however, the regret will suffer. We show that by carefully selecting the blocksize and picking the randomness of the grid, low-regret learning and replicability over all time steps is possible.
Theorem 1.1 (Informal; see Theorem 3.1), Let p > O be a parameter. For the online linear opti- mization problem, there exists adversarially p-replicable algorithm with sub-linear regret.
1.1.2 An Adversarialyy p-Replicable Algorithm for the Experts Problem
Next, we explore the experts problem, where, in each period, the online learner selects an expert from set of experts, incurs the cost associated with the chosen expert, and observes the cost [0, 1] for all experts in that round. The objective of the online learner is to achieve low regret compared to the best expert in hindsight while ensuring replicabilityy across all time steps. We present an adversarially p-replicable learning algorithm with sub-linear regret. This algorithm applies the strategy of partitioning the time horizon into blocks and only updating its actions at the end of each block. Initially, geometric noise is added to each expert, and at the end of each block, the algorithm chooses the expert with the lowest cumulative cost, incorporating the initial noise. We demonstrate that, with appropriately chosen block sizes and noise levels, it is possible to achieve low-regret learning along with adversarial p-replicability. To prove replicability, we leverage the properties of geometric noise, such as memorylessness, and argue that when two trajectories are sufficiently close Lo distance, with high probability the best experts in these trajectories are the same.
Theorem 1.2 (Informal; see Theorem 4.1). Let p 0 be parameter. For the experts problem, there exists an adversarially p-replicable algorithm with sub-linear regret.
1.1.3 A General Framework for Converting an Online Learning Algorithm to an Adversarially p-Replicable Learning Algorithm
Furthermore, in Section 5, we present a general framework for converting an online learner to an adversarially p-replicable algorithm where its regret is function of the regret of the initial algorithm. For this conversion we need the further assumption that the cost incurred on action a and input c, i.e., Cost(a, c), is linear in c: Cost(a, C + 02) Cost(a, c1) + Cost(a, 62) (this assumes that the input sequence is itself in an ambient vector space). We illustrate how this general framework can be applied to both online linear optimization and expert problems. However, this approach comes with a trade-off: while it provides a versatile and unified solution, it gives worse regret bounds compared algorithms specifically designed for each individual setting.
We continue with the approach of grouping time steps into blocks and rounding the cumulative cost vector at the end of each block to the nearest grid point. Specifically, at the end of block i, we compute the difference between the rounded cumulative cost vectors at the ends of blocks i and i 1. This difference is then fed as the i-th input to the initial algorithm, and the action suggested by the initial algorithm is applied throughout block i + 1.
However, we need a slightly more sophisticated approach to relate the regret bound of the external algorithm to that of the internal algorithm (the initial online learner). When providing the i-th input to the internal algorithm, we use two fresh random grids to compute the rounded cumulative cost vectors at the ends of blocks i and i 1. Consequently, the cumulative cost vector at the end of block é is rounded in two different ways: once for the i-th input to the internal algorithm and once for the (i + 1) block. (See Lemma F.1 for more details on why this helps.)
As before, we need to strike a balance between the grid size and the block size to achieve both low-regret and adversarial replicability.
Theorem 1.3 (Informal; see Theorem 5.1). Let p 0 be a parameter, and assume that the cost function Cost(a, c) is linear in c, i.e., Cost(a, C1 + 02) = Cost(a, c1) + Cost(a, e2). Given an internal algorithm ALGina with bounded regret, it can be converted to adversarially p-replicable external algorithm ALGest with bounded regret.
1.1.4 iddReplicability for the Experts Problem
To investigate and contrast the differences between iid and adversarial replicability, in Section H we design an iid p-replicable online algorithm for the experts problem which has low worst-case regret. Recall that in this setting, we have experts, and the cost vectors are drawn iid from an unknown distribution D over [0, 1)". The goal to design an iid p-replicable algorithm with worst-case regret as low as possible which means the following: (1)We say algorithm has worst-case regret K if
4

---

for any cost sequence S = (c1...., er), the expected regret satisfies ER-R (Reg(S, R)] (2)We say an algorithm has replicability p for iid cost sequences S and S' we have
Pr [ (8, (S R) 1211-p 8,8" R
While it is possible to use algorithms that are adversarially replicable, we adopt different approach here to achieve better regret bounds. We still group time steps into blocks, but in this case, the blocks are of varying lengths. Additionally, we add geometric noise of varying magnitude at the end of each block, which helps in keeping the regret low while achieving replicability.
As before, at the end of each block, we select the expert with the minimum cumulative cost (incor- porating the added noise) to use for the entire next block. The first block has length approximately vT, providing an estimate of each experts expected cost under D with an accuracy of 7 Us- ing these estimates, we select the best expert the end of block 1 (after incorporating noise) and stick with them for the next block, which has length 73/1, Proceeding in this manner, ensure an expected regret of at most V per block, with at most log log(T)) blocks in total. (See Algorithm for details.)
Theorem 1.4 (Informal; see Theorem H.1). Let p > be a parameter. For the experts problem, there exists an iid p-replicable algorithm with worst-case regret roughly lovT)og())/)).
In light of our lower bounds (see below or Theorem 1.2) the regret achieved is optimal up to poly log(T)) and other logarithmic factors.
1.1.5 Lower Bounds Regret for Replicable Online Algorithms
In Section I we prove lower bounds on the regret p-replicable algorithm must suffer, both in the iid and adversarial settings. The main idea for the iid setting is to using the lower bound on the replicability of the coin problem from Impagliazzo et al. [2022]. The coin problem involves identifying the bias of a coin (either 1/2+7 or 1/2-7) using T iid samples, with success probability
1 - 8 and replicability at least 1 p. which requires p 2 Ω (
By embedding this problem
in the experts setting (even with = 2) with 7 x Reg/T, we obtain Reg > Ω [VT] In the case of adversarial replicability with n experts, we use the above idea in log(n) phases of length T/ (n) to essentially embed log(n) different instances of the coin problem.
Theorem 1.5 (Informal; see Theorems I.2 and 1.3). If the parameter is sufficiently larger than 1/VT then any iid p-replicable algorithm must suffer worst-case regret 22( Q2VT((1 p Vlog(n)).
Further, any adversarial p-replicable algorithm must suffer worst-case regret of S2( / (Tgg(n))
2 Model
Online Linear Optimization Online linear optimization is a linear extension of the online learn- ing problem, where the online learner ALG must take series of actions d1 Q2 each from possibly infinite set of actions A C R". After the tt action is taken, the decision maker observes the current step's cost e C R". The cost of taking an action when the cost is is c, and the total cost incurred by the algorithm is E, a: G. We use S = {ea,'" ... ,er) to denote the sequence of costs. The learner aims to minimize the regret accrued over T steps where regret is defined as:
Reg(ALG(S)) > Za.a ai min aeA
Σ a.c
Experts Problem In this problem, each period f, the learner ALG picks an expert a, from a set of n experts denoted by A. pays the cost associated with the chosen expert cy and then observes the cost between [0, 1] for each expert. Let S denote the cost sequence {c1, (c.,... cr). The goal of the learner is to have low regret, i.e. ensure that its total cost is not much larger than the minimum total cost of any expert.
Reg(ALG(()) = Σ (ar) min
Σ ca(a
aEA
5

---

iid-Repicaability Let D be distribution over an input domain X, and let ALG be an online al- gorithm. Let S, be independent sequences of length T of inputs drawn iid from D, and let R represent the internal randomness used by ALG. Further, let (S, R) be the action at time on input S and internal randomness R. We say that ALG p-iid replicable if:
PrIEE [T): as R) a,(" Ro] 2 11pp
5,8
Adversarial Online Replicability Throughout the paper, we consider more general version of replicability where all the examples in the sequences S' are not drawn necessarily from the same distribution D. Instead, we assume an adversarial sequence of distributions D1, D2, .... Dr, and the thh element of the sequence is drawn from distribution D.. Let P = _|_ DD. i.c., the product distribution D1 x .... x Dr. Under this assumption, we say an online algorithm ALG is adversarially p-replicable if for sequences S, S" each of length T sampled independently from P, it produces the same sequence of actions with probability least 1 - p. i.e.
Pr M [T) a, R = a,', 8,8',
, RJ) 21
3 Adversarially p-Replicable Online Linear Optimization
In this section, we present Algorithm I that is an adversarially p-replicable algorithm with sub-linear regret for online linear optimization. Our algorithm leverages two main ideas of first partitioning the time horizon into blocks and updating transition points, and second rounding of cumulative cost vectors to the grid points in random grid. The rounding idea is inspired by the "Follow the Lazy (FLL))"(FLL) algorithm of Kalai and Vempala [2005]. However, we argue that their algorithm is not necessarily replicable and to fix this issue, we also need the idea of blocking timesteps and updating the algorithm's is actions only at the transition points. Algorithm 1 is described in Section 3.1. We analyze the regret of Algorithm by appealing to a different algorithm "Follow the Perturbed Leader with Block Updates" that incurs the same expected cost as FLL (Section D.1). Finally, Theorem 3.1 shows that by selecting the block size and noise level carefully Algorithm I achieves adversarial peccaariilp--ppplle p-replicability with sublinear regret bounds.
action only at the endpoints of blocks, referred as
3.1 Follow the Lazy Leader with Block Updates (FLLB(=))
Algorithm 1 is modified version of the "Follow the Lazy (FLL) algorithm of Kalai and Vempala [2005]. FLL first picks a n-dimensional grid with spacing 1/2 where is given as in- put, and random offset p Unif( 1/e)"). Then each iteration, it considers the cube E & + [0, 1/e)", that is the cube starting at Σ 4 with side length 1/e, and then the al- gorithm picks the unique grid point -t-1 inside this cube (see Figure 1). Subsequently, it plays the action that minimizes the total cost pretending the cost vector is 9t-1, a = arg min a 9t-1- FLL achieves sublinear regret, however, in Example 3.1, we argue that FLL does not necessarily satisfy the adversarial p-replicability property.
Example 3.1. Consider two different cost sequences S' sampled from the same product distribu- tion P arriving in an online fashion. Suppose there are only two actions an a2 E A where on has lower cost in hindsight. Suppose Ci = ci = (0, B), where B < 0. This means that day 0 gives a bonus to the second action and pretends that 02 has a better performance initially. Therefore, the algorithm keeps predicting a2 until after sufficient number of examples arrive timestep and it becomes clear that aj has better performance, and then, the algorithm shifts to oulputting for the rest of the timesteps. However, since S, S' are different sequences, it is not necessarily the case that the switching thresholds for S and S' are the same. Consequently, FLL is not necessarily adversarially p-replicable.
In Algorithm 1, in addition to the rounding idea of FLL, we leverage the idea of blocking timesteps to overcome the challenge presented in Example 3.1. Since each timestep t, both S,, Sy are drawn from the same distribution D,, it is the case that the switching thresholds for S and S' are "approximately" the same. We use this intuition to block the timesteps and during each block output the same action. Now as long as the block sizes are large enough, the switching threshold for both sequences S, S' would be within the same block. That helps us to achieve replicability. However, since we outputting the same action for each block and not updating our decision at each round,

---

Clit-1
Figure 1: An illustration of the FLLB(e, B) algorithm. The perturbed point Cia-11 + p is uniformly random over a cube side 1/e with vertex at Cıa-11 (similarly for dp-1 + p). In Theorem 3.1, we prove that by McDiarmid concentration bound, two different trajectories Cıæ-1 and d1.-11 within distance 12( ((vTT) with high probability, and they get mapped to the same grid point gt-1 with high probability.
the regret will suffer. Nevertheless, we show that by carefully selecting the block size, we can achieve adversarial p-replicability and sublinear regret guarantees.
Now we are ready to formally present our "Follow the Lazy Leader with Block Updates" algorithm (Algorithm 1). the beginning, choose offset p [0, 1m uniformly at random, determining grid G G= {p + 1- z E )"). that is grid that originates from p with side length 1/e. Then each iteration t, if 1 is multiple of the block size B, the algorithm plays the action that minimizes
the cost pretending the cost vector is 9t-1, where -h-1 the unique point in G C1a-1 [0, ))))
where C1:--1 the cumulative cost from time to 1-1. Therefore, the action played by the algorithm in step is = arg min,e,4 9t-1- However. if t is not multiple of B, the algorithm stays with the action played in the previous round. In Theorem 3.1, we prove that by setting the values of 8 and B carefully, FLLB achieves strong replicability and sublinear regret guarantees.
Algorithm Follow the Lazy Leader with Block Updates (FLLB(e, B))
Input: Sequence S = (c1, J arriving one by one over the time, e > 0 and block size B.
Sample p [0, 1)" uniformly random. Let 01 be random action picked from A.
Let G {p + 1
2").
for I. ,.... do
if 1 multiple of B then
-t-1 - Gn C1a-11 + 10, 2))
a, arg min a gt-1-
else
// Stay with the previous action.
0e d1-1-
Theorem 3.1 (Regret and Replicability Guarantees of FLLB), FLLB(E, B) adversarially p-
2/3
replicable and achieves regret O(DT5/6 when B
21 211/2lo((1T/
and
VBT and D is the & diameter of the action set A.
In order to prove the theorem, first, we analyze the regret of Algorithm 1. However, we need to be careful when picking the values of and B that the regret does not blow up. If is too large
7

---

then in Algorithm I, lot of different accumulated cost vectors C1:-1 get mapped to the same grid point 9t-1 which would cause lot of regret. Similarly, when is too large, the algorithm takes the same action for large block of time and does not update its decision which would cause the regret to suffer. In order to pick optimal values for & and B, we analyze the regret of Algorithm by appealing to different algorithm "Follow the Perturbed Leader with Block Updates" (FTPLB((, B)) that in expectation behaves identically to (E B) on any single period and incurs the same expected cost. This algorithm is modified version of the "Follow the Perturbed Leader" (FTPL(e)) algorithm by Hannan- -alannnn-Kaa---- Vempala.
3.2 Follow the Perturbed Leader with Block Updates (FTPLB)
First, we describe the FTPL(e) algorithm (Algorithm 5) by Hannan-Kal Kalai- Kalai-Vempala. FTPL(s) first hallucinates fake day 0 with random cost vector Co. where co Uni(((0, ))) Then in each time period t, picks the action that minimizes the cost of all days co. " ct-1
at arg min (Co + 01 +... Ct-1,
aEA
Algorithm 2 Follow the Perturbed Leader(FTPL(()) [Kalai and Vempala, 2005]
Input: Sequence S == (c1.-.. cr) arriving one by one over the time, E >> 0.
10 Sample Co [0, 1 uniformly random. for ..... do 12 a c arg min Ei= C..
The same argument used in Example 3.1 demonstrates that Algorithm sarially p-replicable. Now, describe the "Follow the Perturbed Leader with Block (FdPates B), Algorithm 6). FTPLB first hallucinates a fake day with a random cost vector cp, where op [0, 4)th uniformly at random. Then, picks the action that minimizes the cost of all days co, (BBLLI/BBBB where is the block size.
not adver-
a₂ arg min(co + a +... CB(((-1)/BB aEAA
Algorithm 3 Follow the Perturbed Leader with Block Updates (FTPLB(e, B))
Input: Sequence S =c( CT) arriving one by one over the time. E >> 0 and block size B. Sample co ~ [0, 2 uniformly at random.
for t 1, . do
15
ift 1 is multiple of B then
L at < arg a Ei= a
16
17
else
// Stay with the previous action.
18
at a:-1-
// this equivalent to having a, = arg min E. Bl(t-1)//1 a 04
Remark 3.2. In each step t when t is transition point, FLLB pretends that the cumulative cost vector gt-1 that the unique grid point inside the cube C1--1 [o, 1/E)". Due to the random offiet p of the grid considered in FLLB, 9t-1 is uniformly distributed inside this cube. Furthermore, FTPLB, also pretends the cumulative cost vector is C1æ-1 cn where co ~ Uni [[[ 1/e)"), and therefore it has the same distribution as 9t-1- This implies, FLLB and FTPLB have the same expected cost.
Next, we bound the regret of the FTPLB algorithm. The proof is deferred to the Appendix. Theorem 3.3 (Regret Guarantee of FTPLB). Assume the maximum & length of any cost vector E C is 1, and the & diameter of the action set A is D. co ~ Unif([0, 1/E]") then the expected regret of FTPLB(E, B) in T steps satisfies:
E [e < D(BET + 1/E)
setting 1/(VBT) gives expected regret most D BT.

---

Finally, we are ready to provide proof sketch of Theorem 3.1. The full proof is deferred to Sec- tion D.
Proofsketch of Theorem 3.1. First, we bound the probability of non-replicabilit. Recall that Algo- rithm chooses uniformly random grid of spacing 1/e. In each transition t. if Algorithm picks the action that minimizes the total cost, pretending
transition
point {B + +, +1 1.... ,.. the cumulative cost vector is 9t-1, where 9t-1 is grid point that lies inside c1 + [0, 1/e)" (see Figure 1). Consider two different trajectories C1,".. Ct and ci. ... 4 where each c ~ D; First, we bound the probability that 9t-1 # 9--1 as follows. This event happens iff the grid point C1a-11 + [0, 1 is not d1--1 + [0, 2 the proof, we argue that for any RR,, the cubes [0, 1/=]" and v + [0, 1/e]" overlap in least (1 (1-2f1(o) (o)) fraction. Furthermore, with high probability, the & distance between cumulative cost vectors C1 and 61 is bounded as follows when /2 log(2T/p)) +
prove that
Pr f((x2 -(a) pVnT
P 2T
2T
Now by taking union bound over all the transition points t= (B + 1,2B + 1,...} the total proba-
bility of non-replicability at most (27 =Ep/nTT T. Consequently, we can set values of B, such that the probability of ton-replicability over all the time-steps is at most p:
g.
( 2/ + EpVnT)
T
B
achieve this, suffices to have:
Bp
2p/n1/8/22
Additionally, in order to minimize regret by Theorem 3.3, we need to set =11
VBT' In the proof show that by setting B 0 (1/p))/33) get regret bound of O(DVBT)
Experts
In this section, we investigate the experts problem and present our algorithm "Follow the Perturbed Leader with Block Updates and Geometric (FFss"(FFPLB")) (Algorithm 4) that is adversarially p-replicable learning algorithm with sublinear regret. This algorithm applics the strategy of parti- tioning the time horizon into blocks and only updating its actions the end of each block. Initially, geometric noise is added to each expert, and at the end of each block, the algorithm chooses the expert with the lowest cumulative cost, considering the initial noise. Theorem 4.1 demonstrates that with appropriately chosen block sizes and noise levels, is possible to achieve no-regret learning along with adversarial p-replicability.
Algorithm 4 Follow the Perturbed Leader with Geometric Noise and Block Updates
(FTPLB"(E,
Input: Sequence S= (c..... CT) arriving one by one over the time. 0 and block size B. 19 Sample for every expert a E A, X, Geo(E).
for t:: 1, 1.... , do if 1 is multiple of B then
21
L a arg min Σ'=l ca(a) X..
22
23
else
// Stay with the previous action.
24
Ot <- 0:-1-
// this is equivalent to having = arg min A Σ Bl(t-1)/D) c;(a)
Eiel

---

Theorem 4.1 (Regret and Replicability Guarantees of FTPLB"), FTPLB"(E, B) is adversarially
2/3
2//2( Ioniet// + In(n]
p-replicable and achieves regret Ö(13/6 5//6 (n)p when B
and
Inn
BT
BT
Proof deferred to Section E.
A General Framework for Replicable Online Learning
In this section, we demonstrate a general recipe for converting a regret minimization algorithm ALGint. which call the internal algorithm, to adversarially p-replicable algorithm ALGezt with potentially a higher regret. Our general procedure uses two main ideas, rounding procedure of the loss trajectories inspired by the "Follow the Lazy Leader"(FLL) algorithm of Kalai and Vempala [2005], and blocking of time-steps. Here we present the results for the setting where the internal algorithm Ain takes as input bounded & cost vectors. Section G provides the results for the fo case. As mentioned in the introduction, we require the further assumption that the cost function Cost(a, c) linear in c, i.c. Cost(a, C1 + 02) = Cost(a, 61) + Cost(a, c2). However, this still sufficient to capture both the settings of online linear optimization and experts problem.
Our framework as follows: At each timestep if t is a multiple of the block size B, then, it picks an n-dimensional grid with spacing 1/c where is given as input, and random offset Pe [0, 1/E)", where is the dimension of the space. Then it considers the cube C1 [0. 1/e)", where C1:b = Σx= Gi and picks the unique grid points 9t-1 inside this cube. Furthermore, for n-dimensional grid with spacing 1/c and off'set pl.. Then, it considers the cube CLa--IB + [0, 1/e)" and picks the unique grid point カ-1-B inside this cube. Then, it gives B+2n/E (gt-) s(-1-B) as the input argument to the algorithm ALG and plays the action returned by ALG for the next B timesteps. This framework is given in Algorithm 7. Theorem 5.1 demonstrates that Algorithm 7 is adversarially p-replicable with bounded regret.
fresh random offset P. [0, 1/e)", it picks
Theorem 5.1 (Regret and Replicability Guarantees of Algorithm 7). Let > 0 be a parameter, and assume that the cost function Cost(a, c) is linear in c, i.e., Cost(a, Cj 02) Cost(a, (1) + Cost(a, c2).
Suppose for two different input trajectories CI,-.., and di,... dr where for each time-step t, ce de ~ D.,for each time step t, the ε distance between C1at and d is at most m with probability least - %. Then, Algorithm is adversarially p-replicable and achieves cumulative regret
(ALLGi))(AGGin)) when is most pB 47 B
8nm' and == =
Proof is deferred to Section F. Next, we show the application of Algorithm to the online linear optimization problem.
Corollary 5.2. In the online linear optimization setting, Algorithm 7 is adversarially p-replicable and achieves cumulative regret Ö DTDD7/88 1013//ppp////- p1/4))
6 Further Directions & Open Quesitons
The questions we address in this paper fall within the full-information setting, specifically the experts problem and online linear optimization. A natural future direction is to extend these techniques to the hundit/aatial-inormmatee ideas could be valuable.
setting while requiring adversarial replicability, where we believe our
As mentioned, would also be interesting to explore other problems, such as clustering and rein- forcement learning, that have been studied in the iid context, and extend them to the adversarial replicability setting.
Additionally, the current lower bounds on regret (Theorems 1.2 and I.3), while optimal for the iid- replicability setting, do not match the upper bounds in the adversarial replicability setting for either the experts problem or online linear optimization. An intriguing open question is to prove w (VT) lower bound on regret for a fixed value of p. say 1/100, in the experts setting, or to design an algorithm that achieves O ((VT) regret while remaining p-replicable.
10

---

Acknowledgements
This work was supported in part by the National Science Foundation under grants CCF-2212968 and ECCS-2216899, by the Simons Foundation under the Simons Collaboration on the Theory of Algorithmic Fairness, and by the Office of Naval Research MURI Grant N000142412742. The views expressed in this work do not necessarily reflect the position the policy of the Government and no official endorsement should he inferred. The research was done when SA and SB were at Toyota Technological Institute Chicago.

---

References
Kwangjun Ahn, Prateek Jain, Ziwei Ji, Satyen Kale, Praneeth Netrapalli, and Gil Shamir. Repro- ducibility in optimization: theoretical framework and limits. In Proceedings of the 36th Interna- fional Conference Neural Information Processing Systems, NIPS '22 Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 978171387 1088.
Monya Baker. 1,500 scientists lift the lid on reproducibility. Nature, 533(7604), 2016.
Philip Ball. Is ai leading to reproducibility crisis in science? Nature, 624(7990):22-225 2023.
D Blackwell. Large deviations for martingales, Festschrift for Lucien Le Cam: Research Papers in Probability and Statistics, pages 89-91, 1997.
Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 520-527, 2023.
Eric Eaton, Marcel Hussing, Michael Kearns, and Jessica Sorrell. Replicable reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas. Replicable bandits. arXiv preprint arXiv:2210.0188 2022.
Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni, Grigoris Velegkas, and Felix Zhou. Replicable clustering. Advances in Neural Information Processing Systems, 36, 2024.
Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. User-level differentially private learning via cor-
related sampling. Advances in Neural Information Processing Systems, 34:20172-201844 2021.
Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasject Sekhon. Time-uniforn chernoff bounds via nonnegative supermartingales. Probability Surveys, 17(none), January 2020. ISSN 1549-5787. doi: 10. 2211/11--322 URL http: //tp:///dxxxoo/ oro. /00
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, pages 818-831, 2022.
Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-305 2005.
Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistinguishabiiity of learning algorithms. In International Conference Machine Learning, pages 15586-15622. PMLR, 2023.
Colin McDiarmid. On the method of bounded differences. In J. Siemons, editor, Surveys in Com- binatorics, volume 141 of London Matheratical Society Lecture Note Series, pages 148-188. Cambridge University Press, Cambridge, UK. 1989.
Kelly W. Zhang, Nowell Closser, Anna L. Trella, and Susan A. Murphy, Replicable bandits for digital health interventions, 2024.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Answer: [Yes]
Justification:
Our paper is theoretical and we provide proofs for all our theorems.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We provide lower and upper bounds for our problem, and we discuss the limitations include a gap between our bounds in the further directions and open questions section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
13

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All the proofs for theoretical claims are provided in the main body and ap- pendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should numbered and cross- referenced.
All assumptions should clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relics upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
No experiments, just theoretical results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data also be provided via
often one good way to accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
14

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
No experiments only theoretical results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https: //nips.cc// public/ guides CodeSubmiis somnissionn wwwssooooolli. olicy) for more details.
While we encourage the release of code and data, understand that this might not be possible, so No an acceptable answer. Papers cannot rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips. cc htppppulliie 1 c/ /uwdees Codee is sissPooPoll icy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification:
No experiments, only theoretical results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
15

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
No experiments only theoretical results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK report I-sigma error bars, but should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer:
[NA]
Justification:
No experiments only theoretical results.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://p.....p..otttthcceeeeeeee
16

---

Answer:
[Yes]
Justification:
There are no potential harmful consequences with this study.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there is a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
There are negative impacts. We are studying the replicability of online learning.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper has no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
17

---

Released models that have high risk for misuse or dual-us use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: NA. We build on previous theoretical results and cite all the relevant results in the intro and related work.
Guidelines:
The answer means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswil thoode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Question:
Answer: [NA]
Justification:
No new assets are being released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
18

---

14. Crowdsourcing and research with human subjects
Question: For crowdsoureing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsoureing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects. and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: the core method development in this research does not involve LLMs any important, original non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /t////nuissss// cc//onfernnoee////////ccc 2025/LLM for what should or should not be described.
19

---

A Further Related Work
Online learning is a well-studied and classical field, with extensive literature on the subject. Our work is inspired by Kalai and Vempala [2005].
Algorithmic replicability was independently introduced by Impagliazzo al. [2022], Ghazi et al. [2021], Ahn et al. [2024], and later studied in the context of multi-armes bandits Esfandiari et al. [2022], reinforcement learning Eaton et al. [2024], clustering Esfandiari et [2024]. Several works have shown statistical equivalences and separations between replicability and other notions of al- gorithmic stability including differential privacy [Bun al., 2023, Kalavasis al., 2023]. fact, replicable bandit algorithms have also found use in medical contexts Zhang et al. [2024]. How- ever, all of these works focus on the idd redriiciiyayllity setting, making it intriguing to explore these problems in the adversarial replicability setting.
B Some Standard Concentration Inequalities
Theorem B.1 (Blackwell [Thee] 1) (see Howard et al. [2020])). Let St be a real valued martingale with So If A $ for all then for any a, b we have
P ENENN 8 2 a + bt)
2ab
Therefore, we also have
P PAALEN -a bl) S e
Theorem B.2 (McDiarmid's Inequality McDiarmid [1989]). Let X1. X2...., Xn be independent random variables taking values in a set X, and let f x" + R function such that for all and all ø1, ................................ Zn z E X.
[I, ,.....,, .m.
f(1,, ",...,,, ci.
for some constants C1, C2,..., Then, for any > 0,
2
P(J(X1, x,,) - X,, Xn)) 2 eexp
E c
and
20a
P X2, ....., X,) -iffE[f(11... X....., .x,) -c) exp
Σn < o
C Concentration of trajectories in -norrm
Lemma C.1 (Concentration of trajectories fg-norm). Let Di...., De be distributions over the unit E, ball in IR. Consider two independent sequences of independent random n-dimensional vectors to and {wiHez> where each v; and w; is drawn from D. Then, for > 2 we have
Pr Σ (us - wi)
> cvin
< <exp <exp(1(-3
[c(2-))²
2
Proof. Let u, 8/ wi Note that always |uill & 2. Let f (ui...., ... ue) || Then
If (u,,..., U4-1, ;.-...,,,ii-----.... Uitlo...y Uz) R + IR is 2-Lipschitz for all i E [t]. Hence by McDiarmid's inequality (see Theorem B.2),
22
Pr (u - F (u1.-.. mi)l > e) < exp
48
Now, for vector let (h) denote the thth component. Then,
E [f (u),.... u.] = E [| E, [
E
u
20

---

Applying Jensen's 's inequality we have:
E
E
Σ
(10)
1=1
which by canceling cross terms gives
(K) 2
E
u
Further, by the CauchySehwaaz inequality we have:
2
2
Σ
ui
2
1"h
ui
11)
Σ
ui
(1))
Vnx x
E
ui
(k)
A=1
-Vx x
E
t=1
Vn
E
2
2/tn
(lui22 < 2 as 11l1 & 2)
[f (ui,-.., uz)] 22/n.
Finally, setting e = (c 2) we have,
(_ (c---2) 1-)
Pr Pr[s(vn (wl, u+) > evtml < exp
which proves the lemma.
D Proof of Theorem 3.1
First, we analyze the regret of Algorithm 1. However, we need to be careful when picking the values of e and B so that the regret does not blow up. E is too large then Algorithm 1, a lot of different accumulated cost vectors Cia-1 I get mapped to the same grid point 9:-1 which would cause lot regret. Similarly, when B too large, the algorithm takes the same action for a large block of time and does not update its decision which would cause the regret to suffer. In order to pick optimal values for и and B, we analyze the regret of Algorithm I by appealing to different algorithm "Follow the Perturbed Leader with Block Updates" (FTPLB(s, B)) that in expectation behaves identically to FLLB(e, B) on any single period and incurs the same expected cost. This algorithm is modified version of the "Follow the Perturbed Leader" (FTPL(E)) algorithm by Hannan-Kalai- Vempala.
D.1 Follow the Perturbed Leader with Block Updates (FTPLB)
First, we describe the FTPL(E) algorithm (Algorithm 5) by Hannan- Kalai- Aalai-Vemmpla. FTPL(E) first hallucinates fake day 0 with random cost vector co. where co Uni ))). Then in each time period f, picks the action that minimizes the cost of all days co. 4--1
at arg min (Co + C1 + + 1)
a
21

---

Algorithm 5 Follow the Perturbed Leader(FTPL(e)) [Kalai and Vempala, 2005]
Input: Sequence S= (c1.... or) arriving one by one over the time, E > O.
Sample Cy ~ [0, ! uniformly at random. for t 1, . do ae arg min El Cz.
The same argument used in Example 3.1 demonstrates that Algorithm sarially p-replicable. Now, describe the "Follow the Perturbed Leader with Block (FFPaess B). Algorithm 6). FTPLB first hallucinates a fake day with random cost vector cD. where cp [0, 2) uniformly at random. Then, picks the action that minimizes the cost of all days co, ". (B BBBB where the block size.
not adver-
a₂ arg min(co + c1 + Cm(t-1)/BB..a)
dEA
Algorithm Follow the Perturbed Leader with Block Updates (FTPLB(e, B))
Input: Sequence S = (c1.-... .r) arriving one by one over the time. >> 0 and block size B. Sample Co [0, ! uniformly random.
for t 1,
do if't 1 is multiple of B then
30
L
arg aE Ei=
31
32
else
// Stay with the previous action.
33
ag f 0;-1-
// this is equivalent to having = argmin aE EBB0-1/ a a
Remark D.1. In each step when is a transition point, FLLB pretends that the cumulative cost vector is 9t-1 that is the unique grid point inside the cube C1a-1 + [0, 1/e)". Due to the random offset p of the grid considered in FLLB, 9t-1 uniformly distributed inside this cube. Furthermore, FTPLB, also pretends the cumulative cost vector is C1:-1 + where co ~ (1o,)(()/))))) 1/e)"), and therefore has the same distribution as gt-1. This implies, FLLB and FTPLB have the same expected cost.
In order to bound the regret of Algorithm 6, first show the following lemma holds. Lemma D.2. First, we show that the non-implementable "Be the Leader" (BTL.) algorithm of picking
= arg min(c1 + .... c,,
aEA
has zero (or negative) regret:
(c1,a1) + (C2, 02) + ..... + (CT, aT) S (CI, aT) + (02, aT) + ..... (CT,aT).
Proof. We prove this by induction on T.
Base case: For T the left-hand side and right-hand side equal.
General case: By induction, we can assume:
(c1, .,) + (C2, 02) + ..... (cT-1,eT-1) & (ci + ,CT-1, 11)
We also know by definition of that:
(cr c2 cr- 1,-1,ar aT (cr +... + CT aT).
Putting these together, and adding (er, wT) to both sides, yields the theorem.
it is not implementable since assumes at time the algorithm knows the cost vector before picking action de-
22

---

c
CB[ 1/81-188/
00
C3
Figure 2: An illustration of the FTPLB algorithm. The blue and red boxes corresponding to FTPLB and BTPL respectively.
Theorem 3.3 (Regret Guarantee of FTPLB). Assume the maximum & length of any cost vector C C is 1, and the & diameter of the action set A is D. co Unif([0, 1/el") then the expected regret FTPLB(e, B) in T steps satisfies:
E [R[eg] & D(BET 1/8)
setting 1/(VBT) gives expected regret most D BT.
Proof of Theorem 3.3. We consider another non con-implementable algorithm BTPL and argue that the expected cost paid by FTPLB at time t is close to the expected cost paid by BTPL at time t. BTPL arg min Σ/= a Here, similar to BTL, BTPL assumes knowledge of cost vector C₁ before choosing a₂ which infeasible. Moreover, we demonstrate that the expected cost of BTPL is close to BTL, and since BTL has zero (or negative) regret, we can upper bound the regret of FTPL.
takes the action
FTPLB is choosing its objective function a; = arg min.min..... E ()/B a-c; uniformly at random from a box of side-length 1/s with corner at c₁ + +... CB(c-1/BJ- BTPL is choosing its objective function uniformly random from box of side-length 1/5 with corner at ei .4, (Figure 2). We call these boxes Box FTPLB and BTPL respectively. These boxes each have volume V = (1/e)". Their bottom corners differ by the sum of vector CB[t-1/B]]
, each of l length most 1, and therefore in total differing by an & length at most B. As result, the intersection of the boxes has volume at least (1/e)" B(1/s)=-1 V(1 Bs).
This implies that for some < Be, we can view FTPLB as with probability 1 - choosing its objective function uniformly at random from / = Box FTXLE FTPLB n Box BTPL and with probability choosing its objective function uniformly at random from F = Box, FTPLB \ Box BTPL Similarly, view BTPL with probability p choosing its objective uniformly random from I, and with probability p choosing its objective function uniformly random from B Box@TPL az)
Box FTPLB Thus, if a Ee-]
arg min (c, a)}, aF Ee-F ac) | az arg min (c, a}}. and ag = E.-B (Ct,, 0,) a; = arg min A (c, a)}. then the expected cost of FTPLB time is (1 p)ay par and the expected cost of BTPL time is (1 (1-p)a- pag-
Now, we prove that lar agl S D, then the difference in expected cost between FTPL and BTPL at time is at most pla= an < BDs. Summing over all times t we get difference at most BDTs. To prove that ja a < D, note that for any c E C and a, a' E A. we have (c,a) (c, d') < D. This follows from the fact that the foo length of is at most 1 (this follows from the assumption that E length of is at most 1) and the & diameter of A D. Consequently, JaF agl < D.
BTPL and at BTL show the actions taken by BTPL and BTL time respectively. Let a BTL be the optimal action hindsight. For any vector co. by Lemma D.2, we have
Next, we bound the difference between the cost of BTPL and BTL. Let a
(Co, 00 BTPL) + + (CT. STPL) < ((co + ... CT), cT) @
BTPL < ((co + ... + CT), TT
23

---

Therefore,
BTL + (co, 4T BTPLY - ((c1 + ... CT), aT ac . + +... (CT, aT
BTL
dg
BTPL)
(1)
The left-hand side of Equation (1) the cost of BTPL. The first term on the right-hand side of Equa- tion (1) is the cost of the optimal action in hindsight. Therefore, the expected regret of BTPL is at
BTL most (co, of - ap ). Since has l diameter at most D, and each coordinate of co has
expected value 1/e. therefore [[(co, of - ab T - D/s.
This implies the regret of FTPL is most BDT' + D/c and the proof is complete.
D.2 Proof of Theorem 3.1
Now are ready to analyze regret and replicability guarantees of FLLB Theorem 3.1 (Regret and Replicability Guarantees of FLLB). FLLB E B) is adversarially p-
2/3
replicable and achieves regret /p 1/3), when B 21 [l//Boo((////)+22
and
1 and D is the & diameter of the action set A. VBT
Proof. First, we bound the probability of non-replicability. Recall that Algorithm 1 chooses a uni- formly random grid of spacing 1/E. In each transition f, if is transition point {B 1, 2, + Algorithm 1 picks the action that minimizes the total cost, pretending the cumulative cost vector 9t-1, where 9t-1 is grid point that lies inside c1:-1 - [o, 1/E)" (see Figure 1). Consider two different trajectories C1, ... and c, c..-.., ce where each c2 c4 ~ D; First, we bound the probability that ft-1 1 + -.-1 as follows. This event happens iff the grid point in Cta-1 + [0, [) is not in c=a-2 + [0, _ First, we argue that for any v E R", the cubes [0. 1/s]" and v v 00, 1/E]" overlap in at least
.. 1,
el, (v)) fraction. Take random point x E 1/E]". If $ v [0, 1/E)/ then for some i, I; + [0, 1/E] which happens with probability at most (1;) for any particular
By the union bound, we are done. Thus in order to upper bound the probability that gt # g.
we need to upper bound the & distance between cumulative cost vectors Ci. and Ct. For any
< 1 S T:
Pr -ch) pVnT
(2)
< <exp(- <exp(_(p-20)
(p (p- 222))m (p-)-m
< Pr (4(c - Ggr) 2 pvnt
(3)
2
P
<
(4)
exp(nlog(2T/p))
2T
2T
where Equation (3) holds by Lemma C.I, and Equation (4) holds by setting p / 2ooo (TT) p) +
This implies that the probability of non-replicability at transition point L, i.e. 9t- + 9 1. is at most 27 + =pynnf. By taking union bound over all the transition points t = [B 2B +1, 1,...
the total probability of non-replicability is most (6e + epv/''' B Consequently, we can set values of B, such that the probability of non-replicability over all the time-steps is at most
P
+ spvnnt)
T
<
27
B
in order to achieve this, it suffices to have:
3/2
p/2
B
or equivalently:
Bp
E
2p/n2
24

---

Additionally, in order to minimize regret by Theorem 3.3, we need to set E
1 /BT
Now by setting
Bp
1
2p/n233/2
/BT
it implies that
2/3 2( Loog(TT/pp) vnd
B
=0(T4
P
Finally, plugging in the value of B in Theorem 3.3, gives a regret bound ODD BT) O p 1/33).
E
Missing Proofs of Section (Proof of Theorem 4.1)
In order to prove Theorem 4.1, first, we bound the regret of FTPLB" B). Theorem E.1. The expected regret of FTPLB* (c, B) in T steps satisfies:
lnn
E| E|Reg(FTPLB') 2 =BT +
setting
In gives expected regret most v /BT Inn.
In order to prove Theorem E.1, first, consider the non-implementable algorithm "Be the Perturbed Leader" (BTPL) that takes action di BTPL arg min Ei=1 (a( Xa in each round has small regret. non-inplementable since assumes knowledge of the cost vector of the current step before taking action in the current period.
Lemma E.2. For any expert a E A.
E E[Cost(BTPL)] s Cost(a) E Xx,]
"EAA
Proof. We assume time and assume ca(a) Xa for simplicity of notation. Then it is the case that:
d
BTPL
= arg min
(a(a)
acA
2=0
Let a be the action taken by the non- -on-implementable "Be the Leader" algorithm that is similar to BTPL but does not take into account the noise on each expert:
a
BTL
arg min AEA
ca(a)
1=1
Then BBTL is the optimal action in hindsight given the true cost sequence c1.... For any vector co. we have:
T
Σ ca
BTPL
Σ
BTPL
Σ
BTL ca
(5)
1=0
1=0
where the first inequality exhibits that BTPL has zero or negative regret on the cost sequence co.... cr and is proved similar to Lemma D.2. The second inequality holds since a is the optimal action in hindsight given cost sequence co, C1, Cr. Therefore,
T
(a BTPL &
Σ 1=1
BTL (a
BTL + co(a BTL) - ca BTPL)
(6)
The left-hand side of Equation (6) is the cost of BTPL. The first term the right-hand side is the cost of the optimal action in hindsight. Term oo (a BTL) co (ag (TPL)) S max X,. Therefore, the expected regret of BTPL is most E|max X.) and the proof is complete.
D
25

---

The following lemma shows that the cost paid by FTPLB* at time t is close to the cost paid by BTPL at time t. Let af FTPLB denote the action taken by FTPLB* at time t, then a FTPLLS arg min DEA (1-01)/B Os ca(a) Xa.
Lemma E.3. For any time 1 its T, FTPLB" # dPTPL] eB.
Proof. We prove that for any a' E A. Pria, BTPL = a" of FTPLLB" = =a1 2 1 - - and this will imply lemma. This is the case since
Pr(a ETPLB" = aai BTPL]
Σ
Pria
PTPL
BTPL = | FTPPLB" = a²) Pr(a, FTPLB* = a")
a'EA
and the above would imply the RHS is at least EB.
First, define some notations. For any E A, let Ua 2i=1
BL(-1))BB1 ca(a), and d
By G((a). Now, of FTPPLB' a" implies that:
Un Xa S Up Xa
Therefore for all E A:
Xa. 2 Ua - Up + XXa
Similarly, we have a BTPL a" for all A:
Na 2 U. - Uo + Xa + (Va- vaa)
Next, condition on Xa za for all # a*. Given these To values, define V = maX Ta Up and v = maXaşa" Va- - Va. since all the c.) values are at most 1, U S B. Then it is the case that:
FTPLB" = a", Xa = Za, a + a²) 2 Pr [X.. 2 + u U X 8TPL a" a Pr a X.
U-
X,-
where the probability is only over the randomness in X, since that is the only random variable remaining. By the memorylessness property of geometric random variables, we show the RHS is (1 -) First, we remind the reader of the memorylessness property of random variables:
Fact E.4 (Memorylessness of Geometric Random Variables). Let X Geo(p), then for any pa- rameter k we have:
Pr[X 2 1: ++11 = (1-p)
2 k]
Pr|X 2 k]
This is the case since X ~ Geo(p) implies Pr[X- 2 f = (1 (1- as the first 1 experiments must fail.
Therefore, we get that for any conditioning of X Fa, for a + a", we have:
Pr [a@TPL a") of FTPLB' a", X Fay + a") (1 e) N (1 EB)
which implies:
BTPL a" | a Pr(a
FTPLBB =a' 1
this yields the lemma.
Now we are ready to prove Theorem E.I.
Proof of Theorem E.I. First, we argue that TB(Cost(FTPLB') [[[oos(BBTPL) BT.
Cost(FTPLB") - Cost(BTPL)
(a FTPLB') ca(a.TPL)
1=1
For any 1 1.1. T, we see that et (oTTLL" - < 1, and is indeed 0 if of TTPLB Therefore:
a, BTPL
T
E[Cost(FTPLB') - E|Cost(BTPL)]
Pr(a
FTPLB" + a BTPL < BBT
26

---

where the last inequality holds by Lemma E.3.
By Lemma E.2, know that for any expert a E A::
E[Cost(BTPL)] < Cost(a) + E[max Xal
We can bound the expectation of the maximum of geometric random variables using the following fact:
Fact E.5 (Expectation of maximum of geometric random variables). Let X1, Xn Geo(p) be idd geometric random variables. Then, M[max; X;] 1 + Ha, where Hn is the th Harmonic number.
which implies that for any expert A:
E[Cost(BTPL)) < Cost(a) + Inn
Finally, for any expert E A:
E[Cost(FTPLB")] < Cost(a) +BT + Inn
8
Now we are ready to prove Theorem 4.1. Theorem 4.1 (Regret and Replicability Guarantees of FTPLB"), FTPLB* B) is adversarially
2/3
p-replicable and achieves regret Ö(73/6 In In 5/6 (n)pp when B
8/
locisTie)
log
+1) In(n]
and E
In BT
Proof. First, we bound the probability of non-replicability. Consider two different trajectories C1," Gr and c1, ee where each G, of D,. For each E A, let function fa x. where fa(c1,
I Ca()) Then for each a A, fa satisfies the bounded difference prop- E C., since assume the loo of all cost vectors at most 1(this is the case since we assume cost each expert at each time / [0, 1)), we have:
,4)==
erty. For all i E [t] and all E C1,e2 C2.
sup Ifa Valc,," ... CC-1, C-1, ,.)) - Salei, ". ,G-1, 2, "H ,4) dec. Hence by McDiarmid's inequality (see Theorem B.2),
-252
Pr f (cI. (cI....,,c)) ce) - [fa (cI...., cx)l > e|
< 2exp
41
Therefore, for each expert A:
Pr [BalCu)) (Ba(cuu)-B(aaaeee [[a 2 pVTTinn s Pr (fta(ou)) - [fa(c])]] [[((ca]) 2 pytinn
-p²Inn
2
< exxp
nd /2
By triangle's inequality and union bound:
(Ia(an)) -al(ca)) 2 2pvTTum
4
Pr
12
27

---

By taking the union bound over all experts in A::
Pr Ha E A: fa(c1s) fa((x:t 2 TppVinn
P
(8)
12 21
where the last inequality holds when p V log(8T/p) log
+ 1).
At step f, where ž is transition point, i.e. t = {B + 1, + ................................ ,..... let af 4TTPLB" denote the action taken by FTPLB* given cost sequence "I. cr- and by DFTPLB" denote the action taken by FTPLB* given cost sequence <1, ".. ,.-11 prove that for any a* E A.
Pr Pr
FTPLB" a² a, TTTPLB" =a121-
21 1-1--epv1 4 Tinn
This would imply:
Pr(a
FTPLB" =b.TPLB -FFPLLB
Σ
Pr =a" d
FTPLB"
a") Pr(a:
FTPLB =a"] 2 1-45pv Thnn
Now, df
FTPLB" = aa implies that:
(cu- -xa- S fa(et=11) Xa
Therefore for all a E A:
Xa- 2 fa- (c1:t-1 fa (c1=-1) Xa
Now Xa- 2 fa (c1a-1) (a(cn:11) Xa + 4p ni and for all experts a E A. (f((aa-1) falda-1)1 < 2pv rlnn then it is the case that:
Xa 2 fa (c(.0-) - fa((1111) + Xa
and therefore 1FTPLB" = a
Now, we get that for any conditioning of Xa Fa. for a * a", by the memorylessness property of geometric random variables we have:
Pr b FTTPBL a a
FTPLB" =x Da a + a²1 2 (1 -) LpVT 2 (1 4Epv Thnn
which implies:
FTPLB" =a"] 4epyT'nn P =a" |1,
This implies that the probability of non-replicability 4epy/Tln By taking union bound over all the transition points = [B 1,2B 1,... the total probability of non-replicability is at most (2t + SepyT'nui values of B, such that probability non-replicability over all the time-steps at most p.
transition point t, at most 27 +
Consequently, we can set
P 2T
T
S
B
in order to achieve this, it suffices to have:
4spy/n In 3/2
p/2
B
or equivalently:
Bp
8
SpvInn79/2
Additionally, in order to minimize regret by Theorem E.I, we need to set setting
Now by
BT
Bp
Inn
8pvInn/882
BT
28

---

it implies that
B 8 8
loR(8T/p) log + 1) In(n)T) 2/3
O (0 2/ (n)(1/)))))
Finally, plugging in the value of B in Theorem E.I, gives regret bound of O B1v/Tll O(T5/6 In (n)p
F
Missing Proofs of Section 5
Algorithm General framework for converting a learning algorithm ALG to an adversarially p-replicable algorithm ALGezt when ALGint gets bounded & cost vector input
Input: Sequence = "Ci.....or, arriving one by one over the time. > and block size B and learning algorithm ALG.
34 Let 01 be a random action picked from A. for f. 1, .,..,,,.. do
36
if't 1 is multiple of B and > 1 then
// th time block starts with = (t- 1)/B
37
Sample Pt.Pl ~ [0, 1)mh uniformly random.
Let G - {pt + 1z E z"}.
38
39
Let G" + [p/ + x E }
9:-1 + Gn (c::11 + - 1 1
)m)
40
26 2c
41
6 + G' n 11--11 + 26 28
42
a: ALG
B+ (9 1
43
else
// Stay with the previous action.
44
Or t- a=11
In order prove Theorem 5.1, first prove the following lemma holds which bounds the regret of Algorithm 7.
Lemma F1. Assume that that the cost function Cost(a, e) is linear in c, i.e. Cost(a, 02)
Cost(a, c1) + Cost(a, oz). In Algorithm 7, the regret of ALG over T timesteps is at most:
E[[egr (ALG S (B + 2m ((AL//i
Proof. First, define the following sequences: S {ci,...,oT) S {gn, (g2n g'3)," (g ())) S $/(B + 2n/e). S is the sequence that we feed into ALG Let Rime denote the internal randomness of AL and Rest be the randomness ALG over random offsets Pt, pt each transition point Let Cost(ALG. define the cost of running ALG on sequence S which is equal to Cost(ALG, S) = E, cost(af ,S,), where aALG is the ith action taken by ALG, and (oAL( ,S)) is the incurred cost when action ALG is chosen and the cost vector is St.
By the regret guarantees of ALG over T/B timesteps, it is the case that for any fixed sequence X and action E A:
E [Cost(ALGimt, X)) < Cost(a, X) Regr B (ALG Runt
(9)
and therefore:
E Ruse.Rest
[Cost(ALG $1 < E [Cost(a, 55) RegT (ALGins)
(10)
Rext
29

---

Note that S is probabilistic sequence that depends on Rext. Moreover, Cost(ALGant: 5) is random variable that depends on the randomness of Rint and the random sequence S. Since $ is scaled version of S, then:
[Cost(ALGint:: S)] = (B + 2n/e) Runs Rext
E
[Cost(ALGint, S)]
(11)
Rene Rext
Next, bound the total cost of ALGezt the true cost sequence S. WLOG we assume T is multiple of B, if not, we add zero cost vectors to S to make T a multiple of B. Then:
T/B Σ
[Cost(ALGezt: 5)]
E Rene,Rest
[Cost(aus C(u (l-11)BuB))
(12)
Rint,Reat
where in Equation (12), an is the action taken by ALG in the w-th block, and B) is the cumulative cost vector within the time-interval ((u - 1)B, uBJ. Cost(ALG S) is a random variable that depends Rint and Reat. This is the case since the action a. that is chosen by AL Reas.
depends on Rint and the probabilistic rounded cost vector that fed into AnG which depends on
Furthermore:
T/B Σ
E Rene,Rext
[Cost(ALGint: $)
E Rene.
[Cost(aur JuB 1)8)
(13)
T/B
T/B
Σ
E Rint Rest
(ost((au: JuB K ()n-1))(aaul] = Σ
E [Cost(au; E
Ignn 1(--1) (a
))}
Rint
Rexit
(14)
T/B Σ
T/B Σ
(as CuB Ca-1)B)]
E Runt
(Cost(au: ([-
(15)
Rint
where Equation (14) holds by using the linearity of the cost function, and Equation (15) holds using the fact that a, is independent of both Gu-1)B and JuB. This is the case since u = (t- 1)/B and at transition point a, depends 9t-1 and 9 implying that a, depends on 9)x-1)B and 2 (and not 1(=-1) and guB). Putting together Equations (12) and (15) implies that:
E
(oot((AL S)]
E Rint,
[Cost(ALGentt S)]
(16)
Rine. Raxt
Now, combining Equations (11) and (16) implies:
E
[Cost(ALGeztt, S)] =(B 2n/8) E. Rine.
[Cost(ALGint, S)]
(17)
Rine, Rezi
Now, for any action
A, bound ER... [Cost(a, S)] follows:
[Cost(a, (1/(B 2n/E)) E Reod
[Cost(a, Š)]
(18)
Rex!
T/B
= =1/(B + 2n/e))
Σ
[Cost(a, JuB 11D1 Raxe
E
(19)
==1
T/B
= + ((BB+2n/e))
Σ
Cost(a, C(u ((u-1)
(20)
(I/(B 2 (1.))
(21)
=11/BB + Costa)
(22)
30

---

Now, combining Equations (10), (17) and (22) implies that for any action E A:
ERi Rezt (Cost(ALC MaLLGGart Geat: S)]
Cost(a, S)
+ Regr/B Re@r/B((LGim)) (ALGint)
++ 2n/E
B 2n/E
which implies that for any sequence S and any action E A::
[Cost(ALGGzzt, S)] - Cost(a, S) + (B + 2n/s) ((LLG))
Rine,Reat
and the proof is complete.
Theorem 5.1 (Regret and Replicability Guarantees of Algorithm 7). Let p > be parameter, and assume that the cost function Cost(a, c) is linear in c, ie., Cost(a, C2) = Cost(a, c1) Cost(a, C2).
Suppose for two different input trajectories c,,".", CT and dı,... dr where for each time-step I, Ct, de Di. for each time step the E distance between cıa and d is at most with probability at least -. Then, Algorithm is adversarially p-replicable and achieves cumulative regret O / (ALGGsm))
when 7 is most eB
8nmT and = 22n/B.
27
Proof of Theorem 5.1. First, we argue about the replicability. Here we assume that given two dif- ferent cost sequences C1,- ... .T and d1. dr, where for each timestep Cts de are drawn from the same distribution, for each time step I, the & distance between C1 and d1at is at most m with probability least 1 y
Let 9.9' denote the sequence of grid points selected given the cost sequence (c1. ".......a. ..r) and q, o' denote the sequence of grid points selected given the cost sequence [di,... .d... First, we bound the probability of the event that Jt-1 # ft-1- This event happens iff the grid point in Cla-1 + [0, = is not in d1:t-1 + [0, 2)2² We argue that for any R the cubes [0. 1/e]* and + 1/e]" overlap in at least (1 2t1 (r)) fraction. Take random point x E [0. 1 /e)" If x & gu + [0, 1/8) then for
some i, & + [0, 1/e) which happens with probability at most el (e:) for any particular i. By the union bound, we are done.
This implies the probability of the event that It-1 + @t-1 at transition point f, i.c. t -- 1 is multiple of B, is at most 7 + em. Similarly, the probability that -.-1- B 4-1- at most Y em. By taking union bound over all the transition points {B 1,2 + +,,... the total probability of non-replicability is at most 2(7 em)? T- Consequently, we can set values of B, such that the probability of non-replicability over all the time-steps at most p:
T
2( + Em)
B
Since 7 S 4T we need to set of Algorithm 7 is (B- + 2n/e)Ron Reg B (inG)nt), therefore, in order to minimize the regret, we need
eB
25mT B
2/2. Now, we consider the regret. By Lemma F.I, the regret
set B 2n/e, which implies that p
4emT B
8mmT
Consequently, B
SnmT and the
regret of Algorithm 7 is 2BRegry n (ALG
F. Proof of Corollary 5.2
Proof. By Lemma C.I. for two different trajectories cI.... cc and di.... de of n-dimensional vectors where for each i, c;, de ~ D; we can bound the & distance of the cumulative costs these two trajectories follows:
S Pr (c( - dra) > pVntt < exp (- (p - 2)
Pr [f(aa dr.)) pvnT
(23)
2
where the right hand side at most IT when p 2 / 2log +2, Now, we can apply Theorem 5.1, where m = (v
2 2log 4T/P +2) VnI by Equation (23). In Algorithm 7, we use FTPL algorithm as the internal algorithm for T/ timesteps that gives regret bound RegALG.... O(D DDV/T/B) TTB).. By Theo-
rem 1, the regret of Algorithm is Q ((BRegry/n 1o (ALG,,)) when B is set as V SmnT Plugging in
the values of m. B and RegALG... gives total cumulative regret of Ö(DT 7/ /8 n 1/4).
D
31

---

G General framework when the internal algorithm takes as input bounded Lo cost vectors
In this section, we consider a setting where the internal algorithm AL takes as input a sequence of bounded &oe cost vectors. We provide a general framework in Algorithm 8 that converts the in- ternal algorithm to an adversarially p-replicable algorithm ALGezt with bounded regret. The frame- work is similar Algorithm 7, but with a different normalizing step. Similar Algorithm ff -1 is multiple of the block size B. it picks n-dimensional grid with spacing 1/c where is given as input, and a random offset Pt ~ [0, 1/e)". where n is the dimension of the space. Then considers the cube -1 + [0, 1/5)". where Clsb = Σi= Ci and picks the unique grid points 9t-1 inside this cube. Furthermore, for fresh random offset p 1/e)/ it picks new n-diimensional grid with spacing 1/s and offset pi. Then, it considers the cube C1a-1-B + 1/E)" and picks the unique grid point -'-1- 1--1-8 inside this cube. Then, it gives B+275 (9:-1 9 12-1-B) B) the input argument to the algorithm AL intt The normalizing factor makes sure that the input given to AL Gint has &oo cost at most 1. Then AL plays the action returned by ALG for the next B timesteps. We derive regret and replicability guarantees for Algorithm in Theorem G.2. In order to prove Theorem G.2, first we bound the regret of Algorithm 8 in Lemma G.I. The steps of proving this lemma are similar to Lemma 1,1, with taking into account the different normalizing factor.
Algorithm 8 General framework for converting a learning algorithm ALG to an adversarially p-replicable algorithm AL when ALG gets bounded foo cost vector as input
Input: Sequence S = [c1, (CT) arriving one by one over the time. & > 0 and block size B and regret minimization algorithm ALG.
48
Let a1 be a random expert picked from A. ,,' do
for t:
47
if t 1 is multiple of B and > 1 then
Sample Pt.pl ~ [0, 1)m uniformly at random.
48
49
Let G + {pt + = 2 E 2"). Let G" +- (p/- + { = 2").
50
9t-1 +- Gn (1:111 + 1 2z 1
52
8-1-B G' (1:1118B + ---
28
1 1 11n)
53
a: ALGin
B+? (gt-1 - -
else
// Stay with the previous action.
55
a:-1
Lemma G.1. Assume that that the cost function Cost(a, c) is linear in e, i.e., Cost(a, e + 02)
Cost(a, (1) + Cost(a, 02). In Algorithm 8, the regret of ALG over T timesteps is most:
E[Regr (ALGGz)) < (B + 2/5 Regt/ (ALGint)
Proof. First, we define the following sequences: S = (c.,...,cch S [gB. (92B o'b).... (JB[T/B] BB(TT/J-I))D S = S/(B + 2/e). S is the sequence that we feed into ALG Let Rins denote the internal randomness of ALG and Ress be the randomness of ALGezt over random offsets Pt. pl, at each transition point t. Let Cost(ALG, S) define the cost of running ALG on sequence which is equal to Cost(ALG, S) = Σ, cost(aALG (S),, where a ALG is the 7th action taken by ALG, and (aLG S.) is the incurred cost when action a. ALG is chosen and the cost vector is S,.
By the regret guarantees of ALG over T/B timesteps, it is the case that for any fixed sequence X and action E A:
E [Cost(ALGint, X]] < Cost(a, X) Regry B (ALGint)
(24)
Rint
and therefore:
E Rune.Rest
[Cost(ALG Š) < E [Cost(a, 5)] + Regt (ALGins)
(25)
Rext
32

---

Note that S is probabilisticc sequence that depends on Rext. Moreover, Cost(ALGant: 5) is random variable that depends on the randomness of Rint and the random sequence S. Since $ is scaled version of S, then:
[Cost(ALGint; 5)] (B 2/8)
R Rest
[Cost(ALGint: S)]
(26)
Rine Rext
Next, we bound the total cost of ALG on the true cost sequence S. WLOG we assume is multiple of B, if not, we add zero cost vectors to 5 to make T multiple of B. Then:
T/B Σ
[Cost(ALG S)] })]=
[Cost(au: (lu-1)B:BB).
(27)
Reit
Rent
where in Equation (27), Og is the action taken by ALG in the u-th block, and ((a-1)B:BB is the cumulative cost vector within the time-interval ((u B) uB). Cost(ALGest S) is a random variable that depends Rint and Rezt- This is the case since the action au that is chosen by iLG depends on Rint and the probabilistic rounded cost vector that is fed into ALG which depends on Reaar.
Furthermore:
T/B Σ
E Rina. Roxt
[Cost(ALGGma $)]
E Rinis u=1
[Cost(au: JuB Ku-1)8)]
(28)
T/B
Σ
E Rins, Rase
[Co guB)]
E Ruxt
[Cost(aus Ii Ku-1)
(29)
1=1
now using the fact that an independent both lu-1jB and JaB we have (note that a, depends on 9(a-1)B and (),))
(30)
T/B Σ
E Rins.Ren
[Cost(aas 1(a-1)
(31)
Putting together Equations (27) and (31) implies that:
E
[oost(ALGint-
$}]
E
|Cost(ALGGntt, S)]
(32)
Rine Rezt
Runi
Now, combining Equations (26) and (32) implies:
[Cost(ALGentt, S)] = (B+ E
(Cost(ALG 5)]
(33)
Rant Rext
Raxt
Now, for any action e A, we bound ER... ( [Cost(a, 5)] as follows:
[Cost(a, 5)] = (1/(B + 2/E)) E Ree!
[Cost(a, SD]
(34)
Resi
T/B
(1/(B+2/e))
Σ
E [Cost(a, JuB H(--)))) 1))] Rexe
(35)
u=1
T/B
= [L/(++2/4) Σ
Cost(a, ((o(a,,,u-1)BBuhl)
(36)
==1
(//os C1:))
(37)
(1/(B+2/) (oss)
(38)
33

---

Now, combining Equations (25), (33) and (38) implies that for any action E A:
En Rezt [Cost(ALGente S)]
Cost( S)
+ Regt/ (ALG
B 2/s
B + 2/c
which implies that for any sequence S and any action a E A::
[Cost(ALGeats S)] I Cost(a, S) + (B + 2/=) R (ALG
Reme: Rest
and the proof is complete.
Theorem G.2. (Regret and Replicability Guarantees of Algorithm 8) Let p 0 be parameter, and assume that the cost function Cost(a, c) is linear in c, iee, Cost(a, C1 + (2) Cost(a, (1) + Cost(a, 02). Suppose for different trajectories c1.".. CT and di,... dr where for each time- step i, ct: de ~ Di we can prove that for each time step t, the & distance between Ciat and dı is at most with probability at least 1 7.. Then, Algorithm 8 is adversarially p-replicable and achieves cumulative regret Q [ReeTT B (ALGmn)) when Y is most IT B
pB
==
8m1T and B/B.
Proof of Theorem G.2. First, we argue about the replicability. Here we assume that given two dif- ferent cost sequences C1, ... Cr and d1, ... dr, where for each timestep t, ct, di are drawn from the same distribution, for each time step the & distance between C1: and d1:t most m with probability at least 1 y.
Let 9.g' denote the sequence of grid points selected given the cost sequence fci..... .C) and q,9' denote the sequence of grid points selected given the cost sequence [di,... ,....,,777 drr.. First, we bound the probability of the event that gt-1 * Qt This event happens iff the grid point in C12-1 + [0, 1
not d1:t-1 [0, 11 We argue that for any e R" the cubes [0. 1/e]" and v + 1/e| overlap in at least (1 - =l1(v)) (v)) fraction. Take random point z E [0, 1/e]". . If x & + [0, 1/E]", then for some i, H; & 0 + [0, 1/e] which happens with probability most el (w;) for any particular By the union bound, we are done.
This implies the probability of the event that Jt-1 + 9t-1 transition point i.e. ( 1 is multiple of B, is at most 7 + sm. Similarly, the probability that - * k-1-B is at most + Em. By taking union bound over all the transition points = {B + 1,2B + +,.... } the total probability of non-replicability is at most 2(7 + Em) T B- Consequently, we can set values B, such that the probability of non-replicability over all the time-steps most p:
T
2(T + em)
Since < eB 47 we need to set of Algorithm 8 is (B + RegTy (mL)) therefore, in order minimize the regret, need
2amT 2/2. Now, we consider the regret. By Lemma G.1, the regret
B
to set = 2/e, which implies that p = 2=2m² mT = 8mT of Algorithm 8 2BRegr (ALG
Consequently, B V 'mmT and the regret
B²
G.1 Application of Algorithm 8 to the experts problem
Corollary G.3. In the experts problem setting, Algorithm 8 achieves adversarial p-replicability and p-reperiiiialpppppiiillillllll
cumulative regres (T 1/8 1/8pp -1/4).
Proof. By Lemma C.I, for two different trajectories cI...., and di.-.. de of n-dimensional vectors where for each c;, de D; we can bound the & distance of the cumulative costs of these two trajectories as follows:
I Pr [cca - dra) > pVnt < exp (- (p
(_ 2)
Pr [a(cca - dr.)) > pvnT
(39)
2
where the right hand side is at most & when p 2 2ng 4T/0
+2. Now, we can apply Theorem G.2
a
where m = (v
4T/p + 2) Vni by Equation (39). Algorithm 7, we use FTPL algorithm
34

---

as the internal algorithm for T/B timesteps that gives regret bound RegALG.N. = O
OV-- Flog
By Theorem G.2, the regret is 2 2BReeT/B ( (ALGina) when B is set as SmT Plugging in the values
of m, and RegALG... gives total cumulative regret of O17 n/ 1114)
H iid-Repiiaability in the Experts Setting
In this setting we have experts, say A = ..].. At each time step we get cost profile: = (a (1), a (2,....,,c. (x))) E [0, 1J" with |cr < 1. We want our algorithm to be iid p-replicable with worst case regret K. Recalling from Section 2, this entails:
1. Worst-Case Regret) For any sequence of costs S (c1, .,...,,.. CT) the maximum ex- pected regret (over internal randomness R) suffered by the online algorithm is at most K, ie,
Reg (, R)] K,
n
where Reg(S, R) denotes the regret of the algorithm on the sequence and using internal randomness R.
2. (Replicability) Let S1 be two independent cost vectors of length T sampled iid from DST, where 'D is unknown cost distribution over [0, 1j". Further, let R be the internal randomness of the algorithm. Then,
Pr [ALG(S), R) ALG(S,, R)) 2 S1
The optimal situation would be have iid p-replicable algorithm with worst regret O(VTlnn / f(1/p)) where f is mildly growing function. It turns that with = we require f(1/p) Z 1/p. This is because we can embed the coin problem from Impagliazzo al. [2022] into an instance of regret minimization with n 2. The coin problem is follows: given T iid samples from a coin whose bias is promised to be either 1/2 + 7 or 1/2 - - (for some E [o, 1/2l), we need to identify which is the case with probability at least 1-6 8 for some 5 < 1/16, and while being replicable with probability at least 1 - p. In such case from Impagliazzo et al.
[2022] we have p 2 Ω [VT
We can embed the coin problem in the experts setting by letting K/T (K is the regret upper bound) (see Theorem I.2 for more details). Hence, we get that T
K Ω
It turns out that can match this bound up to logarithmic factors. Specifically, we design iid p-replicable algorithm (Algorithm 9) with
K s o ( (log (oggogg(T)) x log
log log(T) x T[n(n)
Now, we turn explaining the ideas behind Algorithm 9, In the discussion below, we ignore various logarithmic factors such as vlog n and think of p >> O as small fixed constant.
Performance under iid cost sequence: Let us first focus achieving low regret when promised that the cost sequence S = (C1: C2....... CT) is sampled from D for some unknown distribution D over [0, 1 We can always use standard regret minimizing algorithm for this purpose such as FTPL: however, such an algorithm will not satisfy the replicability properties. Hence, we need to adopt different approach.
The idea is that if we observe the experts for the first (()) VT time steps, we have a good approximation of the expected cost of each expert E A, ie, fla == E [c(a),, to within an accuracy
c
of 7-111 using the empirical average Σ/ (a))),,))) (The standard deviation of the empirical average is of the order T-1/4.) During these times we always select fixed expert, say (1) 1. Further, we accrue regret of at most /T during this block of (1) steps.
35

---

Now, using our estimates the Paa we select expert a arg min .EA E5=1 (z(a) for the next ( T time steps. During these T time steps, compared to expert A, accrue regret of at most roughly T-1/4 T = T1/2; this is because Ma(2) Pa X T 1/4
T-1/1
Now, we re-update estimates of Ma 's using the empirical averages and our accuracy is roughly T-3/88 This allows us to select expert a!3) arg migmii,... ne 1 cy(a) for the next block of T7/8 time steps while only accruing roughly vT more in regret. Continuing in this fashion we end up using roughly log log(T) blocks and hence the regret accrued the end of T steps is at most Ollog log(T)TT).
But how do we make the above algorithu replicable? The above strategy unfortunately repli- Pa- In this case al2) is equally likely to be any of the n experts. To overcome the above hurdle we add some noise to each ex- pert at the end of each block. Specifically, after time (("), when deciding expert al2), we add GEo(E Rs T-1/1) noise to each expert independently. The added noise helps us ensure that two different samples of cI,...,,,,00 CI,1) from D&L choose the same a with high probability: we expect that with high probability Va E A Σ cj(a) E (Ma + T-1/4)Z(() Further, let (2) arg m La Xa. then, due to the memorylessness of the Geometric Distribution (see Theorem H.1 for more details), have that with probability at least 1/4
cable. To see this consider the situation when l41 #2
a.
min La No (EA\(o!))
(Ha0) - X 1/4
In such a case (2) = (2) To ensure replicability throughout = 1,..., T, we add appropriate Geometric noise each expert the end of each block.
Worst-Case Regret: Given the above discussion know that with high probability the regret of the algorithm never crosses log log((")) if the cost sequence S (Ci,..., er) is sampled from D&T
Hence, to achieve a worst-case regret bound, we switch to a usual regret minimizing algorithm such as FTPL (with regret upper bound ss vT), whenever the regret of the algorithm at the current time steps exceeds roughly log log(T) Now, clearly on any cost sequence S = (ci,-.., .r) we can never exceed regret of roughly Ollog log(T)
Below formalize the above discussion into Algorithm 9 and Theorem H.I.
36

---

Algorithm 9 Follow the Perturbed Leader with varying Noise & Block Lengths
Input:
Cost sequence (C1s..., CT) arriving one by one over time and replicability parameter p Result: iid p-replicable algorithm with worst case regret K.
56 t t 0 t VIn(8n log (o))()))); f
8log // some useful parameters
57 K - 1000 x (1 x (log lTg(? log(n log log(TT) VT)
for: 1,...,
/" Block begins
7,(0) 71-2" this is the length of block
60
r= then
a =1 // select expert 1 for the first block
61
62
else
63
c(0)
2nd // this noise parameter used for Block
64
Ya A sample X Geo(=(9)
a arg min E)=1s(()) xx(
67
for 1, ,.... Li do
68
t + ++1
Ot f (1) select the same expert throughout the block
69
ift T Reg, 2 K - 2/Tlnn then
71
go to Algorithm 9
if T then
Follow usual FTPL with noise GEo(E //nn/T) for the remaining time steps
Theorem H.1 (lid-replicable algorithm for experts). Algorithm 9 is iid p-replicable and achieves regret
( (log log(T))² log
n log log()
VTT
Proof. Regret analysis: Clearly, the regret Algorithm can never be more that K because as soon In In which in expectation suffers an additional regret of 2/Tlnn.
as Reg, 2 K 2
we switch the usual FTPL with geometric noise Geo(E = / /ln/TT),
Replicability analysis: First, make few observations that are helpful to show the replicability property of Algorithm 9. Let p()) Σ (f), ic, the end of block and μ4, Ex-a(c(a)], We analyze the probability of various events below and the probability should be thought of as over the cost sequence 5 Der and internal randomness R.
1.
The number blocks used by Algorithm 9 at Algorithm 9, say B, is at most log log(T) -1
This is because
Loo (T) + Liog log(T) = 2 2 log log
+ 1-122 log(7)
v2 + > T.
2
2. Recall t Vn((8 log (Tg(g)))) Let (2)) be the event that E/ Cg(a) & Imt p(0)
av p.) Hence, if FE(() does not take place then the cumulative cost of expert a when block ends, ie, at time t = p(i), is within av (P) of the expected cost of expert Here, vP, can be thought of as proxy for the standard deviation of the cumulative cost up till P()),
By McDiarmid's inequality (see Theorem B.2), have Pr[E. < exx( Thus,
Pr
(4)
< 2nBexp(-2od S p/8.
asAAA
37

---

3. Recall that e(t)
20 I5 where
For i, let d.
llog (T)
arg min (HaP P(i-1) - Xa Further, let p(() denote the event that there exists an a E A such that
Mg P(i-1)
( a Ma Pli - x 20 P(--1)
Here, we should think of a as the expected expert to be selected at the beginning of block conditioned on the values of x("). When the event F(( does not happen we have that the expected expert a," is well separated from other experts such that typical cost sequences from DØT ones where F. (( does not occur, it will be the case that (+ =a!")
We claim that Pr[p(]] & e(0) x P( = -y. To see this, for fixed action a E A and constant Y E R let Fa, be the event that a, (f)
and
max (Hapli-1) - (Holli- - xx()) =
BEA
bça
Upon conditioning, we have
Pr(F(() [ar]] = Pr (1 <Y 20 P(i- x > r S (l x 2x V P(i-1),
since x is distributed Geo(E()) and using the memorylessness of the Geometric 10
distribution.
Since this true for all values of a and Y, we have the above claim. Hence,
Pr F
U B
p()
< By < p/8.
4. Let (2ln(16n/p) For E A, let G. be the event that there exists a E [T] such that Eje (a()= Hal > n/T Hence, when G. does not occur it means that the cumulative cost of expert a at any time within n/T of its expected cumulative cost till time Note that event E(() provides possibly a stronger bound on the cumulative cost of expert a at time p(1), but not at all times. Then, by using Theorem B.1 with parameters
S. = Ejsr ((a) pat and hence,
2 we have Pr[G.] I 2exp(-nf /2); nTT b
Pr G =
U Ga 2nexpp-o2/12) p/8.
aeA
5. Let 3 1n(88 =og(Sn log()))lllo/))))) and M max {
(x(() a E A]. and let H() be the event that (i) > z(1)- Hence, if H does not occur then the noise added at the beginning of block to any expert A is at most multiplicative factor over the expected value of 1/el0.
Then, using the fact that x(() (+)( and by a union bound over a A, we have
Pr (0)
< n(1 - 200) < n exp(p3)).
Thus,
Pr
H())
< nB exp((3)) S p/8.
xE[B]
38

---

Properties 4 and 5 will be used later to bound the chance of the algorithm calling the usual FTPL (Algorithm 9), and properties 2 and 3 will be used to bound the chance that the same expert is selected across each block in two different runs of the algorithm on iid inputs. In what follows for a RVV we denote by (S,, R) the realization of Z on the cost sequence S DDT and internal randomness R: further, for an event I let T(S, R) be if (S, R) E I and 0 otherwise. To show replicability we need to show that with probability at least 1 - p (over the internal randomness of the algorithm and over independent cost sequences S2 from D&T) at all times t we have (S,, R)- = (s2, Rt) (a, is the expert selected by the algorithm at time f). For this it sufficient to show that with probability at least p. for all E [B] we have that a R) = a (S2, R) and Algorithm 9 is never called (i.e., at no time does the regret exceed K 2nn.).)
Now, from the above observations, with probability at least 1 - over R and S we have that E(S,, It) = F(SI, Rt) = G(S,, Rt) = H(i, R) and E(S2, It) = F(S2, Rt = G(S,, R) (S2,, R)- O.
Next, consider any S1, S2, R such that E(S, R) F(S,, G(S R) (S R) 0 and E(S2, R) = F(S2, R) = G(S R) = H R) = O. In such a case we have:
1. E E [B] : a R) (S2, R): This is because a. (S1. R) 02 (S1, R), since in
(8)
both cases we are using same randomness R. Further, since E(S, R) = F(1, R) = 0 we
have that (S,, R) = a! (S, Rt.. Similarly, a (5), Rt) = a. (S2, R).
2. At no time does the regret exceed K 2/ n: Since G(Si, R)- HS R) = 0.
therefore, at any time S T the regret suffered by the algorithm can be analyzed as follows.
Let i + 1 be the block which contains the time index t. Then, for any expert E A at time the cost incurred on (Si, Rt is:
Σ (S) R)) 2 pat - -VVT (:,GS)) R 1=1
= (1) Pa + (2) pa +... + (00 Pa + (t- )aa -VVT. (40)
The cost incurred by the algorithm till time & is most:
( + (2) (Hara)s)))) + +220 +... + ( (M + 2av p())
+ (t- - p(() (( + 2nVT.
(41)
This is because for a particular block say e S i the algorithm selects expert a (v) (S1, R) and incurs a cost that is close to the expected cost for (()) R) for [ time steps: within the [() time steps the cost incurred by expert (S1, R) can deviate from (aw R)) (() by at most av p(r-)) + avp( < 2ayPle) (as ESS,, RR = 0). The additional 2n/T term accounts for the deviation over the expected cost for the time steps p(t) + 1,...,, (as G(Si, Rt) = 0).
Now, let us analyze μa (S,, Na for fixed block v. (For ease of presentation in what follows we have removed the explicit reference to (S1, Rt at some places: each RV should be thought of as its realization on (S1, Rt.)
Notice that by Algorithm 9 we have:
plu-1)
p(u-1)
Σ
ca(ao))) x(1)
Σ cj(a) x(o).
5
1-1
j=l
Also, as F(S1, R) = we have
1(s-1)
Malr) p(on) p(o-1)
av 1(v-1) <
Σ
eg (1)
j=1
39

---

and
pln-1)
Σ
cj(a) S pa p(u-1) + av P(u-1),
thus, using x S M(n), we have
20 Pav/P(p-1) M
Muie) Ho S
p(v-1)
Finally, we can upper bound the regret at time on (S1, R) as (Equation (41) Equa- tion (40)):
B L + Σ (Mat - ma)) + (1- (Ma)) -Ma) + 2aBVT +3
2
B
2aVple-1) +
< L
[!0)
p(v-1) + (2aB +
V=2
= VP(v-I) and p(=-1) > (1-11)_ (Li)))
which, by using ((
[(0]
3
becomes
s 5 +3 + 1)VT (2a 3/7) Σ VT
<2aB + 3n + 1)VT + B(2a + 3/7)VT,
which upon In(8n log(T))))))) 8log log(T) and 2 1/2mn(661) becomes,
substituting the values a =
log (T)(p)/)), B =
x (log log())))) x log (= p
n log log())
1000
x vT) -2
P
K -K-2VT nn
I Lower Bounds for Replicable Regret Minimization
First we prove a lower bound on the regret of an iid p-replicable algorithm even with two experts via a reduction from the coin problem of Impagliazzo al. [2022] 7.2).
The coin problem is as follows: promised that a 0-1 coin has bias either 1/2 or 1/2+7 for some fixed how many flips are required identify the coins bias with high probability? Below state the result from Impagliazzo et al. [2022] regarding the replicability of such an algorithm for the coin problem.
Lemma I.1 (Impagliazzo et al. [Lemma 7.2): Sample Lower Bound for the coin Problem). Let 1 and p To. Let B be a p-replicable algorithm that decides the coin problem with success probability at least 1 1-6 8 for = To using T iid samples. Furthermore, assume B is p-replicable, even if its samples are drawn from coin C with bias in (1 T +T) Then B requires sample complexity T E E
1
i.e., E Ω
Using the above lemma obtain the following result. Theorem 1.2 (Lower Bound on the regret of an iid p-replicable algorithm for two experts). Suppose there are two experts A 21, ie, n 2. Let p be a parameter. Then, any iid p-replicable algorithm must suffer worst-case regret of K min(O( (),, T/64) in fact, there exists distribution D over [0, 1|2 such that on cost sequence S = (ci...., cr) sampled from DeT the expected regret of the algorithm is K
40

---

Remark. Using the usual regret lower bound for n. experts we can conclude a lower bound of OVVT/p + V log())) provided this is lesser than T T/64.
Proof. Let ALG be iid p-replicable algorithm with worst-case regret K. Further, let the expert selected by ALG at time be at. We reduce an instance of the coin problem from above with parameters p. 87 and 1/16 the expert setting follows. For sequence of coin flips c2.2......6 CT, where each êg E {0, 1), let Cr,...,r Cr be the cost sequence such that c,(1) = 2g and ((2) = Cj-
K
Now, we feed ALG the cost sequence Cl...., ., Cr corresponding to iid coin flips c1, .2,.... ... CT where the bias of the coin is between 1/2 + and 1/2 replicable. Further, when the coin's ' bias is either 1/2 + T or 1/2 т, a = MAJ {ar E [T]} is good indicator of the coin's 's bias:
For such inputs we know that ALG is p-
answer that the coin has bias 1/2 + r if a and 1/2 8. To see this, suppose that the coin has bias 1/2 and notice that the expected cost of ALG is (the expectations below are over the internal randomness of the algorithm and the coin flips leading to the sequence C1....,cr)
a = 1. Also, we will be correct with probability at least
E|Cost(
E
Ia; (1) + Ia. 2]c{
j=1
E[lla, (1) + I/a 2)cx(2)]
(Linearity of Expectation)
T
Σ
BiLla, = 1](1/2 Iaa, = 2](1/2 -]]
(: ag is independent of ct)
j=1
la 2] 1aa = -11 11)
T/2 IE
Using the fact that the regret most K and that (E)=11((2) T/2 -T' (where the expec- tation is over the coin flips) get:
T
T/2 - E
[a: 2] - -I[ =1]
K
E
1aa = 2] Ila: = 11
> T K/T = (1 8)T (using T
87
Pr[MAJ{a, |t E [T]- x T 2 (1 8)T
Pr[MAJ e [T] = 2] > 1-
Hence, we can use Lemma to conclude that p> [2( --((->)) 5 1/16 the constraint translates K < T/64. This gives the theorem.
[ provided T < 1/4. Using T
K 87 and
Now, we use the above lemma to obtain the lower bound on regret in the case of 2 2 experts when have adversarially p-replicable algorithm.
Theorem I.3 (Lower Bound on the regret of an adversarial p-replicable algorithm for n experts). Suppose there experts (1.2.....)) n). Let p 0 be a parameter: Then, any adversarially p-replicable algorithu must suffer a worst-case regret of min (oooo())))))) T//44
Proof. Let the set of experts be A= = {1, 2, n). It is sufficient to prove the above theorem when 2 for N. We will proceed by induction to prove that the worst-case regret for any iid
p-replicable algorithm, say ALGG, is at least min(U x TTm T//44 where 0 is a universal constant.
41

---

For m 1 this follows from Theorem I.2. For m > 1 we proceed as follows. WLOG we can assume p is such that U <Tm I T/64 or else we can always increase the value of p until the inequality is satisfied. Let L TTmm and consider a cost sequence či,...,ćy cr for two experts {1, 2), ie, each é E [0, 1J2. Let Ci...., Cz be the cost sequence for experts such that cj(a) 2g (1) for a E [n/2] and Cÿ(a) = (2( for > n/2
By using Theorem 1.2 we know that there exists sequence of ê such that the regret of ALG on .I..... Cr. is at least min x vL/p. L/64] = U vL/p. Further, either all experts 1,2, ..2,.... n/2 or all experts n/2 + 1,..., 7 are the min-cost experts for C1, ,,,,..;,r Ct. WLOG let us assume that it is the former case.
sequence eL+1...., êT for the experts 1, .2/....n/2. ie, each ég 0, 1)m/2 let CL+1y.... CT be the cost sequence such that (a(a) (a) if E [n/2] and ca(a) = 1 > n/2. Notice that even conditioned receiving Ci...., Ct, ALG remain adversarially p-replicable. By induction we can find a cost sequence EL+1,...,, Cp for the 2 experts 1, 2,.... n/2 such the regret
Now, for
of ALG (conditioned on ,I,...,CZ, CL) on CL+I..... eT is at least min x v(T L)im
T-h }
61
x (TT-L)(m-1 Hence, the overall regret of ALG is
UXVL/p+UX (T- L) U X vTm/p.
This can be seen by substituting = T/m.
42


Reviews:
[{"review_id": "CmwWqlBn1x", "reviewer": "Reviewer_Cdde", "summary": "The paper studies replicable learning for online learning optimization and the experts setting under the online setting. Previous works studied a similar problem in the online setting with data being generated in an iid fashion from a single distribution whereas this work generalizes the setting to allow data points at different timesteps to be sampled from different distributions (i.e. adversarially chosen). The primary objective of this work is to produce algorithms that fit certain replicability properties along with achieving low regret in the online setting.\n\nThe authors explain that an online learning algorithm is adversarially $\\rho$-replicable to indicate that with probability $1 - \\rho$, and for two sequences $S$ and $S'$ generated iid from an adversarially chosen sequence of distributions, the algorithm generates the same set of actions at all timesteps for both sequences (fixing the algorithm's internal randomness).\n\nThe paper introduces many results for online replicable learning with the property of adversarially $\\rho$-replicability being satisfied. In both online linear optimization and the experts problem, the authors construct two algorithms, one for each setting, that satisfy adversarial replicability along with achieving sublinear regret. More specifically, in online linear optimization, the authors develop an algorithm called the FLLB which is the FLL algorithm executed on the time horizon divided into blocks where the updates happen at the end of each block. Similarly, in the experts problem, the authors take the FTPL and apply the same blocking procedure and use geometric noise instead of the standard exponential noise used by Kalai and Vempala in their FTPL algorithm. They also study regret lower bounds and show a lower bound of $\\Omega(\\frac{\\sqrt{T}}{\\rho})$ and extend their results for iid replicability as well. They additionally introduce a general framework to convert any online regret minimization algorithm to one that has a slightly worse regret guarantee but with adversarially $\\rho$-replicability satisfied.", "questions": "- Regarding the lower bounds for adversarially replicable algorithms, could it be the case that the cost of replicability must exceed the classical $\\sqrt{T}$ barrier as seen in traditional online learning? Or is it possible that one could further refine the upper bounds to make them sharper?\n- While the authors show that one can preemptively select the block length $B$ beforehand to get the optimal guarantees, is there an adaptive, data-dependent way to choose the block length that would still preserve replicability?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper tackles a unique setting of a more generalized version of replicability under the online setting, namely adversarial $\\rho$-replicability.\n- The paper provides a pretty comprehensive treatment of this setting with many different results across online linear optimization, the experts problem, an online-to-replicable algorithm reduction, and derivation of lower bounds under each scenario.\n - They also show a nearly optimal iid replicable algorithm in the expert setting with a bound that matches the lower bound of Impagliazzo et al. (2022) up to logarithmic factors.\n- The paper is also quite well-written. The authors introduce the setting in an effective manner using tangible examples, give easy-to-follow overviews of their algorithmic techniques, and do a good job of explaining technical details.\n\nWeaknesses:\n- Not necessarily a major weakness but there exists a rather noticeable gap between the upper and lower regret bounds, $T^{5/6}$ vs $\\sqrt{T}$, under adversarially replicable algorithms. A small discussion, if available, discussing the challenges in closing the gap or why the gap exists would be interesting.", "was_revised": true, "final_justification": "The authors have addressed all my questions during the rebuttal period. As pointed in other reviews, certain modifications need to be made to the paper to make it more technically rigorous. For example, one reviewer found an important condition that needs to be mentioned in Theorem 5.1. Assuming the authors make these modifications to their paper, I still my retain my original rating of a 5 for this paper.", "rebuttal": "We thank the reviewer for their constructive feedback. We are glad that your found our results interesting. Here is our response to your questions:\n\nQuestion 1:\n\nRegarding the upper bound, our current algorithm would not achieve a better bound. The reason is that, there are two variables in our algorithms, one the block size B, and the other one, the noise level $\\epsilon$. In order to bound the probability of non-replicability to at most $\\rho$, we need to set these two parameters carefully (equation below line 853). Furthermore, in order to minimize regret, we need to set $\\epsilon = \\frac{1}{\\sqrt{BT}}$, line 856. Putting these not inequalities together, gives us the optimum values of noise level $\\epsilon$ and block size B. However, there might be a different algorithm that achieves a better regret bound, and we leave it as an open question.\n\nOn the other hand, regarding the lower bound, currently, all approaches to proving lower bounds in terms of the replicability parameter go via a reduction to the coin problem as defined in [Impagliazzo et al. STOC’ 2022](Lemma 7.2). (Reduction for the stochastic bandits mentioned somewhat informally in Esfandiari et al.) The coin problem is as follows: promised that a 0−1 coin has bias either $1/2−\\tau$ or $1/2+\\tau$ for\nfixed $\\tau > 0$ how many flips $T$ are required to identify the coin’s bias with high probability while being $\\rho$-replicable? Here we have a tight lower bound of $\\rho.\\tau.\\sqrt{T} > \\Omega(1)$. When the reduction is done (as in the paper) the $\\sqrt{T}$ here translates to the $\\sqrt{T}$ in our proof. We don’t believe that this reduction is optimal in the sense that a more batched up division of the time steps where each batch reduces to a coin problem with different $\\tau$ values should lead to a better bound: however, we are unable to execute the above idea. This would also mirror the batching of time steps in the upper bound, and would utilize the full extent of the adversarial setting where the distributions (which correspond to $\\tau$ in the reduction) are time varying.\n\nQuestion 2:\n\n That is a great question. We derived these results so that they would capture both adversarial and iid input sequences, as well as their mixtures, which can be modeled by setting certain distributions as point-masses. However, in the iid case, in Appendix H, we show how to derive better regret bounds $O(\\sqrt{T})$ by having blocks of varying lengths.\nHowever, it is certainly possible that our $T^{5/6}$ regret bound in the general case is improvable, and we leave it as an open question."}, {"review_id": "nKhYtrhZrj", "reviewer": "Reviewer_Pyha", "summary": "\\paragraph{Summary} The paper studies online learning problems, like learning with experts and online linear regression under the requirement of replicability. Loosely speaking, a randomized  algorithm on input sampled from some distribution, is replicable if for two independent set of samples, it is very likely over the internal randomness of the algorithm (probability $\\geq \\rho$ for some replicability parameter $\\rho$) that the algorithm returns the same output on the two sets of samples. The notion was introduced motivated by the replicability crisis in science, but the property is interesting as a stability-notion in its own right, and has connections to concepts like differential privacy and generalization.\n\nThe main results of the paper are replicable algorithms for online learning with experts and online linear optimization (plus a more general framework for online learning problems) with sublinear regret. The input in each round $i$ is assumed to be sampled from some distribution $\\mathcal{D}_i$ chosen by an adversary in an oblivious fashion which significantly generalizes a framework by Esfandiari et al. [2022] where the input is assumed to be iid. The paper also proves almost matching lower bounds for the iid setting through a reduction from replicable coin testing.\n\nThe main algorithmic idea is to partition the sequence of updates into blocks (for the  iid setting the blocks have increasing lengths) where the algorithm within each block plays the same action. Long blocks of course incurs worse regret bounds but they are good for replicability where we only have to worry about the ends of blocks. In order to enforce replicability by the end of the block, their algorithm rounds the regularized cost vector to a random grid point and uses the minimum of that grid points as the action for the next block. In order to not make the grid too big, this requires some concentration bounds for the total cost incurred during a block. The final algorithm chooses the block size appropriately to ensure replicability and low regret.", "questions": "l74: It would be nice with a discussion of whether obliviousness is necessary. I had a vague intuition that since the algorithms are replicable, an adaptive adversary wouldn't be much harder to handle since over the two independent runs, replicability ensures that the outputs are likely the same and then it seems like the adversary adaptively chosing the distribution shouldn't help much. But it's very possible I'm missing something.\n\nl117-118: I'm confused. Doesn't your algorithms have no switching within the blocks?\n\nl209-214: Don't you need some assumption on the norm of the cost vectors? Is it related to the $D$ on l279 (which I think hasn't been defined).\n\nExample 3.1. I had a hard time following the writing in this example and I don't know the precise meaning of \"gives a bonus\" or \"pretends that $a_2$ has better performance initially\". The final sentence could also be phrased stronger I think. \n\nl784: In the def of $a_t$ there is a missing $+$.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "\\textbf{Strengths}: \n(1) I found the problem well-motivated and their model very interesting and natural opening up for several new directions for future work.\n(2) The technique of partitioning into blocks and using random grid shifting after the blocks to enforce both replicability and low regret is very nice. \n(3) It is great that the paper provides a near matching lower bound in the iid setting\n(4) The paper is well-written, and I had little problems following the proofs. I read the first 9 pages and the proof of theorem 3.1 in the appendix, but stopped after that.\n(5) The paper states many interesting problems for future work.\n\n\\textbf{Weaknesses} (1) The paper might benefit by a discussion of how the techniques differ from past work, e.g., Esfandiari et al. [2022]", "was_revised": true, "final_justification": "Please see my discussion with the authors", "rebuttal": "We thank the reviewer for their constructive feedback. We are glad that you found our results interesting. Here is our response to your questions:\n\nWeakness 1:\n\nThank you for the suggestion. We would like to mention that the guarantees for Esfandiari et al. and Komiyama et al. are all in the stochastic bandits setting, and their algorithms have $\\omega(T )$ regret bounds in the adversarial setting.\n\nQuestion 1:\n\nThat is a great point. In fact, Kalai and Vempala also show that if the randomness $p$ in Algorithm 1 is re-drawn in each round, we can achieve sublinear regret even in the case of adaptive adversaries. Since our algorithms are a generalization of FLL by Kalai and Vempala that observation holds in our case as well. We add a remark to highlight that.\n\nQuestion 2:\n\nWhat we mean here is that if we consider the FTPL (and not FTPL with block updates, i.e. FTPLB), over two different cost sequences $S_1$ and $S_2$ that are both drawn from the same sequence $D_1,\\cdots, D_T$, then FTPL changes its actions in near timesteps when executing it on $S_1$ and $S_2$. Hence, since with high probability these changes are in close-by timesteps, they will be in the same blocks (whp). Now, if we consider FTPLB, since it is updating its action only at the endpoints of the blocks, it will pick the same action sequence when executing it over $S_1$ and $S_2$.\n\nQuestion 3:\nYou are correct, we will add this to the model section. In Thm D.3, we explain that the $\\ell_1$ length of c is at most and the $\\ell_1$ diameter of A is D.\n\nQuestion 4:\n\nThat’s a great point; we will enhance the writing of this example. We just mean that initially, when $c_1$ is drawn, that is a vector of length 2 (since we have two actions), the cost for action $a_1$ is higher than the cost of $a_2$ (this is what we mean by bonus, a lower initial cost). However, in hindsight, $a_1$ is a better action, so it would take some time for the algorithm to figure this out.\n\nLast comment:\nPerfect, thanks, we will correct this."}, {"review_id": "VsLZ3rULp1", "reviewer": "Reviewer_JwSX", "summary": "This paper studies the recently-introduced notion of replicability in online learning setups. An adversary decides on a sequence of $T$ (possibly different) distributions, from which the instances are drawn independently. The online learning algorithm is called *replicable* if, fixing the randomness in the algorithm, the outputs match with high probability on two sequences of instances sampled independently. The goal is to design low-regret and replicable algorithms for various online learning settings.\n\nIn comparison, prior work has studied replicable online learning in more restricted settings and/or with weaker guarantees:\n- Some focused on the special case that all $T$ distributions are identical (termed iid-replicability in this work).\n- Some only requires the algorithm to be low-regret on observations drawn from the distributions (rather than on all sequences).\n\nThe main results of this work are summarized below, where polynomial dependence on other parameters (including the replicability parameter) are suppressed:\n- Theorem 3.1: A $T^{5/6}n^{1/6}$ regret upper bound for online linear optimization in $n$ dimensions.\n- Theorem 4.1: A $T^{5/6}\\log^{5/6} n$ regret upper bound for the experts problem with $n$ experts.\n- Theorem 5.1: A general transformation that translates a low-regret (but not necessarily repliable) algorithm into a replicable one.\n- Theorem 6.1: A $\\sqrt{T}\\log(n) / \\rho$ regret upper bound (modulo a $\\mathrm{polylog}(\\log T, 1 / \\rho)$ factor) for the experts problem in the iid replicable setting.\n- Theorems 7.1 and 7.2: Regret lower bounds against replicable online learners in the experts problem.", "questions": "Repeating the \"Weaknesses\" section above:\n- In the online setting, why is it reasonable to assume that one can \"repeat the history\" and observe a sequence of identically distributed data points?\n- For the proof of Theorem 5.1, could you clarify whether the proof relies on some unstated assumptions on the loss, as well as why the step from (14) to (15) is valid?", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The formulation of replicable online learning is natural and clean from a theoretical perspective. It is stronger (and arguably more natural) than those in prior work. Yet, a sublinear regret bound can still be guaranteed for several fundamental online learning settings.\n- The writing is generally clear and easy to follow. Especially, the authors did a good job in comparing their model to prior ones and highlighting the differences.\n\nWeaknesses:\n- I was a bit confused about the statement of Theorem 1.3 (and Theorem 5.1): What families of online learning problems does this result apply to? As stated, there isn't any restriction other than that each instance $c_t$ is a $n$-dimensional vector.\n- However, as I followed the proof of Theorem 5.1 in Appendix F, it appeared to me that more assumptions are needed. For example, in the step from Equation (13) to (14), isn't it assumed that the loss function $\\mathsf{Cost}(\\cdot, \\cdot)$ is linear in the second argument?\n- I didn't follow the step from (14) to (15) either: even assuming the aforementioned linearity, $g_{uB}$ and $g_{(u-1)B}$ are $\\sum_{t=1}^{uB}c_t$ and $\\sum_{t=1}^{(u-1)B}c_t$ rounded to two different grids---why is the difference between them equal to $c_{(u-1)B:uB}$?\n- Except for the iid-replicable experts setting, the upper bounds do not come with lower bounds with matching dependences on $T$.\n- From a more practical perspective, I didn't find that the notion of replicability makes as much sense in the online setting as in the batch/offline/supervised setting. In supervised learning, it makes sense to collect fresh data and replicate the learning. In the online setting, why is it reasonable to assume that one can \"repeat the history\" and observe a sequence of identically distributed data points?\n\nOther comments / writing suggestions:\n- Line 63: There is an extra space before the period.\n- Line 81: The term \"adversarially $\\rho$-replicable\" was a bit misleading to me: compared to being \"iid $\\rho$-replicable\", the only change seems to be that the observations can be differently distributed across timesteps. In other words, they are still independently sampled from distributions, and I didn't quite see what is \"adversarial\" in this formulation.\n- Appendix F, Line 27 of Algorithm 5: Should the condition be \"$t - 1$ is a multiple of $B$ and $t > 1$\"? This is because we shouldn't call the internal algorithm at time $t = 1$.\n\nOverall, while I liked the formulation of the problem and the suite of results that the authors obtained, I have strong concerns over the validity (or at least the scope of applicability) of one of the main results. Therefore, I don't think this submission should be accepted without adequately addressing this point.", "was_revised": true, "final_justification": "During the discussion, the authors acknowledged that one of the main results (Theorem 5.1) holds for a more restricted family of problems---namely, those with a linear loss function $f$---than what is stated in the original submission, and that its proof needs to be slightly revised for it to be rigorous.\n\nAlthough the proposed revision makes sense to me at a high level, unfortunately, its validity and rigor could not be fully evaluated (without reading a fully-revised version of the paper). As pointed out in the other reviews, the technical writing is hard to follow at times due to multiple inaccuracies and undefined notations. Therefore, while this paper studies an interesting problem and makes solid progress, I was afraid that it would be risky to accept this manuscript as is, and thus would still lean towards rejection.", "rebuttal": "We thank the reviewer for the feedback and reviewing efforts, here is our response:\n\nWeakness 1:\n\nYes, thank you for pointing this out: we forgot to mention this condition in the theorem statement. We will include the condition in the theorem statement. The reason is that we need the loss $f (a, c)$ to scale linearly with the `1-norm with c and that if $c'$ is a\nrandom variable with $E[c'] = c$ then $E[f (a, c')] < f (a, c)$ (concavity). But we want to highlight that even with\nthe constraint of linearity of the loss function we are able to capture many settings such as online linear optimization, experts and bandit problems.\n\nweakness 2,3:\nWe need to make a slight change to the following in Algorithm 5: $g_t \\gets G \\cap \\\\{c_{1:t-1} + (-\\epsilon/2,\\epsilon/2)^n\\\\}$ so that over the randomness of the initial random offset of the grid G we have $E_[g_t] = c_{1:t-1}$.\nSimilarly, for G'. We will make this change: it is a minor one and not conceptual.\n\n\nIn light of the previous point, consider the following: in Equation (13), let us bring the $E_{R_{ext}}$ inside. Then we get an expression like:\n$E_{R_{int}} [ E_{R_{ext}} [Cost(a_u, g_{uB} - g'_{(u-1)B})] ]$\n\nwhich by our assumption we can say is at most:\n$E_{R_{int}} [ Cost(a_u, E_{R_{ext}}[g_{uB} - g'_{(u-1)B} \\mid a_u]) ].$\n\nAnd now, using the fact that $a_u$ is **independent** of both $g'_{(u-1)B}$ and\n\n$g_{uB}$, we have:\n\n$E_{R_{ext}}[g_{uB} - g'_{(u-1)B} \\mid a_u]$\n\n$= E_{R_{ext}}[g_{uB} - g'_{(u-1)B}]$\n\n$= c_{uB} - c_{(u-1)B}$\n\n$= c_{(u-1)B:uB}$\n\nThis is the case since at a transition point $t$ (that is when $t = (u-1)B + 1$ and we are permitted to change our action), $a_t$ depends on $g_{t-1}$ and $g'_{(t-1-B)}$,\n\nimplying that $a_u$ depends on $g_{(u-1)B}$ and $g'_{(u-2)B}$\n\n (and not $g'_{(u-1)B}$ \n\nand $g_{uB}$)). Please see line 33 in Alg 5\n\nIn fact, this independence from $g'_{(u-1)B}$ was the main reason for using *two different grids*. Also, due to the rounding procedure we have that \n\n$E[g_{uB}] = c_{uB}$\n\nsimilarly for g'.\n\n\nweakness 5:\nHere is an example in the online setting: Suppose that we have an algorithm for deciding which routes to use to drive to work each day.  We run it for T days, jotting down features of that day.  For instance, Day 1 was Monday at 8am and sunny.  Day 2 was Tuesday at 10am and rainy, etc.  If you imagine that traffic at any given time is a probabilistic function of the features, then what our guarantees say is that if you run it again on a different sequence of T days then (a) we'll have sublinear regret no matter what, and (b) if this new sequence has the same features as the first sequence, then with high probability your entire sequence of actions will be the same.\n\nother comments,\n\nline 81: In the adversarial case, the distributions across different timesteps are picked by an adversary. That’s why we call it adversarial $\\rho$-replicable case.\n\nAppendix F, Sure, we will edit the text, thanks."}, {"review_id": "hOkQLZgG7j", "reviewer": "Reviewer_GsvK", "summary": "This paper studies algorithmic replicability in the online setting. In this setting, an oblivious adversary picks a sequence of distributions over loss vectors before the game begins. The goal is to design low-regret online algorithms that, with high probability, output the exact same sequence of actions on two independently sampled sequences of loss vectors. The authors consider two online learning settings —online linear optimization and learning with expert advice —and design replicable online algorithms that achieve sublinear regret. In the special case where the adversary chooses the same loss distributions for all rounds, the authors design a replicable online learning algorithm with near-optimal regret guarantees. More generally, the authors present a generic conversion of a non-replicable online algorithm into a replicable one. Finally, the authors complement their upper bounds with lower bounds on regret that any replicable algorithm needs to suffer.", "questions": "It would be great if the authors could address all my concerns in Weaknesses 1-4. \n\nAdditional questions:\n1. The technique of batching (and more generally, lazy algorithms) has been studied extensively in online learning (see [1]). What implications do these results have on replicable online learning, if any?\n\n2. Lazy online algorithms have been especially useful for designing differentially private online learning algorithms (see [2]). How does your notion of replicable online learning relate to differentially private online learning? Does one imply the other? \n\n3. Learning with expert advice is a special case of online learning optimization when the decision space is taken to be the n-dimensional simplex. Can your regret bound for replicable online linear optimization be converted into a regret bound for learning with expert advice? That is, do you really need to have a separate algorithm for the problem of replicable learning with expert advice?\n\n[1] Arora, Raman, Ofer Dekel, and Ambuj Tewari. \"Online bandit learning against an adaptive adversary: from regret to policy regret.\" arXiv preprint arXiv:1206.6400 (2012).\n\n[2] Asi, Hilal, et al. \"Private online learning via lazy algorithms.\" Advances in Neural Information Processing Systems 37 (2024): 112158-112183.", "limitations": "There is a significant gap between the regret upper and lower bounds. It would be great if the authors could provide some intuition on how this gap can be reduced.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- The paper studies an important problem in machine learning and presents, to the best of my knowledge, the first formal framework for studying replicability for online learning with full-information feedback. \n- The authors provide several interesting results across various online learning settings, including both lower and upper bounds\n\nWeaknesses: My main concern with this paper is its presentation, which is the main reason behind my rating. Below, I list my concerns. \n1. There are several places where notation is not well-defined and hinders readability:\n  - In many places (Line 248, 274, ...), vectors are being added to spaces. This operation should be defined.\n  - In Line 272, $Z^n$ is not defined.\n  - In Line 274, $c_{1:t-1}$ is not defined.\n  - In Theorem 3.1, $D$ is not defined. \n  - Figure 1 is a bit unclear, it would be good if the text c_{1:t-1} was colored in red, and c'_{1:t-1} is colored blue\n  - In Algorithm 2 and Line 287, \"Geo\" and \"geometric noise\" are not defined. What does geometric noise mean? What is the distribution of this noise? This should be stated precisely in the main text.\n  - In Line 316, I think $\\Omega$ should be $O$\n  - In Line 312, $D$ is not defined. \n  - In Line 326, $K$ is not defined. Also, what am I supposed to take away from this sentence? There is always an upper bound on the regret... \n\n2. The paper currently reads like a list of results without providing much intuition. No intuition/sketches behind the proofs is provided for any of the main Theorems, as the authors repeatedly \"defer the proof to the Appendix.\" The most egregious offense is Section 4, which contains just the algorithm and the theorem statement. The authors should expand on this section and provide insight on why geometric noise is needed and why the results for online learning optimization don't just apply to the expert setting (see Question 3 in \"Additional Questions\"). Section 5 is also not illustrative as Algorithm 5 is not in the main text. The authors should move Algorithm 5 into the main text and provide a proof sketch. Overall, more exposition is needed to ensure that the main text does not just read like a list of results, and hence, I believe that this work requires a rewrite. \n\n3. A minor concern is the significant gap between the lower and upper bounds on the regret for replicable online linear optimization. It would be good if the authors could comment on whether a tighter analysis of the current approach can lead to a better upper bound than the one in Theorem 3.1, and it not, what the barrier is. \n\n4. Another minor concern is regarding novelty. It seems like the techniques used by this paper are not new: rounding has been used by existing work on replicability, and \"blocking\" (more generally, laziness) has also been studied in online learning literature. It would be great if the authors could comment on what makes this work not just a combination of these two techniques.", "was_revised": true, "final_justification": "The authors addressed my main concerns and provided a concrete plan for improving the readability and exposition in the camera-ready version. As such, I have increased my score from a 3 to a 4.", "rebuttal": "We thank the reviewer for their time and feedbacks, here is our response:\n\nweakness1:\n\n1.1 - Sure, we will clarify this in the text. It means the cube starting from the point $\\sum_{i=1}^{t-1} c_i$.\n\n1.2 - We will clarify this. Here, we mean a grid with side $1/\\epsilon$ and a starting point of $p$.\n\n1.3 - We will clarify this. This means $\\sum_{i=1}^{t-1} c_i$.\n\n1.4 - D is the diameter of the action set (pointed in Thm D.3), we will add this to the model.\n\n1.6 - We will add this to the model section. The geometric distribution with parameter $\\epsilon$ is the discrete probability distribution that describes when the first success in an infinite sequence of independent and identically distributed Bernoulli trials occurs. Its probability mass function depends on epsilon and is defined as:\n$P(X=k)=(1−\\epsilon)^{k−1}\\epsilon$\n\n1.7 - You are correct. We will fix that.\n\n\n1.9 - Apologies for the confusion: what we mean is the following. The goal is to design an iid $\\rho$-replicable algorithm with worst-case regret as low as possible. Recall the following\nfrom Section 2: (1)We say an algorithm has Worst-case regret $K$ if  for any cost sequence $S = (c_1, . . . , c_T )$, the expected regret satisfies $\\E_{R\\sim \\cal{R}}[Reg(S,R)]$ (2)We say an algorithm has replicability $\\rho$ if for iid cost sequence.\n\n\nweakness 2:\nDue to the space issues, our remedy for this was to have a longer introduction with an extensive “our contributions” section to explain the intuition behind our results. \n\nweakness 3:\n Regarding the upper bound, our current algorithm would not achieve a better bound. The reason is that, there are two variables in our algorithms, one the block size B, and the other one, the noise level $\\epsilon$. In order to bound the probability of non-replicability to at most $\\rho$, we need to set these two parameters carefully (equation below the line 853). Furthermore, in order to minimize regret, we need to set $\\epsilon = $\\frac{1}{\\sqrt{BT}}$, line 856. Putting these not inequalities together, gives us the optimum values of noise level epsilon and block size B. However, there might be a different algorithm that achieves a better regret bound, and we leave it as an open question.\n\nweakness 4:\nOur main contribution is a principled framework to study replicability with low regret in settings combining stochastic and adversarial elements, whereas previous works focused exclusively on the stochastic case. By considering an adversarial (oblivious) \\emph{sequence of distributions}, our model generalizes the standard oblivious adversary (point-mass distributions) and introduces a natural approach to replicability in adversarial environments.\nIn hindsight, although the employed techniques are standard, it was not a-priori clear that our definitions would yield sublinear regret. Furthermore, the analysis presents technical challenges: certain scenarios do not admit the ideal $\\sqrt{T}$ regret bound (even when $\\rho$, the replicability parameter, is constant), whereas others (e.g., i.i.d. experts) achieve favorable bounds.\n\nQuestion 1:\nWe are borrowing from previous ideas but making them work for replicability requires delicate balance and some cleverness to circumvent certain bottlenecks. We study replicability with low regret in settings combining stochastic and adversarial elements, whereas previous works focused exclusively on the stochastic case. By considering an adversarial (oblivious) \\emph{sequence of distributions}, our model generalizes the standard oblivious adversary (point-mass distributions) and introduces a natural approach to replicability in adversarial environments.\nIn hindsight, although the employed techniques are standard, it was not a-priori clear that our definitions would yield sublinear regret. Furthermore, the analysis presents technical challenges: certain scenarios do not admit the ideal $\\sqrt{T}$ regret bound (even when $\\rho$, the replicability parameter, is constant), whereas others (e.g., i.i.d. experts) achieve favorable bounds.\n\nQuestion 2:\nconnections between online replicability and DP online learning:\n\nWe don't see any direct reduction. For example, we require the entire sequence to be replicated whp, not just any given entry, so it's not at all clear if differential privacy with meaningful parameters would be useful for replicability.  In the reverse direction, we should be able to get privacy for a single entry changing by a bounded amount, but full replicability might be an overkill for that.\n\nQuestion 3:\nOur results for learning from experts is in Section 4 and Theorem 4.1. That being said, by using geometric noise, we end up getting a better dependency on n(number of experts) that is logarithmic instead of polynomial dependency(n^{1/6}) on n for online linear optimization."}]

Author rebuttal:

Meta-review: This paper considers online learning in setting between stochastic and adversarial: they consider adversarial, but oblivious, sequences of distributions as a comparator class under a rho-replicability assumption. They develop non-trivial regret bounds in a variety of settings. Reviewers found hthe treatment of the setting fairly complete, completing with a matching (up to log terms) bound in the i.i.d. setting.
Reviewers also praised the presentation and clarity of the writing. 

There was some concern about the proof of the main theorem, but this seems to have be dealt with during the discussion period. A few points about readability were also discussed, and I hope the authors use the discussion results to improve the quality of the paper.

Given the complehensive results, interesting setting, and good presentation, this was an easy paper to accept.
Decision: Accept (poster)