Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback

We thank the reviewer for their thorough and positive review of our paper. Below we address the reviewer’s main questions and concerns.

Regarding the full knowledge of $\Pi$ and $\mathcal{F}$

We would like to clarify that in the policy class framework of contextual bandits, it is standard to assume the underlying policy class $\Pi$ is finite as no structural assumptions are made on the policy class (see e.g. [1,2,3]). In the general function approximation setting, however, nontrivial bounds can be obtained even in cases where the underlying function class $\mathcal{F}$ is infinite, as long as we have access to an online least-squares oracle for the class which is sufficiently stable - that is, our main result in Theorem 4.6 does not require that $\mathcal{F}$ is finite, and in particular the only interface of the CMAB algorithm with the function class is via the oracle $\mathcal{O}_{sq}^{\mathcal{F},\beta}$. As a Corollary from this general theorem (see Corollary 4.13), we consider a particular case in which $\mathcal{F}$ is finite and derive a more explicit bound with dependence on $\log |\mathcal{F}|$. For infinite classes (such as linear functions), the dependence on $\log |\mathcal{F}|$ can often be replaced by other parameters such as the underlying dimension.

Regarding the definition of the least-squares oracle regret

The quantity $R_T(\mathcal{O}_{sq}^{\mathcal{F}})$ denotes an upper bound on the expected least-squares regret of the online regression oracle in use, and is defined in lines 206-208 of the main text.

Regarding the use of an oracle in the DA-FA algorithm

We emphasize that our main result given in Theorem 4.6 applies in a black-box manner, in the sense that any online oracle can be used in Algorithm 2 and only its regret on the observed sequence affects the resulting bound. In particular, even an oracle which does not have a regret guarantee with respect to all sequences, e.g. one which only has a heuristic regret bound or one which works on the realized sequence of observations, would result in a meaningful regret bound for Algorithm 2.

We would like to thank you again for the supportive review of our paper, and would be happy to answer any further questions you may have during the discussion period.

References:

[1] Dudik, Miroslav, et al. "Efficient optimal learning for contextual bandits." arXiv preprint arXiv:1106.2369 (2011).

[2] Agarwal, Alekh, et al. "Taming the monster: A fast and simple algorithm for contextual bandits." International conference on machine learning. PMLR, 2014.

[3] Auer, Peter, et al. "The nonstochastic multiarmed bandit problem." SIAM journal on computing 32.1 (2002): 48-77.

We thank the reviewer for their thorough and positive review of our paper. Below we address the reviewer’s main questions and concerns.

Regarding the FIFO assumption

While we agree that this assumption might be limiting in some cases, it seems highly unlikely to us that this assumption can be dropped completely in general. The intuitive reason lies in the fact that the interface between the CMAB algorithm and the least-squares oracle heavily depends on the order of the observed observations, which makes it difficult to relate the sequence of observations to the undelayed sequence without the FIFO assumption. One possibility would be to work in batches of length $d_{\max}$ and wait for pending observations, but such an approach would result in a regret bound of the form $\sqrt{d_{\max} KT}$ which is undesirable as it contains a multiplicative dependence of the maximal delay and the number of arms which we wish to avoid. The reviewer also suggests that the FIFO assumption may perhaps be weakened to still obtain meaningful results - this seems to us like a great question for future research and we are currently unsure about the extent to which the FIFO assumption can be relaxed.

We now address the questions raised by the reviewer:

1. The reviewer makes an interesting suggestion regarding weakening the $\beta$-stability assumption to require stability over all intervals of length at most $d_{\max}$. Our current approach which seems inherent given our regret decomposition relies on the fact that the sum over $t$ of discrepancies between oracle predictions between rounds $t$ and $t+d_t$ will be suitably bounded. If we only assumed stability across windows of length $d_{\max}$, it would allow the possibility of a drift of order at least $T$ in the oracle’s predictions across the entire horizon, which we are not sure is possible to handle in our current approach.

2. The gap between the upper and lower bounds in our regret bound seems to us as a result of suboptimality in the upper bound given in Theorem 4.6. That is, we believe that our analysis of the Hedge forecaster is tight, and that using it with perhaps a different CMAB algorithm with improved delay dependence may result in an optimal regret bound without the additional $\sqrt{d_{\max}}$ factor.

We thank you again for the supportive review of our paper, and would be happy to answer any further questions you may have during the discussion period.

We thank the reviewer for their thorough review. Below we address the reviewer’s main questions and concerns.

Regarding the stability and FIFO assumptions

While the stability assumption does limit various oracles in standard use, we emphasize that as we prove in Theorem 4.3, some additional assumption on the oracle other than online regret minimization is necessary in the presence of delays. While we do not have a formal lower bound showing the necessity of the FIFO assumption, the interface between the CMAB algorithm and the oracle in the function approximation setting makes it seems unlikely that such an assumption can be avoided completely, as the oracle’s outputs may be highly dependent on the ordering of the observations, which in turn depends on the trajectory of actions performed by the CMAB algorithm.

Regarding the presentation

We thank the reviewer for pointing out unclarities in our presentation. We will make sure to provide more intuition on the loss estimators for the policy class setting in addition to the explanation in lines 171-177. We will also make sure to add some high-level intuition about the connection between the stability of the algorithm in the policy class setting and the $\beta$-stability in the function approximation setting.

Regarding empirical evidence

We emphasize that this is a purely theoretical paper whose goal is to provide theoretical guarantees for CMAB algorithms in the presence of delayed feedback, which has not been studied in the general function approximation setting prior to this work.

Regarding additional comparisons

We will make sure to include additional discussion on delayed feedback in linear bandits. We will also mention existing works on privacy-aware bandits, though this area of research is not as directly relevant to our work as we mainly focus on delayed feedback in the general function approximation setting of CMAB.

We now address the questions raised by the reviewer:

1. The reviewer raises a very interesting question regarding the $\beta$-stability parameter for other oracles other than Hedge. We remark that in the linear function approximation setting, the standard least squares oracle seems to satisfy such a stability assumption, as is implicit in the analysis of the linear case, see e.g. [1] who study delayed feedback in linear bandits. In this setting, the inverse covariance matrices of the data are monotone in time, which allows relating the least squares estimator with respect to the delayed feedback to the up-to-date estimator in a manner which ultimately results in a suitable stability property. We emphasize that refining the stability assumption and analyzing the stability parameters of existing oracles in use seems like a very interesting question for future research.

2. We assume that by “Doubling-trick” the reviewer refers to the “buckets reduction" in which $d_{\max}$ copies of the non-delayed CMAB algorithm are run in parallel, and each copy is applied in the appropriate block. This approach would yield a regret rate of $O(\sqrt{d_{\max}TK \cdot R(O)})$ in which there is a multiplicative dependence on both $d_{\max}$ and the number of arms $K$. One of our main goals was to avoid such a multiplicative dependence, and to obtain a sum of two bounds: one that depends only on the delays and the other of the form $\sqrt{KT}$ which is the optimal bound without delays.

We thank you again for the informative review of our paper, and would of course be happy to answer any further questions you may have during the discussion period.

References:

[1] Vernade, Claire, et al. "Linear bandits with stochastic delayed feedback." International Conference on Machine Learning. PMLR, 2020.

We thank the reviewer for their thorough and positive review of our paper. Below we address the reviewer’s main concerns and questions.

Regarding the technical depth of the paper

While the technical analysis in our paper builds upon techniques from prior related work, we emphasize that adapting known results in the function approximation setting to the delayed variant is a highly challenging and nontrivial problem. In particular, coming up with a suitable assumption on the online oracle in use which would allow obtaining nontrivial regret bounds is, in our opinion, one of the major contributions of our work. This contribution is highlighted by Theorem 4.3 which shows that an additional assumption on the oracle other than online regret minimization is necessary in order to obtain sublinear regret in the presence of delays, an observation which may seem logical but is highly nontrivial in hindsight. Furthermore, as we show in Lemma 4.12, this stability assumption is satisfied by the Hedge aggregating forecaster with $\beta=\log|\mathcal{F}|$ which is also a nontrivial observation.

Regarding the FIFO assumption

While we do not have a formal justification, we highly believe that the FIFO assumption might be necessary in order to obtain nontrivial bounds in the online function approximation setting with delays. The intuitive reason is that in this setting, the algorithm makes use of an online oracle which estimates the losses in a black-box manner, and whose internal workings can be very complicated. The interface between the CMAB algorithm and the online oracle highly depends on the order in which feedback is fed to the oracle, and thus this order can in general affect the oracle’s outputs. If the FIFO assumption is not satisfied, the CMAB algorithm essentially has no choice but to feed the observations into the oracle in an arbitrary order determined by the adversarial delays sequence, or alternatively work in blocks of length $d_{\max}$ each to force a suitable ordering which would result in an undesirable regret bound of the form $\sqrt{d_{\max} KT}$.

We thank you again for the supportive review of our paper, and would be happy to answer any further questions you may have during the discussion period.