Library

Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds

Adaptivity to the difficulties of a problem is a key property in sequential decision-making problems to broaden the applicability of algorithms. Follow-the-regularized-leader (FTRL) has recently emerged as one of the most promising approaches for obtaining various types of adaptivity in bandit problems. Aiming to further generalize this adaptivity, we develop a generic adaptive learning rate, called stability-penalty-adaptive (SPA) learning rate for FTRL. This learning rate yields a regret bound jointly depending on stability and penalty of the algorithm, into which the regret of FTRL is typically decomposed. With this result, we establish several algorithms with three types of adaptivity: sparsity, game-dependency, and best-of-both-worlds (BOBW). Despite the fact that sparsity appears frequently in real problems, existing sparse multi-armed bandit algorithms with $k$-arms assume that the sparsity level $s \leq k$ is known in advance, which is often not the case in real-world scenarios. To address this issue, we first establish $s$-agnostic algorithms with regret bounds of $\tilde{O}(\sqrt{sT})$ in the adversarial regime for $T$ rounds, which matches the existing lower bound up to a logarithmic factor. Meanwhile, BOBW algorithms aim to achieve a near-optimal regret in both the stochastic and adversarial regimes. Leveraging the SPA learning rate and the technique for $s$-agnostic algorithms combined with a new analysis to bound the variation in FTRL output in response to changes in a regularizer, we establish the first BOBW algorithm with a sparsity-dependent bound. Additionally, we explore partial monitoring and demonstrate that the proposed SPA learning rate framework allows us to achieve a game-dependent bound and the BOBW simultaneously.

cs.LGstat.MLComputer ScienceMathematics
View graphSource

Paper

References (55)

01Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal ArmsTiancheng Jin, Junyan Liu, Haipeng Luo2023 · Neural Information Processing Systems · 22 citations In Library
02A Blackbox Approach to Best of Both Worlds in Bandits and BeyondChristoph Dann, Chen-Yu Wei, Julian Zimmert2023 · Annual Conference Computational Learning Theory · 31 citations In Library
03Best-of-Both-Worlds Algorithms for Partial MonitoringTaira Tsuchiya, Shinji Ito, J. Honda2022 · International Conference on Algorithmic Learning Theory · 18 citations In Library
04Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret BoundsShinji Ito, Taira Tsuchiya, J. Honda2022 · Annual Conference Computational Learning Theory · 20 citations In Library
05Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback GraphsShinji Ito, Taira Tsuchiya, J. Honda2022 · Neural Information Processing Systems · 29 citations In Library
06The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitionTiancheng Jin, Longbo Huang, Haipeng Luo2021 · Neural Information Processing Systems · 50 citations In Library
07Bandit AlgorithmsTor Lattimore, Csaba Szepesvari2020 · 3.4k citations
08Analysis and Design of Thompson Sampling for Stochastic Partial MonitoringTaira Tsuchiya, J. Honda, Masashi Sugiyama2020 · Neural Information Processing Systems · 9 citations In Library
09A Closer Look at Small-loss Bounds for Bandits with Graph FeedbackChung-Wei Lee, Haipeng Luo, Mengxiao Zhang2020 · Annual Conference Computational Learning Theory · 26 citations In Library
10A Modern Introduction to Online LearningFrancesco Orabona2019 · arXiv.org · 563 citations In Library
11Exploration by Optimisation in Partial MonitoringTor Lattimore, Csaba Szepesvari2019 · Annual Conference Computational Learning Theory · 40 citations In Library
12Equipping Experts/Bandits with Long-term MemoryKai Zheng, Haipeng Luo, Ilias Diakonikolas et al.2019 · Neural Information Processing Systems · 15 citations In Library

Scroll for more · 38 remaining

Similar papers

A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $Θ(T^{2/3})$ and its Application to Best-of-Both-WorldsTaira Tsuchiya, Shinji Ito2024 · arXiv (Cornell University) · 5 citations In Library
Optimism in the Face of Ambiguity Principle for Multi-Armed BanditsMengmeng Li, Daniel Kuhn, Bahar Taşkesen2024 · arXiv.org · 4 citations In Library
Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal ArmsTiancheng Jin, Junyan Liu, Haipeng Luo2023 · Neural Information Processing Systems · 22 citations In Library
Heavy-tailed Linear Bandits: Adversarial Robustness, Best-of-both-worlds, and BeyondCanzhe Zhao, Shinji Ito, Shuai Li2025 · arXiv (Cornell University) · 3 citations In Library
Data-dependent Bounds with $T$-Optimal Best-of-Both-Worlds Guarantees in Multi-Armed Bandits using Stability-Penalty MatchingQuan Nguyen, Shinji Ito, Junpei Komiyama et al.2025 · 1 citation In Library
Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-LeaderJongyeong Lee, Junya Honda, Shinji Ito et al.2026 · 0 citations In Library
Problem-Complexity Adaptive Model Selection for Stochastic Linear BanditsAvishek Ghosh, Abishek Sankararaman, K. Ramchandran2020 · International Conference on Artificial Intelligence and Statistics · 35 citations In Library
Beyond the Hazard Rate: More Perturbation Algorithms for Adversarial Multi-armed BanditsZifan Li, Ambuj Tewari2017 · Journal of machine learning research · 3 citations In Library
Sparsity, variance and curvature in multi-armed banditsSébastien Bubeck, Michael B. Cohen, Yuanzhi Li2017 · International Conference on Algorithmic Learning Theory · 68 citations In Library
Learning to Optimize under Non-StationarityWang Chi Cheung, D. Simchi-Levi, Ruihao Zhu2018 · International Conference on Artificial Intelligence and Statistics · 171 citations In Library

Peer review

Accept (poster)NeurIPS 2023 · via OpenReview
Reviewer Utqx7/10 · confidence 3/52023-07-05

Summary

The paper studies the problem of designing no-regret algorithm with three types of adaptivity to the setting: sparsity, game-dependency, and Best-of-Both-Worlds. To do so, the authors propose a new adaptive learning rate, called Stability-Penalty-Adaptive learning rate for Follow the regularized leader. They provide the first $s$-agnostic regret bound in the adversarial regime, where $s$ is the sparsity of the rewards. Moreover, they design the first Best-of-Both-Worlds algorithm with a sparsity-dependent regret bound. Finally, they extend the analysis to partial monitoring.

Strengths

The paper provides new improved regret bounds for different settings. The paper provides a clear comparison with previous work. The proofs of the theoretical results are not straightforward.

Weaknesses

The paper presents many different results and hence it is hard to follow the paper in some points. The analysis of the partial monitoring setting is relegated to the last half page. This makes impossible to have an insight on the results from the main paper.

Questions

.

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

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

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

yes

Reviewer 1eun7/10 · confidence 3/52023-07-09

Summary

This paper proposes a new scheme called SPA to configure adaptive learning rates for FTRL in MAB. Developed from a stability-&penalty-dependent generic regret bound for FTRL, SPA is designed to select learning rates to optimize the bound. SPA is then applied to three scenarios with different types of adaptivity, including sparsity, game-dependency, and BOBW. In particular, SPA eschews the need of knowing the sparsity level in advance as in previous methods, and is shown to achieve a near-optimal regret bound in both stochastic and adversarial settings. Finally, the proposed method is applied to partial monitoring, which achieves a game-dependent bound and BOBW property simultaneously.

Strengths

1. Adaptivity of FTRL is an interesting and important problem. The proposed adaptive methods may improve the applicability of FTRL in real-world scenarios. 2. This paper is technically sound with solid theoretical results. 3. This paper is well written in general and easy to follow.

Weaknesses

1. The design of SPA is rather straightforward, which seems a direct consequence of existing generic regret bound for FTRL. This somehow limits the novelty of the proposed method (though the subsequent extensions to scenarios with various forms of adaptivity are interesting and non-trivial).

Questions

See the "weaknesses".

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

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

2 fair

Contribution

2 fair

Limitations

Limitations have been properly discussed.

Reviewer WVsf6/10 · confidence 1/52023-07-10

Summary

This paper studies how to achieve BOBW regret bounds in sequential decision making problems such multi-armed bandits and partial monitoring games. To this end, this paper comes up with novel SPA learning rates for FTRL. For MAB, this paper shows FTRL with SPA could simultaneously be near-optimal for stochastic and adaptively adversarial sparse MAB, and is agnostic to the sparsity level. For PM, this paper shows it could achieve a regret bound that is both game-dependent and BOBW, and is better than previous results.

Strengths

In addition to the contribution mentioned in summary: 1. The SPA learning rate has an interesting form that may be of interest to the community and might have broader applications.

Weaknesses

1. The improvement upon the previous literature seems not big enough. The main improvement for sparse MAB seems to be removing the sparsity requirement. It is possible I underestimate the hardness of learning sparsity requirement, but since here we only need a multiplicative approximation of the sparsity, may I request the authors to explain why simple ideas such as using successive halving to guess the sparsity level wouldn't work here?

Questions

N/A

Rating

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

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

N/A

Reviewer x1zD6/10 · confidence 1/52023-07-13

Summary

This paper studies the Follow-the-Regularized-Leader (FTRL) framework for bandit problems. It proposes a learning rate dependent on both stability and penalty terms, which is inspired by the analysis. The proposal is helpful to achieve sparisty, game-dependent and Best of both worlds regret for bandit problems under stochastic and adversarial environments.

Strengths

- The proposed learning rate can be used to design algorithms that achieve sparsity-dependent and BOBW for Multi-arm bandit problem, and game-dependent and BOBW in partial monitoring problem. - The proposed learning rate might be of independent interest for other online learning problems. - The preliminaries are well-introduced to average readers.

Weaknesses

- It would be better to provide comparison on regret bounds with $\Delta_{\min}$ and $L_2$ with previous results (some of them don't have these parameters) in Table 1. - There are too many in-line equations, which might hurt presentation.

Questions

- What would we lose if the learning rate only depends on stability **or** penalty, e.g. the sparsity or gama-denpendent property or BOBW property? It would be better to illustrate as remark for comparison.

Rating

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

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

No limitations are discussed in the paper.

Reviewer TasV6/10 · confidence 1/52023-07-29

Summary

This work considers the Follow-the-regularized-leader paradigm for multi-arm bandit and partial monitoring problems. It proposes a new framework for designing FTRL algorithms with a time-dependent learning rate to generate algorithms that is adaptive to the sparsity of the feedback, to the setting being stochastic/adversarial/adversarial with self-bounding constraints, and to the game difficulty of a PM problem. Specifically, it proposes to choose the learning rate $\eta_t$ based on the penalty term (changes in the objective function due to the change of the time-dependent regularizer) and the stability term (a measure of progress) observed in previous iterations.

Strengths

The overall idea of this paper has many implications in different settings: for example, in Section 5.1, it generates algorithms with near-optimal guarantees in the setting of adversarial bandits with sparse feedback with/without restrictions on the signs of the feedback; in Section 5.2 it leads to an algorithm that is adaptive to the sparsity and to the adversarial-ness.

Weaknesses

While all the notations used in this paper are defined before being used, it would be great if some context/discussion can be provided before diving into the statements and analyses. For example, what is the intuitive way to see that $opt\prime_{q_t}(\eta_t)$ captures the game difficulty? It would also be nice to explicitly describe how the learning rate is used in the FTRL updates.

Questions

The algorithm analyzed in Section 5.2 achieves BOBW and adaptivity to sparsity in the adversarial setting. Is it possible to also have a notion of sparsity in the stochastic setting?

Rating

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

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

N/A

Reviewer x1zD2023-08-14

I thank the authors for the response. I have increased the score to reflect the change. - W1: I apologize for not making myself clear. My suggestion is to include discussion to help readers understand results in Table 1. Because parameters $\Delta_{\min}$ does not appear in [9] and $L_2$ does not appear in [25]. We want to understand how the dependency on these parameters of the new result affect the comparison if they behave like a constant or diverge.

Authorsrebuttal2023-08-15

Improving Table 1

Thank you for taking the time to clarify the details of your proposal to improve Table 1. We will include a discussion and comparison of your suggestions in the revised version. We will provide specific details below. > Because parameters $\Delta_{\min}$ does not appear in [9] and $L_2$ does not appear in [25]. Regarding $\Delta_{\min}$: First of all, since both the studies of [9] and [25] consider only the adversarial regime, $\Delta_{\min}$, which can be defined only in the stochastic regime, does not appear in their bounds. It is well known that the optimal regret for the stochastic regime is approximately $O(k \log (T) / \Delta_{\min})$ (due to limited space, this is described in Line 549 in Appendix). Note that our upper bound for the stochastic regime in Theorem 2 can be easily improved to $O( s \log (T) \log (kT) / \Delta_{\min})$, as mentioned in the reply to Reviewer TasV. Regarding $L_2$: Indeed, $L_2$ does not appear in [25], and instead they derive the regret upper bound of $O(\sqrt{sT \log (k/s) })$ with the sparsity level $s$. However, since $L_2 \leq s T$ holds, a rough comparison with our regret upper bound of $O(\sqrt{L_2 \log k })$ is available. The upper bound in [25] is slightly smaller in the worst case, i.e., when $L_2 = s T$, since the inside of the log is $k/s$. However, in many real-world problems, the regret upper bound of $O(\sqrt{L_2 \log k })$ in our paper is likely to be smaller. This is because the $L_2$-dependent regret upper bound can successfully handle not only the situation where the losses are sparse in all rounds but also the situation where the losses are sparse when averaged over the whole round. Hence, our upper bound can be significantly smaller than the bound in [25]. Furthermore, to improve the inside of the log to $k/s$ instead of $k$, the authors in [25] design a $s$-dependent regularizer based on a priori knowledge of the sparsity level $s$. On the other hand, our upper bound holds without a priori knowledge of $s$. Moreover, even if we assume that we know $s$, it is very uncertain whether we can prove one of our main goals, the best-of-both-worlds result (Theorem 2 of our paper), using the regularizer used in [25]. > We want to understand how the dependency on these parameters of the new result affect the comparison if they behave like a constant or diverge. When $\Delta_{\min} \to 0$, although the upper bound in our stochastic regime diverges, the bound for the adversarial regime is still valid even in this case since the stochastic regime is a special case of the adversarial regime. When $\Delta_{\min}$ is constant, the logarithmic regret upper bound like our bound in Theorem 2 cannot be obtained in [9] and [25].

Reviewer TasV2023-08-19

Thank you for the response. The score has been increased. My confidence score remains unchanged as I don't have the expertise to evaluate this paper properly.

Reviewer Utqx2023-08-20

Thank you for the response. My (positive) rating remains unchanged.

Reviewer WVsf2023-08-22

I have read the rebuttal. The clarification is helpful and I suggest the authors add them to the main text if possible.

Program Chairsdecision2023-09-21

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC