Bandit and Delayed Feedback in Online Structured Prediction

Thank you very much for your thoughtful and constructive review. Below are our responses to your comments.

On the surrogate regret

We thank the reviewer for raising this important point. Firstly, we would like to clarify a possible misunderstanding in the following statement by the reviewer:

The surrogate regret proposed in this paper compares the target loss of the online algorithm to the surrogate loss of a fixed offline comparator, which raises concerns about interpretability and fairness. This mixed comparison (target vs. surrogate loss) may lead to misleading conclusions. A small surrogate regret does not necessarily imply strong performance on the original task, as the regret is not measured in a consistent way. ...

The surrogate regret is not a new concept proposed in this paper. It was explicitly introduced by Van der Hoeven (2020, [38]) and has been a central concept in the subsequent work (Van der Hoeven et al., 2021, [39]; Sakaue et al., 2024, [35]). Below, we elaborate on why this measure is appropriate and justified in our setting.

As you rightly noted, the relationship between the target loss and the surrogate loss deserves careful attention. This issue has been thoroughly discussed in prior work, particularly in Sakaue et al. (2024, [35]), and our choice of target and surrogate losses in this paper follows the standard framework established in the literature. Accordingly, the surrogate loss used in our setting does not give the algorithm any unfair advantage, nor does it result in pathological behavior where the constant $a$ becomes arbitrarily small and causes the regret bound to deteriorate excessively. For example, in the case of classification with the logistic loss, which is a standard surrogate loss, the constant is $a = 1 - \ln 2 \approx 0.3$, which is not excessively small and ensures that the resulting bound, scaling as $1/a$, remains meaningful.

More broadly, if one were to analyze the regret solely with respect to the target loss, one would need to consider hypothesis classes consisting of models that predict discrete labels $\boldsymbol{y}$ from input features $\boldsymbol{x}$. However, such models are often computationally intractable to train. In practice, it is standard to adopt the surrogate loss framework, as advocated in the seminal work by Bartlett et al. (2006, [3]), as discussed in Section 1. In this approach, we can efficiently learn estimators that map a feature $\boldsymbol{x}$ to a score vector $\boldsymbol{\theta}$ in the continuous Euclidean space $\mathbb{R}^d$, by applying gradient-based methods to a surrogate loss.

From this perspective, it is both natural and important to study how well we can bound the target loss in comparison to the best possible performance achievable under the surrogate loss framework. This leads to the study of the surrogate regret, which indeed generalizes the finite mistake bound of the classical Perceptron on linearly separable data (Rosenblatt 1958, [34]; cf. Van der Hoeven, 2020, [38], Section 1) and has been the focus of a growing body of work—Van der Hoeven (2020, [38]), Van der Hoeven et al. (2021, [39]), and Sakaue et al. (2024, [35]). This conceptual foundation is central to our work.

In summary, we understand the reasoning behind the reviewer’s concern, but we emphasize that the surrogate regret framework is theoretically sound and widely accepted and that the choice of target and surrogate losses in our paper is fully aligned with the established literature. Therefore, adopting the surrogate regret framework does not weaken the significance of our contributions. We will clarify this point in the revised version of the paper with further discussion.

Thank you for taking the time to provide this valuable review. Below are our responses to the comments.

Intuitive explanations

However, in some Sections, the manuscript becomes quite dense with technical details, which may hinder its understanding especially for readers not deeply familiar with the specific techniques employed. In some parts of the paper, a more intuitive or high-level exposition accompanying the formal developments would help in understanding the main conceptual contributions. One example is Section 3.4, where the pseudo-inverse matrix estimator is introduced.The results up to Section 3.3 rely on a combination of standard tools for handling bandit feedback and prior techniques (e.g., from [35]). While the derivations are technically non-trivial, this part of the paper seems to lack substantial conceptual contributions/new ideas. A similar observation may apply to the delayed feedback setting: the presentation does not clearly articulate what new ideas or techniques are necessary to obtain the results, making it challenging to assess the novelty without delving deeply into the proofs. We apologize for the lack of clarity in the original explanation. Below we provide further clarification on the examples cited in Section 3.4 and the details related to delayed feedback in Sections 4 and 5.

Regarding Section 3.4

• We propose a pseudo-inverse matrix estimator inspired by studies on adversarial linear bandits and adversarial combinatorial full-bandits. By utilizing the loss values, the estimator achieves a $K$-independent bound that is particularly effective for complex structured prediction problems, such as multilabel classification.
• Technically, unlike inverse-weighted gradient estimators, our approach constructs an unbiased estimator without relying on the inverse weighting by probability $p\_t$. This is crucial for removing the dependence on $K$, which arises from the lower bound on $p\_t$. The upper bound for this approach is proven using properties of positive semi-definite matrices and pseudo-inverse matrices (see Lemmas D.5–D.7 for details).
• Additionally, we identify the conditions under which this estimator can be used and characterize the class of loss functions that satisfy these conditions. This is also technically novel.

Regarding Sections 4 and 5

• We discovered that existing algorithms for online convex optimization with delay, which achieve AdaGrad-type regret bounds, can be effectively utilized.
• In Section 4, the core idea is already presented in the proof sketch of Theorem 4.3. The key technical point is leveraging the negative term via the AdaGrad-type regret bound and the inequality $\\|\boldsymbol{G}\_t\\|\_\mathrm{F}^2 \le bS\_t(\boldsymbol{W}\_t)$. (These techniques remain important even when applying the $D$-copy approach mentioned in the rebuttal to Reviewer jZKi.)
• The algorithm and proof ideas in Section 5 are essentially a combination of the discussions already presented in Sections 3 and 4.

We will emphasize these points more clearly in the revision and do our best to provide more intuitive explanations.

Parameter $\omega$ of Assumption 3.6 (iii)

Finally, Assumption 3.6 (iii) is not explicitly discussed, despite the apparent importance of the parameter $\omega$ in the subsequent guarantees.

Thank you for the comment. As pointed out, the value of $\omega$ is indeed important. In the revised version, we will update Corollary 3.8 to include not only the final upper bound but also the explicit values of $\omega$ for each setting—namely, multiclass classification, multilabel classification, and ranking. Specifically, $\omega$ is $d^2$ for multiclass classification, $d^5 / 4m(d - m)$ for multilabel classification with $m$ correct labels, and $m^5$ for the ranking (see Appendix D.4 for details).

We sincerely appreciate the time and effort you devoted to providing a constructive review. Below, we present our responses to your comments.

Q1. Comparison between the $D$ copy approach and ours

The results for the delayed full information are a bit weak I suspect. If we have constant delay, we could just run $D$ copies of the non-delayed algorithm, where each copy makes a prediction every $D$ time steps. Since the non-delayed algorithm has surrogate regret $O(1)$, this would lead to a surrogate regret bound of order $D$.

I am wondering of my construction for the constant delay actually works. If so, would this be optimal?

Thank you very much for your insightful comment. We have examined how the approach of preparing $D$ copies of the non-delayed algorithm (as investigated by Weinberger and Ordentlich, 2002 [41]; Joulani et al., 2013 [23]) would perform in our setting. In what follows, we call this approach the "$D$-copy approach" for simplicity.

As you pointed out, in the full-information feedback setting, it is indeed possible to improve the regret bound to $O(D)$. In contrast, in the bandit feedback setting, we found that our approach has advantages over the $D$-copy approach combined with the inverse-weighted gradient estimator and the pseudo-inverse matrix estimator. Specifically,

• In the full-information setting, the $D$-copy approach combined with the approach of Sakaue et al. (2024, [35]) achieves a regret bound of $O(D)$, which is better than our $O(D^2)$ bound.
• In the bandit setting with the inverse-weighted gradient estimator, the $D$-copy approach applied with our algorithm for Theorem 3.5 yields a bound of $O(\sqrt{K D T})$, which is worse than our $O(\sqrt{(K + D) T})$ bound. Interestingly, such degradation in the regret bound when using $D$ copies naively is also known in the literature of multi-armed bandits: For the classical multi-armed bandit problem, using $D$ copies yields a regret bound of $O(\sqrt{ NDT})$, while the minimax regret for the problem is $\Theta(\sqrt{(N + D) T})$ (Corollary 11 in Cesa-Bianchi et al. 2016 [9]). Thus, our bound of $O(\sqrt{(K + D) T})$ can be seen as an improvement over the naive $O(\sqrt{K D T})$ bound.
• In the bandit setting with the pseudo-inverse matrix estimator, the $D$-copy approach with our algorithm for Theorem 3.7 achieves a bound of $O(D^{1/3} T^{2/3})$, which is the same as our bound in Theorem 5.2. However, as the ODAFTRL paper points out, it is undesirable because each algorithm only leverages $\frac{T}{D+1}$ losses (see page 4 in Flaspohler et al. 2021, [17]), limiting its empirical performance.

In summary, the $D$-copy approach has an advantage in terms of worst-case regret in the full-information setting. However, in the bandit setting, our approach demonstrates superiority against the $D$-copy approach combined with the algorithms for the non-delayed bandit setting, regardless of which estimator is used.

We would like to emphasize that our main contribution lies in the bandit feedback setting for online structured prediction. The full-information delayed feedback setting is handled simply by combining the decoding method of Sakaue et al. (2024, [35]) with ODAFTRL and is not central to our work; it occupies only half a page in our 9-page manuscript.

That said, we agree that it is beneficial to note that the improvement is achievable by the $D$-copy approach in the full-information setting. In the revised version, we will carefully discuss how the $D$-copy approach improves the bound in the full-information setting, and how our method demonstrates advantages over the $D$-copy approach in the bandit setting, in terms of both regret bounds and average-case performance. We again appreciate the reviewer's insightful comment.

Regarding variable delay (mentioned in Weaknesses)

I think that a similar surrogate regret bound should be obtainable for delay that is not constant.

We have provided the algorithm and the upper bounds for the variable delay setting, which is deferred to Appendix G and mentioned in Line 379 due to space constraints.

Here, we briefly describe the results. Let $\tau_t$ denote the delay time of the feedback at time $t$ and $\tau_\ast$ the maximum delay. We obtain an upper bound of $O(\sqrt{\tau_{1:T}}+\tau_\ast)$ in the full-information setting. In the bandit setting, by employing the inverse-weighted gradient estimator and the pseudo-inverse matrix estimator, we obtain upper bounds of $O(\sqrt{KT}+\sqrt{\tau_{1:T}}+\tau_\ast)$ and $O(T^{1/6}\sqrt{\tau_{1:T}}+\omega^{1/3}T^{2/3}+\tau_\ast)$, respectively. Please see Appendix G for the detailed statements and proofs.

Q2. Tightness of results for the delayed bandit setting

It is not clear if the results for the delayed bandit setting are tight. Nevertheless, both results are new and show that the randomized decoding technique from earlier work can be extended to obtain interesting results beyond the setting the technique was originally developed for.

I am wondering if the bounds for the delayed bandit setting are tight

Thank you for the important comment. Proving lower bounds and discussing the tightness of the upper bounds we provided are certainly an important direction. However, in the analysis of surrogate regret bounds, particularly under the bandit feedback setting, proving lower bounds is challenging. Below, we provide information regarding the difficulty of establishing lower bounds in the bandit feedback setting.

Van der Hoeven et al. (2021, [39]) proved an $\Omega(\sqrt{T})$ lower bound in the "graph" feedback setup, which is a variant of the bandit feedback model. However, no surrogate regret lower bound is known for the "bandit" feedback setting, as their construction does not apply to this case (although this may suggest that the lower bound in the bandit setup is possibly $\Omega(\sqrt{T})$). Hence, there seems to be an additional difficulty in constructing surrogate regret lower bounds in the bandit setting. Extending such constructions to the delayed feedback setting would be even more challenging and is beyond the scope of this study. We will include these discussions in the revised version.

Thank you very much for taking the time to provide helpful reviews. Below are our responses to your comments.

Weakness & Q3. Computational tractability

My main concerns are with the computation complexity of the algorithms. Although the framework generalize upon existing works (from multi class prediction to ranking), the algorithm has some assumptions on known invertibility and decoding oracle). I am not sure of the computation feasibility and complexity of the algorithms.

3. As the algorithms depend on assumptions about known invertibility and boundedness of feature spaces, can you address the computational tractability of required oracles (e.g., decoding under complex structure)?

We thank the reviewer for clearly stating the concern regarding the computational aspect. Below, we explain the invertibility of matrices and the computational complexity separately.

Invertibility.

• The matrix $\boldsymbol{V}$, which is assumed to be invertible in Assumption 3.6, is indeed invertible in the multiclass, multilabel classification, and ranking cases. The specific forms of $\boldsymbol{V}$ are given in Section 2.4.
• Regarding the matrix $\boldsymbol{Q}$, it is invertible in the multiclass and multilabel classification cases; we confirm that its minimum eigenvalue is positive in Appendix D.4. Even if the $\boldsymbol{Q}$ is not invertible (i.e., ii-a in Assumption 3.6 fails to hold), the same result can be established under the alternative condition (ii-b), which is indeed true in the case of ranking.

Complexity.

Let us clarify the complexity of decoding and the computation of the pseudo-inverse of $\boldsymbol{P}_t$.

• When decoding with RDUE (Algorithm 2), the dominant cost lies in computing $\hat{\boldsymbol{y}}\_\Omega(\boldsymbol{\theta})$, which is a solution to convex optimization over $\mathrm{conv}(\mathcal{Y})$ as described in Proposition 2.3. This is thoroughly addressed in Sakaue et al. (2024, [35] Section 3.1). In short, $\hat{\boldsymbol{y}}\_\Omega(\boldsymbol{\theta})$ can be computed via a Frank–Wolfe-type algorithm (e.g., Garber and Wolf, 2021, "Frank–Wolfe with a nearest extreme point oracle"), which typically requires $\tilde{O}(d^2)$ linear optimization steps over $\mathrm{conv}(\mathcal{Y})$; let $\tau\_{\mathrm{LO}}$ denote the time for each step.

• We now explain the computation of the pseudo-inverse of $\boldsymbol{P}\_t = \mathbb{E}\_{\boldsymbol{y} \sim p\_t}[\boldsymbol{y} \boldsymbol{y}^\top]$. This is written as the sum of $\mathbb{E}\_{\boldsymbol{y} \sim p}[\boldsymbol{y} \boldsymbol{y}^\top]$ and $\mathbb{E}\_{\boldsymbol{y} \sim \mu}[\boldsymbol{y} \boldsymbol{y}^\top]$, where $p$ is a distribution over $\mathcal{Y}$ induced by RDUE and $\mu$ is the uniform distribution over $\mathcal{Y}$. The latter can be calculated analytically in the multiclass and multilabel classification and ranking cases. For the former, when $\hat{\boldsymbol{y}}\_\Omega(\boldsymbol{\theta})$ is obtained via the Frank–Wolfe algorithm, $p$ is obtained from the convex combination coefficients, whose support size is at most $O(d)$ as implied by Carathéodory’s theorem (cf. Wirth et al. 2024, "The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Control"). Therefore, we can compute $\boldsymbol{P}\_t$ in $O(d^3)$ time, and the pseudo-inversion takes the same order of complexity.

To conclude, the total per-round complexity is typically $O(d^2 \tau_{\mathrm{LO}} + d^3)$, which is feasible and arguably efficient given that $\mathcal{Y}$ may consist of up to $2^d$ labels. We will elaborate further on this point in the revised manuscript.

Q1. Regarding $T\ge B^2K$

1. In Section 3.4, the algorithm use RUDE decoding with $T>>B^2K$ and claimed that this is only for simplicity. Could you elaborate on why this makes things easier and how this can be lifted?

Since the comment concerns the assumption $T \ge B^2K$, we suppose it pertains to Section 3.3 rather than Section 3.4, and we respond accordingly.

The assumption $T \ge B^2K$ is made solely to simplify the presentation. It allows us to consider only the typical scenario where $T$ is sufficiently large to ensure $q \le 1$, which leads to a simpler expression of the regret bound in the main text. This assumption can be entirely removed by setting $q = \min\\{B\sqrt{K/T}, 1/2\\}$ and adding an additive term of $O(K)$ to the regret upper bound in Theorem 3.5. Please let us know if this is not the kind of response the reviewer was expecting.

Q2. Bandit feedback vs. indicator feedback

2. In Section 3.4, the paper defines bandit feedback as observing the scalar loss $L\_t(y\_t)$, but then states the algorithm only uses the indicator $\mathbb{I}[\hat{y_t}=y_t]$, then does the algorithm still holds for general bandit feedback?

Yes, in Section 3.3, we only use the information of $\mathbb{1}[\hat{\boldsymbol{y}\_t}=\boldsymbol{y}\_t]$, and thus the same result can be obtained under a more general bandit feedback setting where only the 0-1 loss value is observed (see Remark 3.4). Specifically, since $L\_t(\hat{\boldsymbol{y}\_t}) = L(\hat{\boldsymbol{y}\_t}; \boldsymbol{y}\_t)$ is non-negative and takes zero if and only if $\hat{\boldsymbol{y}\_t} = \boldsymbol{y}\_t$ as in Assumption 2.1, $\mathbb{I}[L\_t(\hat{\boldsymbol{y}\_t}) > 0]$ is identical to the 0-1 feedback. On the other hand, in Section 3.4, observing the loss $L\_t(\hat{\boldsymbol{y}\_t})$ is crucial. This is because we use the actual loss values to compute a pseudo-inverse matrix estimator, which allows us to improve the dependency on $K$.

Q4. Regarding non-uniform delay

4. In practice, I am assuming $D$ can be non uniform across steps and unknown to the algorithm beforehand. But here the algorithm needs to know in advance. Can this assumption be removed?

Regarding the setting where delays can be non-uniform (which we refer to as variable delays), we discuss it in Appendix G, as mentioned in line 379. Due to space limitations, we could not include this discussion in the main text.

Moreover, the assumption that the delay $D$ is known in advance is not necessary. Since the ODAFTRL algorithm determines the decision point using all observed feedback, the value of $D$ becomes known from the time the first feedback is observed. We acknowledge that the current manuscript may have given the impression that $D$ must be known beforehand, and we will revise this part to clarify the explanation accordingly.

Thank you very much for taking the time to provide such a thoughtful and detailed review. Below, we present our responses to your comments.

Q1. Multiclass classification model

1. Could you explain the multiclass classification model in lines 168-173? Why is $L(y;e_i)=\indic[y\neq y]$? The indicator function evaluates to $0$ always in the presented form.

We apologize for the confusion caused by the typographical error. The correct definition is $L(\boldsymbol{y};\mathbf{e}\_i)=\mathbb{1}[\boldsymbol{y}\neq \mathbf{e}\_i]$. We will correct this in the revised version.

Q2. Practical significance

2. The paper motivates the structured learning problem through several examples, including multiclass classification, multilabel prediction, and ranking. However, the practical significance of the proposed model remains unclear.

In practice, structured prediction arises across various domains, from natural language processing to bioinformatics (BakIr et al., 2007, [2]), as discussed in Section 1. In particular, our online setting with efficient linear estimators is well suited for applications such as ad click prediction (McMahan et al., 2013, “Ad Click Prediction: A View from the Trenches”) and ranking in recommendation systems (Rendle et al., 2009, “BPR: Bayesian Personalized Ranking from Implicit Feedback”), where both real-time performance and efficiency are critical.

It is not evident how this approach offers tangible benefits over standard methods in real-world scenarios. For instance, in the case of multiclass prediction, given the setup described, wouldn’t the algorithm risk learning a model that simply overfits to the training data?

Thank you for the question. We are not entirely sure what is meant by "standard method" in this context, so we would appreciate clarification if possible. If the question refers to batch learning, then the problem setting itself is fundamentally different, making direct comparison difficult.

Our work considers the online learning setting, in which issues such as overfitting—commonly discussed in statistical learning—do not arise. Unlike batch learning, where a predictor is trained using a given training dataset and evaluated on a test dataset, online learning assumes that data arrives sequentially and the model (in our case, matrix $\boldsymbol{W}\_t$) is updated in an online manner. Therefore, there is no distinction between training and test data in online learning, and thus the overfitting risk present in batch learning does not exist in our setting.

Q3. Relation to existing literature

3. The paper mentions the bandit setting (with incomplete information) as a key extension to the past works. However, [38] and others have studied the bandit setting. Could you explain and position the contribution w.r.t the existing literature?

Our work addresses a more general problem class than those in prior studies. Specifically, while Van der Hoeven (2020, [38]) and Van der Hoeven et al. (2021, [39]) focused on online multiclass classification under bandit feedback, our work addresses online structured prediction, which includes multiclass classification as a special case. At the same time, our work can be seen as an extension of the existing study on online structured prediction with full-information feedback (Sakaue et al., 2024, [35]) to bandit and delayed feedback.

Q4. Improvement of the dependence on $K$

4. Is the key contribution the improvement on the sublinear dependence on $K$?

Yes, one of our main contributions is establishing the $O(\sqrt{KT})$ regret bound, improving upon the $O(K\sqrt{T})$ bound of Van der Hoeven (2020, [38]) and Van der Hoeven et al. (2021, [39]). We would like to remark that another, more important contribution is the regret upper bound that is explicitly independent of $K$, achieved through the use of the pseudo-inverse matrix estimator.

If so, given that the models considered in existing works are more general,

We would like to clarify that the statement “the models considered in existing works are more general” is not accurate. As explained in our response to the third question, we address structured prediction, which is a more general framework than multiclass classification considered in Van der Hoeven (2020, [38]) and Van der Hoeven et al. (2021, [39]). One caveat is that these previous studies cover a broader class of surrogate losses, including the (smooth) hinge loss. That said, our work—based on the Fenchel–Young loss framework, following Sakaue et al. (2024, [35])—subsumes the standard logistic loss as a special case. To be precise, while we focus on the logistic loss with base $2$, their framework also accommodates the base-$K$ logistic loss. We believe that we have adequately addressed this subtle difference in the main text. Indeed, Reviewer 4Bpe noted, “I particularly appreciated the authors for their clear (and honest) comparison with related work (e.g., discussion on pages 261–269).”

could you explain how essentially the algorithm and proof techniques achieve the $\sqrt{K}$ improvement beyond the simplified problem setting compared to other works?

The $\sqrt{K}$ improvement leverages the following techniques:

• Extending the randomized decoding algorithm, originally designed for full-information feedback, to a form applicable to the bandit feedback setting (RDUE, Algorithm 2).
• Using RDUE, we show that in the bandit feedback setting, the constant $a$ in Assumption 3.2, which appears as a $1/a$ factor in the regret bound, can be made smaller compared to Van der Hoeven (2020, [38]), based on Lemma 3.1.
• Exploiting the negative term by using the inequality $||\boldsymbol{G}\_t||\_\mathrm{F}^2 \le bS\_t(\boldsymbol{W}\_t)$ in the proof of Theorem 3.5.
• We carefully set the mixing probability $q$ of uniform exploration (Line 276).

Q5. Regret bound in Theorem 4.3

5. The regret bound in Theorem 4.3 is different from the bound mentioned in the abstract and introduction of the papers? Can you explain?

There might be a misunderstanding regarding the upper bound stated in the abstract. The upper bound in Theorem 4.3 pertains to the delayed full-information feedback setting, whereas the bound in the abstract refers to the non-delayed bandit feedback setting. There is no inconsistency between the main text and the abstract. In the revised version, we will modify Line 8 of the abstract to read "for non-delayed bandit feedback" instead of "for bandit feedback", to avoid confusion.

Q6. Assumption 3.2

6. Could you explain Assumption 3.2?

This assumption ensures that a decrease in the surrogate loss leads to a proportional decrease in the target loss. It plays a crucial role in establishing an upper bound on the target loss via the surrogate loss. Note that we refer to it as an “Assumption” merely for ease of reference; it is in fact directly guaranteed by Lemma 3.1.

Importantly, one must ensure that the parameter $a$ lies in the interval $(0, 1)$. As discussed in Lines 240–242, this condition is satisfied in our structured prediction setting due to Sakaue et al. (2024, [35]) with $a = 1 - \frac{4\gamma}{\lambda \nu}$. In the case of multiclass classification, Van der Hoeven et al. (2021, [39], Lemma 1) also provide a decoding method that guarantees this condition, with $a = 1/K$.

What is the meaning of $L\_t(\hat{y}\_t)$?

$L\_t(\boldsymbol{y})=L(\boldsymbol{y};\boldsymbol{y}\_t)$ is a simplified notation for the loss function at time $t$. We defined it in Line 164 and in the notation table (Appendix A). In the revised version, we will add a reminder when it reappears in a distant section, in order to improve readability.

Q7. Experiments

The abstract mentions that algorithms are numerically tested; however, there are no numerical results provided in the paper.

7. Can you provide experimental results to support the results and improvement over existing approaches?

As referenced in Lines 70–72 and Lines 84–86, we have included experiments in Appendix H. Due to space constraints, we were unable to include the experimental results in the main text. Given the extra space in the camera-ready version, we plan to include (part of) the experiments.

Q8. Independence of $T$ in Theorem 4.3

8. The paper claims the bound I Theorem 4.3 is independent of $T$? However, there is a dependence on $T$.

Note that the upper bound involves $\min$. Since $\min\\{D^2, D^{2/3}T^{1/3}\\}\le D^2$ holds, the upper bound in Theorem 4.3 is indeed independent of $T$.

Q9. Technical novelty in delayed feedback

9. Can you explain the technical challenges and the novelty in the proof approach for the delayed feedback extension?

We believe that exploring delayed feedback in online structured prediction is a novel direction in its own right, even though it is not the primary focus of our paper (this topic occupies only one page in our 9-page manuscript). To our knowledge, delayed feedback in this setting has received very limited attention in the literature, despite its practical importance (see also the discussion in Lines 44–48), which makes it challenging due to the scarcity of directly applicable tools. To address this challenge, we have uncovered the benefit of bridging two previously separate lines of research: online convex optimization with delayed feedback and online structured prediction. Specifically, by leveraging AdaGrad-type regret bounds under delay, we show that a finite regret bound can be achieved in the full-information setting, and that in the bandit feedback setting, our approach yields tighter bounds than the $D$-copy strategy (see also our rebuttal to Reviewer jZKi).