A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays

Weaknesses:

1. We will add a clarification around Lines 48-49, where the term is first used. Technically, the distribution drift is the ratio $x_{t+d_t,i} / x_{t,i}$ of the probability of playing action $i$ at round $t+d_t$, when the observation arrives, to the probability it had when it was played at round $t$.

2. Thanks, we will fix it.

3. Thanks for the suggestion.

4. We had to decrease the skipping threshold of Zimmert and Seldin (2020) to control the distribution drift that is due to the loss shift (see Appendix B.2 in the supplementary material). More explicitly, $K^{1/3}$ comes from a bound on the weighted average of loss estimates in Equation (25) that is bounded in Lemma 9. For now we do not know how to remove this factor, but we expect that it might require a different analysis of the distribution drift.

5. The core of Lemma 2, which relates drifted regret to the actual regret, is based on Lemma 3, which controls the distribution drift using implicit exploration and skipping. The factor of 1/4 in front of $\overline{Reg}\_T$ in Lemma 2 and the summation of implicit exploration terms come from Lemma 3. Virtual rearrangement of arrivals is needed in the proof of Lemma 2, because at the moment we have no other way to analyze multiple simultaneous arrivals. Lemma 5, which analyzes Algorithm 2 for virtual rearrangements, shows that the additional delay caused by the rearrangements is small (limited by $\sigma_{\max}^t$).

6. Thanks for the references.

Questions:

1. It is a common practice to use \citeauthor{...} command on repeated mentions of the same paper within a short text span distance, whenever it does not lead to confusion which work is being mentioned. We hope it was not confusing in Line 58. We can add a year if necessary.

2. The term “outstanding observations” was introduced by Zimmert and Seldin (2020). An observation is considered “outstanding” from the moment an action from which it originates is played to the moment it is revealed to the algorithm.

3. Skipping is done both in the algorithm and in the analysis.

4. Yes, it is straightforward to obtain a bound for $C$-corrupted regime.

The algorithm design itself needs to be more novel

It is very common for BOBW algorithms to bear close resemblance to the adversarial algorithms they are derived from, because it allows inheritance of the adversarial regret guarantees. For example, the EXP3++ algorithm (Seldin and Slivkins, 2014) only makes a small modification to the exploration distribution of the well-known EXP3 algorithm, and the Tsallis-INF algorithm (Zimmert and Seldin, 2021) is essentially identical to the INF algorithm designed by Audibert and Bubeck (2010) for adversarial bandits. The major contribution of many BOBW papers, including ours, is the stochastic analysis that stays within the predefined framework of the parent adversarial algorithm, which only allows minor algorithmic modifications due to the necessity to preserve the adversarial regret guarantees. The preservation of the algorithm design is, therefore, a desired feature. The value and technical sophistication of these contributions, including ours, should not be underestimated though. We introduced several important algorithmic and analytical tools:

1. We are the first to control the distribution drift without altering the learning rates, by using implicit exploration and skipping (Lemma 3). Prior work controlled the drift by damping the learning rates using knowledge of $d_{\max}$, but this technique adds $d_{\max}$ linearly to the regret bound and fails in presence of just a single outlier of order $d_{\max}$.
2. Implicit exploration design is very delicate, because it has to be sufficiently large to control the drift, but at the same time sufficiently small, because it adds up linearly to the bound. We have designed an implicit exploration scheme that does not ruin neither the stochastic nor the adversarial bound (Lemma 4). Note that our implicit exploration scheme depends on the delays, but not the losses. Therefore, it has a great potential to be useful in other settings with delayed feedback.
3. We have also derived the first approach to relate drifted and non-drifted regret in presence of delay outliers (Lemma 2). This contribution involves introduction of the greedy rearrangement algorithm (Algorithm 2) and drift control by Lemma 3. Prior work has only allowed to relate drifted regret and the actual regret, when the delays were bounded by $d_{\max}$, and it was adding $d_{\max}$ linearly to the regret bound. Thus, it was failing in presence of even a single delay of order $T$.

We believe that our contribution has the potential to bring a transformative effect to the field of BOBW learning with delayed feedback.

The algorithm design is not optimized

• Concerning (1): when an observation is processed at time $t$ it modifies the playing distribution $x_t$ at time $t$. If at time $t$ we would decide to go back to some old observations, the actual delay from the moment the action was played to the moment it is reconsidered would remain above the updated threshold, so it would not be possible to add it back.

• Concerning (2): while it feels wasteful to drop observations, we note that the cardinality of the skipped set is smaller than the regret bound, which is in turn sublinear in the total number of observations. Processing of skipped observations would add a lot of pain in the analysis, but add nothing in terms of the bound (because of matching lower bounds), and almost nothing in terms of empirical performance, because of the small size of the skipped set relative to the total number of observations.

Q1: We are sorry, it is a typo. It should be $\hat \ell_{t, i_{T}^{*}}$ at the end of the display between Lines 328 and 329 in Appendix A.

References Y. Seldin and A. Slivkins. One practical algorithm for both stochastic and adversarial bandits. ICML, 2014. J-Y. Audibert and S. Bubeck. Regret bounds and minimax policies under partial monitoring. JMLR, 2010.

A detailed explanation of the selection of regularizers or learning rates: The learning rates and regularizers were taken directly from Zimmert and Seldin (2020), because we had to have the adversarial regret guarantee. The intuition behind the choice of regularizers is that the adversarial regret bound, $\sqrt{KT} + \sqrt{dT\log K}$ for fixed delays $d$, and the construction of the matching lower bound combine a lower bound for bandits to show the necessity of the $\sqrt{KT}$ term, and a full information lower bound to show the necessity of the $\sqrt{dT / logK}$ term. The negative Tsallis-entropy regularizer with power 1/2 is optimal in the bandit setting, and the negative entropy regularizer is optimal in the full information setting, and the combination achieves the optimal regret bound in the delayed feedback setting. The learning rate $\eta_t$ is the standard learning rate for bandits, and the learning rate $\gamma_t$ is the standard full information learning rate. We refer to Zimmert and Seldin (2020) for further details. The primary challenge addressed by our work is that these regularizers and learning rates also work in the stochastic setting. We make a small adjustment of $\gamma_t$ by a constant due to adjusted skipping.

What makes analysis challenging due to aiming BoBW bounds: First, we want to emphasize that our focus is on BoBW analysis in presence of delay outliers, and that the work of Masoudian et al. (2022) cannot handle delay outliers, because even a single delay outlier of order $T$ renders both their stochastic and adversarial regret bound linear. Concerning analytical challenges: the stochastic part of our analysis is based on control of the distribution drift (the ratio $x_{t+d_t,i} / x_{t,i}$ of the probability of playing action $i$ at round $t+d_t$, when the observation arrives, to the probability it had when it was played at round $t$). Control of the distribution drift is the most commonly used approach in bandits with delayed feedback, also used by Masoudian et al. (2022). So far the only way to control the distribution drift was by damping the learning rate, but it only applies when the maximal delay $d_{\max}$, which corresponds to the control range, is known, and it adds $d_{\max}$ linearly to the regret bound. Therefore, this technique fails in presence of delay outliers. We are the first to achieve control of the distribution drift in presence of delay outliers. In order to achieve it we introduced several important algorithmic and analytical tools:

1. We are the first to control the distribution drift without altering the learning rate. Our control is based on a combination of implicit exploration, which is used to control the drift due to the change of regularizer, and skipping, which is used to control the drift due to the loss shift (Lemma 3).
2. The challenge in designing a successful implicit exploration scheme is that implicit exploration has to be sufficiently large to control the ratio, but at the same time sufficiently small, because it adds up linearly to the bound. We have shown that the contribution of our implicit exploration to the bound, $\sum_{t=1}^T \lambda_{t,t+\hat d_t}$, does not ruin neither the stochastic nor the adversarial bound (Lemma 4).
3. We have also derived the first approach to relate drifted and non-drifted regret in presence of delay outliers (Lemma 2). Prior work has only allowed to relate the two when the delays were bounded by $d_{\max}$, and it was adding $d_{\max}$ linearly to the regret bound. Thus, it was failing in presence of even a single delay of order $T$.

We believe that all these tools will find additional applications in other learning settings. Finally, we note that the analysis of Zimmert and Seldin (2020) only applies in the adversarial setting. It is unknown whether their analysis technique, which is not based on distribution drift, can be applied in the stochastic setting.

Interpretation of implicit exploration terms $\lambda_{s,t}$: The role of $\lambda_{s,t}$ is to control the distribution drift (the ratio $x_{t+d_t,i} / \max(x_{t,i}, \lambda_{t,t+d_t})$). To control the ratio it cannot be too small, but since $\sum_{t=1}^T \lambda_{t,t+\hat d_t}$ adds up linearly to the bound, it cannot be too large either. Note that $\lambda_{s,t}$ only depends on the delays, but not the losses.

Concerning the novelty of our approach to handling excessive delays: First, we want to emphasize that the work of Masoudian et al. (2022) is unable to cope with excessive delays, because even a single delay of order $T$ renders their regret bound linear in both stochastic and adversarial environments. The work of Zimmert and Seldin (2020) only copes with excessive delays in the adversarial regime. It is the only work on delayed feedback and adversarial losses known to us that is not using control of the distribution drift in the analysis, but it is unknown whether their analysis technique can be applied to stochastic losses to obtain BOBW results. The stochastic part of our analysis is based on the more broadly used approach based on control of the distribution drift (the ratio $x_{t+d_t, i} / x_{t,i}$ of the probability of playing action $i$ at round $t+d_t$, when the observation arrives, to the probability it had when it was played at round $t$). So far the only way to control the distribution drift was by damping the learning rate, but it only works when the maximal delay $d_{\max}$, which corresponds to the control range, is known, and it adds $d_{\max}$ linearly to the regret bound. Therefore, this technique fails in presence of delay outliers. We are the first to achieve control of the distribution drift in presence of delay outliers. In order to achieve it we introduced several important algorithmic and analytical tools:

1. We are the first to control the distribution drift without altering the learning rate. Our control is based on a combination of implicit exploration, which is used to control the drift due to the change of regularizer, and skipping, which is used to control the drift due to the loss shift (Lemma 3).
2. The challenge in designing a successful implicit exploration scheme is that implicit exploration has to be sufficiently large to control the ratio, but at the same time sufficiently small, because it adds up linearly to the bound. We have shown that the contribution of our implicit exploration to the bound, $\sum_{t=1}^T \lambda_{t,t+\hat d_t}$, does not ruin neither the stochastic nor the adversarial bound (Lemma 4).
3. We have also derived the first approach to relate drifted and non-drifted regret in presence of delay outliers (Lemma 2). Prior work has only allowed to relate the two when the delays were bounded by $d_{\max}$, and it was adding $d_{\max}$ linearly to the regret bound. Thus, it was failing in presence of even a single delay of order $T$.

We believe that all these tools will find additional applications in other learning settings.

Clarification concerning the use of Lemmas 11 to 13, which were taken from Masoudian et al. (2022): We recall that $\overline{Reg}\_T= \sum_{t=1}^T x_{t,i}\Delta_i$. Substitute this definition into the inequality in Line 435. Lemmas 11 to 13 are used to bound three parts of the inequality in Line 435 by finding the worst-case choice of $x_{t,i}$ for each of the parts. Since the worst-case choice of $x_{t,i}$ is algorithm-independent, the lemmas can be applied. We will add the clarification to the paper.