uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs

Authors: Yu Chen, Jiatai Huang, Yan Dai, Longbo Huang
Primary area: learning theory
Keywords: Heavy Tailed, Multi-Armed Bandits, Parameter-Free, Best-of-Both-Worlds

Abstract:
In this paper, we present a novel algorithm, `uniINF`, for the Heavy-Tailed Multi-Armed Bandits (HTMAB) problem, demonstrating robustness and adaptability in both stochastic and adversarial environments. Unlike the stochastic MAB setting where loss distributions are stationary with time, our study extends to the adversarial setup, where losses are generated from heavy-tailed distributions that depend on both arms and time. Our novel algorithm `uniINF` enjoys the so-called Best-of-Both-Worlds (BoBW) property, performing optimally in both stochastic and adversarial environments *without* knowing the exact environment type. Moreover, our algorithm also possesses a Parameter-Free feature, *i.e.*, it operates *without* the need of knowing the heavy-tail parameters $(\sigma, \alpha)$ a-priori.
To be precise, `uniINF` ensures nearly-optimal regret in both stochastic and adversarial environments, matching the corresponding lower bounds when $(\sigma, \alpha)$ is known (up to logarithmic factors). To our knowledge, `uniINF` is the first parameter-free algorithm to achieve the BoBW property for the heavy-tailed MAB problem. Technically, we develop innovative techniques to achieve BoBW guarantees for Parameter-Free HTMABs, including a refined analysis for the dynamics of log-barrier, an auto-balancing learning rate scheduling scheme, an adaptive skipping-clipping loss tuning technique, and a stopping-time analysis for logarithmic regret.

Decision: accept (spotlight)
Reviewer scores: 8, 8, 6, 8

Reviews and discussion:
<thread>
creation date:
1729350351105

thread_type:
official_review

<thread_object>
creator: reviewer_ua58

<content>
summary:
This paper studies parameter-free best-of-both-worlds (BOBW) for HT-MABs, where 1) HT means that the loss distributions can be unbounded but have $\\alpha$-th moment bounded by $\\sigma^{\\alpha}$, for some $\\sigma>0, \\alpha\in(1,2]$; 2) BOBW means that one single algorithm can enjoy logarithmic gap-dependent regret in the stochastic environment (loss distributions are fixed over time) and worst-case optimal regret in adversarial environment (loss distributions change over time), without knowing in advance whether the environment is sto. or not; 3) parameter-free means that the algorithm doesn’t now the value of $\\sigma>0, \\alpha\in(1,2]$, but can ensure the regret guarantee as if they were known.

An algorithm called uniINF is proposed, which ensures $\\tilde{O}(\\frac{K}{(\\Delta_{\\text{min}})^{\\frac{1}{\\alpha-1}}}) $ (expected pseudo-)regret in sto. env. (which is optimal up to log terms and the gap dependency), and near-optimal regret in adv. env. (which is optimal up to log terms) when the loss distributions of the optimal arm satisfy the truncated non-negative assumption (Assumption 1). This is the first parameter-free BOBW result in HTMAB. Previous results approach that in one single env. only (either sto. or adv.).

Technically, this is achieved by several components, including 1) iterative and adaptive learning rate scheduling; 2) adaptive clipping/skipping; 3) refined analysis for log-barrier regularizer.

strengths:
The parameter-free BOBW bound in HTMAB is a quite strong guarantee, and to achieve this, several technical innovations are proposed.

weaknesses:
I’m not happy with how Assumption 1 is justified. From Line 193 to 195, it says that "we make the following **essential** assumption. As shown in (Genalti et al., 2024, Theorems 2 & 3), without Assumption 1, there does not exist HTMAB algorithms that can … without knowing either $\\alpha$ or $\\sigma$." However, this statement could be misleading based on my understanding on (Genalti et al., 2024).

The negative result shown in (Genalti et al., 2024) is that, it’s impossible for one single algorithm to match the lower bound in (Bubeck et al., 2013) for all unknown $\\sigma>0$ or $\\alpha\\in(1,2]$. However, I don’t think it has been characterized that how weak the needed assumption to be "parameter-free" in HTMAB. In fact, in the conclusion part of (Genalti et al., 2024), it even says that "investigating the role of the truncated non-positivity assumption, especially, whether weaker assumptions can be formulated."

Therefore, I would urge the authors to refine the statements related to Assumption 1, as currently it may leave the impression that Assumption 1 is a necessary condition for "parameter-free", which as of now it’s still unclear yet.

questions:
1. To my understanding, this paper claims to develop a new analysis for $DIV_t$ (also named stability term) when using log-barrier, and introduces an extra $(1-x_{t,i})^2$ factor in the bound, which is the key to get self-bounding property and BOBW. However, I don't quite understand what it means by “$S_t$ is adequately large compared to $||c_t||_{\infty}$”. I tried to find a formal lemma or theorem statement for this new bound (with exactly the same form) on $DIV_t$ term but I failed. Could the authors help explain this? Under what conditions does this new bound hold?

2. What’s the difficulty to get the refined gap dependency? From the appendix, I feel that in both DIV term and SHIFT term, we cannot achieve that. Could the authors elaborate more on that (from the analysis perspective)? Is it because the regularizer is log-barrier rather than Tsallis entropy?

Post rebuttal ===============================

I'm increasing the score from 6 to 8.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730022089913

thread_type:
official_review

<thread_object>
creator: reviewer_3k75

<content>
summary:
This work establishes the first parameter-free algorithm for heavy-tailed multi-armed bandits (MABs) with best-of-both-worlds (BOBW) properties. This algorithm does not require prior knowledge of heavy-tail parameters $(\sigma, \alpha)$ and simultaneously obtains the (nearly) optimal regret in both the stochastic and adversarial environments.

strengths:
1. **Technical innovations**: The proposed algorithm and its analysis incorporate new ingredients including a new skipping and clipping scheme of the loss estimates and a stopping time argument to bound the stability terms and the skipping errors, which seem to be technically valuable and might be of independent interest.
2. **Writing**: Generally, this work is well written.

weaknesses:
1. **More comparisons with existing literature**: Most parts of the presentation in this work are clear. However, I would like to suggest the authors provide more discussions and comparisons with the techniques in existing literature. For instance, the exclusion of the optimal arm $i^\ast$ in Eq. (5) when using the log-barrier regularizer is also achieved by [1,2]. I am not very sure whether there are additional technical nuances between the exclusion of the optimal arm in Eq. (5) of this work and those in [1,2]. For the data-dependent learning rates, several works have also leveraged them to achieve BOBW results in various online learning problems (say, [2,3,4,5,6,7]). Besides, when bounding the stability term of OMD/FTRL, a key property required is to ensure the multiplicative stability of the update of the prediction. In this work, such a property is guaranteed by Lemma 4. However, it seems not appropriate to call such a lemma “novel” as on Line 423, since it has also appeared in previous works when using the log-barrier regularizer (say, Lemma 9 in [8]; Lemma 12 in [9]).

[1] Ito. Parameter-Free Multi-Armed Bandit Algorithms with Hybrid Data-Dependent Regret Bounds. COLT, 21.

[2] Ito. Hybrid Regret Bounds for Combinatorial Semi-Bandits and Adversarial Linear Bandits. NeurIPS, 21.

[3] Ito et al. Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs. NeurIPS, 22.

[4] Tsuchiya et al. Best-of-Both-Worlds Algorithms for Partial Monitoring. ALT, 23.

[5] Ito et al. Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds. COLT, 23.

[6] Kong et al. Best-of-three-worlds analysis for linear bandits with follow-the-regularized-leader algorithm. COLT, 23.

[7] Ito et al. Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds. COLT, 24.

[8] Lee et al. A closer look at small-loss bounds for bandits with graph feedback. COLT, 20.

[9] Jin et al. Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition. NeurIPS, 20.

questions:
1. If $(\sigma, \alpha)$ is known a priori, can we eliminate Assumption 1? What are the main technical difficulties when eliminating Assumption 1 in the case of known $(\sigma, \alpha)$?
2. In the previous work [10], the Tsallis entropy regularizer is used while the log-barrier regularizer is used in this work. Is it because the magnitude of the loss estimates in this work is larger than the magnitude of the loss estimates in [10]?

[10] Huang et al. Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed
Bandits. ICML, 22.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730727960389

thread_type:
official_review

<thread_object>
creator: reviewer_jqu5

<content>
summary:
The paper addresses the heavy-tailed MAB problem, a variant of the stochastic bandit problem where rewards are sampled from distributions having potentially infinite variance. The main contribution of this work is to provide an algorithm with tight regret guarantees in both the stochastic and adversarial HTMAB problem. While the performance in the stochastic setting is worse (not in terms of T) than existing algorithms (e.g. AdarUCB), the algorithm simultaneously deals with the two settings and is tight in both the instance-dependent and independent sense.

strengths:
The paper is written, and it provides an exhaustive review of the existing literature.

The contribution is clear, and it is well highlighted which open question the paper addresses.

The paper also presents some nice technical contributions in the algorithm and in the proofs.

weaknesses:
Overall, the contribution is limited when it comes to applications since adversarial HTMABs are uncommon in the real world and the literature. Instead, in the purely stochastic setting, the algorithm does slightly worse than AdaRUCB by a factor of  $\log \frac{\sigma^\alpha}{\Delta_{min}}$ (Genalti et al.)

questions:
- How do applications justify the adversarial HTMAB? Can you please provide some examples?

- I think it would be interesting to highlight the trade-off between ADAR-UCB and UniInf more. How is the best-of-both-worlds property related to the extra factor in the stochastic setting's regret bound? Does your algorithm require extra round-robin turns (as in Adar-UCB)?

- Do you know what the optimal performance would be without the truncated non-negativity assumption? Are there any known lower bounds for the problem without this assumption?

- It would be interesting to understand if alternative (and possibly weaker) assumptions can lead to the same performances (I would like to point out that Theorems 2 and 3 from Genalti et al. don't necessarily imply that this specific assumption is required, but rather that without any assumptions such performances are unattainable).
</content>
</thread_object>

</thread>
<thread>
creation date:
1731040688232

thread_type:
official_review

<thread_object>
creator: reviewer_hjba

<content>
summary:
The paper studies Heavy-Tailed MultiArmed Bandits (HTMAB) problem. The main contribution of the paper is to design an optimal algorithm that achieves both Best of-Both-Worlds (BoBW) and Parameter-free properties for HTMAB, where BoBW means that the algorithm performs optimally in both stochastic and adversarial environments and Parameter-free means that the algorithm do not need to know the the heavy-tail parameters in advance.

strengths:
1. The paper is well written. The theoretical results and proof appear to be correct.
2. The paper achieves worst-case BoBW optimal regret for HTMAB, which improves previous results proposed in [Huang 2022].

weaknesses:
1. The paper should include the comparisons with previous scale-free MAB works, e.g. [1-5]. Specifically, the algorithm structure proposed in the paper seems very close to the one proposed in [3], which also uses the clipping/skipping technique and inf regularization. The differences should be further clarified.
2. Assumption 1 is a bit weird. I can understand why it is unavoidable, but I suggest that the authors can give the best (not worst-case optimal) upper bounds we can get without this assumption.

questions:
When $\alpha, \sigma$ known, it is trivial to use regular FTRL based algorithm to achieves (nearly) optimal worst-case regret for adversarial bandit problems with potentially heavy-tailed losses (fix the clipping bound $[-r,r]$ with $r=\sigma T^{1/\alpha}K^{-1/\alpha}$ and use Theorem 4 in [6]). When $\alpha, \sigma$ are unknown, intuitively, it suffices to use the adaptive clipping bound according to the empirical estimation of $\alpha, \sigma$ (Line 6 of ALG 1). Is the high-level idea of the algorithm in this paper the one I described?


References: 
[1] Putta, Sudeep Raja, and Shipra Agrawal. "Scale-free adversarial multi armed bandits." International Conference on Algorithmic Learning Theory. PMLR, 2022.

[2] Chen, Mingyu, and Xuezhou Zhang. "Scale-free Adversarial Reinforcement Learning." arXiv preprint arXiv:2403.00930 (2024).

[3] Chen, Mingyu, and Xuezhou Zhang. "Improved Algorithms for Adversarial Bandits with Unbounded Losses." arXiv preprint arXiv:2310.01756 (2023).

[4] Huang, Jiatai, Yan Dai, and Longbo Huang. "Banker online mirror descent: A universal approach for delayed online bandit learning." International Conference on Machine Learning. PMLR, 2023.

[5] Hadiji, Hédi, and Gilles Stoltz. "Adaptation to the range in k-armed bandits." Journal of Machine Learning Research 24.13 (2023): 1-33.

[6] Wei, Chen-Yu, and Haipeng Luo. "More adaptive algorithms for adversarial bandits." Conference On Learning Theory. PMLR, 2018.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732245769274

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We sincerely thank all reviewers for their efforts in reviewing our paper and for their valuable comments. We have revised our manuscript based on feedback and submitted the revision. Changes in the revision are highlighted in pink and detailed below:

1. We have revised the Related Works section and added a comprehensive literature review in Appendix A, which addresses the reviewers' comments. This includes enhanced comparisons of scale-free MABs and further discussion on data-dependent learning rates.

2. We thank the reviewer for pointing out potential confusion in our initial discussion of the truncated non-negative assumption (Assumption 1). We have modified the statement (see Lines 187-190) and included a detailed discussion in Appendix B to clarify this assumption further.

3. We have refined our description of the novel analysis for multiplicative stability in heavy-tailed scenarios, detailed in Lines 420-424. This revision aims to more clearly introduce our innovative approach and its implications.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a best-of-both-worlds algorithm for the heavy-tailed multi-armed bandit problem, which achieves optimal performance in both stochastic and adversarial environments. A significant strength of the proposed algorithm is its adaptability to the (unknown) heavy-tail parameter. However, its limitations include the regret upper bound in the stochastic setting depending solely on the minimum gap $\Delta_{\min}$ rather than the individual gaps $(\Delta_i)$, and the requirement of the truncated-non-negativity assumption (Assumption 1). Regarding the latter point, the authors have appropriately justified its necessity by referencing the lower bound established in prior work [Genalti et al., 2024]. The authors have adequately addressed the reviewers' concerns and questions. Given the consensus among the reviewers to accept the paper, I support its acceptance.

Additionally, there are areas for improvement as follows:
* The current text in Lines 213-253 may give the impression that this paper is the first to demonstrate the best-of-both-worlds property using log-barrier regularization in FTRL. However, previous studies, such as (Wei & Luo, 2018) and (Ito, 2021b), have also shown that the best-of-both-worlds property can be achieved using log-barrier regularization. It would be better to revise the description to avoid potential misunderstandings.
> While log-barrier regularizers were commonly used in the literature for data-adaptive bounds such as small-loss bounds (Foster et al., 2016), path-length bounds (Wei & Luo, 2018), and second-order bounds (Ito, 2021b), this paper introduces novel analysis illustrating that log-barrier regularizers also provide environment-adaptivity for both stochastic and adversarial settings.
* Regarding Assumption 2, while it is true that this assumption is common in prior work, it may also be worth mentioning that Tsallis-INF (Zimmert & Seldin, 2019) and its extensions do not require this assumption; The analysis of Tsallis-INF is provided in (Ito, 2021b), and its extension is presented in (Jin et al., 2023).