Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms

Summary

The paper introduces a new algorithm for multi-armed bandit problems, leveraging the FTRL framework and the flexible $\beta$-Tsallis entropy family of regularizers, where $\beta \in [0,1]$. This algorithm firstly uses a new learning rate schedule to offer best-of-both-worlds guarantees for a wide range of regularization parameters. Secondly, it eliminates the requirement of the uniqueness assumption of the optimal arm. Thirdly, it improves the stochastic bounds for Shannon entropy and Log-barrier regularization.

Strengths

- The paper introduces new elegant learning rates for $\beta$-Tsallis entropy, providing a best-of-both-worlds guarantee. - It generalizes the regret analysis approach by Ito (2021) by removing the uniqueness assumption of the optimal arm. - As $\beta$-Tsallis entropy is an important regularization in bandit algorithm, the results could be useful in other settings too.

Weaknesses

- The results presented in the paper for the plain multi-armed bandit, in my view, lack interest and significance compared to the algorithmic and analysis novelties. Specifically, there is no improvement in terms of regret bounds in the plain multi-armed bandit problem, as FTRL with $1/2$-Tsallis regularizer (1/2-Tsallis-INF algorithm) already achieves the optimal bound in both adversarial and stochastic regimes, and the uniqueness assumption has already been addressed by Ito (2021). The only potential value lies in applying the same ideas to other settings, such as the decoupled exploration and exploitation problem explored, as discussed in the paper. - The bounds in intermediate regimes between stochastic and adversarial, where $C \neq 0$ seem to be suboptimal as they do not interpolate well between the optimal bounds of the two regime. Read question 2 and 3 for further clarification of this issue. - There are few undefined notations used in the analysis. For instance, Equation (6) introduces the notation $D_U$ without providing a clear definition, and the same issue applies to $\phi_U(x)$ and $\phi_V(x)$ in Equation (7). If the used notation for this part were consistent with Ito (2021), $\phi_U(x)$ must accept $x$ from $\mathbb{R}^{|U|}$ but in Equation (7) it takes $x \in \mathbb{R}^{K}$. This inconsistency requires revision for clarity and accuracy.

Questions

1- As stated in the paper, the regularizer always includes a small amount of extra log-barrier. Typically, the use of log-barrier introduces an additional multiplicative factor of $\sqrt{\log T}$ in the adversarial bound. However, your adversarial bound in Theorem 3.3 does not reflect this when $\beta = 1/2$. Can you elaborate on this? 2- Regarding the results on regime so called adversarial regime with a self-bounding constraint, In lines 183 and 184, you claim that your bound smoothly interpolates between $\log T$ and $\sqrt{T \log T}$ as $C$ ranges from $0$ to $T$. However, the presence of $D$ in your bound raises doubts about this smooth interpolation since $D$ can be as large as $C$, and $C$ can be on the order of $\mathcal{O}(T)$. This essentially shows that your bound has no robustness to corruption. Could you address this inconsistency? 3- Following up on the previous question, there is an improvement in the analysis of the $1/2$-Tsallis-INF algorithm by Masoudian and Seldin (2021), which demonstrates smooth interpolation between the two optimal bounds, $\mathcal{O}(\sum_{i \neq i^*} \frac1{\Delta_i}\log T)$ and $\mathcal{O}(\sqrt{KT})$ as $C$ increases. Is there any way to achieve a similar improvement for your algorithm? If not, discuss the challenges involved in obtaining the same improvement for intermediate regimes? 4- In the contribution section, for log-barrier regularization, the authors claim to have removed the uniqueness assumption of the optimal arm utilized in Ito (2021) and improved the stochastic bound. However, it should be noted that the algorithm proposed by Ito does not align completely with the algorithm presented in this paper, as Ito employs optimistic follow the regularized leader with different learning rates. Please provide further clarification. References: - Shinji Ito, Parameter-Free Multi-Armed Bandit Algorithms with Hybrid Data-Dependent Regret Bounds, COLT 2021 - Saeed Masoudian and Yevgeny Seldin, Improved analysis of the tsallis-inf algorithm in stochastically constrained adversarial bandits and stochastic bandits with adversarial corruptions, COLT 2021

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Summary

The authors focus on best-of-both-worlds (BOBW) algorithms based on follow-the-regularized-leader (FTRL) in multi-armed bandits. The theoretical guarantees for most existing FTRL-based BOBW algorithms were based on the assumption that the best arm is unique in order to take advantage of self-bounding techniques. It is known that this assumption can be removed by the paper in [13], but its analysis was only applicable to the case of Tsallis-INF (FTRL with 1/2-Tsallis entropy), one of the most representative BOBW algorithms. Extending the analysis of [13], the authors show that a BOBW guarantee can be obtained with FTRL with more general regularizers, i.e., negative Shannon entropy, log-barrier, and FTRL with $\beta$-Tsallis entropy, without the assumption of an unique optimal arm. Furthermore, by using the new theory, the authors improve the regret upper bound in the stochastic regime in the decoupled setting.

Strengths

- The paper is very well organized and well written. - The paper greatly advances the theory of [13], excluding the unique optimal arm assumption for a wide range of typical regularizers. The assumption have been employed for constructing BOBW algorithms with FTRL, and this is an interesting and important technical contribution to the community. - In addition, the authors affirmatively answer the question of whether it is possible to achieve BOBW without knowing $\Delta_{\min}$ when $\beta$-Tsallis entropy with $\beta \neq 1/2$ (which was unresolved in Zimmert and Seldin [31]), and the question of whether it is possible to achieve BOBW with Shannon entropy using ${\Delta_{\min}}$ to $\Delta_i$-wise in the stochastic setting (unresolved in Ito et al. [14]). The both of contributions are interesting and important. The related points are listed in weakness.

Weaknesses

- There do not appear to be any major weaknesses in this paper. - One weakness would be a discussion of whether removing the assumption of unique optimal arm actually improves or worsens the performance of algorithms (The reviewer expects the algorithm becomes more conservative, and the performance becomes worse.) - Since the discussion excluding the assumption of unique optimal arm is cumbersome on its own, it would be desirable to have a discussion of which techniques in the paper contributed to resolving the problems. More specifically, which components of the algorithm play an important role in resolving the problems of [31] and [14], which are mentioned in the above Strengths part? In addition, if we accept the assumption of unique optimal arm, can we achieve improvements in [31] and [14] with a much more similar argument? Minor issues and typos: - line 87: Sepcifically -> Specifically

Questions

- Shannon entropy relies on $(\log T)^2$ rather than $\log T$, which is the case for all published algorithms using FTRL with Shannon entropy, but do the authors think it is possible to make it to $\log T$? - In addition to the above, the reviewer expect the authors to answer the questions listed in Weaknesses. - Along with them, the reviewer hopes that the author will address the questions that have been pointed out in the "Weaknesses" section above.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

NA

Summary

This paper studies the problem of designing adaptive multi-armed bandit algorithms that perform optimally in both the stochastic setting and the adversarial setting simultaneously (often known as a best-of-both-world guarantee). The authors show that the uniqueness assumption is unnecessary for FTRL with a broad family of regularizers and a new learning rate schedule. For some regularizers, their regret bounds also improve upon prior results even when uniqueness holds.

Strengths

1. The considered problem, i.e., best-of-both-world for multi-armed bandit, is important in the bandit literature. 2. The theoretical analysis looks sound, and the improvement is significant. 3. This paper is well-written and clearly organized.

Weaknesses

1. This paper does not provide any experimental result. It would improve the paper if the authors could conduct empirical evaluation for their algorithms and compare to existing BOBW algorithms, to validate their theoretical results.

Questions

Please see the weaknesses above.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Please see the weaknesses above.

Summary

This paper considers the problem of proving best of both worlds guarantees for algorithms based on the FTRL framework for the multi-armed bandits problem. While it has been demonstrated in (Zimmert and Seldin (2019,2021)) that Tsallis-INF (FTRL with the $1/2$-Tsallis entropy regularizer) achieves optimal regret in both the adversarial and stochastic settings simultaneously, their analysis for the stochastic case relied on the assumption that the optimal arm is unique. The more recent work of Ito (2021) showed that Tsallis-INF still enjoys $\\log T$ regret in the stochastic case even if the optimal arm is not unique. In this paper, the authors generalize the analysis of Ito (2021) to other regularizers. Namely, they prove, without the uniqueness assumption, best-of-both-worlds guarantees for FTRL with any $\\beta$-Tsallis regularizer (including the log barrier and the Shannon entropy regularizers) using a new arm-dependent learning rate, albeit all regularizers are mixed with the log barrier for technical reasons.

Strengths

- This work provides best of both worlds guarantees without the unique optimal arm assumption for FTRL with a broad family of regularizers. While the use of the $1/2$-Tsallis regularizer is the optimal choice (and already analyzed by Ito (2021)) for the standard bandits problem, other choices are still useful in closely related problems as illustrated in the decoupled exploration and exploitation problem. - Moreover, this work seems to be the first to provide BOBW guarantees (without requiring prior knowledge of the suboptimality gaps) for the $\\beta$-Tsallis regularizer when $\\beta$ is not $1/2$. - Overall, the paper is well written and the presentation is clear. A concise sketch of the analysis technique is provided in the last section, and the proofs seem mostly well written and easy to follow.

Weaknesses

- Unlike Ito(2021), the provided bounds include an added term of order $|U| \\log(T) / \\Delta_\\min$ where $U$ is the set of optimal arms and $\\Delta_\\min$ is the smallest sub-optimality gap. Thus, the bounds are negatively affected when there are many optimal arms. While this is still an improvement in cases where prior works only achieved a $K \\log(T) / \\Delta_\\min$ dependence (as in the Shannon entropy case), in other cases (most notably for the $1/2$-Tsallis regularizer analyzed by Ito (2021) without the uniqueness assumption) the provided results are inferior to prior works. - The fact that all regularizers are summed with a log barrier term is a little unsatisfactory. For instance, in the Shannon entropy case, we potentially lose the appealing property of having closed form expressions for the predictions of FTRL. - Though probably curable with a doubling trick, the fact that the proposed approach sometimes requires prior knowledge of the time horizon is a minor weakness.

Questions

- It seems that the log barrier was not added to the Tsallis regularizer in the decoupled exploration and exploitation problem, was it to avoid the $K \\log T$ term? Why did the analysis go through in this case but not in the standard bandits problem?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The authors did address some of the limitations of their work. Notably the fact that their analysis requires adding a log barrier term to all the considered regularizers. The authors also acknowledged, though a little less explicitly, the extraneous dependence of their bounds on the number of optimal arms.

Response confirmed

Thank you for your response. All questions have been answered. The rating will remain the same.

Thank the authors for their response

Thank the authors for their response. This paper can be improved by including experiments. I tend to keep my score.