one of my concern is that the algorithm only works for the finite context case, which is very restrictive in real applications.

The proposed algorithm (Algorithm 1) can also work for the infinite context case, in which it enjoys the second regret upper bound in Corollary 1 (line 222): $R_T = O \left( \sqrt{dT \log K} + \lambda_0 \sqrt{T / (d \log K)} \right)$. In fact, this regret upper bound does not include $S = |\mathcal{X}|$ or $L$, and the value of $g(x)$ is not required to define $\eta(x)$ in showing this second upper bound. Hence, we do not require Assumption 1 (line 192) to show this bound.

In the infinite context case, however, further challenges regarding the computational complexity and practicality of the algorithm should be noted. For example, we need to compute $V(p_t)$ (defined in line 195) in the algorithm as it appears in the definition of $\hat{\theta}_t$ in (3), which tend to be computationally expensive, depending on the computational model and the setup of distributions. We also require Assumption 2 (line 196) as well.

In addition, the implementation of the algorithm requires the knowledge of the context distribution, which is also a limitation of the algorithm.

We agree with this comment. Relaxing this assumption is an important future research direction. We believe that the technique of Matrix Geometric Resampling [NO20] can be used to relax the assumptions that the context distribution is known, and to consider settings where any number of samples from the distribution can be accessed. However, as long as this is employed, an extra $\sqrt{\log T}$ factor seems inevitable. To further relax the assumption, [LWZ23] have proposed algorithms that do not even require access to a simulator from which the learner can draw samples from the context distribution. For such a setup, there is no known algorithm that achieve a $(\log K)$-dependent bound or that avoid extra $\sqrt{\log T}$ factors, to our knowledge.

As for the regret bound, while the leading term matches the lower bound, the optimality of the additonal term is unclear. Specifically, in the second bound, $L$ may also be related to $T$ (e.g. $T^{-c}$), making the additional term dominant.

The parameter $L$ is defined on the basis of the context distribution, independent of $T$, in Assumption 1 and does not grow with $T$ after fixing the problem instance. Thus, after fixing the context distribution arbitrarily, the additional term will not be dominant in a regime in which $T$ is sufficiently large. However, conversely, if we consider the regime of considering the worst-case context distribution after fixing $T$, then the additional term can be dominant, as the reviewer suggested.

We here note that the additional term in the second bound of Corollary 1 is the minimum of $\lambda_0 \sqrt{\frac{T}{d \log K}}$ and $\lambda_0 L^{\beta/\alpha} \sqrt{T^{1-\beta}}$, and hence large $L$ is not necessarily problematic. However, the parameter $\lambda_0$, which is defined in Assumption 2 on the basis of the context distribution and exploration policy $p_0$, can be arbitrarily large depending on the context distribution, which might make the additional term dominant.

Whether Algorithm 1 can be extended to infinite / unknown context case?

Please refer to the response above.

Whether the additional term in the upper bound for contextual linear bandits is unavoidable?

This is an open question at this time to our knowledge. However, if the main term can be $O(\sqrt{d^2 T \log T})$ instead of $O(\sqrt{d T \log (K \min \\{ 1, S/d \\}}))$, then we can remove the terms regarding $\lambda$ and $L$, as shown in Theorem 4 of [LWZ23].

Reference

• [LWZ23]H. Liu, C.-Y. Wei, and J. Zimmert. Bypassing the simulator: Near-optimal adversarial linear contextual bandits. NeurIPS2023.
• [NO20] G. Neu and J. Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits. COLT2020.

I also have a question about the proof of Lemma 3. In equation (15), a lemma in the bandit algorithm book is introduced to derive regret bounds. As far as I can see, the lemma only works for fixed $X_0$. However, in the learning process $p_t$ might depends on the historical contexts $X_0, X_1, X_2, \ldots, X_{t-1}$. I am confused about the usage of the lemma and hope for some explanations.

As mentioned in lines 227--229, the variable $X_0$ is a kind of dummy random variable that does not appear in the decision-making process or algorithms, but appear only in the analysis, and is defined to be independent of $X_1, X_2, \ldots, X_{T}$ (and therefore is independent of any other variables including $p_t$). The approach of such an analysis is proposed by [NO20], in which this is referred to as the ghost sample. The idea and usage of this technique are explained around (1) of Section 2 of [NO20]. Since $X_0$ is independent of all other random variables, it justifies the approach of marginalizing w.r.t. $X_0$ after evaluating for a fixed $X_0$. The revised version explains this more explicitly.

Reference

• [NO20] G. Neu and J. Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits. COLT202.

I am still confused about the proof so I hope for more detailed analysis. The linear contextual bandit problem seems too dirty so we can consider contextual bandit problem instead. For example, we assume there are $K$ arms in $X$. In each round. Let the context distribution $D$ be the uniform distribution over all subsets of $X$ with size $K/2$. Consequently, with high probability $X_i\neq X_j$ for any $i\neq j$. We then choose the reward function $r_t(x)$ as a Bernoulli variable with mean $1/2$. Then the best response $\pi^*$ is the policy such that $\pi^*(X_t): = \arg\max_{x\in X_{t}}r_{t}(x)$. With hight probability, we have $\sum_{t=1}^T \max_{x\in X_{t}}r_t(x)=T$. However, to reach a sublinear regret, one needs to identify the arms with reward $1$ in all but $o(T)$ rounds without any prior information. This seems impossible.

Could you please explain more about this?

Using this framework is very beneficial in best-of-both-worlds settings rather than in the purely adversarial or purely stochastic regimes. Have you considered generalizing your results to that setting?

Thanks for your suggestion. We believe that our results can be extended to the best-of-both-worlds (BOBW) setting if some difficulties are overcome. Challenging factors are inferred from the fact that there are only limited number of results achieving BOBW with FTRL using Tsallis entropy with $\alpha \neq 1/2$. The few such examples are [ITH24], [JLL23] and [RS20], which seem to require careful adjustment of learning rates that may depend on the feedback and output distributions so far, as is given, e.g., in Algorithm 1 of [JLL23]. They also seem to require some sort of stability condition, as given in equation (25) of [ITH24] and in Section C.3 of [JLL23]. If we can overcome these challenges, we believe our results can be extended to the BOBW setting.

Reference:

• [ITH24] Shinji Ito, Taira Tsuchiya, and Junya Honda. Adaptive learning rate for follow-the-regularized-leader: Competitive analysis and best-of-both-worlds. COLT2024.
• [JLL23] Tiancheng Jin, Junyan Liu, and Haipeng Luo. Improved best-of-both-worlds guarantees for multiarmed bandits: FTRL with general regularizers and multiple optimal arms. NeurIPS2023.
• [RS20] Chloé Rouyer and Yevgeny Seldin. Tsallis-INF for decoupled exploration and exploitation in multiarmed bandits. COLT2020.

While the lower bound for the MwE problem improves on prior results, it requires to consider a harder setting than the standard one by restricting the learner.

We deeply appreciate your suggestion. We agree that this is an important issue, and we will add this point to the abstract and introduction. In addition, we will mention in the revised version that showing a similar results in the "classical" problem setting remains as an open question.

For instance, the proof of Corollary 1 would benefit from a more detailed explanation of the steps; additionally, an intuitive explanation of the choice of the context-dependent learning rate would help the reader while possibly helping in adapting a similar idea in other related problem settings.

The revised version will includes a step-by-step explanation of how to calculate to show the bounds in Corollary 1. The context-dependent learning rate is designed so that the regret upper bound of Theorem 3 is bounded well. In fact, if we consider minimizing $\sum_{x} \frac{g(x)}{\eta(x)}$ subject to the constraint of $\sup_{x} \frac{\eta(x)}{ g(x)^{\beta} } \le$ const, the optimal solution is given as $\eta(x) \propto (g(x))^{\beta}$.

Finally, the results in this current work still do not achieve minimax optimality...

As you pointed out, for linear bandits and contextual linear bandits, minimax regret bounds have only been identified when $K$ is within a specific setting or range. The revised version will place more emphasis on this fact and make it clear that relaxing these assumptions is an open question to be resolved in future studies.

Could you expand a bit on how the argument at lines 278-279 allows us to keep the generality of the values of $S$, $K$, and $d$ as claimed?

We first note Theorem 4 implies that, if some $d'$ satisfies $K \ge 2^{d'}$ and $d \ge d'S$, we can obtain a regret lower bound of $R_T = \Omega(d'\sqrt{ST})$. Let $(d, K, S)$ be an arbitrary given parameter set satisfying $K \le 2^d \le K^S$. We then have $\log_2 K \le d \le S \log_2 K$. Define $d' := \lfloor \log_2 K \rfloor$ and $S' := \lfloor d / \log_2 K \rfloor \le S$. Then, as we have $K \ge 2^{d'}$ and $d \ge S' \log_2 K \ge S'd'$, from Theorem 4, we obtain a regret lower bound of $R_T = \Omega(d' \sqrt{S'T}) = \Omega( \sqrt{d' S' T d'} )$ for a problem instance with parameters $(d, K, S')$. By combining this with $d' S' = \Omega( d )$ and $d' = \Omega( \log K ) = \Omega( \log_+ (K \min \\{ 1, \frac{S}{d} \\}))$, we obtain $R_T = \Omega( \sqrt{ d T \log_+ ( K \min \\{1, \frac{S}{d} \\}) })$. As we have $S' \le S$, the same lower bound applies to the problem with parameters $(d, K, S)$ as well. The revised version will include a more detailed explanation like the above.

Do you think the ideas from the different lower bounds for linear bandits could be adapted and combined to prove a regret lower bound for arbitrary values of $K$?

We believe there is hope, and we have tried that approach, but have not yet succeeded. What we have considered so far is a generalization based on the combination of standard multi-armed bandits ($K = d$) and hypercube bandits ($K = 2^d$). For example, we have considered a problem in which we choose one of the the $k$ hypercubes and then choose a point in that hypercube, i.e., we set $d = d' k$ and define an action set as $\mathcal{A} = (\{ -1, 1 \}^{d'} \times \{ 0 \}^{d-d'}) \cup ( \{ 0 \}^{d'} \times \{ -1, 1 \}^{d'} \times \{ 0 \}^{d - 2d'}) \cup \cdots \cup (\{ 0 \}^{d-d'} \times \{ -1, 1 \}^{d'})$. We then have $K = |\mathcal{A}| = 2^{d'} k = d 2^{d'} / d'$. This construction almost covers the range of $K \in [d , 2^d]$ by adjusting the parameter $d' \in [1, d]$. We conjecture that a lower bound of $\Omega(d'\sqrt{kT})$ holds in this setting. We have been attempting to prove a lower bound using hard instances of hypercube bandits [DKH07], but the existing methods of analysis (e.g. [CHZ24]) do not seem directly applicable and have not yet been able to show the lower bound.

Minor comments/typos:

Thank you so much for your many helpful comments. Each will be reflected in the revised version.

Reference:

• [DKH07] V. Dani, S. M. Kakade, and T. Hayes. The price of bandit information for online optimization. NeurIPS2007.
• [CHZ24] H. Chen, Y. He, and C. Zhang. On interpolating experts and multi-armed bandits. ICML2024.

Motivation: The paper lacks an exploration of practical applications of the proposed work, thus indicating a deficiency in motivation. Incorporating a discussion on potential practical applications would significantly add value of the results presented in the paper.

We appreciate your suggestion. Since our results on linear bandits and contextual linear bandits imply improvements in the regret upper bound compared to existing algorithms, we expect improved performance in real-world applications and believe they will be useful in practice. However, this study focuses primarily on the goal of revealing the limits of achievable regret upper bounds for the fundamental online decision-making problems, rather than on specific applications.

Future Work: The paper does not discuss potential directions for future research.

The revised version describes open questions and future research direction more explicitly, as we mentioned in "Author Rebuttal" above.

No empirical results verifying the bounds.

This paper does not include empirical results because, in general, results of some specific numerical experiments are not very informative for the purpose of validating the analysis of minimax regret. Indeed, the minimax regret corresponds to the worst-case scenario, i.e., the problem instances that are most unfavorable loss-sequences for the algorithm. Numerical experiments on specific data are rarely the worst-case input, and it is difficult to know how close to the worst-case it is. The same reason may explain why many existing studies focusing on minimax regret do not include numerical experiments.

I found some typos that the author(s) might want to correct.

We deeply appreciate your pointing out the typo. We consider that all of them need to be corrected as you pointed out, and we will reflect them in the revised manuscript.

The proposed algorithm for contextual linear bandits (CLB) requires an initial exploration policy p0 as one of its input parameters. How is this policy determined at the start of the algorithm? Are there any specific assumptions or conditions on p0 necessary for it to adhere to the presented upper bound?

The necessary assumption on $p_0$ is described in Assumption 2 (line 196), where $\lambda( p_0 )$ is defined just above it. As long as this assumption is satisfied, $p_0$ can be determined in any way. In particular, if $p_0$ is determined using g-optimal design, then $\lambda(p_0) \le Ld$ holds, and hence this assumption is satisfied, as explained just after Assumption 2. The parameter $\lambda_0 = \lambda(p_0)$ depending on $p_0$ affects the asymptotically non-dominant terms (in the regime of $T \rightarrow \infty$) of the regret upper bounds provided in Theorem 3 and Corollary 1.