Replicable Online Learning

We thank the reviewer for their time and feedbacks, here is our response:

weakness1:

1.1 - Sure, we will clarify this in the text. It means the cube starting from the point $\sum_{i=1}^{t-1} c_i$.

1.2 - We will clarify this. Here, we mean a grid with side $1/\epsilon$ and a starting point of $p$.

1.3 - We will clarify this. This means $\sum_{i=1}^{t-1} c_i$.

1.4 - D is the diameter of the action set (pointed in Thm D.3), we will add this to the model.

1.6 - We will add this to the model section. The geometric distribution with parameter $\epsilon$ is the discrete probability distribution that describes when the first success in an infinite sequence of independent and identically distributed Bernoulli trials occurs. Its probability mass function depends on epsilon and is defined as: $P(X=k)=(1−\epsilon)^{k−1}\epsilon$

1.7 - You are correct. We will fix that.

1.9 - Apologies for the confusion: what we mean is the following. The goal is to design an iid $\rho$-replicable algorithm with worst-case regret as low as possible. Recall the following from Section 2: (1)We say an algorithm has Worst-case regret $K$ if for any cost sequence $S = (c_1, . . . , c_T )$, the expected regret satisfies $\E_{R\sim \cal{R}}[Reg(S,R)]$ (2)We say an algorithm has replicability $\rho$ if for iid cost sequence.

weakness 2: Due to the space issues, our remedy for this was to have a longer introduction with an extensive “our contributions” section to explain the intuition behind our results.

weakness 3: Regarding the upper bound, our current algorithm would not achieve a better bound. The reason is that, there are two variables in our algorithms, one the block size B, and the other one, the noise level $\epsilon$. In order to bound the probability of non-replicability to at most $\rho$, we need to set these two parameters carefully (equation below the line 853). Furthermore, in order to minimize regret, we need to set $\epsilon =$\frac{1}{\sqrt{BT}}$, line 856. Putting these not inequalities together, gives us the optimum values of noise level epsilon and block size B. However, there might be a different algorithm that achieves a better regret bound, and we leave it as an open question.

weakness 4: Our main contribution is a principled framework to study replicability with low regret in settings combining stochastic and adversarial elements, whereas previous works focused exclusively on the stochastic case. By considering an adversarial (oblivious) sequence of distributions, our model generalizes the standard oblivious adversary (point-mass distributions) and introduces a natural approach to replicability in adversarial environments. In hindsight, although the employed techniques are standard, it was not a-priori clear that our definitions would yield sublinear regret. Furthermore, the analysis presents technical challenges: certain scenarios do not admit the ideal $\sqrt{T}$ regret bound (even when $\rho$, the replicability parameter, is constant), whereas others (e.g., i.i.d. experts) achieve favorable bounds.

Question 1: We are borrowing from previous ideas but making them work for replicability requires delicate balance and some cleverness to circumvent certain bottlenecks. We study replicability with low regret in settings combining stochastic and adversarial elements, whereas previous works focused exclusively on the stochastic case. By considering an adversarial (oblivious) sequence of distributions, our model generalizes the standard oblivious adversary (point-mass distributions) and introduces a natural approach to replicability in adversarial environments. In hindsight, although the employed techniques are standard, it was not a-priori clear that our definitions would yield sublinear regret. Furthermore, the analysis presents technical challenges: certain scenarios do not admit the ideal $\sqrt{T}$ regret bound (even when $\rho$, the replicability parameter, is constant), whereas others (e.g., i.i.d. experts) achieve favorable bounds.

Question 2: connections between online replicability and DP online learning:

We don't see any direct reduction. For example, we require the entire sequence to be replicated whp, not just any given entry, so it's not at all clear if differential privacy with meaningful parameters would be useful for replicability. In the reverse direction, we should be able to get privacy for a single entry changing by a bounded amount, but full replicability might be an overkill for that.

Question 3: Our results for learning from experts is in Section 4 and Theorem 4.1. That being said, by using geometric noise, we end up getting a better dependency on n(number of experts) that is logarithmic instead of polynomial dependency(n^{1/6}) on n for online linear optimization.

I thank the authors for their response and clarifying the polynomial dependence on the number of experts for OLO . However, I am still concerned about the overall presentation of the paper. I will increase my score from 3 to 4 contingent on the authors explaining how they plan to address the presentation issues highlighted in Weakness 2 (i.e improving the exposition, intuition, and proof sketches around their main results)

We thank the reviewer for their response. We understand your point and here is how we plan to improve the presentation of the paper:

Since we have a longer "our contributions" section that goes through the intuition of all the results, we can just keep the results corresponding to Section 6 and 7 in the Apendix. This would be ok since Sections 1.1.4 and 1.1.5 are already giving the intuition behind these results in the main body.

Then we would use this freed-up space to explain our results in Section 3 and 4 (adversarially $\rho$-replicable online linear optimization and experts) more thoroughly. That being said, after Thm 3.1. we would add the following paragraph (similar to lines 757-766 in the current version):

"First, we analyze the regret of Algorithm 1. However, we need to be careful when picking the values of $\epsilon$ and $B$ so that the regret does not blow up. If $\epsilon$ is too large then in Algorithm 1, a lot of different accumulated cost vectors $c_{1:t-1}$ get mapped to the same grid point $g_{t-1}$ which would cause a lot of regret. Similarly, when $B$ is too large, the algorithm takes the same action for a large block of time and does not update its decision which would cause the regret to suffer. In order to pick optimal values for $\epsilon$ and $B$, we analyze the regret of Algorithm 1 by appealing to a different algorithm ''Follow the Perturbed Leader with Block Updates'' ($FTPLB(\epsilon,B)$) that in expectation behaves identically to $FLLB(\epsilon,B)$ on any single period and incurs the same expected cost. This algorithm is a modified version of the ``Follow the Perturbed Leader'' ($FTPL(\epsilon)$) algorithm by Hannan-Kalai-Vempala. "

Then we would add a summary of FTPLB algorithms that would be similar to lines 766-775. Also, add lines 776-781 that explain why FTPLB and FLLB have the same expected cost. After that, we present the regret bounds for FTPLB algorithm that would be moving Thm D.3 to the main body (keep the proof in the appendix). After that, we are ready to present a proofsketch for Thm 3.1. This would explain the replicability part and how to put the bounds for replicability and regret together to derive optimal values for $\epsilon$ and $B$ and the final regret bound.

For Section 4, we will explain how to prove Thm 4.1. That is, first we analyze its regret, which would be moving Thm E.1. lines 862-863 to the main body. Adding a proof-sketch for it would be easy, we just need to state that proof uses the following points: 1-the difference between the cost of FTPLB* and BTPL is bounded. 2- the difference between the cost of BTPL and the best expert in hindsight is bounded. Then we add a proof-skecth for Thm 4.1. The prooksketch would be to first explain the replicability bound (similar to lines 944-947) and then explaining how we put the bounds for regret and replicability together to find optimal values for $\epsilon$ and $B$. Furthermore, we will also add a remark to highlight why adding geometric noise derives better regret bounds in the experts setting compared to online linear optimization.

This re-write would give a better presentation of Section 3 and 4., it would also perhaps allow us to move Alg 5 to the main body. As we said earlier, moving Sections 6 and 7 would be alright since the main intuition behind these results are already explained in the our contributions section.

Happy to incorporate any further suggestions, and thanks for your feedback.

We thank the reviewer for the feedback and reviewing efforts, here is our response:

Weakness 1:

Yes, thank you for pointing this out: we forgot to mention this condition in the theorem statement. We will include the condition in the theorem statement. The reason is that we need the loss $f (a, c)$ to scale linearly with the `1-norm with c and that if $c'$ is a random variable with $E[c'] = c$ then $E[f (a, c')] < f (a, c)$ (concavity). But we want to highlight that even with the constraint of linearity of the loss function we are able to capture many settings such as online linear optimization, experts and bandit problems.

weakness 2,3: We need to make a slight change to the following in Algorithm 5: $g_t \gets G \cap \\{c_{1:t-1} + (-\epsilon/2,\epsilon/2)^n\\}$ so that over the randomness of the initial random offset of the grid G we have $E_[g_t] = c_{1:t-1}$. Similarly, for G'. We will make this change: it is a minor one and not conceptual.

In light of the previous point, consider the following: in Equation (13), let us bring the $E_{R_{ext}}$ inside. Then we get an expression like: $E_{R_{int}} [ E_{R_{ext}} [Cost(a_u, g_{uB} - g'_{(u-1)B})] ]$

which by our assumption we can say is at most: $E_{R_{int}} [ Cost(a_u, E_{R_{ext}}[g_{uB} - g'_{(u-1)B} \mid a_u]) ].$

And now, using the fact that $a_u$ is independent of both $g'_{(u-1)B}$ and

$g_{uB}$, we have:

$E_{R_{ext}}[g_{uB} - g'_{(u-1)B} \mid a_u]$

$= E_{R_{ext}}[g_{uB} - g'_{(u-1)B}]$

$= c_{uB} - c_{(u-1)B}$

$= c_{(u-1)B:uB}$

This is the case since at a transition point $t$ (that is when $t = (u-1)B + 1$ and we are permitted to change our action), $a_t$ depends on $g_{t-1}$ and $g'_{(t-1-B)}$,

implying that $a_u$ depends on $g_{(u-1)B}$ and $g'_{(u-2)B}$

(and not $g'_{(u-1)B}$

and $g_{uB}$)). Please see line 33 in Alg 5

In fact, this independence from $g'_{(u-1)B}$ was the main reason for using two different grids. Also, due to the rounding procedure we have that

$E[g_{uB}] = c_{uB}$

similarly for g'.

weakness 5: Here is an example in the online setting: Suppose that we have an algorithm for deciding which routes to use to drive to work each day. We run it for T days, jotting down features of that day. For instance, Day 1 was Monday at 8am and sunny. Day 2 was Tuesday at 10am and rainy, etc. If you imagine that traffic at any given time is a probabilistic function of the features, then what our guarantees say is that if you run it again on a different sequence of T days then (a) we'll have sublinear regret no matter what, and (b) if this new sequence has the same features as the first sequence, then with high probability your entire sequence of actions will be the same.

other comments,

line 81: In the adversarial case, the distributions across different timesteps are picked by an adversary. That’s why we call it adversarial $\rho$-replicable case.

Appendix F, Sure, we will edit the text, thanks.

We thank the reviewer for their constructive feedback. We are glad that you found our results interesting. Here is our response to your questions:

Weakness 1:

Thank you for the suggestion. We would like to mention that the guarantees for Esfandiari et al. and Komiyama et al. are all in the stochastic bandits setting, and their algorithms have $\omega(T )$ regret bounds in the adversarial setting.

Question 1:

That is a great point. In fact, Kalai and Vempala also show that if the randomness $p$ in Algorithm 1 is re-drawn in each round, we can achieve sublinear regret even in the case of adaptive adversaries. Since our algorithms are a generalization of FLL by Kalai and Vempala that observation holds in our case as well. We add a remark to highlight that.

Question 2:

What we mean here is that if we consider the FTPL (and not FTPL with block updates, i.e. FTPLB), over two different cost sequences $S_1$ and $S_2$ that are both drawn from the same sequence $D_1,\cdots, D_T$, then FTPL changes its actions in near timesteps when executing it on $S_1$ and $S_2$. Hence, since with high probability these changes are in close-by timesteps, they will be in the same blocks (whp). Now, if we consider FTPLB, since it is updating its action only at the endpoints of the blocks, it will pick the same action sequence when executing it over $S_1$ and $S_2$.

Question 3: You are correct, we will add this to the model section. In Thm D.3, we explain that the $\ell_1$ length of c is at most and the $\ell_1$ diameter of A is D.

Question 4:

That’s a great point; we will enhance the writing of this example. We just mean that initially, when $c_1$ is drawn, that is a vector of length 2 (since we have two actions), the cost for action $a_1$ is higher than the cost of $a_2$ (this is what we mean by bonus, a lower initial cost). However, in hindsight, $a_1$ is a better action, so it would take some time for the algorithm to figure this out.

Last comment: Perfect, thanks, we will correct this.

We thank the reviewer for their constructive feedback. We are glad that your found our results interesting. Here is our response to your questions:

Question 1:

Regarding the upper bound, our current algorithm would not achieve a better bound. The reason is that, there are two variables in our algorithms, one the block size B, and the other one, the noise level $\epsilon$. In order to bound the probability of non-replicability to at most $\rho$, we need to set these two parameters carefully (equation below line 853). Furthermore, in order to minimize regret, we need to set $\epsilon = \frac{1}{\sqrt{BT}}$, line 856. Putting these not inequalities together, gives us the optimum values of noise level $\epsilon$ and block size B. However, there might be a different algorithm that achieves a better regret bound, and we leave it as an open question.

On the other hand, regarding the lower bound, currently, all approaches to proving lower bounds in terms of the replicability parameter go via a reduction to the coin problem as defined in [Impagliazzo et al. STOC’ 2022](Lemma 7.2). (Reduction for the stochastic bandits mentioned somewhat informally in Esfandiari et al.) The coin problem is as follows: promised that a 0−1 coin has bias either $1/2−\tau$ or $1/2+\tau$ for fixed $\tau > 0$ how many flips $T$ are required to identify the coin’s bias with high probability while being $\rho$-replicable? Here we have a tight lower bound of $\rho.\tau.\sqrt{T} > \Omega(1)$. When the reduction is done (as in the paper) the $\sqrt{T}$ here translates to the $\sqrt{T}$ in our proof. We don’t believe that this reduction is optimal in the sense that a more batched up division of the time steps where each batch reduces to a coin problem with different $\tau$ values should lead to a better bound: however, we are unable to execute the above idea. This would also mirror the batching of time steps in the upper bound, and would utilize the full extent of the adversarial setting where the distributions (which correspond to $\tau$ in the reduction) are time varying.

Question 2:

That is a great question. We derived these results so that they would capture both adversarial and iid input sequences, as well as their mixtures, which can be modeled by setting certain distributions as point-masses. However, in the iid case, in Appendix H, we show how to derive better regret bounds $O(\sqrt{T})$ by having blocks of varying lengths. However, it is certainly possible that our $T^{5/6}$ regret bound in the general case is improvable, and we leave it as an open question.