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

We are grateful for your valuable time and detailed review. Below are our responses to the review.

The authors should consider including an optimization problem aligned with (1) to better illustrate the hard problems.

Thank you for the comment regarding optimization problems. But, we may not understand the reviewer's intent, so if you have time, we would appreciate it if you could be more specific about what optimization problems should be included.

Additionally, more explanation is needed for the terms $z_t, h_t, u_t$ in the introduction or preliminaries sections to enhance understanding.

Thank you for your suggestion. We will add an intuitive explanation of $z_t$ and $h_t$ in the introduction, along with an example in the expert setting. As for $u_t$, it is a parameter that depends on the problem setting, and we provided examples in the sections on partial monitoring and graph bandits in the main text.

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.

Thank you for your comment. From a high-level perspective, these assumptions hold even for partial monitoring, which includes many sequential decision-making problems as special cases, as confirmed in Section 5. In this sense, we do not consider them to be strong assumptions.

Below, we provide a detailed explanation of each assumption: Assumptions (i) and (ii) naturally arise in the analysis of FTRL. In particular, Assumption (i): This is very standard because this is satisfied if we use an unbiased estimator $\hat{\ell}$. For example, it can be found in Chapter 11 of Lattimore and Szepesvari's book [36]. Assumption (ii): This is an upper bound on the stability term of FTRL, which can be controlled if the magnitude of the loss estimator is bounded favorably, and it is standard assumption in the analysis of bandit algorithms. For example, it can be found in Chapter 29 of Lattimore and Szepesvari's book [36]. Assumption (iii): This can be satisfied by ensuring the stability of the output of FTRL and has been investigated in various settings, for example, [55,26,28] and (Bubeck et al. 2018). For these reasons, Assumptions (i), (ii), and (iii) are considered relatively mild. The second condition in Eq. (14) has been used in existing research on best-of-both-worlds [26,28]. The first condition in Eq. (14) is new but can be seen as a natural extension of the second condition in Eq. (14) to problems with the minimax regret of $\Theta(T^{2/3})$.

• Bubeck et al. Sparsity, variance and curvature in multiarmed bandits. ALT 2018.

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?

Thank you for your valuable comment to improve the paper. From Assumption (iii) we have $h_t \leq c h_{t-1}$ for some constant $c$. Hence if we set $\hat{h}\_t \leftarrow c h_{t-1}$, we have $h_t \leq \hat{h}\_t$. Note that $h\_{t-1}$ can be calculated from the information available at the end of round $t-1$, so it can be used when determining $\beta_t$. In the revised version, we will include this discussion.

Why does Theorem 7 not depend on $p_0$?

The parameter $p_0$ is a parameter that should be appropriately determined according to the problem setting. We design $p_0$ in Algorithm 1 to satisfy Assumption (ii). For example, in partial monitoring, we set $p_0 = 1/k$, and in graph bandits, we set $p_0 = u$ (see Line 265). To improve the current text, we will revise the statement in Theorem 7 to, "If Algorithm 1 satisfies Assumptions (i)--(iii), then its regret is bounded as ...".

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?

The values of $z_t$ and $u_t$ are determined by the problem setting and the regularizer. In general, $u_t$ is chosen to satisfy the condition for stability (the assumption of Lemma 14 in our paper). Controlling the magnitude of the loss estimator by adding appropriate exploration to manage the stability term is common in the literature of FTRL in bandit problems (e.g., [8,26,54] and [36, Chapter 27]).

Regarding $z_t$, it is difficult to provide a general determination strategy within the limited space, as it varies depending on the form of the adaptive bounds that the algorithm designer aims to achieve. However, in the context of best-of-both-worlds bounds, it is common for $z_t$ to be determined based on the output of FTRL, $q_t$, to satisfy conditions similar to Eq. (14) in Theorem 2 [61,62,55,26,28].

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.

Thank you very much for taking the time to carefully review our paper and for providing many questions. Below are our responses to your review.

The effectiveness of the SPB-matching framework depends on the proper tuning of parameters, which might limit its practical applicability without further optimization techniques.

Thank you for your comment about practical applicability. However, we may not fully understand the reviewer's intent, so if you have time, we would appreciate it if you could be more specific about what further optimization techniques mean.

If the further optimization problem refers to the optimization of the fractional domination number in graph bandits as described in Eq. (19), note that this optimization problem can be computed efficiently by solving a linear programming problem once before the game begins [13].

Additionally, note that the tuning of parameters can be determined based on past observations, without the need to solve any optimization problem other than FTRL. This is standard in many best-of-both-worlds algorithms (e.g., [26,54,62]).

there are no experiments, as a result of which, it is unclear how the proposed method works in practice, even in the simulation.

Thank you for your comment. This paper focuses on theoretical aspects, and investigating the numerical performance in simulations or practical scenarios is an important future work.

... 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 ...

Thank you for pointing out this important point. The case where $a=2$ is special due to the classification theorem in partial monitoring. Partial monitoring is a very general problem that includes a wide range of sequential decision-making problems as special cases. It is known that, depending on the relationship between the loss matrix $\mathcal{L}$ and the feedback matrix $\Phi$, the minimax regret can be classified into one of four categories: $0$, $\Theta(\sqrt{T})$, $\Theta(T^{2/3})$, or $\Omega(T)$ (see line 484). Among these, the classes with non-trivial difficulties and particular importance are the problems with a minimax regret of $\Theta(\sqrt{T})$ and $\Theta(T^{2/3})$. This paper focuses on the problems with a minimax regret of $\Theta(T^{2/3})$ due to this classification theorem. In the revised version, we will explain why we particularly focus on the $\Theta(T^{2/3})$ case.

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.

Under the general online learning setup given in Section 2, it is almost impossible to prove a lower bound for Theorem 2. This general online learning setup is extremely general. For instance, it includes partial monitoring as a special case. However, partial monitoring itself is very complex, and even when focusing solely on the adversarial regret, no lower bound that depends on variables other than $T$ is known (see Item 14 of Section 37.9 in Lattimore and Szepesvari's book [36]). Since constructing a lower bound within the general online learning framework is far more challenging than considering a lower bound for partial monitoring, it is almost impossible to prove a lower bound for Theorem 2.

Still, the results for graph bandits (Corollary 9) obtained as a special case of Theorem 2 match the lower bound. Additionally, as mentioned in Global Comments, in the setting of multi-armed bandits with paid observations, the upper bound obtained by SPB-matching in the adversarial regime also matches the lower bound. From these observations, we can see that Theorem 2 matches the lower bound in several problem settings.

Could the author explain why $\gamma_t \geq u_t / \beta_t$ (in line 138) is needed? In which lemma or proof is this condition necessary?

This condition is used to bound the magnitude of the loss estimator $\hat{\ell}_t$. For example, in partial monitoring it is used in Eq. (61), and in graph bandits it is used in Eq. (79). Thanks to this lower bound of $\gamma_t$, we can apply Lemma 14 to control the stability term of FTRL (The LHS of (56)). In the revised version, we will provide a more detailed explanation in line 138 about why this condition is necessary.

Such efforts to bound the magnitude of the loss estimator are not unique to this paper but frequently appear in FTRL-related analyses. For instance, in the Exp3 algorithm [8], which is equivalent to FTRL with Shannon entropy, they employ exploration to bound the magnitude of the gain vector.

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 ...?

The high-level reason for the improvement is that the introduction of SPB-matching allows us to use the Tsallis entropy regularizer with an appropriate exponent $\alpha$. Such improvements have been known in various contexts, such as multi-armed bandits [3,5], sparse bandits (Kwon and Perchet, 2016), and (strongly observable) graph bandits (Zimmert and Lattimore, 2019 and [26]). To achieve best-of-both-worlds using Tsallis entropy, we need to derive a regret upper bound that depends simultaneously on stability and penalty components [26,28,55]. Our paper makes this possible even for problems with a minimax regret of $\Theta(T^{2/3})$.

• Kwon and Perchet. Gains and losses are fundamentally different in regret minimization: The sparse case, JMLR 2016.
• Zimmert and Lattimore. Connections between mirror descent, Thompson sampling and the information ratio, NeurIPS 2019.

Due to space constraints, we will respond to the items that are considered to have a relatively small impact on the evaluation in the following Comments.

We greatly appreciate your thorough and thoughtful review of our work. Here are our responses to your feedback.

The proposed learning rate is highly inspired by an existing adaptive learning rate in a recent work [26]. ... which does not bring enough challenges.

Yes, as the reviwer pointed out, the proposed adaptive learning rate is highly inspired by [26]. The primary challenge in our paper lies in finding a beneficial form of regret upper bounds that simultaneously depend on both stability and penalty for problems with a minimax regret of $\Theta(T^{2/3})$. We found that the form of $O\Big( \big(\sum_{t=1}^T \sqrt{z_t h_{t+1} \log T} \big)^{1/3} \Big)$ is beneficial. To our knowledge, this form of regret upper bound is new. In the revised version, we will include a discussion on these points. Due to the space constraint, please refer to primary challenge in our paper in Global Comments for further details.

... only logarithmic improvements for partial monitoring and even worse results for graph bandits.

and

... the authors emphasize that "Our bound is the first BOBW FTRL-based algorithm with the $O(\log T)$ bound ...". it is not much to be particular about, ...

Logarithmic improvement

First, logarithmic improvement is important. Historically, significant efforts have been dedicated to achieving an $O(\sqrt{kT})$ regret upper bound without the logarithmic term in multi-armed bandits [3,5]. Attempts to improve this logarithmic term have subsequently led to the development of the notable best-of-both-worlds algorithm in multi-armed bandits [61]. Furthermore, beyond multi-armed bandits, there are numerous efforts aimed at improving the logarithmic factor to enhance performance, for example, (Kwon and Perchet 2016; Zimmert and Lattimore 2019; Eldowa et al. 2023). Based on these points, we can see that the improvement of the logarithmic factor is important.

References

• Kwon and Perchet. Gains and losses are fundamentally different in regret minimization: The sparse case, JMLR 2016.
• Zimmert and Lattimore. Connections between mirror descent, Thompson sampling and the information ratio, NeurIPS 2019.
• Eldowa et al. On the Minimax Regret for Online Learning with Feedback Graphs, NeurIPS 2023.

Comparison with graph bandits result in Dann et al. [15]

As pointed out, the regret upper bound for our graph bandits indeed deteriorates compared to the bound of Dann et al. [15] (this difference arises because the (fractional) weak domination number in Dann et al. becomes the fractional domination number in our bound, and note that this change only worsens the bound when the feedback graph has a self-loop).

However, the approach of Dann et al. [15] employs a highly complex, multi-stage reduction approach. Moreover, it has the disadvantage of discarding past observations, similar to the doubling-trick. We have demonstrated that the framework of Follow-The-Regularized-Leader alone can achieve an upper bound similar to that accomplished by this highly complex approach, which is a significant theoretical advancement.

Generality to other problem settings Using our SPB-matching, we believe that best-of-both-worlds algorithms can be developed for a wide range of problems with a minimax regret of $\Theta(T^{2/3})$. For instance, the authors found after the submission that it is possible to achieve best-of-both-worlds bounds in multi-armed bandits with paid observations [53] by SPB-matching. Due to the space constraint, please refer to Generality to Other Problem Settings in Global Comments for further details.

... 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 ...

Thank you for your suggestion. Rule 1 was included for theoretical interest, and as the reviewer pointed out, it is not used in Sections 4 and 5. In the revised version, we will emphasize that only Rule 2 is used in Sections 4 and 5.

... the majority of the literature review is only proposed in the appendix, ...

Due to page constraints, much of the literature review had to be included in the appendix. In the revised version, we will aim to include as much of the literature review as possible in the main text.

Below, we provide replies to the questions.

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?

Thank you for your question. By employing their black-box reduction approach, it seems possible to achieve an upper bound of the same order as our upper bound in globally observable partial monitoring. Apologies for not realizing this at the time of submission. This is because Dann et al.'s method cannot be used in partial monitoring games with minimax regret of $\sqrt{T}$ unless the loss of the selected action is observed [56]. Nevertheless, as previously mentioned, the approach by Dann et al. [15] is a complicated approach involving multi-stage reductions and has the drawback of discarding past observations, similar to the doubling-trick. Hence, demonstrating that using the FTRL framework alone can achieve the same upper bound is a significant theoretical advancement. In the revised version, we will include the regret upper bound obtained by Dann et al. in Table 1 and describe the differences between their method and the advantages of using FTRL directly.

Due to space constraints, we will respond to the items that are considered to have a relatively small impact on the evaluation in the following Comments.

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.

We appreciate your valuable time and helpful comments. Below is our response to your comments.

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 is fixed. It would be beneficial to further discuss the difficulties encountered when tackling the 'hard problem'.

The primary difficulty in our paper lies in finding a beneficial form of regret upper bounds that simultaneously depend on both stability and penalty for problems with a minimax regret of $\Theta(T^{2/3})$. For problems with a minimax regret of $\Theta(\sqrt{T})$, it is known that the form of $O\Big(\sqrt{\sum_{t=1}^T z_t h_{t+1} \log T}\Big)$ for the stability component $z_t$ and the penalty component $h_t$ allows us to derive best-of-both-worlds bounds [26, 28, 55]. However, for problems with a minimax regret of $\Theta(T^{2/3})$, it is non-trivial to determine the form of regret upper bounds that are useful for achieving best-of-both-worlds bounds. We found that the form of $O\Big( \big(\sum_{t=1}^T \sqrt{z_t h_{t+1} \log T} \big)^{1/3} \Big)$ is beneficial. To our knowledge, this form of regret upper bound is new. In the revised version, we will include a discussion on these points.

Regarding the difference on the exploration rate from Section 4.1 of [26] (we believe Section 5.1 is a typo for Section 4.1), they only consider problems with a minimax regret of $\Theta(\sqrt{T})$, and they set the exploration rate $\gamma_t$ either to $\gamma_t = 0$ or $\gamma_t \simeq z_t / \beta_t$. When $\gamma_t \simeq z_t / \beta_t$, the additional regret due to this exploration is of the same order as the stability term, and thus a tuning strategy of the learning rate $\beta_t$ remains the same. In contrast, in problems with a minimax regret of $\Theta(T^{2/3})$, due to the nature of handling indirect feedback, forced exploration becomes necessary. As a result, the magnitude of the loss estimator increases, resulting in $\gamma_t$ appearing in the denominator of the stability term (see Lines 134--140). Hence, if we use $\gamma_t \simeq z_t / \beta_t$, the stability term becomes excessively large. Setting a larger exploration rate, $\gamma_t \simeq \sqrt{z_t / \beta_t}$, resolves this issue.

Thank you very much for your valuable time and thorough review. Regarding the minor comments and typos, we will address and correct them in the revised version. Below is our response to the review:

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.

Thank you for your valuable comments. For the partial monitoring problem, when we use $\beta_1 = 64 c_{\mathcal{G}}^2 / (1 - \alpha)$, which satisfies the first inequality in Eq. (17), we have $\kappa = O(c_{\mathcal{G}}^2 \log k + k^{3/2} (\log k)^{5/2})$ and $\kappa' = \kappa + O\left( ( c_{\mathcal{G}}^{2/3} (\log k)^{1/3} + \sqrt{c_{\mathcal{G}} \log k} ) ( \frac{1}{\Delta_{\min}^2} + \frac{C}{\Delta_{\min}} ) \right)$. For the graph bandit problem, when we use $\beta_1 = 64 \delta^* / (1 - \alpha)$, which satisfies the first inequality in Eq. (20), we have $\kappa = O(\delta^* \log k + k^{3/2} (\log k)^{5/2})$ and $\kappa' = \kappa + O\left( ( (\delta^* \log k)^{1/3} + \sqrt{\delta^* \log k} ) ( \frac{1}{\Delta_{\min}^2} + \frac{C}{\Delta_{\min}} ) \right)$. In the revised version, we will make the influence of $\kappa$ and $\kappa'$ explicit.

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.

Thank you for pointing out this important point. We believe that our approach may not be applicable to all problems with the minimax regret of $\Theta(T^{2/3})$ (hard problems), and as the reviewer suggests, different novel ideas might be required. Still, if a hard problem has a structure similar to hard graph bandits and partial monitoring problems that requires additional exploration, we believe that the best-of-both-worlds bounds can be achieved by SPB-matching.

For instance, the authors found after the submission that it is possible to achieve best-of-both-worlds bounds in multi-armed bandits with paid observations [53] by SPB-matching. In this setting, the learner can observe the loss of any action by paying a cost, and the goal of the learner is to minimize the sum of the regret and total paid costs for observations. The cost of observations behaves similarly to the bias term in the stability–penalty–bias decomposition, and thus our SPB-matching learning rate can be applied. In particular, we can show that the sum of the regret and paid costs is roughly bounded by $O\big( (c k \log k)^{1/3} T^{2/3} + \sqrt{T \log k} \big)$ in the adversarial regime and by $O\big( \max\\{c,1\\} k \log k \log T / \Delta_{\min}^2 \big)$ in the stochastic regime for the cost of observation $c$. This is the first best-of-both-worlds bounds for multi-armed bandits with paid observations, and the bound for the adversarial regime is of the same order as [53, Theorem 3], demonstrating the effectiveness of the SBP framework. The proof is almost the same as in the cases of graph bandits and partial monitoring. The revised version will include this discussion.

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.