Online Learning in the Random-Order Model
Authors: Martino Bernasconi
Andrea Celli
Riccardo Colini Baldeschi
Federico Fusco
Stefano Leonardi
Matteo Russo
Venue: ICML 2025 poster (2025)
Keywords: random order
online learning
online classifications
Primary area: theory->online_learning_and_bandits

Abstract: In the random-order model for online learning, the sequence of losses is chosen upfront by an adversary and presented to the learner after a random permutation. Any random-order input is *asymptotically* equivalent to a stochastic i.i.d.~one, but, for finite times, it may exhibit significant *non-stationarity*, which can hinder the performance of stochastic learning algorithms.

While algorithms for adversarial inputs naturally maintain their regret guarantees in random order, simple no-regret algorithms exist for the stochastic model that fail against random-order instances.  

In this paper, we propose a general procedure to adapt stochastic learning algorithms to the random-order model without substantially affecting their regret guarantees. This allows us to recover improved regret bounds for prediction with delays, bandits with switching costs, and online learning with constraints. Finally, we investigate online classification and prove that, in random order, learnability is characterized by the VC dimension rather than by the Littlestone dimension, thus providing a further separation from the general adversarial model.

Online Learning in the Random-Order Model
Martino Bernasconi" 1
Andrea Celli
Riccardo Colini Baldeschi 2 Federico Fusco" *3
Stefano Leonardi
Matteo Russo" *3
Abstract
and matroid selection (Babaioff et al., 2018; Korula & Pál, 2009; Dimitrov & Plaxton, 2012; Ezra et al., 2022), and online approximation algorithms (Gupta & Singla, 2020). However, it has received little attention in online learning, where the standard input regimes are either (i.i.d.) stochastic or adversarial (see, e.g., Lattimore & Szepesvári, 2020),
In the random-order model for online learning, the sequence of losses is chosen upfront by an adver- sary and presented the learner after a random permutation. Any random-order input is asymp- totically equivalent to stochastic i.i.d. one, but, for finite times, it may exhibit significant non- stationarity, which can hinder the performance of stochastic learning algorithms. While algorithms for adversarial inputs naturally maintain their re- gret guarantees in random order, simple no-regret algorithms exist for the stochastic model that fail against random-order instances.
The study of online learning in the random- -oderr model is part of a broader research agenda that explores meaningful models beyond worst-case analysis (Roughgarden, 2020).
Examples of other "intermediate" input models for online learning can be found in Ben-Davis et al. (1997); Slivkins & Upfal (2008); Lykouris et al. (2018); 8); Sachs et al. (2022); Haghtalab et al. (2022); Mazzetto & Upfal (2023).
In this paper, we propose a general template to adapt stochastic learning algorithms to the random-orde order model without substantially affect- ing their regret guaranices. This allows us to re- cover improved regret bounds for prediction with delays, online learning with constraints, and ban- dits with switching costs. Finally, we investigate online classification and prove that, in random der, learnability is characterized by the VC dimen- sion rather than the Littlestone dimension, thus providing further separation from the general adversarial model.
In random-orded online learning, the T loss vectors are generated arbitrarily by some adversary and then undergo a uniform shuffling before being presented to the learner. This input model is some extent intermediate between the stochastic model, where losses are drawn i.i.d. from fixed but unknown distribution, and the adversarial one, where the adversary decides both the losses and the order in which they are presented to the learner.
A classical probabilistic result by De Finetti (1929) (see also De Finetti, 1937; Hewitt & Savage, 1955; Diaconis & Freedman, 1980) sequences of exchangeable random variables implies that sampling without replacement (i.e., the distribution over random -rdeer loss sequences) is asymp- totically indistinguishable from i.i.d. sampling from some fixed distribution over losses!. However, in the standard finite-time online learning framework, the non-stationarity of the random-order model can undermine learning algo- rithms that perform well in the stochastic setting. This observation raises several questions about the random-order model and its relationship with other input models.
1. Introduction
Random order is natural input model for online algo- rithms: the input is generated upfront by an adversary but is presented to the algorithm after a uniform random per- mutation. The random-order model is extensively studied across various areas of computer science and economics, such as optimal stopping problems (Dynkin, 1963; Krengel & Sucheston, 1977; Peng & Tang, 2022), online matching
1.1. Our Results
'Equal contribution 'Department of Computing Sciences, Boc- coni University, Milan, Italy "Central Applied Science, Meta, Lon- don. UK 'Department of Computer, Control and Management Engineering "Antonio Ruberti", Sapienza University, Rome, Italy. Correspondence to: Federico Fusco <fuscof diag. uniromal itt>.
In this paper, we initiate the systematic study of the random- order input model in online learning. Since any realization of random-orde sequences of losses can be naturally cap- tured by the standard adversarial model, it is immediate to see that any algorithm for the adversarial model maintains its guarantees random order. Conversely, any i.i.d. se-
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).
For more details, we refer to Appendix A.

---

Online Learning in the Random Order Model
quence can be simulated by a random-order one by first sampling T losses and then applying uniform permutation. These two considerations show that the random-order model lies between the i..d. and adversarial input model?:
sarial minimax regret is @(T%)), while the stochastic one is @(vT) (Cesa-Bianchi et al., 2013; Dekel al., 2014) We explore a simplified version of SIMULATION based on DACCESSSVVEELIMINATTA
similar to the algorithm by Agrawal et al. (1988), and show that this approach recovers the vT rate in the random-order model.
i.i.d. < random-order N adversarial.
The hierarchy between the three models implies that inves- tigating the random-order model is especially compelling in problems that exhibit a performance gap between the stochastic and adversarial models. In such problems, a natural question is: What happens when we apply an algo- rithum designed for the stochastic setting to the random-order model? One might expect such algorithms to perform rea- sonably well since the adversary can only select the support of the distribution. However, we show an algorithm that be- haves nicely against stochastic inputs, but fails in a carefully designed random-order instance (Section 3). We comple- ment this negative result with a positive one. While we cannot directly apply algorithm designed for the stochas- tic setting to the random-order model, we propose general template, SIMULATION, to adapt learning algorithms from the i.i.d. setting to the random-order model, without signif- icantly affecting their regret guarantees (Section 4). This implies that the minimax regret regimes in the random-order model essentially collapse to stochastic i.i.d. ones. We demonstrate the applicability of our template across mul- tiple problems that exhibit a stark separation between the adversarial and stochastic regimes.
Online Classification. For (binary) classification, there is a well-known separation between statistical (offline) learn- ing' and online learning. While the learnability the former setting characterized by the Sopnik-Chervonenkke (VC) dimension, the latter is determined by the Littlestone dimen- sion (Ben-David et al., 2009). In general, the Littlestone dimension dominates the VC dimension, and there are sim- ple examples (e.g., one-dimensional thresholds) of families with constant VC dimension and infinite Littlestone dimen- sion. In Appendix H, we prove that the VC dimension char- acterizes learnability also in the random-order model, thus providing& a further separation between this model and the general adversarial one. Notably, results similar in spirit to ours have been recently obtained in Haghtalab et al. (2022); Raman & Tewari (2024), where they prove that online bi- nary classification is characterized by the VC dimension even in a non-stationary setting, as long as the adversarial input is smooth (Haghtalab et al., 2022) or the learner has access to good predictions (Raman & Tewari, 2024).
Discussion. On theoretical level, our results have two main implications: (i) the minimax regret rates for random- order and the stochastic model are typically the same, and (ii) it is fairly easy to construct the desired random- -oderr algorithm starting from a stochastic one. These results also have important practical implications: if the order in which the input is presented can be controlled, the same regret rate achievable in the stochastic setting can be obtained by simply shuffling the dataset.
Prediction with Delayed Feedback. The interplay be- tween online learning and delayed feedback has been stud- ied extensively. While many delay models exist, the general finding is that the delay parameter d influences regret bounds additively in the i.i.d. model and multiplicatively in the ad- versarial one (Desautels al., 2012; Joulani et al., 2013; Masoudian et al., 2022). In Corollary 4.4, we show an al- gorithm with Ö(VT + d) regret rate in the random-order model, which qualitatively matches the stochastic result.
1.2. Our Techniques
The Birthday Paradox. We show that algorithms de- signed for the stochastic setting may fail in the randem-order model, by leveraging the birthday paradox (from pool of elements, duplicate appears after about vnn samples). In a pool of T loss vectors, a random-order instance corresponds to uniform sampling without replacement, whereas sam- pling with replacement mimics an i.i.d. distribution. When the support is finite, these processes are statistically distinct (Diaconis & Freedman, 1980).
Online Learning with Constraints. In online learning problems with time-varying constraints there is a strong sep- aration between the adversarial case, where it is impossible to attain sublinear regret and constraints violations (Mannor et al., 2009), and the stochastic case, where Ö regret is achievable (Yu et al., 2017). We present an algorithm (Corol- lary 4.8), based on SIMULATION, that guarantees regret of order Ö O(VT) and zero constraints violation, matching the results for stochastic environments.
SIMULATION.
In contrast to the previous negative result, we develop template, SIMULATION, to adapt stochastic algorithms to the random-order model. It partitions the
Bandits with Switching Costs. In the bandits with switch- ing costs problem, the learning algorithm incurs an addi- tional unitary loss every time it changes action. The adver-
Notee, here statistical (offline) learning is equivalent to stochas- tic online learning, due to the standard online-to-offlin reduction.
For a formal proof, see Appendix
2

---

Online Learning in the Random Order Model
time horizon into log T geometrically increasing windows. At the start of each window, past data is used to simulate an i.i.d. distribution matching the expected values of the unddom-order instance, allowing the algorithm to train in an i.i.d. setting without incurring real loss. The action fre- quencies during training are then used on the actual instance within the current block. The analysis leverages that sam- pling without replacement, even if statistically distinct from ii.d. sampling, concentrates around the same mean.
random-order model are generated by an adversary and are presented to the learner in random order. The adversary
generates a (multi-)set of loss vectors hg E [0, 1J2, then they are presented to the learner uniformly at random, i.e., a permutation ' is drawn and the loss at time is (()()) = 4- We adopt the notation [r]] to denote the set {1, 21, ,,), and we denote by A. the n-dimensional probability sim-
plex. The model and results for the online classification are deferred to the Supplementary Materials (Appendix H).
1.3. Further Related Work
2.1. Prediction with Delayed Feedback
Random-order Online Convex Optimization. Random- order inputs in online convex optimization has been studied in Garber et al. (2020) and Sherman et al. (2021). Their main result is that such random-order instances allow for logarithmic regret even if the single losses are not strongly convex, as long as the cumulative loss is strongly convex.
In Prediction with Delayed Feedback, the loss vectors are revealed to the leamee after known and fixed delay d. More precisely, for any t, the learner only observes the loss vector f, after d time steps. We have the following definition of (expected) regret of algorithm A choosing actions a against the random-order input S of losses fI,...,er:
T Σ ((aa)) 1=1
T
Online Combinatorial Problems in Random Order. Random-order inputs have also been studied in the context of online combinatorial optimization in Dong & Yoshida (2023). They consider approximate follow-the-leader algo- rithms and prove that when the offline optimization algo- rithm has low average sensitivity (i.e., the average impact of single points on the output is small, notion introduced in Varma& & Yoshida (2023),, then the offline-to-online re- duction carries over also in the random-order model.
= E
min Σ 4((a)
(I)
aEIM t=1
We denote with regret of the algorithm A its worst-case regret, i.e., sups (r, Note, the benchmark i.e. the performance of the best fixed action in hindsight - is not influenced by the realization of the random permuta- tion (in fact, we can equivalently write the benchmark as min, Σ he(a)). There is a plethora of delayed feedback models studied in the literature; for the sake of simplicity, here we adopt arguably the simplest one with fixed and known delay d, as in, e.g., Masoudian et al. (2022). With minimal effort, our results also apply to other models, e.g..
Online Learning with Long-Term Constraints Online learning under time-varying constraints was first studied by Mannor et al. (2009), who showed that achieving both sub- linear regret and constraint violations is impossible when costs and rewards are linear but adversarially generated. Therefore, significant gap exists between the stochas- tic setting, where Ö(VT) regret and constraint violation are achievable (Yu et al., 2017; Badanidiyuru et al., 2013; Agrawal & Devanur, 2014), and the adversarial setting, where guarantees typically take the form of no-a-regret bounds, with a E (0, 1) representing the competitive ratio (Immorlica et al., 2022; Castiglioni et al., 2022a;b; Kessel- heim& & Singla, 2020; Bernasconi et al., 2024). Some studies achieve improved results under adversarially generated con- straints, but at the cost of using a weaker baseline, such as static regret (Sun et al., 2017). Another line of work (Balseiro et al., 2023; Fikioris & Tardos, 2023) bridges the gap between stochastic and adversarial settings by making assumptions about the environment's evolution over time.
random delay or unknown delay.
2.2. Online Learning with Constraints
We consider a setting similar to Balseiro et al. (2023) in which the learner has m resource-consumption constraints. At each I, the learner plays I2 E As and subsequently observes a reward vector rz E [o, 1] and m cost vec- tors (CI,t,...,Co)
E [0, 1| one for each available resource." 4 The objective of the learner is maximize the cumulative rewards ΣL= r/.
2t while guaranteeing that, for each j E [m], Ei= JT I B, where B is the available budget for each resource. The per-iteration budget is de- fined as p = B/T. We assume that there is a known action Ø such that (2) = 0 for all j and t (this can be thought as a "skipping turn" action, usually employed in the Bandits with Knapsack literature, see e.g., Badanidiyuru et al. (2013); Immorlica et al. (2022)).
2. Model
'In the literature on Online Leamnnng with Constraints and Bandits with Knapsacks, it customary to use rewards instead of losses, and we follow the same notation here.
A learner repeatedly chooses one of actions over a time horizon T. At each time step t, the loss associated to ac- tion a is denoted by (a) E (0. 1]. The loss vectors in the
*Assuming that all budgets are the same comes without loss of generality. See discussion in Immorlica et al. (2022).
3

---

Online Learning in the Random Order Model
In the random-order input model, an instance & is repre- sented by multi-set of T tuples (r; (1,,aa.... CCm) presented to the learner in uniform random order. We denote with F the average reward of the tuples in S, and, for each re- source j. we let 6j be its average consumption. The natural benchmark for the problem is given by the solution to the following LP (see, e.g., Immorlica et al. (2022)):
against random-order one. We consider the basic Predic- tion with Experts problem, where the learner immediately observes the loss vector & upon playing de. The regret in the stochastic setting is defined with respect to the expected per- formance of the best fixed arm, while in the random-order model it is defined as in Equation (1) (see also Appendix B for a comparison on the regret definitions).
{ maxrEA. (T, s.t.
Consider the following simple BIRTHDAY- TEEST algorithm: it repeatedly plays the first action until certain stopping time 7 is realized, after which it starts to run some no-regret algorithm such as FOLLOW-THIE THEN--THE--EDDE (Hannan, 1957) from scratch.? ? The stopping time T is defined as the first time step when one of two things happens: either (1) &f (4T, for = ... T), t. Intuitively, up to time T, the algorithm's 's behavior while playing action 1 is essentially test to determine whether the losses for this action are drawn uniformly at random from the set {1/r i- 1..,.....TT
OF, CI...., 2m² 3m)=
(c),)) S [m
With OPTLP, we denote the solution to the above LP instan- tiated with the average rewards and costs computed from S. Then, we define the regret in this setting as
or (1) = (1) for some s o
R3 (A.)) = TTOPTTP Σn 2
1=1
where 7 E [T] is the stopping time of the algorithm (i.e., the time in which the first of the m resources is fully depleted). Once T is reached, the algorithm plays 2 for the remain- der of the time horizon. Therefore, our algorithm enforces resource consumption constraints strictly, similar to what happens in bandits with knapsacks (Immorlica et al., 2022). This is stronger requirement than ensuring sublinear con- straint violations, which is the typical approach in online learning with long-term constraints (Mannor et al., 2009; Yu et al., 2017; Castiglioni et al., 2022b).
If the underlying distribution is ii.d, then T realizes pretty soon, while it never does under the random-order model. This result is based on folklore calculations related to the birthday paradox, but we report a self-contained proof for completeness in Appendix D.
Lemma 3.1. For any ii.d input and T sufficiently large, it holds that E [T] S 2VT.
Consider now the performance of BIRTIIDAY-TEST against any i.i.d. input: it suffers at most constant instantaneous re- gret up to the stopping time T (for an overall expected regret of 4VT, as proved in Lemma 3.1) and then run FOLLOW- THEELEADER, for an overall regret rate of (VTToog'
2.3. Bandits with Switching Costs
In the bandit with switching costs problem, at the end of each time i, the algorithm only observes its loss (a())) and suffers an additional unitary loss every time changes ac- tion. For instance, this is the same model studied in Cesa- Bianchi et al. (2013); Dekel et al. (2014). The goal is to devise a learning strategy that minimizes the suffered loss or, cquivalently, minimizes the regret with respect to the best- fixed action in hindsight. We then have the following defi- nition of (expected regret) of algorithm A choosing actions at 6 against the random- madder-orderiie input S of losses f,,.... ly:
It turns out that there exists a random-order instance that fools BIRTHDAY-TEST. The instance has only two actions: action 1, whose losses are given by a permutation of the set (t/T, for i = 1, yields 0 loss. BIRTIDAY-TEST on this instance always plays the first action, accumulating regret at each time step (as r will never realize by definition), for a cumulative regret of (2T)). All in all, we have proved the following result.
... ..., T), and action 2, which always
T Σ (I
(A,
(a) aE(k]
min
Theorem 3.2. Consider the Prediction with Experts prob- lem. BIRTHDAY-TESS exhibits O( O(yTlog any stochastic i.i.d. instance, but there exists random-order instance against which it suffers Q(T) regret.
log T') regret against
We denote with regret of the algorithm A its corst-case regret, i.e., supg Rr (A. Note, the benchmark is not influenced by the switching cost or by the random permu- tation (in fact, we can equivalently write the benchmark as minae[M] Dinhh(a)
4. A General Template: SIMULATION
In this Section, we present a general reduction template: SIMULATION. We then show how this general idea can be applied to prediction with delayed feedback, in online learning with constraints, and bandits with switching costs.
3. The Birthday Paradox
In this section, we analyze a learning algorithm that exhibits the no-regret property against any stochastic input but fails
We only need the algorithm to be no-regret on stochastic i.i.d. inputs.
Forr simplicity, we define +T+1 = ar.
4

---

Online Learning in the Random Order Model
Algorithm 1 1
Algorithm 2 *
Input: stochastic algorithm for i = 2...2...... log T do
Input: stochastic algorithm A
Environment: actions, time horizon T
(i) fid-ify past data Construct a distribution on past data D;
Model: full feedback model with delay d.
Play any action at time 1
(ii) Train A on simulated past Run algorithm A over 2' i.i.d. samples of DD;
Initialize multiset O = {(1}
for i = 0, 1, 1,2,..... [log 7 do
(iii) Test over new data
Let 2, be the uniform distribution on O (iid-ify past]
Let na) be the times that A plays action a on D;
Run A over 2' i..d. samples of D;
{Training]
for t 2 + 1, + .......2 2 do
Let (a be the number of times that A plays
Play action at (m.(1)/2i,. ,...... mx(6)/2))
< i. dd+22 2
(Beginning of 7th block]
end for The SIMULATION Template
for f = f4 t + 2,..,,, + 2' do
( Play action at (ni(1)2''. ..... (x(2)/22)
(Test)
Add loss E to O when revealed i T, then terminate
SIMULATION. The core idea of our approach (see the pseudocode for details) is to divide the time horizon into blocks of geometrically increasing length, performing three key operations within each block. At the beginning of the i-th block, which has a length of roughly 2', we look at the feedback received during the previous time steps and con- struct a distribution D; (for instance, by uniform sampling on the previous 2 samples). Next, we "train" our stochastic algorithm A on D, (without incurring real losses). Finally, we use A's observed performance over D; to play against the actual losses in the time block. We observe that SIMULA- TION is not a black-box reduction but general "recipe" for adapting stochastic algorithms to the random-order setting.
end for
Play arbitrarily for the next d time steps end for SIMULATION for delayed feedback
previous time blocks, which are 2'. Therefore, sampling according to D, yields an unbiased estimator of the aver- age loss in the previous blocks. This is formalized in the following Lemma.
Lemma 4.1. Fix any sequence of losses and time block i. Then we have:
EEND ((aa)=51) 1
-EEEEE ((aa) Va [k]. S'iHEET,
To build high-level intuition on the effectiveness of SIMU- LATION, can look at its performance when the underly- ing stochastic algorithm is BIRTHIDAY-TEST. By fictitiously letting play SIMULATION against distribution D; we trigger the stopping time r so that BIRTHDAY- TEST starts playing as FOLLOW-THE. LEED-EE on the testing part.
In the analysis of SIMULATION for prediction with delayed feedback, we employ a generic stochastic routine A which is guaranteed i.i.d. regret bound of Rith (A) against any stochastic input of length T'.
Theorem 4.2. Consider the problem of online prediction with delayed feedback in the random-one cadde model, and let d be the delay parameter. Rumning SIMULATION for de- layed feedback with stochastic routine A (SIM-A) yields the following regret bound:
4.1. Predictions with Delayed Feedback
In the prediction with delayed feedback model, the learner has access to the loss vector after d time steps. To specialize the SIMULATION template to this model, we need to account for the delayed feedback by adding a buffer of d time steps between the blocks, allowing enough time receive the feedback corresponding to the previous block (we refer to the pseudocode for further details).
(SIM-)) & Tog T + dlogg T El Ridd (A).
Proof. Fix any input sequence = (hi,..... hrr). any real- ization of the permutation {f,, } and denote with at the corresponding best action (a* only depends on S, not the specific permutation). For any block i, the stochastic algorithm A is trained over 2' i.i.d. samples from D,, and the empirical frequencies (a()/22+ are then used to play in T.. For any action i, denote with (a(a) the gap between the loss of action a and that of action a* according to D,:
At the beginning of the generic time block i, the distribution D; that is used to simulate past data is simply the uniform distribution over all the loss vectors observed in the blocks before the thh which are contained in the multiset O (the the
losses observed in i d time steps corresponding previous buffers are discarded). To simplify the notation, we denote with T; the time steps in the zth time block, i.e.,
(a) EL-D, [((a) ((a))=((a))]
T; = (.,,..,, 4 + 2 1}, where t, 2 +i- d.
From the guarantees on the regret bound of A, we get
Fix any sequence of losses and any block i. At the beginning of T,, the multiset O contains all the losses observed in the
Σ E [mz(aa) A.(a) S (idd
(2)
5

---

Online Learning in the Random Order Model
where the expectation is with respect the randomness in the i.i.d. sampling from D;-
Claim 4.3. For any block i, the corresponding clean event
is realized with probability least 1 - 1/T.
The gaps (a) induced by the distribution D; are related to the empirical gaps (a) experienced in the previous time blocks by Lemma 4. In partieular, for any (a(a) (the
Then, conditioning on the clean event &,, we can improve the bound in Equation (4):
superscript stands for "past") we have:
E [e(((())) - -(((")) Riji
A7(a)= 2
ΣΣ (4(a) (e(a*))
(By definition)
5 2' max (a(a) A7(a)
"EiTETY
BENDD [e(()) {(a")]
(By Lemma 4.1)
$ 2 (a)) Af(a)), Aa)) Ax(a)))
= -.(aa)
(By definition of A.())
S 4 T 25.
Plugging in the above equality into the stochastic regret guarantees as in Equation (2), we get:
By removing the conditioning w.r.t. the clean event (and using the probability bound as in Claim 4.3 and the fact that the regret suffered under the bad event is at most 2'), we get:
Ebma(a))4(()) < R (A).
(3)
While the above inequality characterizes the performance of SIMULATION if run on "past" losses, we need to relate it to the "future" or actual ones, i.e., the ones appearing in time block i. We denote with (a) the gaps in the current time block. Let's now look at the actual regret suffered by the algorithm during T::
Σ (E(G(()) (((aa))))))))))))))))))))))))( R (A) + 5 bolog T 2'. tE::
We are ready to bound the overall regret: for any time block, we have the above inequality, while for the log I buffers, we suffer an overall regret of at most dllog T. All in all, we have that the regret Rr of SIMULATION for delayed feedback with routine A is at most:
Σ IE
(E [a())] - le(a"))
log T'
Σ E [n((a)] Σ (4((a) (((a))
(By design)
RT
S
Rid + logT 2 2
2
EE.,
1=0
Σ Bmi (a(a)
(By definition of (a)
log T
S 5 + d T
Ridd (A).
Σ (m,(a) (7(a) + Σ E [m.(aa) (Ar(a) (()))))(())))
This concludes the proof.
< (A) 2' max (a) - AT(a)),
(4)
In particular, if we instantiate algorithm A to be FOLLOW- THE-LEADEE we get the following guarantees.
where the last inequality follows because of Equation (3) and the fact that Eme[k] (a) = 2'. So far, our argument works for any input model, as the sequence of losses was arbitrary; now it's time to exploit the fact that random-order sequences exhibit concentration. In particular, we want to argue that, for any block i and action a, both the past and future empirical gaps (a) and (a(a) are close to the actual gap A(a), where
Corollary 4.4. There exists algorithm for online predic- tion with delayed feedback in the random-orad order model that enjoys an O(yTlog T + dlog T) regret bound.
4.2. Online Learning with Constraints
In the Online Learning with Constraints model, the learner has to play against an environment in which each action a E [k] has an associated reward and a vector of costs. We analyze the problem within the random-order model and show that, in this setting, is possible achieve regret guar- antees comparable those in the stochastic case, despite impossibility results for the adversarial setting (Mannor et al., 2009).
1 Σ (na(a)-h((a")) ((a)
Σ (((a)))((a')) E
= T
T RE|21
We introduce the precision 6; = /o0 sponding clean event E,:
log T/2 and the corre-
E, (m)) A(a)., (a) - A(a)) s e,, va).
Here, we show how we can adapt SIMULATION in the pres- ence of long-term constraints. The main difficulty in adapt- ing SIMULATION this setting the fact that the costs
We can show that such event is realized with high probability (see Appendix E for omitted proofs).
6

---

Online Learning in the Random Order Model
Algorithm *
sollowing regret bound with probability at least
8,
Input: stochastic algorithm A, budget B, parameter Environment: K actions, time horizon T Play any action time
log( MAT
T lllog
(
(iak
RT(SSM-A) 00
p²
P
Initialize 0= fr.,c........ for i = 0, 1,,2,, 2, ..... .og T do
log T
Rigl (A,
Let D, be the uniform distribution over (iid-ify past) Run algorithm A over 2' i.i.d. samples of D; with budget p- 10-0% 0 and 8' = 1og T {Training) Let (a) be the number of times that A plays action a. Compute [a) as nx(m)/2² for each action for t = 2' 2, +2 ...,, 2 1 (Play against the actual sequence) do
+
where 8' E Ö(8),
Proof. Fix any sequence S E [0,1] [.1]xxxxmtt> and any per- mutation {(re, Ct,1..... c, beem Let x" be the solution to OPT For each time block we are going to define the following quantities: r; Σi I't is the empirical mean of the rewards on the "next" block, r. r===== = Ei= Pt is the empirical mean of rewards in the "past" block, and F; [r] is the expected reward w.r.t. Dj. Similarly define ci.j. R. and G.j for each resource E [m]] Clearly, Fg rf and Es,j = =C...-
Play 24 and subsequently add (re, ct..... to O end for end for SIMULATION for Online Learning with Con- straints
impose constraints on the entire time horizon, while SIMU- LATION naturally works on each block independently.
We can define the benchmark OPTLP the past block as max x' TT r zED;
To run SIMULATION in this setting, we need access to an algorithm A for stochastic online learning with constraints (see, c.g., Castiglioni et al., 2022a; Bernasconi et al., 2024). In particular, in stochastic environment with mean reward i and mean costs (ō....., m A guarantees a regret upper bound, with probability at least 1 - 5, of
s.t.
max D T JE/m]
S p 2. = Ps.
where E; v 6- 2- (T)) Ō(V2-1). We
define the event & = 11 - Fl I 4. Ir; Flloo I
ei, ||لاا - C |> I < 1|a, -gll S Vj E [m]]. From now on, we condition on the event &,, which we show to hold with high probability with respect to the permutation.
T OPOPLLr(F.0 C1. ....,,,.................. C Σ
TTa xn S Rhi (A,
The regret of SIMULATION can be written as
where 7 denotes the first time in which a resource j is fully depleted, that is Ei= The > pT.
TogT
2
Ry (SIM-A,,)) =
Σ
7 x
Σ
1=2'+1
In each block i we train A on i..dd samples (riid. jid.i ..... Hid.t),
D..9 Then, we take the empirical frequency of play x; obtained in the training step and use it against the actual environment in the time block 2 + 1, 1,..,,2--1, 2"-1
Σ
2
(F x² - r. rTTx))
(5)
where the second equality holds thanks to the fact that we are playing the fixed learned distribution 2; in the i-th block, which is the one learned while playing against D.
Crucially, during each training phase, we instantiate AA with a slightly reduced per-iteration budget of p Ō(v2-t). This allows us to control concentration terms in the analysis. Then, one of the main challenges is proving that this budget rescaling does not significantly affect the guarantees of the algorithm A during the simulation phase.
We only consider blocks with index i > i" where we set i' = (logg(lg log())/))/p)) otherwise we would have ps < 0 which is the first block for which p: = p-2e; 2 p/2. For each block i < it we suffer linear regret (since we are forced to play the null action Ø), and this contributes to Σ 2 E 0112²) additional regret term
Theorem 4.5. Consider the problem of online learning with long-term constraints in the random-order model. Running SIMULATION with stochastic routine A (SIM-A) yields the
The no-regret properties of A guarantee that, with probabil- ity at least 1 8':
We assume that A guarantees that p + Rijdd / (A,, p) is mono- tone decreasing. Note that regret itself respects this property (a lower budget implies weaker performance). We assume upper hound follows the same behavior, which is true for all known algorithms for the problem.
the
2' OPT
LP
Σ 1=1
x. Tr. 2 (xt xx
< Rild (A,p - 2. 2.e.),
Too simplify the notation we drop the block index i when clear.
7

---

Online Learning in the Random Order Model
where of is the solution to OPTi, and
resource j E [m] are given by:
Mog
2
Togt1 1]
E'
Tg Aj S (p- Ei) 22
Jid
(6)
Σ
Σ
2' 02
3g
C
I2 Co.j
2=
which holds for all & E [2t] and for all j E [m]
[ogt]
Tog
Σ ==1
2
c.
24 +
2'. (ct.s - [,,) 24
Consider one term of the regret decomposition of Equa- tion (5):
[lg tl
llg
2
24
2'
(8)
FT - :; I4 = (FTx* x²
r xt) + (r!"
x -r; x²))
Ridd&
A, p.)
where the last inequality holds by conditioning on all &.. To analyze the first term, we can consider the following se- quence of random variables Z E'= ( G..) Fgg-
< (F x=' - T. 2 +
+ (F+ - -r:) (7)
2
where the last inequality holds by the regret properties of A. Now, we have to analyze the first and last terms of the inequality above. The last term is easy to bound. Indeed, conditioning on & it holds that
This a martingale sequence (since ED, [aag = C. and has differences bounded by 1) with Z 0 and thus, by Aruma-Hoeffdinng we have that with probability at least 3m log 7 with respect to the randomness of D;;
(F: (F:- S ||+ Fllox + ||F rillz0 S 20:-
2
=
lid s.j
245) 2 2'
Bounding the first term is trickier as it is equivalent to bound- ing the difference between the values of two LPs. Indeed, it can be rewritten as OPTLP - OPTLp- The following claim (whose proof can be found in Appendix F) shows that this difference is not too large.
and thus for all i E [log T) and j E [m]]
2
2 c. 2te
T Caa
It. S 2'6 2' 2 2.c e2)
with probability at least 1 - 8/3 (by union bound on all E [log T] and j E [m]), and the second inequality holds thanks the properties of A (Equation (6)). Plugged back into Equation (8) get that
Claim 4.6. For all i > it, under the event Ei, we have that
PPTIP-OPHH S 1+ 1+-1 3) )
[log $1
x. Ca.j
(2'4 + 2' + 22 - 2.)))) S pt.
Plugging everything back into Equation (7) get that, conditioning on the events E,,
Finally, prove that all of the previous results hold with probability at least 1 - 8. We have three sources of random- ness; the first is due to the permutation, which is encoded by the events &,. The following claim proves that these hold with high probability." 10
T
RT
4
3 1 p)
+ 26; + Rijd."" (A, (i)
+1
log( mkT p²
6
log T
log T
Rid 8' (A,
Claim 4.7. The event NooTT & holds with probability at least 8/3.
00
+
1=1
1=
log( MkT
Tlog
mk))
log T
50
Rid.
(A, 2:
A, 6)
Second, we have the randomness of the i.i.d. sampling. By Azuma-Hoefiding inequality, we proved that this holds with probability at least - 5/3. Finally, the algorithm A has guarantees with probability 8' = 1 - 6/3 log(T) each time is run on a block i. By a further union bound, we have that these events hold jointly with probability 1 - 8. This concludes the proof.
1
1=1
where we used that - I2jid. (A, p) has to be monotone decreasing and positive. Moreover, note that the probability measure is the one induced by the random permutation and does not depend on the algorithm.
10e proof similar the proof of Claim 4.3 by relying on Theorem C.I with additional union bounds on the constraints.
Next, we analyze the violations, which for each and each
8

---

Online Learning in the Random Order Model
In particular, we can instantiate A to be the algorithm of Castiglioni et al. (2022a) that guarantees that Ri (A. p) E 00/e/Tlogg ( and we can prove the following:"'
Algorithm 4 *
Environment: A actions and time horizon T Model: bandit feedback with switching costs ((a) + 0, sı(a) < 0, for all actions
Corollary 4.8. There exists an algorithm for online learning with long-tern constraints for the anndom-orde model with regret 02//² + vT/p with high probability.
A <- [k] set of active actions
1o < [log k.
for t = 1....2". 2 do
Our reduction maintains the same regret guarantees as A. but for an extra 1/0² instead of l/2. However, this term does not depend on T, excluding poly-logarithmic factors.
Play at = modulo &
{Play each action once}
r((a)) + n((a)) +1
{(az) t m)as) E.=1 p(sla)
end for
4.3. Bandits With Switching Costs
for i = io.... log T do
Let t v 10k log T 2- {Precision for block i}
We present an algorithm for the Bandits with Switching Costs problem that suffers O(VT) regret in the random- order model, as opposed to the adversarial setting, where the minimax regret rate is O(T%/s (Dekel et al., 2014).
for a E A do
Play action action for 21/ rounds
Let l(a) mोn E - [(a.=u) La(a)
end for
Our algorithm
Play last active action a up to time min min - 1,
maintains a set of active actions and proceeds in geomet- rically increasing time blocks. In each time block, it simply plays in a low-switching round-robin way the ac- tions that are still active; then it updates the confidence bounds on the actions played and discards the ones that are proved to be, with high probability, suboptimal. We refer to the pseudocode for more details. Note, SIMULATION- JUCCESSIVE-ELLMIAATOO is an application of the SIM- ULATION paradigm to this problem, using as stochastic subroutine
Update accordingly naa) and E(a)
Remove from A all actions a such that
((a) - > min (A(a') + ee) d'EA
end for SAMULATIOO-SUCCESSSO E ELIMINATION
the Ologg phases. Therefore, the overall switching cost is always O(k T). We move our attention to the regret incurred by playing suboptimal actions. We can argue by concentration for random-order sequences (see Appendix C) that in the generic phase only actions with overall suboptimality gap O(q-1) are still active, with high probability. Moreover, once again by concentration, we can argue that these actions' actual (permuted) losses during the generic block are "close" to their actual suboptimality gap. Summing up for all blocks and plugging in our choice of the precision parameters 6; yields the desired regret bound. U
Slivkins, 2019): running SUCCESSIVE ELLMINAATONO (e.g., Chapter 1 of on the i.i.d. version of past data quickly converges to playing round-robin on the active actions. For simplicity, we analyze this simpler version of the algorithm, already specialized for the routine SUCCESSIVE EL ELMINATION.... We note that this algorithm is similar to low-switching algorithm in the literature (Agrawal et al., 1988) that achieves VT regret in the stochastic case. It shares the geometrically increasing blocks and the idea of playing each active arm in contigu- ous intervals in each block; the main difference is that they use UCB as a routine to choose the next action, while our to simplify the
5. Conclusion and Further Directions
algorithm uses DECCEESSIVEEELMIINEEO analysis for the random-order input model.
We study online learning in the random-order model, which lies between the adversarial and i..dd settings, contributing to the analysis of problems beyond worst-case instances. We show that stochastic algorithms may fail in the random-order model and, to address this, we propose SIMULATION, a general template for designing effective random-order algo- rithms. We study various relevant online learning problems and prove that random-order and stochastic inputs share the same minimax regret, improving on the adversarial case. While SIMULATION successfully provides black-box reduc- tions for full feedback, the bandit model still requires a more specialized approach. Providing black-box constructions for broader feedback settings, including bandit feedback, is an interesting avenue for future research.
We state here the main result concerning SIMULATION- SUCCESSIVE ELIMINATION. BUCLESSIVEELLLMMNAATON We defer the complete proof to the Supplementary Materials (Appendix G).
Theorem 4.9. There exists an algorithm for bandits with switching costs in the random-orde order model with regret WWVKTlog' T).
Proof Sketch. switches actions at most Okk) times during each one of
The algorithm of Castiglioni et al. (2022a) is, in its turn, instan- tiated with WEE.INE--RROO---- DESCENT with negative entropy as both the primal and dual algorithm.

---

Online Learning in the Random Order Model
Acknowledgements
Balseiro, S. R., Lu, H., and Mirrokni, V. The best of many worlds: Dual mirror descent for online allocation prob- lems. Operations Research, 71(1):101-19, 2023.
The work of MB, AC, FF, SL, and MR was partially funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union the European Re- search Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
Ben-David, S., Kushilevitz, E., and Mansour, Y. Online learning versus offline learning. Muchine Learning, 29: 45-63, 1997.
Ben-David, S., Pál, D., and Shalev-Shwarzz S. Agnostic online learning. In COLT, 2009.
AC is partially supported by MUR PRIN 2022 project 2022R45NBB funded by the NextGenerationEUU program and by the ERC grant Project 101166666 PLA-STEER. FF, SL, MB and MR are also partially supported by the FAIR (Future Artificial Intelligence Research) project PE0000013, funded by the NextGenerationEU program within the PNRR-PE-AI scheme (M4C2, investment 1.3, line on Artificial Intelligence). FF, SL, and MR are sup- ported by the Meta/Sapienza project on "Online Constrained Optimization and Multi-Calibration in Algorithm and Mech- anism Design" and by the PNRR MUR project IR0000013- SoBigData.it SL and MR are also partially supported by the MUR PRIN grant 2022EKNE5K (Learning in Markets and Society).
Bernasconi, M., Castiglioni, M., Celli, A., and Fusco, F. Beyond primal-dual methods in bandits with stochastic and adversarial constraints. In NeurIPS, 2024.
Bousquet, O., Boucheron, S., and Lugosi, G. Introduc- tion to statistical learning theory. In Advanced Lectures on Machine Learning, volume 3176 of Lecture Notes in Computer Science, pp. 169-207. Springer, 2003.
Castiglioni, M., Celli, A., and Kroer, C. Online learning with knapsacks: the best of both worlds. In Proceedings of the 39th International Conference on Machine Learn- ing, volume 162 of Proceedings of Machine Learning Research, pp. 2767-2783, PMLR, 17-23 Jul 2022a.
Impact Statement
Castiglioni, M., Celli, A., Marchesi, A., Romano, G., and Gatti, N. A unifying framework for online optimization with long-term constraints. In NeurlPS, 2022b.
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Cesa-Bianchi, N., Dekel, O., and Shamir, O. Online learning with switching costs and other adaptive adversaries. In NIPS, pp. 1160-1168, 2013.
References
De Finetti, B. Funzione caratteristica di un fenomeno aleato- rio. In Atti del Congresso Internazionale dei Matematici, Tomo VI, pp. 179-190, 1929.
Agrawal, R., Hedge. M., and Teneketzis, D. Asymptotically efficient adaptive allocation rules for the multiarmed ban- problem with switching cost. IEEE Transactions on Automatic Control, 33(10):899-900 1988.
De Finetti, B. La prévision: ses lois logiques, ses sources subjectives. In Annales de I l'institut Henri Poincaré, vol- ume 7, pp. 1-68, 1937.
Agrawal, S. and Devanur, R. Bandits with concave rewards and convex knapsacks, In EC, pp. 989-1006. ACM, 2014.
de Finetti, B. Sulla proseguibilità di processi aleatori scambiabili. Rendiconti Istituto di Matematica dell'Universite di Trieste. An International Journal of Mathematics, 1969.
Alvarez-Melis, D. and Broderick, A translation of "the
characteristic function of random phenomenon" by bruno de finetti. arXiv e-prints, pp. arXiv-1512, 2015.
2015.
Dekel, O., Ding, J., Koren, T., and Peres, Y. Bandits with switching costs: T//s regret. In STOC, pp. 459-467. ACM, 2014.
Babaioff, M., Immorlica, N., Kempe, D., and Kleinberg, R. Matroid secretary problems. J. ACM, 65()):35: 2018.
Desautels, T., Krause, A., and Burdick, W. Parallelizing exploration-explootttion tradeoffs with gaussian process bandit optimization. In ICML, 2012.
Badanidiyuru, A., Kleinberg, R., and Slivkins, A. Bandits with knapsacks. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 207-216. IEEE, 2013.
Diaconis, P. and Freedman, D. Finite Exchangeable Se- quences. The Annals of Probability, 8(4):745 - 764, 1980.
10

---

Online Learning in the Random Order Model
Dimitrov, N. B. and Plaxton, C. G. Competitive weighted matching in transversal matroids. Algorithmica, 62(1-2): 333-348, 2012.
Korula, N. and Pál, M. Algorithms for secretary prob- lems graphs and hypergraphs. In ICALP (2), volume 5556 of Lecture Notes in Computer Science, pp. 508-520. Springer, 2009.
Dong, J. and Yoshida, Y. A batch-to-online transformation under random-order model. NeurIPS, 2023.
Krengel, U. and Sucheston, L. Semiamarts and finite values. Bulletin of The American Mathematical Society, 83(10): 627-629, 1977.
Dynkin, E. B. The optimum choice of the instant for stop- ping markov process. Sov. Math. Dokl., 4(01))627-629, 1963.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Ezra, T., Feldman, M., Gravin, N., and Tang, Z. G. General graphs are easier than bipartite graphs: Tight bounds for secretary matching. In EC, pp. 1148-1177. ACM, 2022.
Littlestone, N. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Mach. Learn., 2(4):285-318; 1987.
Fikioris, G. and Tardos, É. Approximately stationary bandits with knapsacks. In COLT, volume 195 of Proceedings of Machine Learning Research, pp. 3758-3782. PMLR, 2023.
Lykouris, T., Mirrokni, V. S., and Leme, R. P. Stochastic bandits robust to adversarial corruptions. In STOC, pp. 114-122. ACM, 2018.
Mannor, S., Tsitsiklis, J. N., and Yu, J. Y. Online learn- ing with sample path constraints. Journal of Machine Learning Research, 10(3), 2009.
Garber, D., Korcia, G., and Levy, K. Y. Online convex opti- mization in the random order model. In ICMI,, volume 119 of Proceedings of Machine Learning Research, pp. 3387-3396. PMLR, 2020.
Masoudian, S., Zimmert, J., and Seldin. A best-of-both- worlds algorithm for bandits with delayed feedback. In NeurIPS, 2022.
Gupta, A. and Singla. S. Random-order models. Be- yond the Worst-Case Analysis of Algorithms, pp. 234-258. Cambridge University Press, 2020.
Mazzetto, A. and Upfal, An adaptive algorithm for learn- ing with unknown distribution drift. In NeurlPS, 2023.
Haghtalab, N., Han, Y., Shetty, A., and Yang, K. Oracle- efficient online learning for smoothed adversaries. In NeurlPS, 2022.
Peng, B. and Tang, Z. G. Order selection prophet inequality: From threshold optimization to arrival time design. In FOCS, pp. 171-178. IEEE, 2022.
Hannan, J. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, 3(2):97-139, 1957.
Raman, V. and Tewari, A. Online classification with predic- tions. In NeurIPS, 2024.
Hewitt, E. and Savage, L. J. Symmetric measures on carte- sian products. Transactions of the American Mathemati- cal Society, 80(2):470-501 1955.
Roughgarden, T. (cd.). Beyond the Worst-Cass Analysis of Algorithms. Cambridge University Press, 2020.
Sachs, S., Hadiji, H., van Erven, T., and Guzmán, C. Be- tween stochastic and adversarial online convex optimiza- tion: Improved regret bounds via smoothness. In NeurlPS, 2022.
Hoeffding, W. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc., 58-33-3,, 1963.
Sauer, N. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145-147, 1972.
Immorlica, N., Sankararaman, K., Schapire, R., and Slivkins, A. Adversarial bandits with knapsacks. Journal of the ACM (JACM), 69(6): 2022.
Serfling, J. Probability inequalities for the sum in sam- pling without replacement. The Annals of Statistics, pp. 39 48, 1974.
Joulani, P., György, A., and Szepesvári, C. Online learning under delayed feedback. In JCML (3), volume 28 JMLR Workshop and Conference Proceedings, pp. 1453-1461. JMLR.org .or.. 2013.
Shelah, S. combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247-260, 1972.
Kesselheim, T. and Singla, S. Online learning with vector costs and bandits with knapsacks. In COLT, volume 125 of Proceedings of Machine Learning Research, pp. 2305. PMLR, 2020.
Sherman, U., Koren, T., and Mansour, Y. Optimal rates for random order online optimization. NeurIPS, pp. 2097-2108, 2021.

---

Online Learning in the Random Order Model
Slivkins, A. Introduction multi-armed bandits. Found. Trends Mach. Learn., 12(1-2):1-22 2019.
Slivkins, A. and Upfal, E. Adapting to a changing envi- ronment: the brownian restless bandits. In COLT, pp. 343-354. Omnipress, 2008.
Sun, W., Dey, D., and Kapoor, A. Safery-aware algorithms for adversarial contextual bandit. In ICML, volume of Proceedings of Machine Learning Research, pp. 3280- 3288. PMLR, 2017.
Vapnik, V. N. and Chervonenkis, A. Y. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Applications, 16(2):264-280, 1971.
Varma, N. and Yoshida, Y. Average sensitivity of graph algorithms. SIAM Comput., 52(4)11039-18811,000 2023.
Yu, H., Neely, M. J., and Wei, X. Online convex optimiza- tion with stochastic constraints. In NIPS, pp. 2017.
12

---

Online Learning in the Random Order Model
A. The De Finetti Theorem
The De Finetti Theorem states that any (infinite) sequence of exchangeable" random variables behaves (in distribution) as a mixture of i..d. distribution. This result has been initially proven for binary random variables De Finetti (1929) (a translated version is available on the arXiv Alvarez-Melis & Broderick (2015)), and then generalized real random variables in De Finetti (1937); Hewitt & Savage (1955). However, this representation theorem does not hold (de Finetti, 1969; Diaconis & Freedman, 1980) for finite sequences. In particular, Diaconis & Freedman (1980) provides tight quantitative bounds on the difference between exchangeable sequences and their "closest" mixture of i..d. distributions. We report here a lower bound on such distance.
Let U2a be an urn containing n red and n black balls. Let H2n,2k, respectively M2n,2k, represent the distribution of the number of red balls out of 2k draws made at random without, respectively with, replacement from U2n- Furthermore, for any random variable P in [0. 1], consider the random experiment that consists of first sampling p according to P and then sampling k Lid. Bernoulli with parameter p; denote with P,, the distribution of the number of successes according to this experiment. We have the following Theorem (Proposition 31 and Theorem 40 of Diaconis & Freedman (1980)):
Theorem A.1. Let tend to oc, and k E o(n). Then, for any random variable P in [0. 1). the following inequality holds:
2 k + +0 HE n
22 P..L/TV 2 2m M2n,28lITV
(m
Stated differently, sampling with replacement and without replacement induce different distributions whose total variation distance roughly scales linearly in the sampled fraction the urn.
B. The Hierarchy between the Three Models
The random-order model is intermediate between the i..dd. and adversarial input model. We provide here formal proof of this fact for the standard online learning setting with A actions and loss minimization.
Stochastic i.idd Input Model. The input S is defined by a distribution D over loss vectors, from which T i.i.d. samples are drawn. The regret suffered by algorithm A on input S is defined as follows:
T - - E((a))
Ri (A,S) = maxx [E(A]
The stochastic regret Riid (A) of an algorithm its worst-case regret against all stochastic inputs.
Random-Order Model. The input S is defined by set fhi...., of T loss vectors, that are presented in random order the learner, so that the generic & is hx(e)) for random permutation æ. The regret suffered by algorithm A input S is defined as follows:
T E
RRO (AA max E kE
Σ 4(a) (((a)
Σ
(a()))
min [
he(a).
The random-order regret RRO (A) of algorithm is its worst-case regret against all random-order inputs.
(Oblivious) Adversarial Model. The input S is defined by sequence of T loss vectors. The regret suffered by algorithm
A input S is defined as follows:
T Σ
T
RA (A, = max E
(la))-ee00 = E
(ax)
min
4(a).
aElk]
aelk
The adversarial regret RADV (A) of an algorithm A is its worst-case regret against all adversarial inputs.
A sequence X1, X3...., X, of random variables exchangeable if for any finite set of indices I (ii,..., te), and any permutation o over it holds that (X.....,, X,,) distributed as (Xa(i)) Xa
13

---

Online Learning in the Random Order Model
No-regret. An algorithm is said to enjoy the no-regret property in certain input model if it exhibits sublinear regret (in the time horizon 7) uniformly over all possible inputs in that model.
The informal statement contained in the main body that i.i.d N random- 3 adversarial is formalized in the following theorem.
Theorem B.1. For any learning algorithm A, the following regret hierarchy holds:
R2 (A) S 80 (A) RADD (A).
Proof. We start with the first inequality of the statement. Consider any random instance S, and let X S [0, 1] be the support of the random variable underlying S, and denote with Σx the multiset of all the subsets of T elements in X (possibly with repetitions). Finally, for any a Ex. denote with & the event that the set the realized losses a. We have the following:
max E [
Σ (((e)) E((a)
max (E( oeEx
P(E,) E Σ (e(as) - E
I max [k(
(a())) - E
= E
max aE|k]
(((as) - ec
t=1
(R Sx,
where the first inequality follows by an averaging argument (i.e., there exists a / E Σx that dominates the average stochastic regret), and the last equality holds because once the multiset of realized values â is fixed (we need multisets because there may be repeated elements), then all possible permutations are equally likely and thus we are back at the random-order model. Moreover, note that the max;e[M] only depends on the multiset and not on the specific realizations (so that we can safely move it into the expectation). Taking the sup with respect the stochastic inputs yields the first inequality.
The argument for the second inequality is similar. Fix any random-order instance S, characterized by set of T losses fhi.... } that are randomly permuted according to æ, and denote with S the corresponding ad adversarial input. Denote with IT the set of all permutations over the T rounds. We have the following:
max EE aE,N
Σ ((aar) - E((a)
max DEI
E
Σ ha())(a)) ((())a)
< max R
ADV Sx)
sell
(A,
where n² is the permutation that maximizes the regret. Taking the sup with respect to the random-order inputs yields the second inequality.
The above results tell that the minimax regret for the i.i.d. setting is at most that for the random-order one, which, in turn, is upper bounded by that of the adversarial input model.
C. Concentration for Sampling without Replacement
In the original paper by Hoeffding (Hoeffding, 1963), concentration bound for sampling without replacement is provided. Theorem C.I. Let yı y2,.... yr be a sequence of numbers in [0, 1}, and consider an uniform random subset S C (y1....,yy }. where s = {S]. Then, the following inequality holds for any 0:
PP
Σ J.ES
1 2 A < 2expí -s22)
OuOut of simplicity, we assume such support finite. The general statement can proved with minimal arrangement.
14

---

Online Learning in the Random Order Model
where J + LEETT Ut is the average over the whole sequence.
Stated differently, if we have access to samples in the random-order model, we have that, with probability at least (1 6), the following concentration holds:
log(2/6)
Σ 3:ES
1 S
(9)
For completeness, we note that random-order sequences typically concentrate faster than i.i.d. ones. There is, in fact, a refined analysis of Hoeffding inequalities that holds in the random-order model, due to Serfling (1974), that provides the following tighter concentration bound:
Σ WEES
1 S
$
(1-
$
log(2/6
(10)
T
28
D. Missing Proof from Section 3
Lemma 3.1. For any ii.dd input and T sufficiently large, it holds that E [r] < 2VT.
Proof. It is immediate to observe that E [r] maximized when distribution of the losses on arm the uniform distribution on the support (f/r, for i 2, ........ T}. so we analyze that case. As first step in the analysis, we find an integral formula for the expected value of (when & (1) is drawn i..dd from {t/r, for i 1,2, ........ I),, and then we study its asymptotic behaviour. We have the following chain of inequalities:
E [
P
t=0
T
(T
-)
(Avoid collision up to time
T...T
t=0
T
t
T
Σ
=dd dx
( (f = j!)
2 T
(1+
e
= dx
T
too
T
y
-VT
dy
(11)
VT
then focus on the integral term, at the right-most side of Equation (11), and study the convergence of integrand with fu)), and consider its limit for large T:
E|r vT
Denote the
1 lim fr( = lim exp T log 1+ /r) - yVT = e 202 T-+00
T+00
Moreover, fr(y) is monotonically decreasing T and fi(y) is integrable; therefore, we can apply the dominated conver- gence theorem and argue that
E
400
lim (r(y) = ( e 2-200 dy = 2
lim T Too VT
T To
which concludes the proof.
15

---

Online Learning in the Random Order Model
E. Missing Proof from Section 4.1
Claim 4.3. For any block the corresponding clean event is realized with probability at least - 1/T.
Proof of Claim 4.3. (,(a) and (a) have the same distribution, so we focus only on the former. By Hoedffding incquality for sampling without replacement (Theorem C.I), we have that, for each E [k]]
12g 2
(a(a)) - S
S E
with probability at least 27 The statement follows by union bounding over 2 events (and S T).
F. Missing Proof from Section 4.2
Claim 4.6. For all i >> it, under the event & we have that
(1+ 3 p
O OPTLP S ti
Proof of Claim 4.6. First, we consider the following inequalities:
OPT - OPTT F x² -pp x;
= (f - -- xx + p. (x* xx²)
S c rft T (x* xt})
(Under &
Now, we consider the second term. We will show that x approximately feasible for the LP for which x; is optimal and, thanks to the strict feasibility action Ø, we obtain that x* cannot be too much better than at. Under the event & we have that
GT x S
x + p
which shows that x* is Bec-feasible for the constraints of OPT LP. Then consider i = Bx* + (1 - 3)Ø with 3 = 2-2ies clearly ejj ã < and thus it is feasible for OPTip and r i == B rfe r². Then
p+e.
T (x 21) = =. T (i - x7) + +rp Txx x)
+ P. (x" - +)
(o is feas. OPTi,)
s B)r Tx - 3e,
(/ 1)
p
which concludes the proof.
G. Missing Proofs from Section 4.3
We start analyzing the algorithm by counting the number of switches. Regardless of the instance and the randomness the algorithm, switches action at most + times in each of the (log 7') time blocks. This is summarized in the following Lemma.
Lemma G.1 (Low-Switching). For any realization of SMMUAATOV-SUCCESSVEEELIMMMMMMMO the total switching cost is at most 24 log
We now restate and prove the regret guarantees of SIAULATTONSSUCISSIVELLLMMMM
Theorem 4.9. There exists algorithm for bandits with switching costs in the random-order model with regret O(v KT log" T).
16

---

Online Learning in the Random Order Model
Proof. Fix any random-order instance S, a set of T vectors -/u,.... :.r....,,,,,, and denote with {(a) the average loss associated with each action a: {(a) Stery f//0)/r. Denote with a* any action with maximum and introduce the gap A(a) f(a) f(a"). For any time block i, let (a) denote the value of the estimator of E(a) the end of that time block, and denote with (a)a) the number of blocks (included the 1h) in which action has been active. Note that once an action is deactivated, it stays like this for the rest of the algorithm.
For each time block T. there are at most ways in which it can be partitioned into the sub-blocks used by the round-robin phase of the algorithm, depending on the cardinality the active set A. We make here simplifying assumptions for the calculations: we assume that the time blocks are perfectly divisible into sub-blocks. This is to avoid considering the suffix of the time block corresponding the remainder of the division in sub-blocks. Note, this assumption is to simplify calculations: having more samples regarding the last active action only improves concentration.
For each action and block i, we define the following clean event that requires that L(a) is well estimated across all possible sub-blocks In block we denote with B (g) the gt sub-block of 2// time steps, i.e., B (g) = (2 + 9/5) + 1.....,2(( (g+ 1/
((a)) 2/15
log T 10
E
{(a) S
Vj E [k] and E [i]
2/1
(g)
Claim G.2. For any block i and action o, the clean even Eg has probability at least 1 1/1..
Proof. Fix any B (g), by applying Hoeffding for sampling with replacement (Theorem C.I), we get that the following inequality holds with probability at least 1 T
(((a)
log
{(a)
$
10
2/
2
(E
Union bounding over all choices of j and (at most) i: choices of g yields the desired statement.
is now natural to look at the overall clean event & by intersecting the E. over all log T time blocks and actions. By union bounding, we hence get that the clean event holds with high probability.
Claim G.3 (Clean event). The clean event has probability least 1/2.
Before proceeding, underline that the clean event does not depend in any way the algorithm, but is only probabilistic statement over the random permutation, which considers fixed intervals. The crucial observation is that, under the clean event, we are sure that SIMULATIIO-SSUCESSSI SUCCESSIVE-ELLMMMNTTI ELIMINATION maintains precise estimates throughout. More precisely, denote with (a(a) the estimate E(a) maintained at the end of block i, we have the following claim:
Claim G.4. For all block i and active action a, conditioning on the clean event, we have that
log T
((((a) - E(a)) S 5k
2
Proof. If the action a active at the beginning of block i, then it has been explored in all previous blocks. Denote with T(a) the number of times action has been played up to block i included, and with T3 (a) the times in the generic block T when action has been played; clearly [T5] is at least 2//n and T(a) Ejs: Ti(a).
17

---

Online Learning in the Random Order Model
We have the following result:
(a(() {(a)
Σ Σ jši (ET)(a)
(((a)
((a)
T(a)
(((a)
Σ
(a)
Σ
A(a)
T(a)
Tj(a)
jSi
(ET
log T
T(a) Σ (a)
10
(By definition of clean event)
(a)a)
Σ
10 (a) log
T(a) i5
log" 3 T T(a)
10
(By Jensen Inequality)
log T
5k
2
where in the last inequality we used that an active action is played with frequency at least 1/k.
The fact that all active actions are well estimated (and that there always exists at least one active action) implies that the best action is always active, under the clean event. fact, for any block and active action a holds that
(a - S l(a") S ((a) S ((a) + +
which contradicts the deactivation rule. We have then proved that the instantaneous regret in the generic block under the clean event, is most 2e,. We know that the clean event is realized with high probability (Claim G.3), and that the number of switches is O log T) (Lemma G.1). All in all, we have the following bound on the regret:
log T
(SSE) & 2k log T + 4
Σ 24 E Olyy kT T).
1=1
thus concluding the proof.
H. Classification in the Random-Order Input Model
We study the classical model in binary classification: we have family H of hypotheses h defined bounded loss function é is defined. Formally, for any hypothesis h and pair (x, with E X' and y {0, 1). ((h(z),)) y) E [0, 1] denotes the cost incurred by predicting label h(x) (x, v) (see e.g., Bousquet et al., 2003). Note, to be uniform with the literature, in this section we use é to denote the loss function (as opposed to the loss vectors as in the rest of the paper) and for classifiers (as opposed to the non-shuffled input loss vectors as in the rest of the paper).
X for which
PAC Model. In the PAC learning model, the learner has access to i.i.d. samples from a joint distribution 'D from which pairs (X, Y)) are drawn, and its goal is to quickly estimate or approximate the best classifier, i.e., the classifier that minimizes E [((((X) Y) It is a standard result in learning theory that a class H is learnable, i.e., the best classifier is arbitrarily approximable if and only if the dyc dimension of H bounded, and that the convergence rate also depends on dvc (see, e.g., Vapnik & Chervonenkis, 1971).
(Adversarial) Online Model. the online model (Littlestone, 1987), the input-label pairs are generated adversarially, and the performance of a learning algorithm is measured with respect to the best hypothesis in H. Surprisingly, the online learnability of a family H governed by a stricter notion of dimension, the Littlestone dimension.
18

---

Online Learning in the Random Order Model
Random-Order Model. In this paper, we study the random-order model: the input is provided by a multiset S of (a,, y) pairs, which are presented by the learner in uniform random order. The performance measure of learning algorithm is its regret with respect to the best classifier on S. As the input arrives according to some random permutation n, we let eT (h) = ((h(2x())) M=(t)) be the loss of hypothesis h E H. at time (t). Similarly, we let & (h) = -)=(())s(()) (h) be the empirical loss accrued by time x (t), and (h) т---1 Era(r)>a(o)) (h). Moreover, we denote by E(h) Σو= ((((z)), U+) the average loss of hypothesis h on the whole dataset composed of 'T' input-label pairs.
H.1. Sample Complexity with Handom-OOree Input
Lemma H.1. Consider the problem of online binary classification in the random- model. For a hypothesis class H with VC-dimension dvc, given the first t 1 out of samples from a uniform permutation n, it holds that, for all h E H.
[e(h) - 2 1 (h)] - 2
1
(v
(ddve
8dve log t-1
(=
(2e(t= (2e(t-1)
+
8
log
2 7 )
dvc
with probability at least 1 1 5.
The proof of Lemma 1.1 implements version of the classical "symmetrization" argument for uniform convergence in the i.i.d. setting (Bousquet et al., 2003). We consider "ghost sample" made of t --1 out of T samples, that is the set of input-label pairs (r) (r)) extracted according to independent uniform permutation n².
Claim H.2. Fix any time t > 1 and precision & > 0 such that (t - 1)e 2 8, then the following inequality holds:
Px
sup (((h) - (h)) 2 S 21P x, LAE
sup
(1) -
(12)
NEE
Proof. For any realization of and n², and any classifier h E H. we have that
[[((()) (1) >>. | (0,,, S L (1-
since for any three reals a, b, and > 0, if a- b| > e and aa cl < S.4 then
aa bl < aa cl + cl |b cl 2
We take expectations with respect to the second sample extracted according to 't' and get
(;) Par [((()) غي_ (b))
< St _ < P (0)(0)) -Z) (h))
Since E(h) Ex'' (h)) for all h E and > 1, we can apply Chebyšev's inequality and obtain
Fx [1(hh) (1) 2 4E [[ (h))²1
4(t - 1)
4
< (t - 1) (t -t- 1t
The second inequality follows because the second moment is bounded in [0, 1], as losses are bounded in [0. 1]. Therefore,
(1-
4 1)
$ PPr 1 (h) (h) (0) (())
't < P
sup NEh
Lي (1))
We can now apply the sup over all h E H. on the left-hand side of the above inequality and then take the expectation also with respect to the randomness of æ. This implies the statement, as (t 2) 2 8.
Proof of Lemma H.I. Claim H.2 allows us to replace ε(h) by an empirical average over the ghost sample. As re- sult, the right-hand side only depends on the projection of the class H on the double sample drawn from n, n' H ((am(r)) (r(r)) (Ix(()) (ret)) denoted succinetly as H.."", which gives
(h) 2 (h)) N Et
(1) 2 tt (1) ( 2
IP Pr
sup hER
- sup
2
hEH
19

---

Online Learning in the Random Order Model
We now apply Hoeffding's inequality (as in Theorem C.1) ( ez (h), for a fixed h E H. To why it possible, construct equivalent process extracting sample and "ghost sample" according losses presented in an arbitrary ordering e (h)...... (h) and ordering induced by the uniform random permutation x', eT (h).... e (h). Let wy (h) = (ez e (h)) be the pair of variables matched by index, f(w+(h) = & (+ - E (h), and F(h) = (f(== (h)) | r E [7]]. Note that, for every xt,
and x' respectively. Consider
Σ (1)+ = Σ (() -
Σ TE[T]
E (h) O.
TETT]
TE[T]
We extract uniform random subset F composed of t functions
(()+(h) from F(h), and get
FF)F(()
t-1 Σ
1
f(w, 24 2exp (-(t 1)c;)
TEP
by Hoeffding's 's inequality (as in Theorem C.I). Therefore, we have
(-(-
P [12_10h) - 2 o
< 2xxp
(13)
2
Combining everything, we obtain
sup 1 (h) (h)] 2 4
P sup ((h) - (1)1 heW
< 2P n,,
NIE
2
2P n,,!!
sup
P (h) (1)1
hEHpo
(e(l- 1) dvc dvc
2
.P.,. (h) -
- (1) 2 ft
2
(e(t- 10-11)
dyc
(1 (1- 1)e2
< 4
eep
dvc
4
The second inequality is an application of the Sauer-Sheil lemma (Vapnik & Chervonenkis, 1971; Sauer, 1972; Shelah, 1972), and the last by the expression in (13). The proof concludes by setting
1 ( 8dve E 2
(v
2e(t - 1) dvc
8
2 8
1-1
log
V
log
H.2. Regret of an Empirical Risk Minimizer with Random-Order Input
Theorem H.3. Consider the problem of online binary classification in the random-ore order model. Fo hypothesis class H with VC-dimension dyc, given the first out Tf samples from uniform permutation n, the algorithm ARO that returns the minimizer
he arg min keH (()())<((()
Σ (T)).
achieves a regret of at most
T dvc
R R5) / dydc
Proof. Define, for any t E [T], the clean event in the past as E.T = { (((N) - ( vh E H) and in the future
as E Efuture- { [((h) T (h) S cr-e+1 4h E H}. The clean event time is E, = gpast E Efuture
20

---

Online Learning in the Random Order Model
The instantaneous regret at time (() under the clean event is
e7 (he) - (T() S E7 (he) (h-( + (k)) -77((")
(17 (he) - [(hh)))))))))))))))))) + (e(he) (((hh)- (ho)) + - (T()))
- (07 (he) ((bb))) + ((((1")-((h") + 2
The first inequality above follows by definition of hu the empirical loss minimizer, which gives (h²) - E7 ( 2 0. Note that the clean event on the order in which the elements arrive but only on the following two multisets: Spast Sttuuure, i.c. the multisets that represent the past (from time т (1) until <(t 1)) and future (from time x(t) until π (T)). We now take the expectation conditioning on the clean event and the two multisets Spest Sfunrre Therefore,
(he) - E7 (h')) Ee, Spust Sfuture]] 2E + (h+) E(h,)) - (CT - -((h)) E Speat Sfuture"
-24 +
Σ
1
E [(e(, (z). - E(h,)) + ((()"()) - E(h")) & Spast stture)]
T -+11
(
2e4 + 2. E
sup [E(h) (b)] Spust Stuture
LNEH
s 2(E + eT-1+1).
The equality above holds because once Spmn, Stuture are fixed, the loss at time T(() is uniformly sampled from the future. By the tower property of conditional expectation (on all the possible values of Speat Sfuture), ), we have proven that the expected instantaneous regret conditioned on the clean event & is at most:
2eT
V
(() & s 2(Et + ET- & 32dve log
E e7
dvc
where the last inequality holds by taking = 1/T in Lemma H.1. By definition of regret and under this choice of 6, we have
RT (AAO ,S s) =
E ( - e (h')
&d] PP [&4] + E (e) (h²) & P [E.]
(E(T]
2ET
1 + T-++1
32dvc log
+T T
dvc
t-1
T dvcI log
S B
dvc
which concludes the proof.
21


Reviews:
[{"review_id": "1MiIgdYkKN", "reviewer": "Reviewer_iXLi", "summary": "The paper studies a general online learning setting where in every round $t \\in [T]$ there is an unknown loss vector $\\ell_t$, the learner needs to make a decision $x_t \\in \\mathcal{X}_t$, and incurs loss $\\langle x_t, \\ell_t\\rangle$ (there might also be constraints that need to hold across the whole time horizon, like budget constraints.) Unlike the fully adversarial setting, the authors consider the case where the loss vectors are chosen by the adversary and then a random permutation of them is presented to the algorithm. The authors show that there exist (pathological) stochastic algorithms that do not work in this model. Then, the authors propose a template that can be used to obtain a \"stochastic-to-online\" transformation in their setting which works by breaking the interaction into logarithmic many intervals of doubling size, and using the interval $t-1$ to train the stochastic algorithm and apply it appropriately to interval $t$. They instantiate the template in various setting including online learning with delayed feedback, online learning with budget constraints, and Littlestone's online learning. The key technical observation is that the performance of the stochastic algorithm within consecutive intervals should be very close (e.g., Claim 4.3).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed comments and positive feedback about the paper. \n\nRegarding the specific comments and suggestions proposed: \n1. Yes, that is correct. We will rephrase the sentence to make it clearer. \n2. As correctly stated by the reviewer, Follow-the-leader is no-regret only in the stochastic setting and may perform poorly in the adversarial setting. We use Follow-the-leader as a subroutine in BIRTHDAY-TEST, where we only need its no-regret property on stochastic inputs. Indeed, we only claim that BIRTHDAY-TEST is no-regret in the stochastic setting, as any no-regret algorithm for the adversarial setting automatically retains its no-regret property on random order instances.\n3. And 4. Thanks for the suggestions; we will rephrase such comments and update the wording accordingly.", "claims_and_evidence": "Yes, they are supported by proofs.", "methods_and_evaluation_criteria": "The claims contain proofs, which make sense.", "theoretical_claims": "The claims seem to be sound.", "experimental_designs_or_analyses": "N/A.", "relation_to_broader_scientific_literature": "The results are of interest to theorists mostly, and practitioners secondarily.", "essential_references_not_discussed": "References discussed.", "other_strengths_and_weaknesses": "Strengths:\n\n- The authors consider a pretty general online learning setting and study a beyond-worst-case analysis of it by considering random permutations of the input sequence.\n\n- The authors propose a pretty general template and they instantiate it in various settings showing strong results.\n\n- The technical ideas are solid (at least they are above the bar of ICML).\n\nWeaknesses:\n\n- I don't see any strong weaknesses. Personally, I believe the claim that the paper \"initiates the systematic study of the random- order input model in online learning.\" is a bit of stretch. I agree that the setting the authors study is more general than prior work, but special cases of it have been studied extensively (e.g. OCO with random permutation arrivals).", "other_comments_or_suggestions": "- “The empirical distribution from this phase is then applied to the actual instance within the current block.” -> not sure what this means, do you mean the model trained on i.i.d. Samples from the empirical distribution of this phase?\n\n- Why is “follow-the-leader” no-regret in the adversarial setting? Maybe follow the perturbed leader? (follow the leader suffers from switching the chosen action all the time and being one step behind from the optimal algorithm).\n\n\n- “Surprisingly, there exists a random-order instance that fools BIRTHDAY-TEST.” -> I think the birthday-test algorithm is interesting, but I don’t think it’s surprising that it is fooled by a random-order input; given the construction (which is nice), I think it is clear that this algorithm will get confused.\n\n- I wouldn’t call it “procedure” because this reads more as a black-box transformation but rather a “template”, but this is just personal preference.", "questions_for_authors": "No further questions, please look at the comments.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NcL9i3TScL", "reviewer": "Reviewer_AxPZ", "summary": "This paper introduces a general framework, referred to as SIMULATION, that adapts stochastic (i.i.d.) learning algorithms to the random order model without significantly altering their finite-time performance guarantees. The core idea is straightforward: partition the time horizon into blocks of geometrically increasing length, sample an i.i.d. instance from past observations, and use it to train the algorithm in the current block.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback about the paper.\n\n**Adversarial algorithms in RO** As we mention in Section 1.1., and detail in Appendix B, there is a natural hierarchy between the i.i.d., random order, and adversarial input models. In particular, any learning algorithm for the adversarial setting retains its regret bounds against RO inputs. However, an algorithm with optimal regret bounds in the adversarial setting may not be optimal in the (easier) RO model. Consider, for example, the bandits with switching cost problem, where the adversarial minimax regret is $\\Theta(T^{2/3})$, as opposed to the stochastic (and RO) rate of $\\Theta(\\sqrt{T})$. If we were to use the optimal (in the adversarial setting) algorithm by Arora, et al. “Online bandit learning against an adaptive adversary: from regret to policy regret” (ICML 12) on a RO instance, we would obtain a (suboptimal) $\\Theta(T^{2/3})$ regret bound (note, in fact, that their approach consists in dividing the time horizon in $T^{2/3}$ time batch, so the algorithm switches freely action between consecutive time batches, for a switching budget $\\Omega(T^{2/3})$). A similar argument can be carried out for the prediction with delays model, where adversarial algorithms still retain their multiplicative dependence on the delay parameter, regardless of the input structure.\n\n**Comparison with Best-of-both-worlds literature [3]** The reviewer asks “Since the random order model lies between these two extremes [adversarial and i.i.d.] in terms of generality, do such algorithms [BoBW algorithms] not already address the problem in this setting?”. The answer to this question is, in general, negative. In the typical BoBW literature (as e.g., [3]), the goal is to design learning algorithms with good instance-independent bounds in the adversarial setting and logarithmic instance-dependent bounds on stochastic instances. An algorithm with these properties is only guaranteed to retain its adversarial instance-independent bounds on the random order instance, not its instance-dependent stochastic guarantees; this implies its suboptimality as soon as there is a gap between adversarial and random order. On the contrary, our paper provides a general template to construct tight algorithms for the RO model that match the minimax regret for the i.i.d. scenario.\n\n**Comparison with other related works** We thank the reviewer for the suggested literature. We will incorporate a discussion of both references in the final version of the paper. Although close in spirit to our research agenda of investigating the relationship between random order and i.i.d. inputs in online algorithms, our model and results are orthogonal to the ones studied in [1,2]. Consider, for instance, our online learning with constraints model. At each time step, our learning algorithm selects an action before observing the losses and constraint violations. In contrast, the online algorithm for Online Stochastic Convex Programming [1] first observes the losses and violations, and only then makes a decision. In other words, our setting falls within the domain of online learning, whereas theirs falls within the domain of competitive analysis.\n\n**Counterexample** Regarding the point raised on the counterexample, the primary goal behind our construction is to provide a general framework that extends the applicability of algorithms designed for the i.i.d. setting beyond purely stochastic environments. Even though UCB may work “as-is” in this specific random order instance, the counterexample shows that not all algorithms that achieve sublinear regret bounds in the i.i.d. model automatically have sublinear bounds on regret in the random order model. This highlights the need for our general construction. We hope that the power of this general template is evident from the various instantiations we present across different online problems.\n\n**Results of Immorlica et al** We are not sure we understand the concern raised by the reviewer regarding Immorlica et al. Indeed, the competitive ratio appears only in the adversarial setting of Immorlica et al. while here we show no-regret (ie, competitive ratio = 1). Our results align with those established by previous work for the stochastic setting. Specifically, we refer the reviewer to the stochastic regret guarantees in the work of Immorlica et al. There, they show a regret bound of $T/B\\cdot \\sqrt{T}$, which is $\\sqrt{T}/\\rho$ in our notation. Note that if we employed the algorithm of Immorlica et al. as a subroutine, we would still obtain the same regret rates as in Corollary 4.8. Moreover, in all cases in which $T\\sqrt{T}/B$ is meaningful (i.e., when $B \\ge \\Omega(\\sqrt{T})$), we obtain the same exact rate of $T/B\\sqrt{T}$ (since the term $1/\\rho^2$ becomes negligible as $1/\\rho^2=(T/B)^2 \\le T\\sqrt{T}/B$).\n\nIf any concerns remain on this matter, we are happy to clarify further. Otherwise, we encourage the reviewer to reconsider this point in light of our answer.", "claims_and_evidence": "The findings are interesting but somewhat expected, given that the random order model is statistically indistinguishable from the i.i.d. model in the asymptotic sense. Additionally, there is a well-established body of literature on best-of-both-worlds algorithms that achieve optimal performance in both stochastic and adversarial settings [3]. Since the random order model lies between these two extremes in terms of generality, do such algorithms not already address the problem in this setting?\n\nA key concern is the omission of highly relevant work [1], which presents near-optimal algorithms for various problems (including online packing, online learning, and feasibility) in both i.i.d. and random order models. Furthermore, reference [2] is also pertinent to this study. \n\nReferences:\n\n[1] Agrawal, S., & Devanur, N. R. (2014). Fast algorithms for online stochastic convex programming. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1405-1424.\n\n[2] Devanur, Nikhil R., & Hayes, T. P. (2009). The AdWords problem: Online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM Conference on Electronic Commerce, pp. 71-78.\n\n[3] Bubeck, S., & Slivkins, A. (2012). The best of both worlds: Stochastic and adversarial bandits. In Conference on Learning Theory, pp. 42-1. JMLR Workshop and Conference Proceedings.", "methods_and_evaluation_criteria": "This seems to be fine.", "theoretical_claims": "The proofs are clear.", "experimental_designs_or_analyses": "No experimental result has been reported.", "relation_to_broader_scientific_literature": "Please see the comments above.", "essential_references_not_discussed": "[1] Agrawal, S., & Devanur, N. R. (2014). Fast algorithms for online stochastic convex programming. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1405-1424.\n\n[2] Devanur, Nikhil R., & Hayes, T. P. (2009). The AdWords problem: Online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM Conference on Electronic Commerce, pp. 71-78.\n\n[3] Bubeck, S., & Slivkins, A. (2012). The best of both worlds: Stochastic and adversarial bandits. In Conference on Learning Theory, pp. 42-1. JMLR Workshop and Conference Proceedings.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "Typographical Error:\n•\tLine 155, Second Column: \"this can be tough ...\"", "questions_for_authors": "1.\tWhat happens when adversarial algorithms are applied in the random order setting? Do they yield improved guarantees in this model?\n2.\tIs the proposed transformation universal in the sense that it provides a best-of-both-worlds result for both random order and i.i.d. inputs? Given the extensive literature on best-of-both-worlds models achieving optimal performance in stochastic and i.i.d. settings [3], the authors should discuss how their work relates to this body of research.\n3.\tHow do the results in this paper compare to those in [1] and [2]?\n4.\tThe counterexample presented in Section [3] appears somewhat artificial. What happens if one applies a standard no-regret algorithm, such as UCB, to the random order input?\n5.\tTheorem 4.5 is meaningful only when $B=O(T)$. If $\\rho$ is small, the bound loses significance. This contrasts sharply with the results of Immorlica et al. (2022), which achieve an optimal competitive ratio even for small budgets.\n\nReferences:\n\n[1] Agrawal, S., & Devanur, N. R. (2014). Fast algorithms for online stochastic convex programming. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1405-1424.\n\n[2] Devanur, Nikhil R., & Hayes, T. P. (2009). The AdWords problem: Online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM Conference on Electronic Commerce, pp. 71-78.\n\n[3] Bubeck, S., & Slivkins, A. (2012). The best of both worlds: Stochastic and adversarial bandits. In Conference on Learning Theory, pp. 42-1. JMLR Workshop and Conference Proceedings.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QSgOHviEkJ", "reviewer": "Reviewer_82fy", "summary": "- This paper studies online learning in the random order model. Here, the adversary can pick an arbitrary sequence of loss functions, but must randomly permute them before presenting them one at a time to the learning algorithm. \n- They show that, in full generality, online algorithms with low-regret under stochastic adversaries fail to obtain sublinear regret under random-order adversaries. \n-  On the other hand, the authors show how to use an online learning algorithm for stochastic adversaries to construct an online learning algorithm under a random-order adversary with minimal blow up in regret guarantees. \n- Using this conversion, they give improved regret bounds for several settings: prediction with delayed feedback, online learning with constraints, bandits with switching costs, and online classification. \n- For online classification, they show that the VC dimension is sufficient for learnability under random-order adversaries.\n\n## Update after rebuttal\n\nI thank the authors for their response. As they have satisfactorily addressed my questions and concerns, I will maintain my positive score for this paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and positive feedback about the paper.\n\n**Paper organization.** Unfortunately, we had to move part of our results to the appendix in the interest of space. We thank the reviewer for the suggestion, and we will exploit the extra page in the camera ready (and move/shorten Section 3) to move part of Appendices E and F in the main body.\n\n**Tightness of our results.** We would like to point out to the reviewer that any lower bound for the stochastic setting also applies to the random order one (see also Appendix B); therefore, our results are tight (up to poly-log terms) for the random-order model (as they match the stochastic lower bounds). We highlight that all the settings of interest had minimax rates in the adversarial setting strictly worse than in the stochastic one (see section 1.1). For example, in bandits with switching costs, the adversarial setting is $T^{2/3}$ minimax optimal, while in the RO (and stochastic) is $\\sqrt{T}$ minimax optimal. We thank the reviewer for the idea of a table summarizing the result. We will implement it in the camera-ready. \n\n**Comparison between random order and stochastic models.** While we expected the RO model to be somewhat closer to the stochastic model than the adversarial one, we strongly believe quantifying the “distances” to be non-obvious. \nIn particular, our construction proving the non-existence of a black-box reduction from the stochastic to the random-order model shows that any similar “conversion result” needs a non-trivial component. We find the training and testing procedure both intuitive and interesting, as it successfully distills the similarities between random-order and i.i.d. instances. Finally, we find it surprising that the results we obtain are also tight in all the settings we consider (see the answer to Tightness of our results). We thank the reviewer who pointed out that this should be highlighted better. We will add a discussion in the final version.\n\n**Additional literature.** We thank the reviewer for pointing out the recent NeurIPS’24 paper [1]. We will discuss it in the camera-ready.\n\n**Other comments and suggestions.** We will move the sentence about $n_i(a)$ accordingly. Thanks.", "claims_and_evidence": "To me, the claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the authors evaluate their algorithms using the standard notion of regret.", "theoretical_claims": "I went through the proofs of Section 4.1 in the main text. The claims seem to check out to me.", "experimental_designs_or_analyses": "This is a purely theoretical paper with no experiments.", "relation_to_broader_scientific_literature": "This paper fits nicely into the recent interest of going beyond worst-case adversaries in online learning. Here, the goal is to obtain better regret guarantees by weakening the adversary in some reasonable way. From this perspective, this paper shows that what makes online learning hard under a worst-case adversary is not the fact that the adversary can pick an arbitrary sequence of loss functions, but the order of these loss functions. Indeed, this paper shows that even if you allow the adversary to pick the set of loss functions arbitrarily, online learning can be as easy as batch/stochastic learning if the adversary cannot control the order in which they are shown to the learner.", "essential_references_not_discussed": "With regards to online classification, a recent paper [1] studies a different type of intermediate setting where predictions about the future examples that need to be classified is available to the learner. Similar to the findings of this paper, the authors there show that for binary classification, VC dimension is also sufficient when such predictions are available. \n\n[1] Raman, Vinod, and Ambuj Tewari. \"Online Classification with Predictions.\" NeurIPS (2024).", "other_strengths_and_weaknesses": "**Strengths:** \n- The paper is well-written and easy to follow. \n- The conversion is intuitive and natural\n\n**Weaknesses:** \nOne gripe I have with this paper is with its organization.\n- In Section 1.1, the authors state that they apply their conversion to get improved regret bounds for 4 settings: prediction with delayed feedback, online learning with constraints, bandits with switching costs, and online classification. Yet, in the main text, only two of these are discussed in detail. My suggestion would be to move Section 3 to the Appendix and use the extra space to provide more details about your results for bandits with switching costs and online classification.\n- In addition, the authors do not provide a comparison between the regret bounds they achieved under a random-order adversaries ad the optimal regret bounds under a worst-case adversaries. This makes it hard to tell how much of a quantitative advantage a random order provides. It would be helpful to have a table summarizing your results for the random-order adversary as well as the optimal regret bounds for a worst-case adversary.\n\nMy other issue with this paper is that the results are not very surprising as they just result from running the stochastic algorithm on sub-samples of the history. This approach is intuitive, but it is not clear that it is optimal for the random-order model in any of the settings that the authors study. Unfortunately, the authors do not provide lower bounds for the random-order adversaries in any of their settings.", "other_comments_or_suggestions": "I would move the sentence \"Let $n_i(a)$ denote the times...\" under (iii)  to after the sentence \"Run algorithm $A$...\" in (ii) in Simulation Procedure. It was not immediately clear to me that $n_i(a)$ was the number of times $A$ played action $a$ on iid data from $D_i$.", "questions_for_authors": "(1) What are the lower bounds for random order adversaries in each of the settings you study? If the stochastic algorithm is optimally chosen, do you obtain the optimal regret bounds under random order adversaries in any of your settings?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PSfc2RrUR3", "reviewer": "Reviewer_xKSP", "summary": "This paper studies online learning in the random order model, where the loss functions are fixed in advance but are presented in a random order. It has been known that the random order model lies between the stochastic model, where the loss functions are drawn from a fixed distribution, and the adversarial model, where loss functions are selected adversarially. This paper focuses on designing algorithms under the random order model by making use of algorithms under the stochastic models. On the one hand, the paper gives an example that shows naively running an algorithm that works under the stochastic model would result in a linear regret under the random order model. On the other hand, this paper introduces a framework that designs no-regret learning algorithms under the random order model using no-regret learning algorithms under the stochastic model. Examples of how this framework works include Prediction with Delayed Feedback and Online Learning with Constraints.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback about the paper.\n\n**Importance of the BIRTHDAY-TEST.** In Section 3, we prove that there is no black-box reduction from random-order to i.i.d. That is, we cannot hope to prove a statement of the form: “Any algorithm with sublinear regret in the stochastic setting has sublinear regret in the RO instance” which, in principle, could reasonably be expected. To argue about this impossibility, we exhibit a specific algorithm (BIRTHDAY-TEST) that is no-regret against any stochastic i.i.d. instance but fails against a specific random-order instance. We stress that this algorithm is only used in the proof of this impossibility result.\n\n**Structure of the paper.** Unfortunately, we had to move important parts of our results to the appendix in the interest of space. We will exploit the extra page in the camera-ready version (and possibly move/shorten Section 3) to move parts of Appendices E and F in the main body.\n\n**Ben-David et al. 97.** We thank the reviewer for pointing out this paper. Although not directly related to our model (we study random order, and they study online, worst-case offline, best-case offline, and self-directed sequences), they share our interest in investigating alternative input generation models beyond adversarial and i.i.d. We will add a discussion in the camera-ready version.", "claims_and_evidence": "The claims and related technical lemmas are stated clearly and the proofs of the statements are clear.", "methods_and_evaluation_criteria": "This paper uses regret bounds as a measurement of the performance of the online learning algorithms, which is standard in analyzing online learning algorithms.", "theoretical_claims": "I only checked the proofs of the statements in the main body of the paper, For theorems in the appendix, I only checked the statements of the technical lemmas used for proving the theorems but did not check the proof carefully.", "experimental_designs_or_analyses": "This paper is theoretical and does not need experiments to support the results.", "relation_to_broader_scientific_literature": "Online learning with adversarial order and stochastic order has been studied extensively. The random order model though is asymptotically equivalent to the stochastic setting, is different from the stochastic setting in finite time. The algorithmic framework presented in this paper might inspire designing no-regret learning algorithms for other online learning problems under the random order model.", "essential_references_not_discussed": "The setting studied in this paper is new and I think there are not many prior works closely related to this paper.", "other_strengths_and_weaknesses": "Strengths:\n1. Random order is an intermediate model that lies between the stochastic setting and the adversarial setting. This paper shows that under the finite time analysis, the random order model is different from the stochastic setting and also designs an algorithmic framework that can convert existing no-regret learning algorithms in the stochastic setting into a no-regret learning algorithm under the random order model. This framework might be useful for studying other online learning problems in the random order model\n2. The statements and the proofs of the theorems and the technical lemmas are clear. This makes the paper easy to follow.\n\nWeakness:\nI am confused about the structure of the main part of the paper. It is a bit unclear what the central result the paper wants to sell as there are many different online learning problems considered in this paper. Furthermore, it seems that bandits with switching costs as well as classification in the random order model are both important parts of this paper. However, even informal statements of results from these parts are not stated in the main body. In particular, it seems that the results on classification in the random order do not have deep connections with the simulation framework. These make the structure of the main part of the paper strange and confusing.", "other_comments_or_suggestions": "Though not directly related, models such as online learning in the best order/ worst order/self-directed order models have been proposed since the 1990s. It could be helpful if related papers such as \n\n*Ben-David, Shai, Eyal Kushilevitz, and Yishay Mansour. \"Online learning versus offline learning.\" Machine Learning 29 (1997): 45-63.*\ncan be cited and discussed.", "questions_for_authors": "I am very confused about the motivation for analyzing the birthday testing problem in the stochastic setting. The first phase of the birthday testing problem looks quite artificial, even without the first phase, the algorithm should still be no-regret and by removing the first phase it should not result in a linear regret under the random order model. So, I am not sure what the analysis of the birthday testing problem implies.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work studies online learning in the random-order model, an interesting middle ground (in the finite case) between the i.i.d. stochastic model and adversarial orders. In particular, the authors:
1. show that directly applying a no-regret algorithm for the stochastic model can fail against a random-order instance (i.e., they demonstrate a separation between the two models), and
2. design a sublinear-regret algorithm called `Simulation` that uses a low-regret algorithm in the stochastic model as a black-box subroutine.

Overall, the reviewers lean towards acceptance (scores: [4, 2, 3, 3]). Note that Reviewer AxPZ (score: 2) did not respond to the authors' rebuttal. The paper is very well written, and in general we appreciate bringing more attention to beyond-worst-case bounds.
Decision: Accept (poster)