Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update

Thanks for your helpful comments. Below, we address your main questions regarding the technical contributions, extensions to GLB, experiments, and related works. For other minor issues (e.g., typos), due to limited space, we will directly revise the paper according to your suggestions.

Q1. "cannot handle the case when $\nu_t$ is unknown, which weakens the theoretical contributions"

A1. Thanks for the comment. We'd like to remind that knowing the moment $\nu_t$ is shared by our work and previous works for heavy-tailed linear bandits, and this issue is orthogonal to our main contributions.

• Relying on moment $\nu_t$: Note that existing works including the current SOTA [Huang et al., 2024] require the moment information $\nu_t$, even if they can use an offline MLE estimator. Similarly, our work also faces this issue; however, in contrast, we can ensure one-pass efficiency. Handling unknown $\nu_t$ is indeed important and challenging for the community, which is left as future work to explore.
• Theoretical contribution: Even with known $\nu_t$, designing a one-pass algorithm remains highly non-trivial due to several challenges, including using one-pass OMD to approximate full-batch MLE, and handling Huber loss and heavy-tailed noise. We kindly request the reviewer to refer to A2 for Reviewer McYB for more details. Thanks!

Q2. "...generalize to the generalized linear bandit (GLB)..."

A2. In fact, there is prior work that applies OMD to logistic bandits (an important class of GLB) with sub-Gaussian noise, while our paper uses OMD for linear bandits with heavy-tailed noise. This suggests a potential combination. Nonetheless, an evident challenge is how to design a suitable Huber-type regression loss tailored to nonlinear link functions of GLB for the offline MLE estimator. We leave this as an exciting direction for future work. Thanks!

Q3. Experiments on several aspects ("time-varying $\nu_t$"; "the empirical advantage of HvtLB"; "parameter sensitivity"; "linear regret curves", etc)

A3. Thanks for those careful comments! To address your concerns, we have conducted additional experiments and comparisons in the anonymous URL https://default-anno-bucket.s3.us-west-1.amazonaws.com/HvtLB_revised_exp.pdf

Including, varying $\nu_t$ in Figure 2, empirical advantage in Figure 4, and linear regret issue in Figure 5. For parameter sensitivity, key parameters in the algorithm, such as Huber threshold, are not chosen by tuning but are derived from theoretical analysis. As a result, they indeed can be relatively sensitive. We will add these results in the revised version.

Q4. More details on [Sun et al. 2020], and differences between [Kang & Kim]

A4. Thanks for the helpful suggestion. In the revised version, we will include more details on [Sun et al. 2020]. As for [Kang & Kim], the similarity in titles may cause confusion. However, there are key differences in both setting and methods.

• Setting: We focuses on linear bandits with infinite arm set, where context $X_t$ chosen depends on previous $\\{X_s\\}_{s<t}$. Our goal is to design a one-pass algorithm with optimal regret. In contrast, [Kang & Kim] studies linear contextual bandits with finite arm set, where $X_t$ is i.i.d. sampled. Their method is based on offline MLE and is not online.

• Algorithm: Even with a similar Huber regression, the designs differ fundamentally. We use OMD with a carefully designed recursive normalization factor, while [Kang & Kim] uses offline MLE with a forced exploration mechanism. Please refer to A5 for more details.

Q5. "In [Kang & Kim] and [Kang et al.], ... if the upper bound $\nu$ is known, then your Huber loss can be free of the normalization factor as well?"

A5. Thanks for the question. Our Huber loss still requires this factor, even if $\nu$ is known. The normalization factor $\sigma_s$ not only ensures variance-awareness but also guarantees that the denoised data lies within the quadratic region of the Huber loss. This ensures that the Hessian has a lower bound, which is crucial for the analysis. We achieve this by designing a recursive factor, where $\sigma_t$ depends on the last round confidence bound $\beta_{t-1}$ (see line 5 in Algorithm 1).

While these two works avoid this factor, they introduce additional algorithmic mechanisms and assumptions to achieve a similar goal: (i) [Kang & Kim] introduces a forced exploration strategy and Assumption 4 to ensure that the Hessian has a lower-bounded minimum eigenvalue; (ii) [Kang et al.] adopts the local adaptive majorize-minimization method and Assumption 3.1 to establish the Local Restricted Strong Convexity condition (Definition A.3), which guarantees a lower bound on the Hessian.

We are grateful for your careful review! If our clarifications have adequately addressed your concerns, please consider updating your score. Thanks!

Thanks for your helpful suggestions. Below we will address your main concerns regarding the technical contributions and report additional experiments.

Q1. about the contributions ("Compared to [1], the contribution of this work is incremental", "elaborate on the main theoretical contributions in relation to [1]")

A1. Thank you for the comments. We believe there may have been a misunderstanding due to our insufficient emphasis on the technical contributions, particularly the challenges of applying OMD to heavy-tailed bandits. We will revise the paper to ensure this aspect is presented more clearly. Here, we'd like to take this opportunity to clarify these challenges and further emphasize our contributions.

• Challenge 1: Using one-pass OMD to approximate full-batch MLE. The offline MLE estimator leverages the entire history of data, enabling its estimation error to be well-controlled. In contrast, OMD updates the one-pass estimator using only current data, making it inherently challenging to ensure the final regret remains unaffected. While OMD is known for its effectiveness in minimizing regret, adapting this capability into a good statistical estimator is far from straightforward. In fact, as shown in Section 4.1, even under Sub-Gaussian noise (a significantly easier scenario), deploying OMD requires: (i) carefully designing the local norm to collaborate with self-normalized concentration, and (ii) properly using the negative term in the regret analysis to control the generalization gap.
• Challenge 2: Handing Huber loss and heavy-tailed noise. In the heavy-tailed setting, deploying OMD as a one-pass estimator is even more challenging. The primary difficulty arises from the curvature of the Huber loss, which is partially linear (undesired region) and partially quadratic (desired region), necessitating careful control of the threshold. Furthermore, in the estimation error analysis, the bias introduced by the one-pass OMD update manifests as an additional stability term that can grow as $\mathcal{O}(\sqrt{T})$. It is critical to carefully design both the adaptive normalization factor of the Huber loss and the learning rate in OMD, together to effectively manage the estimation error.

We will revise the paper to ensure these challenges and our technical contributions are clearly elaborated.

Q2. About experiment "explore the case where the degree of freedom satisfies $1<df\leq 2$"

A2. Thank you for the suggestions. We have conducted additional experiments to address your concerns. We summarize all the details and results in the following anonymous URL: https://default-anno-bucket.s3.us-west-1.amazonaws.com/HvtLB_revised_exp.pdf

Please refer to Figure 2 in this anonymous URL for details, where we use $df = 1.7$ for the Student’s t-distributions. Additionally, we also tested other heavy-tailed noise distributions and ensured they satisfy the condition that there exists an $\epsilon \in (0, 1)$ such that the $(1+\epsilon)$-th moment is bounded, which can be found in Figure 1. We will add these results in the revised version.

Q3. About experiment "insufficient, as they are conducted solely on synthetic datasets"

A3. Thanks for your comments. We'd like to emphasize that our paper primarily focuses on the theoretical side, which we have elaborated the technical contributions in detail (please refer to A1). The synthetic data are well-suited for setting different configurations to support our theoretical findings. On the practical side, it might be more interesting to explore online MDPs and adaptive control, given the fundamental connection between linear bandits and decision-making problems. We believe that our proposed algorithm (with suitable modifications) could be highly useful. We leave these extensions for future investigation and prefer not to spend more spaces for them in this paper to avoid diverting readers from the main focus.

Q4. "In Eq.(7), replace the notation with $z_t(\theta)$"

A4. Thank you for pointing out the confusion, we will make the presentation clearer in the revised version.

Q5. "heavy-tailed distributions does not encompass the sub-Gaussian case...I suggest discussing only the heavy-tailed case in Section 4 to avoid potential confusion"

A5. Thank you for this important suggestion. We intended to use the sub-Gaussian case as a simplified example to demonstrate how to deploy the OMD estimator in linear bandits. However, your suggestion is very reasonable, and we will revise the paper to avoid this confusion.

Thanks for your helpful suggestions. We will add more experiments and improve the paper writing to more clearly emphasize the technical contributions. If our responses have properly addressed your concerns, please consider updating your score. Thanks!

Thanks for the valuable feedback and appreciation of our work! We will revise the paper accordingly. Below, we answer your questions.

Q1. More discussions about algorithms without knowledge of $\epsilon$ and $\nu_{t}$ in advance.

A1. Thanks for the suggestion. Relaxing this assumption is indeed an important direction for future research of heavy-tailed bandits. The literature and techniques you mentioned for removing the need for known $\nu_t$ could potentially be adapted to the heavy-tailed setting. We will include a more detailed discussion of these works in the revised version.

Q2. " Is there any similar self-bounding concentrations in the world of heavy-tailed distributions? If yes, could you briefly explain what's the main issue when doing it for the learning setup?"

A2. Thanks for the question. As far as we know, Existing results based on empirical variance typically require either a bounded norm or sub-Gaussian assumption which is not applicable to heavy-tailed distributions, since in the heavy-tailed setting (e.g., when only the $(1+\epsilon)$-moment is bounded), the empirical variance itself can be unbounded.

Besides, after our submission, we noticed a recent paper published on arXiv that studies the heavy-tailed bandit setting (with $\epsilon = 1$) and claims to eliminate the need for knowing the variance using a peeling-based algorithm, under certain assumptions [1]. Although we have not studied the paper in detail yet, we believe its result is noteworthy.

[1] Ye et al., Catoni Contextual Bandits are Robust to Heavy-tailed Rewards.

We are grateful for your careful review! We will provide more discussion about the literature you suggested in the revised version.

Thanks for your suggestions on experiments and literatures. We will revise the paper accordingly. However, there is an important misunderstanding regarding our technical contributions that we need to clarify.

Q1. "contribution is not significant...only contribution is the replacement of the batch GD with OMD..."

A1: We respectfully disagree with the comments. The SOTA method (HEAVY-OFUL) [Huang et al., 2024] adopts an offline MLE estimator and achieves optimal regret for heavy-tailed linear bandits. However, ensuring the one-pass" property is crucial for online algorithms to update efficiently without storing the entire historical data. Our work builds on HEAVY-OFUL and develops an OMD-based one-pass algorithm, while also ensuring that the final regret remains unaffected. This is technically highly non-trivial. We believe it is unfair to describe as merely "replacing the batch GD with the OMD algorithm for online per-sample updates". Below, we outline the technical challenges in more detail.

• Challenge 1: Using one-pass OMD to approximate full-batch MLE. The offline MLE estimator leverages the entire history of data, enabling its estimation error to be well-controlled. In contrast, it is intuitively non-trivial to develop a one-pass estimator (which uses only the current data) while still ensuring that the estimation error remains as good as the offline MLE estimator. In fact, as shown in Section 4.1, even under Sub-Gaussian noise (a significantly easier scenario), deploying OMD requires: (i) carefully designing the local norm to collaborate with self-normalized concentration, and (ii) properly using the negative term in the regret analysis to control the generalization gap.
• Challenge 2: Handing Huber loss and heavy-tailed noise. In the heavy-tailed setting, deploying OMD as a one-pass estimator is even more challenging. The primary difficulty arises from the curvature of the Huber loss, which is partially linear (undesired region) and partially quadratic (desired region), necessitating careful control of the threshold. Furthermore, in the estimation error analysis, the bias introduced by the one-pass OMD update manifests as an additional stability term that can grow as $\mathcal{O}(\sqrt{T})$. It is critical to carefully design both the adaptive normalization factor of the Huber loss and the learning rate in OMD, together to effectively manage the estimation error.

Overall, we believe these technical contributions are not only interesting to the bandits community but also have a broad impact on the audiences of online MDPs and online adaptive control. We will improve the paper's writing to emphasize these points more clearly. Thanks!

Q2. "offline bandit learning could be explored more"

A2. Thanks for pointing out the literature on offline bandit learning, which relates to managing extreme values caused by importance weighting. We are happy to incorporate a discussion in the revision.

Q3. "Experiment setup is very limited and insufficient to prove the claims"

A3. We'd like to emphasize that our paper primarily focuses on the theoretical side, which we have elaborated the technical contributions in detail (please refer to A1). Experiments are intended to support our theoretical findings.

We are happy to conduct additional tests to better address your concerns, and new results and plots are summarized in the following anonymous URL: https://default-anno-bucket.s3.us-west-1.amazonaws.com/HvtLB_revised_exp.pdf

Concretely, we add experiments of various heavy-tailed noise (including Pareto, Lomax, Fisk); time-varying $\nu_t$; varying arm set case; more comparation about empirical advantage of our methods. We will include these additional tests in the revised version. Hope these will address your concerns.

Q4. "It is claimed that the method can be adapted to more generalized decision-making ... but no theoretical or experimental evidence is provided"

A4. Without a doubt, the linear bandit model is fundamental in online learning. Our work makes an important step for linear bandits with heavy-tailed noise. As mentioned, our technical contributions are already substantial enough to gain interest from the community.

Given the importance of linear bandits, the discussion in Section 5 is intended to highlight the potential of our Hvt-LB algorithm to broader decision-making scenarios. However, we prefer not to spend more spaces for those extensions to avoid diverting readers from the main focus, i.e., linear bandits. We believe our techniques will be of interest to audiences working on online linear MDPs and adaptive control.

We appreciate your suggestions and will add additional experiments and related works accordingly. We will also emphasize technical contributions more clearly. If our clarifications have adequately addressed your concerns, please consider updating your score. Thanks!

Thanks for your careful review! In the following, we will address your main concerns and report additional experiments.

Q1. "How will the empirical performance of the algorithm vary with changing $\nu_t$? I suggest the authors provide results for varying $\nu_t$ to support the claim that the algorithm is adaptive to $\nu_t$."

A1. Thanks for the suggestion. We have conducted additional experiments of time-varying $\nu_t$ to further support the variance-aware property of our method. We summarize all the details and results in the following anonymous URL: https://default-anno-bucket.s3.us-west-1.amazonaws.com/HvtLB_revised_exp.pdf

Please refer to Figure 2 of this anonymous URL for details. We will add these results in the revised version.

Q2. " The novelty seems limited, as the challenges of combining online mirror descent with heavy-tailed bandits are not discussed clearly. Could the authors provide specific challenges in deriving the results of applying online mirror descent to heavy-tailed bandits?"

A2. Thank you for the comments. We believe there may have been a misunderstanding due to our insufficient emphasis on the challenges of applying OMD to heavy-tailed bandits. We will revise the paper to ensure this aspect is presented more clearly. Here, we'd like to take this opportunity to clarify these challenges.

• Challenge 1: Using one-pass OMD to approximate full-batch MLE. The offline MLE estimator leverages the entire history of data, enabling its estimation error to be well-controlled. In contrast, OMD updates the one-pass estimator using only current data, making it inherently challenging to ensure the final regret remains unaffected. While OMD is known for its effectiveness in minimizing regret, adapting this capability into a good statistical estimator is far from straightforward. In fact, as shown in Section 4.1, even under Sub-Gaussian noise (a significantly easier scenario), deploying OMD requires: (i) carefully designing the local norm to collaborate with self-normalized concentration, and (ii) properly using the negative term in the regret analysis to control the generalization gap.
• Challenge 2: Handing Huber loss and heavy-tailed noise. In the heavy-tailed setting, deploying OMD as a one-pass estimator is even more challenging. The primary difficulty arises from the curvature of the Huber loss, which is partially linear (undesired region) and partially quadratic (desired region), necessitating careful control of the threshold. Furthermore, in the estimation error analysis, the bias introduced by the one-pass OMD update manifests as an additional stability term that can grow as $\mathcal{O}(\sqrt{T})$. It is critical to carefully design both the adaptive normalization factor of the Huber loss and the learning rate in OMD, together to effectively manage the estimation error.

We will revise the paper to ensure these challenges are clearly elaborated.

Q3. "In Lemma $1$, $\sigma_{\min }$ is used without being defined beforehand."

A3. Thank you for the detailed review! We will correct this in the revised version, specifically, $\sigma_{\min }$ is a small positive constant to avoid singularity, and we provide the setting of $\sigma_{\min}$ in Theorem 1.

Q4. "Is there a way to remove the requirement for knowledge of the horizon time $T$?"

A4. Thanks for the question. The requirement of a known time horizon $T$ can be removed using the doubling trick. Specifically, we let the algorithm restart at time steps $2^1, 2^2, 2^3, 2^4, \ldots, 2^M$. If the time horizon is $T$, then the total number of intervals is $M \approx \log T$. When the time horizon is known, the regret bound is $\widetilde{\mathcal{O}}(T^{\frac{1}{1+\epsilon}})$. Since the length of each interval $2^m$ is known in advance, we can apply the same bound within each interval. Then the overall regret can be calculated by:

$\widetilde{\mathcal{O}}\left(\sum_{m=1}^M\left(2^m\right)^{\frac{1}{1+\epsilon}}\right)=\widetilde{\mathcal{O}}\left(\sum_{m=1}^M 2^{\frac{m}{1+\epsilon}}\right)=\widetilde{\mathcal{O}}\left(2^{\frac{1}{1+\epsilon}} \frac{2^{\frac{M}{1+\epsilon}}-1}{2^{\frac{1}{1+\epsilon}}-1}\right)=\widetilde{\mathcal{O}}\left(\frac{2^{\frac{1}{1+\epsilon}}}{2^{\frac{1}{1+\epsilon}}-1}\left(T^{\frac{1}{1+\epsilon}}-1\right)\right) = \widetilde{\mathcal{O}}(T^{\frac{1}{1+\epsilon}}).$

In this way, we are able to remove the requirement of known $T$ in advance, while still achieving a regret bound of $\widetilde{\mathcal{O}}(T^{\frac{1}{1+\epsilon}})$, up to a constant factor overhead.

Thanks again for your insightful comments. We will add more experiments and improve the presentation in the revised version.