Improved Regret for Bandit Convex Optimization with Delayed Feedback

We investigate bandit convex optimization (BCO) with delayed feedback, where only the loss value of the action is revealed under an arbitrary delay. Let $n,T,\bar{d}$ denote the dimensionality, time horizon, and average delay, respectively. Previous studies have achieved an $O(\sqrt{n}T^{3/4}+(n\bar{d})^{1/3}T^{2/3})$ regret bound for this problem, whose delay-independent part matches the regret of the classical non-delayed bandit gradient descent algorithm. However, there is a large gap between its delay-dependent part, i.e., $O((n\bar{d})^{1/3}T^{2/3})$, and an existing $\Omega(\sqrt{\bar{d}T})$ lower bound. In this paper, we illustrate that this gap can be filled in the worst case, where $\bar{d}$ is very close to the maximum delay $d$. Specifically, we first develop a novel algorithm, and prove that it enjoys a regret bound of $O(\sqrt{n}T^{3/4}+\sqrt{dT})$ in general. Compared with the previous result, our regret bound is better for $d=O((n\bar{d})^{2/3}T^{1/3})$, and the delay-dependent part is tight in the worst case. The primary idea is to decouple the joint effect of the delays and the bandit feedback on the regret by carefully incorporating the delayed bandit feedback with a blocking update mechanism. Furthermore, we show that the proposed algorithm can improve the regret bound to $O((nT)^{2/3}\log^{1/3}T+d\log T)$ for strongly convex functions. Finally, if the action sets are unconstrained, we demonstrate that it can be simply extended to achieve an $O(n\sqrt{T\log T}+d\log T)$ regret bound for strongly convex and smooth functions.

Paper

Similar papers

Peer review

Reviewer GZvs6/10 · confidence 4/52024-07-06

Summary

The paper investigates the online convex optimization problem with delayed bandit feedback. The main contribution is introducing a new algorithm that uses a block updating mechanism with FTRL, proving the algorithm achieves a delay-dependent regret of $O(\sqrt{dT})$, which is known to be optimal when the average delay is close to the maximal delay: $\bar{d} \approx d$.

Strengths

* The paper shows a valuable algorithm that improves on the known regret bounds for the delayed BCO. * The techniques used, specifically block updates, while not novel, are original for this kind of problem.

Weaknesses

* The paper could be written more clearly. I found myself understanding parts of the introduction only after going through the entire paper (e.g. line 69). * The proofs are hard to follow. Some explanations before each lemma to understand how those are used would be helpful. * It seems hard to use the blocking updates to further improve the regret, so the value of the presented algorithm could be temporary.

Questions

Can you explain each term in the theorems and where does it come from? As is, the theorems are packed with different terms and besides substituting the optimal values I don't know how to interpret them

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors properly acknowledge the limitations of their work.

Reviewer knrh7/10 · confidence 3/52024-07-12

Summary

The paper investigates the problem of bandit convex optimization (BCO) with delayed feedback, where the value of the action is revealed after some delay. The authors proposed an algorithm D-FTBL, and proved that it enjoys a regret bound of $O\left(\sqrt{n} T^{3/4}+\sqrt{d T}\right)$, closing the gap between the previous result and the lower bound on delay-dependent part. Furthermore, the proposed algorithm can improve the regret bound to $O\left((n T)^{2 / 3} \log ^{1 / 3} T+d \log T\right)$ for strongly convex functions, and if the action sets are unconstrained, the proposed algorithm can achieve an $O(n \sqrt{T \log T}+d \log T)$ regret bound for strongly convex and smooth functions.

Strengths

- The writing style of the article is excellent, and the overall flow is very smooth and enjoyable to follow. - The literature review is thorough and well-integrated into the paper. It provides a solid foundation for the research by situating it within the existing literature of BCO and highlighting the gaps that the authors aim to fill. - The methodology seems innovative. The application of blocking update mechanism not only adds substantial value to the current study but also potentially inspires other problems with delayed feedback. - The theoretical results presented in the paper are logically sound and well-supported. Each point is substantiated with adequate evidence, avoiding any logical leaps or inconsistencies.

Weaknesses

The paper lacks numerical experiments. Besides this, I did not spot any significant weaknesses.

Questions

I would be curious about how much improvement can be made in practice. In bandit setting, people often consider large time horizon, in which cases the regret is dominated by the delay-independent term.

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

The authors addressed the limitations and consider it as future work.

Reviewer pbhB7/10 · confidence 3/52024-07-12

Summary

This paper studies the problem of bandit convex optimization with delayed feedback (where the feedback for round $t$ is delayed by an arbitrary number of rounds $d_t$). For this problem, they show $O(\sqrt{n} T^{3/4} + \sqrt{d T})$ regret in general, $O((n T)^{2/3} \log^{1/3} (T) + d \log(T))$ regret for strongly-convex functions, and $O(n \sqrt{T \log(T)} + d \log(T))$ regret for smooth and strongly-convex functions in an unconstrained settting. In these bounds, $n$ is the dimension, $T$ is the horizon and $d$ is the maximum delay.

Strengths

- Their results for the general setting strictly improve on results that use the maximum delay $d$ (Heliou et al (2020)), and supplement results that use the average delay $\bar{d}$ (Bistritz et al 2022). - They give improved regret for specific settings. - The literature review is very thorough and the authors are diligent in pointing to the origin of ideas throughout the paper. - There is extensive discussion on the difference in techniques with respect to existing approaches and how their approach result in tighter regret gaurantees. - The presentation is clear and intuitive.

Weaknesses

- The paper only makes an improvement on state-of-the-art for certain delay sequences, i.e. when $d = O((n\bar{d})^{2/3} T^{1/3})$.

Questions

No questions at this point.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

There is some discussion of the limitation due to the fact that the regret is given in terms of maximum delay rather than average delay.

Reviewer S7rX5/10 · confidence 3/52024-07-13

Summary

This paper studies the bandit convex optimization problem with delayed feedback, where the loss value of the selected action is revealed under an arbitrary delay. Previous work achieves $\mathcal{O}( \sqrt{n} T^{3/4} + (n\bar{d})^{1/3} T^{2/3})$ regret bound of this problem. The authors develop a novel algorithm and show that it improves the delay-related part to $\mathcal{O}( sqrt{dT})$ when $d$ the maximum delay, is close to $\bar{d}$, the average delay (specifically, strictly better when d = $\mathcal{O}( (n\bar{d})^{2/3} T^{1/3} )$. The authors claim that the primary idea is to decouple the joint effect of the delays by incorporating the delayed bandit feedback with a blocking update mechanism, which reduces the correlation between recent delayed updates (otherwise there could be a $d^2$ term).

Strengths

1. Though I have skimmed the proof of several lemmas, the analysis part seems to be rigorous and mathematically correct. 2. The usage of blocking update mechanism is very interesting, and could be applied in other similar settings.

Weaknesses

1. The contribution of this work is quite concerning. It would be better for the authors to emphasis the contribution (either algorithmic or analytic) on improving the delayed feedback result for BCO problem in certain conditions that the max delay $d$ is close to $\bar{d}$? Some parts of the proof are rather straightforward and standard.

Questions

The questions are raised in the weakness section. I am willing to re-evaluate the scores if these questions are properly answered.

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

This paper is pure theoretical and does not have any limitations.

Reviewer vCin7/10 · confidence 4/52024-07-15

Summary

The authors consider the problem of bandit convex optimization in the adversarial setting under delays. In each round, an adversary selects a convex function $f_t$, the optimizer selects an input $x_t$ and observes $f_t(x_t)$ with a delay of $d_t$ timesteps. The goal is to minimize regret with respect to the best action in hindsight. Without any delay, the best regret is obtained by the zeroth order one-point flaxman updates. Prior work in the delayed setting adapts this algorithm to use the oldest available feedback to make the update. However, the observation that the authors make is that according to this scheme, information might become available much before it is used -- if there is older information that has not been used yet. So instead, to minimize the gap between availability and utilization of information, the authors propose a blocking algorithm. Where at the end of each block, all available information so far is used to make the update. This enables them to get improved regret bounds.

Strengths

1. The paper is very well-written with the results laid out very clearly, and the rationale for the solution explained well. 2. The solution to use blocking in order to minimize stale information is creative, and leads to better bounds. 3. The results are comprehensive across different classes of objectives, and the authors thus show the wide applicability of the technique.

Weaknesses

**Significance** The practical impact of this theoretical toy seems limited, and the problem was of more interest a couple of years ago. In order to increase the reception, it would be instructive to connect the implications of these findings to other topics of recent interest or include some simulations

Questions

1. Could the authors comment on what the problem looks like for the regular stochastic case with all $f_t = f$ for some fixed $f$, and how this might make the problem easier under delays? 2. Why do the authors conjecture that the lower bound depends on $\bar{d}$, whereas the upper bound depends on $d$? What improvements would be required to get these to match?

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Yes

Reviewer pbhB2024-08-07

Thank you for the response

Thanks for the clear response. I'm sticking with my positive score.

Reviewer vCin2024-08-09

Thanks for the clear response

Thank you for the response, which I find quite helpful. I will stick with my positive score.

Reviewer knrh2024-08-09

Thank you for the response. I will keep my score positive.

Reviewer S7rX2024-08-13

Thank the authors for their response. I would like to keep the current score.

Program Chairsdecision2024-09-25

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC