A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $\Theta(T^{2/3})$ and its Application to Best-of-Both-Worlds

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 15:45:07

Abstract: Follow-the-Regularized-Leader (FTRL) is a powerful framework for various online learning problems. By designing its regularizer and learning rate to be adaptive to past observations, FTRL is known to work adaptively to various properties of an underlying environment. However, most existing adaptive learning rates are for online learning problems with a minimax regret of $\Theta(\sqrt{T})$ for the number of rounds $T$, and there are only a few studies on adaptive learning rates for problems with a minimax regret of $\Theta(T^{2/3})$, which include several important problems dealing with indirect feedback. To address this limitation, we establish a new adaptive learning rate framework for problems with a minimax regret of $\Theta(T^{2/3})$. Our learning rate is designed by matching the stability, penalty, and bias terms that naturally appear in regret upper bounds for problems with a minimax regret of $\Theta(T^{2/3})$. As applications of this framework, we consider three major problems with a minimax regret of $\Theta(T^{2/3})$: partial monitoring, graph bandits, and multi-armed bandits with paid observations. We show that FTRL with our learning rate and the Tsallis entropy regularizer improves existing Best-of-Both-Worlds (BOBW) regret upper bounds, which achieve simultaneous optimality in the stochastic and adversarial regimes. The resulting learning rate is surprisingly simple compared to the existing learning rates for BOBW algorithms for problems with a minimax regret of $\Theta(T^{2/3})$.

Main paper: 
  
 Appendix:  


Decision: Reviewers expressed mostly positive opinions on the novelty and significance of this work. Mild doubts about the level of contribution not reaching the bar of NeurIPS were discussed but were eventually dismissed. I recommend acceptance (poster) with the caveat that the authors commit to addressing the reviewers' comments in the revised version.

Reviews: review: paper_summary: paper_summary: The paper introduces a novel adaptive learning rate framework for Follow-the-Regularized-Leader (FTRL) tailored to online learning problems characterized by a minimax regret of Θ(T^2/3). This new learning rate, termed Stability-Penalty-Bias (SPB) matching, is designed by balancing stability, penalty, and bias terms within the decomposition of the regret as $\text{Reg}\_T \\leq \\sum\_{t=1}^T \\frac{z\_t}{\\beta\_t \\gamma\_t} + \\beta\_1 h\_1 + \\sum\_{t=2}^T (\\beta\_t - \\beta\_{t-1}) h\_t + \\sum\_{t=1}^T \\gamma\_t$. The paper demonstrates the efficacy of this approach through its application to two significant “hard” online learning problems: partial monitoring and graph bandits, both of which involve indirect feedback. The proposed framework improves upon existing Best-of-Both-Worlds (BOBW) regret bounds, providing simpler yet effective learning rates compared to existing methods and consequently achieving $O(\\log T)$ regret in the stochastic regime and $O(T^{2/3})$ in the adversarial regime.
strength_weakness: strength_weakness: There is a clear effort by the authors to provide a smooth and clear description of the SPB-matching technique.
However, the large number of parameters made it hard to fully understand how each would exactly influence the analysis of the final regret bound of the algorithm.
Only after multiple reads did the full details click and it was clear how all the pieces nicely fit together.
In any case, this appears to be caused by the generality of this unified framework and is likely to be unavoidable.

Furthermore, the regret bounds in Corollaries 9 and 11 are not fully clear because of the presence of $\\kappa$ and $\\kappa’$.
Given that all the other parameters have specific values for the two problems considered here, and both $\\kappa$ and $\\kappa’$ are a function of them, replacing them and thus having an explicit dependence on the actual parameters of the problems could make it easier to understand the regret guarantees in the two corollaries and to compare them with previous related results.
Even a simple comment on the influence of $\\kappa$ and $\\kappa’$ to the regret bound for in these two specific cases would help the reader.
questions: questions: - The possibility of adopting similar ideas to other “hard” online learning problems is suggested in the conclusions. However, while the hardness of the problems considered here is mainly related to the observability of the losses, other problems have different characteristics that make them “hard”. For example, the additional hardness of bandits with switching costs is about the loss being adaptive to the previous action of the learner, leading to an extra cost whenever the learner changes the action to play. On the other hand, SPB-matching is related to the presence of the bias term due to having extra exploration to tackle the limited observability. Do the authors believe a variant of SPB-matching could help with these additional problems? Or do they believe these problems would require different novel ideas? Just some vague intuition about this would be appreciated.
- What are the lower bounds for partial monitoring with global observability? I think being clearer about this would help the reader understand the quality of your regret bound for this problem.

Minor comments/typos:
- Line 211: “literature” instead of “litarature”
- Line 221: l.h.s. of the inline equation should be $\\sum\_{c=1}^k \\bigl( G(c,\\Phi\_{cx})\_{a} - G(c,\\Phi\_{cx})\_{b} \\bigr)$
- Line 695: duplicate “which is not desirable.”
- Line 700: “Shannon” instead of “Shanon”
- Lines 701-702: “dominating” instead of “domination”
limitations: limitations: The authors address potential limitations.
paper_summary: paper_summary: This paper considers the online problems with a minimax regret of $\Theta(T^{2/3})$ and proposes a new learning rate tuning based on the FTRL algorithm to tackle these problems. The development of the learning rate is straightforward and simpler compared to previous works. The proposed algorithm is versatile in various applications, and the authors prove that it can achieve improved best-of-both-worlds regret bounds.
strength_weakness: strength_weakness: The main technique of designing learning rates so that the stability and bias terms are matched seems to already appear in the cited paper [26], and the development of the method seems to focus on how to solve the additional term introduced by the 'forced exploration' strategy. With a quick glance at the cited paper [26], in Section 5.1, this paper also employs the 'forced exploration' strategy, except that the balance ratio $\gamma$ is fixed. It would be beneficial to further discuss the difficulties encountered when tackling the 'hard problem'.
questions: questions: Could the author respond to the concerns in the 'Weaknesses'?
limitations: limitations: NA
paper_summary: paper_summary: In this work, the authors propose a simple and adaptive learning rate for FTRL, which can achieve the minimax regret of $O(T^{2/3})$ for some hard online learning problems. Specifically, they have applied their algorithm (FTRL with the proposed learning rate) to achieve the best-of-worlds regret bounds for partial monitoring (with global observability) and graph bandits (with weak observability), respectively. For the first problem, compared with the best existing results, this paper achieves an $\log(T)/\log(k)$ improvement in the stochastic setting, and an $(\log(T)+\log^2(T)/\log(k))^{1/3}$ improvement in the adversarial setting. But, for the second problem, compared with the best existing results, it seems that this paper can only achieve worse regret bounds (by a factor of $\delta^\ast/\delta$) in the stochastic and adversarial settings.
strength_weakness: strength_weakness: However, I have some concerns about this paper.
1) The proposed learning rate is highly inspired by an existing adaptive learning rate in a recent work [26]. Although the existing one can only be utilized to achieve the minimax regret bound of $O(\sqrt{T})$ for some relatively easy problems, the only difference for the proposed learning rate is to further trade off a bias term (with the stability term), which does not bring enough challenges.
2) The motivation for such a learning rate for FTRL is to deal with some hard online learning problems (e.g., partial monitoring and graph bandits) that have been well-studied before. Although this paper has applied their algorithm (FTRL with the proposed learning rate) to achieve the best-of-worlds regret bounds for partial monitoring and graph bandits respectively, it does not bring significant advantages compared with existing results, i.e., only logarithmic improvements for partial monitoring and even worse results for graph bandits.
3) In Section 3, two update rules are proposed for the simple and adaptive learning rate. However, in Sections 4 and 5, it seems that only the second update rule is utilized. So, it is confusing why the authors propose the first update rule and spend non-ignorable spaces in the main text to introduce the corresponding results.
4) The writing of this paper needs to be improved. For example, the majority of the literature review is only proposed in the appendix, which indeed reduces the readability of this paper. In addition, in line 273, the authors emphasize that "Our bound is the first BOBW FTRL-based algorithm with the $O(\log T)$ bound ...". Although this is not wrong, it is not much to be particular about, because there already exist other non-FTRL-based algorithms to achieve the  $O(\log T)$ regret bound.
questions: questions: Besides the concerns discussed above, I also have the following two questions.
1) Can the authors provide a detailed comparison between the proposed algorithm and existing algorithms in works [26, 54]?
2) It seems that Dann et al. [15] propose a black-box approach to best-of-worlds regret bounds in bandits. Can their approach be utilized to solve the partial monitoring problem?
limitations: limitations: The authors have provided some discussions on the limitations of this work.
paper_summary: paper_summary: The paper aims to develop a new adaptive learning rate framework for the Follow-the-Regularized-Leader (FTRL) algorithm that addresses online learning problems with a minimax regret of $\Theta(T^{2/3})$. 

It specifically targets problems with indirect feedback, such as partial monitoring and graph bandits, and demonstrates the efficacy of the proposed framework in improving Best-of-Both-Worlds (BOBW) regret upper bounds.
strength_weakness: strength_weakness: 1. **Practical Consideration:** The effectiveness of the SPB-matching framework depends on the proper tuning of parameters, which might limit its practical applicability without further optimization techniques. Furthermore, there are no experiments, as a result of which, it is unclear how the proposed method works in practice, even in the simulation. 
2. **Clarity and Accessibility:**  The paper is difficult to follow due to its technical nature. Some equations and results are presented without sufficient explanation, and the extension to the two case studies introduces many new concepts that are hard to follow.
questions: questions: 1. **Extension to High-dimensional Sparse Bandits:** The $\Theta(T^{2/3})$ regret reminds me of the results in high-dimensional sparse linear bandits [1*]. The regret in [1*] is $\Theta(s^{1/3}T^{2/3})$ (where $s$ is the level of sparsity), and the algorithm in [1*] also depends on a sort of "forced exploration." Is it possible to apply the framework developed in this paper to this high-dimensional and sparse setting?
   
    -  [1*] Hao, Botao, Tor Lattimore, and Mengdi Wang. "High-dimensional sparse linear bandits." Advances in Neural Information Processing Systems 33 (2020): 10753-10763.

2. **Other Upper Bounds:** The introduction of the minimax regret $\Theta(T^{2/3})$ is somewhat abrupt. It makes me wonder whether in some cases, there is a minimax regret like $\Theta(T^{a/(a+1)})$ for some parameter $a>0$ and why the case $a=2$ is so special that we should focus on it.

3. **General Lower Bound:** Is there any general lower bound for the regret in Theorem 2? While particular cases may have existing lower bounds, a general tight lower bound is expected given that the paper starts from a general framework and provides a general upper bound.
   

4. **Clarification on Exploration Rate Requirement:** Could the author explain why $\gamma_t \ge u_t/\beta_t$ (in line 138) is needed? In which lemma or proof is this condition necessary?
   
5. **Comparison of SPB-Matching Rules:** Which rule is better in theory or practice: Rule 1 or Rule 2 in (6)?
   
6. **High-Level Explanation of Regret Improvement:** Could the author briefly explain why the regret is improved after applying the established framework in Sections 5 and 6? Is there any high-level explanation beyond the technical details?
limitations: limitations: See the Weaknesses and Questions.
paper_summary: paper_summary: This paper provides a new adaptative learning rate framework for hard problems, called Stability-Penalty-Bias matching learning rate (SPB-matching). Using this SPB-matching learning rate, the paper proposes a Best-of-both-worlds (BOBW) algorithm framework for hard online learning problems. It not only achieves simultaneous optimality in the stochastic and adversarial regimes but also achieves the MS-type bound in the adversarial regime with a self-bounding constraint. The paper further shows the utility of their frameworks by studying two hard problems: partial monitoring and graph bandits.
strength_weakness: strength_weakness: - **Need more background introduction**: The authors should consider including an optimization problem aligned with (1) to better illustrate the hard problems. Additionally, more explanation is needed for the terms $z_t, h_t, u_t$ in the introduction or preliminaries sections to enhance understanding.
- **Strong assumptions**: Although the assumptions in Theorem 7 are checked for two specific problems, they are quite strong and may not hold for many hard problems. The authors should add more discussion about these assumptions, explaining the meaning of each assumption and identifying scenarios in which these assumptions hold.
questions: questions: - Can the authors provide more explanations on the terms $z_t$, $h_t$, and $u_t$?
- On page 5, line 146, the paper assumes access to $\hat{h}_t$, which upper bounds $h_t$. Why is this always the case in reality?
- Why does Theorem 7 not depend on $p_0$?
- Why are $z_t$ and $u_t$ chosen as they are in the two examples? What is the practical meaning behind this choice? How should $z_t$ and $u_t$ be decided for other examples?
- Typo: In Lemma 5, line 163, it should be $J \in \mathbb{N}$ instead of $j \in \mathbb{N}$.
limitations: limitations: See weaknesses.

Comments: title: Additional Replies
Additional Replies
comment: Thank you for the exhaustive responses to my questions and the useful insights. I am keeping my positive score.
Thank you for your responses. I will keep my positive score.
Thanks for the authors' response. I currently do not have additional questions, and will make my final decision after further discussing with other reviewers and AC.
Thank you for your response to my comments. 
The explanation provided by the authors addresses my concerns about the strong assumptions, so I will raise my score to 6. I hope the authors will include an intuitive explanation of $z_t$ and $h_t$ in the revised version.
Here, we will respond to the items that are considered to have a relatively small impact on the evaluation, which cannot be included in the above rebuttal due to the space constraint.

> Is it possible to apply the SPB-matching framework developed in this paper to high-dimensional sparse linear bandits (by Hao-Lattimore-Wang 2020)?

Thank you for your suggestion.
The paper by Hao, Lattimore, and Wang (2020) on high-dimensional sparse linear bandits considers the stochastic regime. 
To the best of our knowledge, there are no studies investigating whether a dimension-free bound is possible in the adversarial regime similar to Hao, Lattimore, and Wang (2020). 
Therefore, before investigating the applicability of our SPB-matching framework in this setting, it is necessary to study high-dimensional sparse linear bandits in the adversarial regime.

> Which rule is better in theory or practice: Rule 1 or Rule 2 in (6)?

First, the information available for determining $\beta_t$ differs between Rule 1 and Rule 2. In Rule 1, it is assumed that the information up to time $t-1$, $z_t$, $u_t$, and $\hat{h}_t \geq h_t$ are known when determining $\beta_t$. In Rule 2, it is assumed that the information up to time $t-1$ and $\hat{h}_t \geq h_t$ are known when determining $\beta_t$. Rule 1 is included due to theoretical interest and is not used in Sections 4 and 5. In the revised version, we will explicitly state this and further emphasize that the information available when determining $\beta_t$ differs between Rule 1 and Rule 2.
Here, we will respond to the items that are considered to have a relatively small impact on the evaluation, which cannot be included in the above rebuttal due to space constraints.


> What are the lower bounds for partial monitoring with global observability?

To the best of our knowledge, beyond the dependency on $T$, little is known about the lower bound for partial monitoring (with global observability). 
In the adversarial regime, the dependency on $T$ is known to be $\Omega(T^{2/3})$ [9, 34, 35]. 
However, little is understood about the dependencies on the variables $k$, $d$, and $m$, which is also mentioned in Section 37.9 of [36]. 
In the stochastic regime, an asymptotic distribution-dependent lower bound of $\Omega(D (\nu^* )\log T)$ is known [30], where $D(\nu^*)$ denotes the optimal value of a certain complex optimization problem. 
However, it is not clear how this $D(\nu^*)$ depends on $k$, $d$, and $m$, and investigating this is important future work. 
In the revised version, we will discuss that little is known about the dependencies other than $T$ for the lower bound in partial monitoring.

> Can the authors provide a detailed comparison between the proposed algorithm and existing algorithms in works [26, 54]?

(Comparison with [26])
As mentioned above, this study considers problems with the minimax regret of $\Theta(T^{2/3})$, and an ideal form dependent on the stability component $z_t$ and penalty component $h_t$ are different.

(Comparison with [54])

In [54]:
- Their main regularizer is the negative Shannon entropy.
- The regret upper bound in the stochastic regime is $O((\log T)^2)$.
- Their learning rate (for globally observable games) is highly complicated.

Our approach:
- Our main regularizer is the negative Tsallis entropy.
- The regret upper bound in the stochastic regime is $O(\log T)$.
- The learning rate is designed based on a simple principle that matches stability, penalty, and bias components.