Online Learning in the Random-Order Model

We thank the reviewer for the positive feedback about the paper.

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.

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.

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.

We thank the reviewer for their feedback and positive feedback about the paper.

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.

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.

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

Additional literature. We thank the reviewer for pointing out the recent NeurIPS’24 paper [1]. We will discuss it in the camera-ready.

Other comments and suggestions. We will move the sentence about $n_i(a)$ accordingly. Thanks.

We thank the reviewer for their feedback about the paper.

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.

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.

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.

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.

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

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

We thank the reviewer for their detailed comments and positive feedback about the paper.

Regarding the specific comments and suggestions proposed:

1. Yes, that is correct. We will rephrase the sentence to make it clearer.
2. 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.
3. And 4. Thanks for the suggestions; we will rephrase such comments and update the wording accordingly.