Online Learning with Local Permutations and Delayed Feedback

We propose an Online Learning with Local Permutations (OLLP) setting, in which the learner is allowed to slightly permute the \emph{order} of the loss functions generated by an adversary. On one hand, this models natural situations where the exact order of the learner's responses is not crucial, and on the other hand, might allow better learning and regret performance, by mitigating highly adversarial loss sequences. Also, with random permutations, this can be seen as a setting interpolating between adversarial and stochastic losses. In this paper, we consider the applicability of this setting to convex online learning with delayed feedback, in which the feedback on the prediction made in round $t$ arrives with some delay $\tau$. With such delayed feedback, the best possible regret bound is well-known to be $O(\sqrt{\tau T})$. We prove that by being able to permute losses by a distance of at most $M$ (for $M\geq \tau$), the regret can be improved to $O(\sqrt{T}(1+\sqrt{\tau^2/M}))$, using a Mirror-Descent based algorithm which can be applied for both Euclidean and non-Euclidean geometries. We also prove a lower bound, showing that for $M<\tau/3$, it is impossible to improve the standard $O(\sqrt{\tau T})$ regret bound by more than constant factors. Finally, we provide some experiments validating the performance of our algorithm.


Introduction
Online learning is traditionally posed as a repeated game where the learner has to provide predictions on an arbitrary sequence of loss functions, possibly even generated adversarially. Although it is often possible to devise algorithms with non-trivial regret guarantees, these have to cope with arbitrary loss sequences, which makes them conservative and in some cases inferior to algorithms not tailored to cope with worstcase behavior. Indeed, an emerging line of work considers how better online learning can be obtained on "easy" data, which satisfies some additional assumptions. Some examples include losses which are sampled i.i.d. from some distribution, change slowly in time, have a consistently best-performing predictor across time, have some predictable structure, mix adversarial and stochastic losses, etc. (e.g. Sani et al. [2014], Karnin and Anava [2016], Bubeck and Slivkins [2012], Seldin and Slivkins [2014], Hazan and Kale [2010], Chiang et al. [2012], Steinhardt and Liang [2014], Hazan and Kale [2011], Rakhlin and Sridharan [2013], Seldin and Slivkins [2014]).
In this paper, we take a related but different direction: Rather than explicitly excluding highly adversarial loss sequences, we consider how slightly perturbing them can mitigate their worst-case behavior, and lead to improved performance. Conceptually, this resembles smoothed analysis Spielman and Teng [2004], in which one considers the worst-case performance of some algorithm, after performing some perturbation to their input. The idea is that if the worst-case instances are isolated and brittle, then a perturbation will lead to easier instances, and better reflect the attainable performance in practice.
Specifically, we propose a setting, in which the learner is allowed to slightly reorder the sequence of losses generated by an adversary: Assuming the adversary chooses losses h 1 , . . . , h T , and before any losses are revealed, the learner may choose a permutation σ on {1, . . . , T }, satisfying max t |t − σ(t)| ≤ M for some parameter M , and then play a standard online learning game on losses h σ(1) , . . . , h σ(T ) . We denote this as the Online Learning with Local Permutations (OLLP) setting. Here, M controls the amount of power given to the learner: M = 0 means that no reordering is performed, and the setting is equivalent to standard adversarial online learning. At the other extreme, M = T means that the learner can reorder the losses arbitrarily. For example, the learner may choose to order the losses uniformly at random, making it a quasistochastic setting (the only difference compared to i.i.d. losses is that they are sampled without-replacement rather than with-replacement).
We argue that allowing the learner some flexibility in the order of responses is a natural assumption. For example, when the learner needs to provide rapid predictions on a high-frequency stream of examples, it is often immaterial if the predictions are not provided in the exact same order at which the examples arrived. Indeed, by buffering examples for a few rounds before being answered, one can simulate the local permutations discussed earlier.
We believe that this setting can be useful in various online learning problems, where it is natural to change a bit the order of the loss functions. In this paper, we focus on one well-known problem, namely online learning with delayed feedback. In this case, rather than being provided with the loss function immediately after prediction is made, the learner only receives the loss function after a certain number τ ≥ 1 of rounds. This naturally models situations where the feedback comes much more slowly than the required frequency of predictions: To give a concrete example, consider a web advertisement problem, where an algorithm picks an ad to display, and then receives a feedback from the user in the form of a click. It is likely that the algorithm will be required to choose ads for new users while still waiting for the feedback from the previous user.
For convex online learning with delayed feedback, in a standard adversarial setting, it is known that the attainable regret is on the order of O( √ τ T ), and this is also the best possible in the worst case Weinberger and Ordentlich [2002], Mesterharm [2005], Langford et al. [2009], Joulani et al. [2013], Quanrud and Khashabi [2015]. On the other hand, in a stochastic setting where the losses are sampled i.i.d. from some distribution, Agarwal and Duchi [2011] show that the attainable regret is much better, on the order of O( √ T + τ ). This gap between the worst-case adversarial setting, and the milder i.i.d. setting, hints that this problem is a good fit for our OLLP framework.
Thus, in this paper, we focus on online learning with feedback delayed up to τ rounds, in the OLLP framework where the learner is allowed to locally permute the loss functions (up to a distance of M ). First, we devise an algorithm, denoted as Delayed Permuted Mirror Descent, and prove that it achieves an expected regret bound of order O( T (τ 2 /M + 1)) assuming M ≥ τ . As M increases compared to τ , this regret bound interpolates between the standard adversarial √ τ T regret, and a milder √ T regret, typical of i.i.d. losses. As its name implies, the algorithm is based on the well-known online mirror descent (OMD) algorithm (see Hazan et al. [2016], Shalev-Shwartz et al. [2012), and works in the same generality, involving both Euclidean and non-Euclidean geometries. The algorithm is based on dividing the entire sequence of functions into blocks of size M and performing a random permutation within each block. Then, two copies of OMD are ran on different parts of each block, with appropriate parameter settings. A careful analysis, mixing adversarial and stochastic elements, leads to the regret bound.
In addition, we provide a lower bound complementing our upper bound analysis, showing that when M is significantly smaller than τ (specifically, τ /3), then even with local permutations, it is impossible to obtain a worse-case regret better than Ω( √ τ T ), matching (up to constants) the attainable regret in the standard adversarial setting where no permutations are allowed. Finally, we provide some experiments validating the performance of our algorithm. The rest of the paper is organized as follows: in section 2 we formally define the Online Learning with Local Permutation setting, section 3 describes the Delayed Permuted Mirror Descent algorithm and outlines its regret analysis, section 4 discusses a lower bound for the delayed setting with limited permutation power, section 5 shows experiments, and finally section 6 provides concluding remarks, discussion, and open questions. Appendix A contains most of the proofs.

Setting and Notation
Convex Online Learning. Convex online learning is posed as a repeated game between a learner and an adversary (assumed to be oblivious in this paper). First, the adversary chooses T convex losses h 1 , . . . , h T which are functions from a convex set W to R. At each iteration t ∈ {1, 2, . . . , T }, the learner makes a prediction w t , and suffers a loss of h t (w t ). To simplify the presentation, we use the same notation ∇h t (w) to denote either a gradient of h t at w (if the loss is differentiable) or a subgradient at w otherwise, and refer to it in both cases as a gradient. We assume that both w ∈ W and the gradients of any function h t in any point w ∈ W are bounded w.r.t. some norm: Given a norm · with a dual norm · * , we assume that the diameter of the space W is bounded by B 2 and that ∀w ∈ W, ∀h ∈ {h 1 , h 2 , ..., h T } : ∇h (w) * ≤ G. The purpose of the learner is to minimize her (expected) regret, i.e.
where the expectation is with respect to the possible randomness of the algorithm. Learning with Local Permutations. In this paper, we introduce and study a variant of this standard setting, which gives the learner a bit more power, by allowing her to slightly modify the order in which the losses are processed, thus potentially avoiding highly adversarial but brittle loss constructions. We denote this setting as the Online Learning with Local Permutations (OLLP) setting. Formally, letting M be a permutation window parameter, the learner is allowed (at the beginning of the game, and before any losses are revealed) to permute h 1 , . . . , h T to h σ −1 (1) , . . . , h σ −1 (T ) , where σ is a permutation from the set P erm := {σ : ∀t, |σ (t) − t| ≤ M }. After this permutation is performed, the learner is presented with the permuted sequence as in the standard online learning setting, with the same regret as before. To simplify notation, we let f t = h σ −1 (t) , so the learner is presented with the loss sequence f 1 , . . . , f T , and the regret is the same as the standard regret, i.e.
. Note that if M = 0 then we are in the fully adversarial setting (no permutation is allowed). At the other extreme, if M = T and σ is chosen uniformly at random, then we are in a stochastic setting, with a uniform distribution over the set of functions chosen by the adversary (note that this is close but differs a bit from a setting of i.i.d. losses). In between, as M varies, we get an interpolation between these two settings.
Learning with Delayed Feedback. The OLLP setting can be useful in many applications, and can potentially lead to improved regret bounds for various tasks, compared to the standard adversarial online learning. In this paper, we focus on studying its applicability to the task of learning from delayed feedback.
Whereas in standard online learning, the learner gets to observe the loss f t immediately at the end of iteration t, here we assume that at round t, she only gets to observe f t−τ for some delay parameter τ < T (and if t < τ , no feedback is received). For simplicity, we focus on the case where τ is fixed, independent of t, although our results can be easily generalized (as discussed in subsection 3.3). We emphasize that this is distinct from another delayed feedback scenario sometimes studied in the literature (Agarwal and Duchi [2011], Langford et al. [2009]), where rather than receiving f t−τ the learner only receives a (sub)gradient of f t−τ at w t−τ . This is a more difficult setting, which is relevant for instance when the delay is due to the time it takes to compute the gradient.

Algorithm and Analysis
Our algorithmic approach builds on the well-established online mirror descent framework. Thus, we begin with a short reminder of the Online Mirror Descent algorithm (see e.g. Hazan et al. [2016] for more details). Readers who are familiar with the algorithm are invited to skip to Subsection 3.1.
The online mirror descent algorithm is a generalization of online gradient descent, which can handle non-Euclidean geometries. The general idea is the following: we start with some point w t ∈ W, where W is our primal space. We then map this point to the dual space using a (striclty convex and continuously differentiable) mirror map ψ, i.e. ∇ψ (w t ) ∈ W * , then perform the gradient update in the dual space, and finally map the resulting new point back to our primal space W again, i.e. we want to find a point where ψ * is the dual function of ψ. This point, w t+ 1 2 , might lie outside our hypothesis class W, and thus we might need to project it back to our space W. We use the Bregman divergence associated to ψ to do this: Specific choices of the mirror map ψ leads to specific instantiations of the algorithms for various geometries. Perhaps the simplest example is ψ (x) = 1 2 x 2 2 , with associated Bregman divergence ψ (x, y) = 1 2 · x − y 2 . This leads us to the standard and well-known online gradient descent algorithm, where w t+1 is the Euclidean projection on the set W of w t − η · g t . Another example is the negative entropy mirror map ψ (x) = n i=1 x i · log (x i ), which is 1-strongly convex with respect to the 1-norm on the simplex W = x ∈ R n + : n i=1 x i = 1 . In that case, the resulting algorithm is the well-known multiplicative updates algorithm, where w t+1,i = w t,i ·exp(−ηg t,i )/ n j=1 w t,i · exp(−ηg t,j ). Instead of the 1-norm on the simplex, one can also consider arbitrary p-norms, and take ψ(x) = 1 2 · x 2 q , where q is the dual norm (satisfying 1/p + 1/q = 1).

The Delayed Permuted Mirror Descent Algorithm
Before describing the algorithm, we note that we will focus here on the case where the permutation window parameter M is larger than the delay parameter τ . If M < τ , then our regret bound is generally no better than the O( √ τ T ) obtainable by a standard algorithm without any permutations, and for M < τ /3, this is actually tight as shown in Section 4.
We now turn to present our algorithm, denoted as The Delayed Permuted Mirror Descent algorithm (see algorithm 1 below as well as figure 1 for a graphical illustration). First, the algorithm splits the time horizon T into M consecutive blocks, and performs a uniformly random permutation on the loss functions within each block. Then, it runs two online mirror descent algorithms in parallel, and uses the delayed gradients in  Figure 1: Scheme of predictions and updates of both parallel algorithms (best viewed in color; see text for details). Top color bars mark which iterations are in T 1 (purple lines) and which are in T 2 (green lines). Top timeline shows which predictor, w f or w s , is used to predict in each iteration. Middle timeline shows where gradients for updating w f come from (first τ iterations of the previous block), and lower timeline shows where gradients for updating w s come from (first M − τ iterations of the same block, each gradient from exactly τ rounds back). order to update two separate predictors -w f and w s , where w f is used for prediction in the first τ rounds of each block, and w s is used for prediction in the remaining M − τ rounds (here, f stands for "first" and s stands for "second"). The algorithm maintaining w s crucially relies on the fact that the gradient of any two functions in a block (at some point w) is equal, in expectation over the random permutation within each block. This allows us to avoid most of the cost incurred by delays within each block, since the expected gradient of a delayed function and the current function are equal. A complicating factor is that at the first τ rounds of each block, no losses from the current block has been revealed so far. To tackle this, we use another algorithm (maintaining w f ), specifically to deal with the losses at the beginning of each block. This algorithm does not benefit from the random permutation, and its regret scales the same as standard adversarial online learning with delayed feedback. However, as the block size M increases, the proportion of losses handled by w f decreases, and hence its influence on the overall regret diminishes.
The above refers to how the blocks are divided for purposes of prediction. For purposes of updating the predictor of each algorithm, we need to use the blocks a bit differently. Specifically, we let T 1 and T 2 be two sets of indices. T 1 includes all indices from the first τ time points of every block, and is used to update w f . T 2 includes the first M − τ indices of every block, and is used to update w s (see figure 1). Perhaps surprisingly, note that T 1 and T 2 are not disjoint, and their union does not cover all of {1, . . . , T }. The reason is that due to the random permutation in each block, the second algorithm only needs to update on some of the loss functions in each block, in order to obtain an expected regret bound on all the losses it predicts on.

Algorithm 1 Delayed Permuted Mirror Descent
Input: M , η f , η s Init: w f 1 = 0, w s 1 = 0, j f = j s = 1 Divide T to consecutive blocks of size M , and permute the losses uniformly at random within each block. Let f 1 , . . . , f T denote the resulting permuted losses.
Receive a loss function from τ places back: . If none exists (in the first τ iterations), take the 0 function.
Predict using w s js Receive a loss function from τ places back:

Analysis
The regret analysis of the Delayed Permuted Mirror Descent algorithm is based on a separate analysis of each of the two mirror descent sub-algorithms, where in the first sub-algorithm the delay parameter τ enters multiplicatively, but doesn't play a significant role in the regret of the second sub-algorithm (which utilizes the stochastic nature of the permutations). Combining the regret bound of the two sub-algorithms, and using the fact that the portion of losses predicted by the second algorithm increases with M , leads to an overall regret bound improving in M .
In the proof, to analyze the effect of delay, we need a bound on the distance between any two consequent predictors w t , w t+1 generated by the sub-algorithm. This depends on the mirror map and Bregman divergence used for the update, and we currently do not have a bound holding in full generality. Instead, we let Ψ (η f ,G) be some upper bound on w t+1 − w t , where the update is using step-size η f and gradients of norm ≤ G. Using Ψ (ηf ,G) we prove a general bound for all mirror maps. In Lemmas 3 and 4 in Appendix A.1, we show that for two common mirror maps (corresponding to online gradient descent and multiplicative weights), Ψ (η f ,G) ≤ c · η f G for some numerical constant c, leading to a regret bound of O( T (τ 2 /M + 1)). Also, we prove theorem 1 for 1-strongly convex mirror maps, although it can be generalized to any λ-strongly convex mirror map by scaling.
Theorem 1. Given a norm · , suppose that we run the Delayed Permuted Mirror Descent algorithm using a mirror map ψ which is 1-strongly convex w.r.t. · , over a domain W with diameter B 2 w.r.t the bregman divergence of ψ: ∀w, v ∈ W : ψ (w, v) ≤ B 2 , and such that the (sub)-gradient g of each loss function on any w ∈ W satisfies g * ≤ G (where · * is the dual norm of · ). Then the expected regret, given a delay parameter τ and step sizes η f , η s satisfies: , the regret is bounded by . similar to the standard adversarial learning case. However, as M increases, the regret gradually improves to O( √ T + τ ), which is the regret attainable in a purely stochastic setting with i.i.d. losses. The full proof can be found in appendix A.1.1, and we sketch below the main ideas.
First, using the definition of regret, we show that it is enough to upper-bound the regret of each of the two sub-algorithms separately. Then, by a standard convexity argument, we reduce this to bounding sums of terms of the form E for the second sub-algorithm (where w * f and w * s are the best fixed points in hindsight for the losses predicted on by the first and second sub-algorithms, respectively, and where for simplicity we assume the losses are differentiable). In contrast, we can use the standard analysis of mirror descent, using delayed gradients, to get a bound for the somewhat different terms E[ w f t − w * f , ∇f t−τ (w f t−τ ) ] for the first sub-algorithm, and E [ w s t − w * s , ∇f t−τ (w s our assumptions on the gradients of the losses and the distance between consecutive predictors produced by the first sub-algorithm. Overall, we get two regret bounds, one for each sub-algorithm. The regret of the first sub-algorithm scales with τ , similar to the no-permutation setting, but the sub-algorithm handles only a small fraction of the iterations (the first τ in every block of size M ). In the rest of the iterations, where we use the second sub-algorithm, we get a bound that resembles more the stochastic case, without such dependence on τ . Combining the two, the result stated in Theorem 1 follows.

Handling Variable Delay Size
So far, we discussed a setting where the feedback arrives with a fixed delay of size τ . However, in many situations the feedback might arrive with a variable delay size τ t at any iteration t, which may raise a few issues. First, feedback might arrive in an asynchronous fashion, causing us to update our predictor using gradients from time points further in past after already using more recent gradients. This complicates the analysis of the algorithm. A second, algorithmic problem, is that we could also possibly receive multiple feedbacks simultaneously, or no feedback at all, in certain iterations, since the delay is of variable size. One simple solution is to use buffering and reduce the problem to a constant delay setting. Specifically, we assume that all delays are bounded by some maximal delay size τ . We would like to use one gradient to update our predictor at every iteration (this is mainly for ease of analysis, practically one could update the predictor with multiple loss functions in a single iteration). In order to achieve this, we can use a buffer to store loss functions that were received but have not been used to update the predictors yet. We define Grad f and Grad s , two buffers that will contain gradients from time points in T 1 or T 2 , correspondingly. Each buffer is of size τ . If we denote by F t the set of function that have arrived in time t, we can simply store loss functions that have arrived asynchronously in the buffers defined above, sort them in ascending order, and take the delayed loss function from exactly τ iterations back in the update step. This loss function must be in the appropriate buffer since the maximal delay size is τ . From this moment on, the algorithm can proceed as usual and its analysis still applies.

Lower Bound
In this section, we give a lower bound in the setting where M < τ 3 with all feedback having delay of exactly τ . We will show that for this case, the regret bound cannot be improved by more than a constant factor over the bound of the adversarial online learning problem with a fixed delay of size τ , namely Ω √ τ T for a sequence of length T . We hypothesize that this regret bound also cannot be significantly improved for any M = O(τ ) (and not just τ /3). However, proving this remains an open problem.
Theorem 2. For every (possible randomized) algorithm A with a permutation window of size M ≤ τ 3 , there exists a choice of linear, 1-Lipschitz functions over [−1, 1] ⊂ R, such that the expected regret of A after T rounds (with respect to the algorithm's randomness), is For completeness, we we also provide in appendix A.2 a proof that when M = 0 (i.e. no permutations allowed), then the worst-case regret is no better than Ω( √ τ T ). This is of course a special case of Theorem 2, but applies to the standard adversarial online setting (without any local permutations), and the proof is simpler. The proof sketch for the setting where no permutation is allowed was already provided in Langford et al. [2009], and our contribution is in providing a full formal proof. The proof in the case where M = 0 is based on linear losses of the form f t = α t · w t over [−1, +1], where α t ∈ {−1, +1}. Without permutations, it is possible to prove a Ω( √ τ T ) lower bound by dividing the T iterations into blocks of size τ , where the α values of all losses at each block is the same and randomly chosen to equal either +1 or −1. Since the learner does not obtain any information about this value until the block is over, this reduces to adversarial online learning over T /τ rounds, where the regret at each round scales linearly with τ , and overall regret at least Ω(τ T /τ ) = Ω( √ τ T ). In the proof of theorem 2, we show that by using a similar construction, even with permutations, having a permutation window less than τ /3 still means that the α values would still be unknown until all loss functions of the block are processed, leading to the same lower bound up to constants.
The formal proof appears in the appendix, but can be sketched as follows: first, we divide the T iterations into blocks of size τ /3. Loss functions within each block are identical, of the form f t = α t · w t , and the value of α per block is chosen uniformly at random from {−1, +1}, as before. Since here, the permutation window M is smaller than τ /3, then even after permutation, the time difference between the first and last time we encounter an α that originated from a single block is less than τ . This means that by the time we get any information on the α in a given block, the algorithm already had to process all the losses in the block, which leads to the same difficulty as the no-permutation setting. Specifically, since the predictors chosen by the algorithm when handling the losses of the block do not depend on the α value in that block, and that α is chosen randomly, we get that the expected loss of the algorithm at any time point t equals 0. Thus, the cumulative loss across the entire loss sequence is also 0. In contrast, for w * , the optimal predictor in hindsight over the entire sequence, we can prove an expected accumulated loss of −Ω( √ τ T ) after T iterations, using Khintchine inequality and the fact that the α's were randomly chosen per block. This leads us to a lower bound of expected regret of order √ τ T , for any algorithm with a local permutation window of size M < τ /3.

Experiments
We consider the adversarial setting described in section 4, where an adversary chooses a sequence of functions such that every τ functions are identical, creating blocks of size τ of identical loss functions, of the form f t (w t ) = α t · w t where α t is chosen randomly in {−1, +1} for each block. In all experiments we use T = 10 5 rounds, a delay parameter of τ = 200, set our step sizes according to the theoretical analysis, and report the mean regret value over 1000 repetitions of the experiments.
In our first experiment, we considered the behavior of our Delayed Permuted Mirror Descent algorithm, for window sizes M > τ , ranging from τ + 1 to T . In this experiment, we chose the α values randomly, while ensuring a gap of 200 between the number of blocks with +1 values and the number of blocks with −1 values (this ensures that the optimal w * is a sufficiently strong competitor, since otherwise the setting is too "easy" and the algorithm can attain negative regret in some situations). The results are shown in Figures 2  and 3, where the first figure presents the accumulated regret of our algorithm over time, whereas the second figure presents the overall regret after T rounds, as a function of the window size M .
When applying our algorithm in this setting with different values of M > τ , ranging from M = τ + 1 and up to M = T , we get a regret that scales from the order of the adversarial bound to the order of the stochastic bound depending on the window size, as expected by our analysis. For all window sizes greater than 5 · τ , we get a regret that is in the order of the stochastic bound -this is not surprising, since after the permutation we get a sequence of functions that is very close to an i.i.d. sequence, in which case any algorithm can be shown to achieve O( √ T ) regret in expectation. Note that this performance is better than that predicted by our theoretical analysis, which implies an O( √ T ) behavior only when M ≥ Ω(τ 2 ). It is an open and interesting question whether it means that our analysis can be improved, or whether there is a harder construction leading to a tighter lower bound.
In our second experiment, we demonstrate the brittleness of the lower bound construction for standard online learning with delayed feedback, focusing on the M < τ regime. Specifically, we create loss functions with blocks as before (where following the lower bound construction, the α values in each block of size τ = 200 is chosen uniformly at random). Then, we perform a random permutation over consecutive windows of size M (ranging from M = 0 up to M = 9 10 τ in intervals of 1 10 τ ). Finally, we run standard Online Gradient Descent with delayed gradients (and fixed step size 1/ √ T ), on the permuted losses. The results are presented in Figure 4.
For window sizes M < τ 2 we see that the regret is close to the adversarial bound, whereas as we increase the window size the regret decreases towards the stochastic bound. This experiment evidently shows that this hardness construction is indeed brittle, and easily breaks in the face of local permutations, even for window sizes M < τ .

Discussion
We presented the OLLP setting, where a learner can locally permute the sequence of examples from which she learns. This setting can potentially allow for improved learning in many problems, where the worst-case regret is based on highly adversarial yet brittle constructions. In this paper, we focused on the problem of learning from delayed feedback in the OLLP setting, and showed how it is possible to improve the regret by allowing local permutations. Also, we proved a lower bound in the situation where the permutation window is significantly smaller than the feedback delay, and showed that in this case, permutations cannot allow for a better regret bound than the standard adversarial setting. We also provided some experiments, demonstrating the power of the setting as well as the feasibility of the proposed algorithm. An interesting open question is what minimal permutation size allows non-trivial regret improvement, and whether our upper bound in Theorem 1 is tight. As suggested by our empirical experiments, it is possible that even small local permutations are enough to break highly adversarial sequences and improve performance in otherwise worst-case scenarios. Another interesting direction is to extend our results to a partial feedback (i.e. bandit) setting. Finally, it would be interesting to study other cases where local permutations allow us to interpolate between fully adversarial and more benign online learning scenarios.

A.1 Analysis Of The Delayed Permuted Mirror Descent Algorithm
We will use throughout the proofs the well known Pythagorean Theorem for Bregman divergences, and the 'projection' lemma that considers the projection step in the algorithm.

Lemma 1. Pythagorean Theorem for Bregman divergences
Let v be the projection of w onto a convex set W w.r.t Bregman divergence ψ : v = argmin u∈W ψ (u, w), Lemma 2. Projection Lemma Let W be a closed convex set and let v be the projection of w onto W, namely, v = argmin x∈W x − w 2 . Then, for every u ∈ W, w − u 2 − v − u 2 ≥ 0 The following lemma gives a bound on the distance between two consequent predictions when using the Euclidean mirror map: Lemma 3. Let g ∈ R n s.t. g 2 < G, W a convex set, and η > 0 be fixed. Let w ∈ W and w 2 = w − η · g. Then, for w = argmin u∈W w 2 − u 2 2 , we have that w − w ≤ η · G Proof. From the projection lemma: w 2 − w 2 2 ≥ w − w 2 2 and so: w 2 − w 2 ≥ w − w 2 . From definition: w 2 − w 2 = η · g 2 ≤ η · G. and so we get: We prove a modification of Lemma 2 given in Menache et al. [2014] in order to bound the distance between two consequent predictions when using the negative entropy mirror map: Lemma 4. Let g ∈ R n s.t. g 1 ≤ G for some G > 0 and let η > 0 be fixed, with η < 1 √ 2·G . For any distribution vector w in the n − simplex, if we define w to be the new distribution vector ∀i ∈ {1, ..., n} , w i = w i · exp (−η · g i ) n j=1 w j · exp (−η · g j ) Proof. Since g ∞ < G and η < 1 √ 2·G we get that ∀i : |η · g i | < 1. We have that: Since w 1 = 1, we can apply Holder's inequality, and upper bound the above by Using the inequality 1 − x ≤ exp (−x) ≤ 1 1+x for all |x| ≤ 1, we know that 1 − η · g i ≤ exp (−η · g i ) ≤ 1 1 + η · g i and since −ηG ≤ η · g i ≤ ηG we have that 1 − η · g i ≤ exp (−η · g i ) ≤ 1 1 + η · g i ≤ 1 1 − ηG and so we get: Using again the fact that −ηG ≤ η · g i ≤ ηG, we have Now, since ηG < 1, we get that: and so we can conclude that Since η < 1 √ 2G , we get (η · G) 2 < 1 2 . Thus we get: which gives us our desired bound.
With the above two lemmas in hand, we bound the distance between consequent predictors by cηG, where c is a different constant in each mirror map: c = 1 for the euclidean case, and c = 3 for the negative entropy mirror map. Note that both mapping are 1-strongly convex with respect to their respective norms. For other mappings with a different strong convexity constant, one would need to scale the step sizes according to the strong convexity parameter in order to get the bound.

A.1.1 Proof of Theorem 1
We provide an upper bound on the regret of the algorithm, by competing against the best fixed action in each one of the sets of iterations-the first τ iterations and the last M − τ iterations in each block. This is an upper bound on competing against the best fixed predictor in hindsight for the entire sequence. Formally, we bound: f t (w) and w * s = argmin where expectation is taken over the randomness of the algorithm. The diameter of the domain W is bounded by B 2 , and so ψ w * f , w f 0 ≤ B 2 and ψ (w * s , w s 0 ) ≤ B 2 . We start with a general derivation that will apply both for w s and for w f simultaneously. For the following derivation we use the notation w j , w j+1 omitting the f, s superscript, for denoting subsequent updates of the predictor vector, whether it is w s or w f . Denote by g j the gradient used to update w j , i.e., ∇ψ w j+ 1 2 = ∇ψ (w j ) − η · g j , and w j+1 = argmin w∈W ψ w, w j+ 1 2 .
Then the expected sum of losses is: Eᾱ (1→i,j−τ −1) w i,j · 1 2 · 1 + 1 2 · (−1) = 0 The last equality is true because every first α in any block has probability 1 2 to be either +1 or −1. We now continue to the expected sum of losses for the optimal choice of w * = argmin w∈W