Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits

Thank you for your support of our work and your valuable feedback. We respond to them separately.

I was a bit confused by the discussion of \cX \equiv \cS^{d-1} because the notation of the sphere is not defined

$\mathcal{S}_{d-1}\\coloneqq\lbrace x \in \mathbb{R}^d:\\|x\\|=1\rbrace$ is the unit hypersphere in $\mathbb{R}^d$. We have added the definition as suggested.

I had missed the discussion on considering only algorithms for which $\tau\_t=0$

We have revised the discussion of considering only the case where $\tau_t = 0$: Typically, we can check that $\hat{\\alpha}\_{t}$ is no less than one because when $\\tilde{x}\_{t} = x\_{t}^{\\star}$, we have $\\alpha\_{t} = \\|x\_{t}^{\\star}\\|\_{V\_{t}^{-1}}/\\|\\tilde{x}\_{t}\\|\_{V\_{t}^{-1}} = 1,$ and $\hat{\\alpha}\_{t}$ is an upper bound for $\\alpha\_{t}$. As a result, it holds that $\\hat{\\mu}\_{t} = (1+\\hat{\\alpha}\_{t})(1+\\iota\_{t}) + (1-\\hat{\\alpha}\_{t})\\tau\_{t} \\leq (1+\\hat{\\alpha}\_{t})(1+\\iota\_{t}),$ i.e., setting $\\tau\_{t} = 0$ yields a valid upper bound for $\hat{\\mu}\_{t}$. Given this observation, we will focus on scenarios where $\\tau\_{t} = 0$ for all $t \\in [T]$. We will add more explanations regarding this in the final version of the proof.

Weaknesses:

In Line 102, the paper says that “derive a general, instance-dependent frequentist regret bound”. Usually ‘instance-dependent’ in bandit literature means that the regret depends on the sub-optimality gap. Here there may be some confusion.

Thank you for your valuable feedback. We have used “a data-driven frequentist regret bound” instead in the revision to avoid the confusion.

Since the algorithm still needs to compute the OFUL solution, the computational advantage may be limited. Can authors discuss in the experiments what percentage of rounds need to be replaced with OFUL?

Thank you for your valuable feedback. We have conducted additional simulations (in Appendices I and J of the revised manuscript) to report the percentage of rounds where the OFUL actions are used. The results show that OFUL actions are only frequently used at certain beginning stage of the time horizon, and tends to remain at a low level after that. This indicates that limited amount of course-corrected exploration at the beginning efficiently fixed TS and Greedy in the problematic instances. Hence, although the computational cost depends on the hardness of the problem but is typically low.

Some writing suggestions: a) In Section 4.1, the definition of $\\tilde{x}_t$ and $x_t^*$ should be moved before the Proposition 4. b) In Appendix C, the $\leq$ in Line 872 should be $\geq$, the $\in$ in Line 882 should be $\notin$.

Thank you for your suggestions. We have implemented these corrections in the revision.

Weaknesses:

The method involves setting hyper-parameters (also inflation and optimism parameters) for the course-corrected algorithm. How it is chosen in the experiments is not discussed. More insights into how these parameters influence the outcome or suggestions for selecting optimal values would strengthen the practical utility of the method.

Thank you for your valuable feedback. In the revised manuscript (Appendix I and J), we have conducted additional simulations to show the influence of $\mu$ and have provided suggestions on tuning it. Furthermore, we should clarify that the inflation and optimism parameters are determined by the choice of algorithm (OFUL, TS, or Greedy). Specifically, for OFUL, we have $\iota_t=0, \tau_t=1$; for Greedy $\iota_t=0, \tau_t=0$; and for LinTS, $\iota_t=\widetilde{\mathcal{O}}(1)$ (which depends on system parameters but remains fixed) and $\tau_t=0$.

Empirically, TS-MR appears to perform similar to the better one of LinTS and OFUL in most cases when the balancing parameter is carefully chosen. While this result aligns with intuition, the paper lacks a discussion of the specific situations in which TS-MR could significantly outperform both LinTS and OFUL.

Thank you for your valuable feedback. We would like to clarify that the primary goal of the proposed algorithm is not to outperform the baseline algorithms. Rather, it aims to employ only necessary exploration to maintain optimal worst-case performance guarantees while avoiding excessive conservative actions that degrade empirical performance and increase computational costs. Nevertheless, the simulation results show that the course-corrected algorithm can be better than both baseline algorithms (see, e.g. Figure 3(b) and 4(b) in Section 7 where Greedy-MR outperforms Greedy and LinTS).

The proposed method involves calculating $\hat{\mu}_t$ each round, which can be can be computationally demanding. This could limit the scalability of the proposed method, especially in applications where the dimension $d$ or the number of actions $T$ is large. It may benefit from a discussion of strategies to mitigate computational costs in such scenarios.

Thank you for your valuable feedback. The most computationally demanding step in calculating $\\hat{\mu}\_t$ is the SVD decomposition of the sample covariance matrix $V_t$. However, since $V_t=\lambda_{\text{reg}} I+\sum_{s=1}^t x_s x_s^{\top}$ is updated by a rank-one matrix at each timestep, its SVD decomposition can be updated efficiently (see, e.g., [1]). Consequently, the total complexity of calculating $\hat{\mu}_t$ is equivalent to that of Greedy and TS ($\tilde{O}(Td^2)$) and does not become a computational bottleneck. We will include this discussion in the final version of the paper.

[1] Gandhi, Ratnik, and Amoli Rajgor. "Updating singular value decomposition for rank one matrix perturbation." arXiv preprint arXiv:1707.08369 (2017).

Questions:

Line 310: "On the right-hand side of equation 4...one cannot apply Proposition 2..." Could you explain why? Proposition 2 applies to an "arbitrary" sequence, so it seems general enough to be applied here.

Thank you for your comments. Note that when implementing the algorithms, the sample covariance matrix at time $t$ takes the form $V_t = \lambda\_{\\text{reg}} I + \sum\_{s=1}^{t} \\tilde{x}\_{s} \\tilde{x}\_{s}^{\\top}$ ， where $\\{\\tilde{x}\_{s}\\}\_{s \\in [t]}$ are the action chosen at time $s$. Although $\\{\\tilde{x}\_s\\}\_{s\\in[t]}$ can be arbitrary, Proposition 2 holds only when the action sequence and the sample covariance matrix are consistent with each other. Specifically, Proposition 2 can only be applied to $\\{\\tilde{x}\_s\\}\_{s\in[t]}$, yielding the inequality $\\sum\_{s=1}^t \\left\\|\\tilde{x}\_s\\right\\|\_{V\_s^{-1}}^2 \\leq 2 d \\log \\left(1+\\frac{t}{\\lambda\_{\\text{reg}}}\\right).$ We will revise the sentence to improve clarity.

Line 266: why $\tilde{x}_t=x_t^*$ leads to $\alpha_t$ no less than 1? If $\alpha_t$ is no less than 1, shouldn't the inequality in line 367 go the other way?

Thank you for your comments. Since $\\hat{\\alpha}\_t$ serves as an upper bound for $\\alpha\_t$ for all potential $\\tilde{x}\_t$, and given that when $\\tilde{x}\_t = x\_t^{\\star}$, we have $\\alpha\_{t} = \\|x\_{t}^{\\star}\\|\_{V\_{t}^{-1}}/\\|\\tilde{x}\_{t}\\|\_{V\_{t}^{-1}} = 1$, it follows that $\\hat{\\alpha}\_t \\geq 1$. We have corrected the inequality typo in line 367 and revised the accompanying discussion.

Weaknesses:

The main weakness concerns the reproducibility of the experiments. The authors provide few explanations regarding the experiment setup in the paper and no information regarding the algorithm's parameters and implementation. They did not provide their code, and the details they give in the Appendix are not sufficient to reproduce the same experiments. Therefore, it was impossible to assess the soundness of the simulation results.

Thank you for your comments. We have attached the code to the supplementary material to reproduce the simulation results.

A second weakness concerns the experimental comparison. The authors should have included experiments assessing the influence of the algorithm parameter on the performance. ... It would have been for the authors to include a comparison with a different algorithm such as UCB.

• We appreciate the reviewer's comment. We have conducted simulations in the revised manuscript ( Appendices I and J ) to illustrate the influence of $\mu$ and have provided suggestions on tuning it.
• We appreciate the reviewer's comment, which provides us with the opportunity to further clarify the relationship between UCB and OFUL in the context of linear bandit problems. At a high level, OFUL implements the UCB principle by utilizing the linear structure of the problem and can be regarded as a UCB-type algorithm for linear bandits. Specifically, UCB chooses the action with the highest upper confidence bound, while OFUL solves: $\max\_{x \in \mathcal{X}\_t} \\left\\langle x, \\widehat{\\theta}\_t \\right\\rangle + \\|x\\|\_{V\_t^{-1} }\\beta\_{t,\\delta^{\\prime},\\lambda_{\\text{reg}}}^{RLS}$ , and here $\\|x\\|\_{V\_t^{-1} }\\beta\_{t,\\delta^{\\prime},\\lambda_{\\text{reg}}}^{RLS}$ represents the confidence radius of the reward of $x$. We will add further explanation regarding this to improve clarity in the final version of the paper.

Another point of improvement concerns the figures in the paper. First, the font size in all figures in the paper is too small to read on a printed version of the paper. Second, some figures lack explanations such as Figure 3 which seems to show a confidence interval for the regret of Greedy algorithm and LinTS algorithm without any explanation.

We appreciate the reviewer’s feedback. We have adjusted the font size of the figures to improve the readability. The confidence intervals in Figure 3 show the $\pm$ 2*SE of the mean regret. We will add more explanation in the final version of the paper.

Questions:

A first suggestion is to include a proof of Corollary 1, if possible, in the main part of the paper.

We appreciate your feedback and have accordingly incorporated the proof.

A second suggestion is to include the pseudocode of the proposed methods TS-MR and Greedy-MR in the paper's main text.

We appreciate your feedback feedback and will include them in the final version of the paper.

Another suggestion concerns the experiments. The authors should provide enough material and explanations so that it is possible to replicate and verify the results of the simulations. We suggest the authors share the code they used to generate the simulations, as well as to include more details about the experiments in the Appendix: ...

Thank you for your valuable feedback.

• We have attached the code to the supplemental material to fully reproduce our simulation results and will add the pseudocode to the final version of the paper.
• We have included the references regarding converting classification tasks into bandit problems.
• For all simulations, we set $\lambda_{\text{reg}} = 1$, $\delta = 0.001$ and sample $\\eta_t \\sim \\mathcal{D}^{SA}(\\delta) = \\mathcal{N}(0, \\frac{1}{\\sqrt{2d \\log(2d/\\delta)}}I_d)$ such that $\\mathbb{P}_{\\eta \\sim \\mathcal{D}^{S A}(\\delta)}[\|\\eta\| \leq 1] \\geq 1-\\delta$. For TS-MR, we set $\iota_t = 1$ for all $t \in [T]$.
• We have conducted simulations in the revised manuscript ( Appendices I and J ) to illustrate the influence of $\mu$ and have provided suggestions on tuning it.
• We have fixed the typo on line 500.

The authors should also improve the readability of the Figures in the main body of the paper as the font size is too small. They should also provide explanations in Figures 3 (b) and (c) regarding what seems to be confidence intervals.

We appreciate your feedback and have adjusted the figures accordingly. We will add more explanations in the final version of the proof.

There are some notations throughout the paper that are either not defined or used before they were defined: ...

Thank you for your suggestions. We have fixed all the notation problems mentioned above in the revision.

Other suggestions include: ...

Thank you for your suggestions. We have modified all the typos mentioned.

We appreciate the reviewer for the constructive feedback. We respond to them separately below.

The author(s) may consider to place the comparison among Theorem 1 and results from existing papers in the main paper. The comparison is not clear at first glance.

Thank you for your suggestion. We will enhance the comparison related to Theorem 1 and include it in the main text of the final version of the paper.

Sections 6 and 7 indicate that a preset threshold $\mu$ can clearly reduce the regret and Remark 3 discusses the choice of $\mu$. However, I wonder under which types of real-life scenarios we can know $\mu$ and what is the choice of $\mu$ in simulations.

Thank you for your comment. For synthetic datasets, we set $\mu = 8$ in Example 1 for both TS-MR and Greedy-MR algorithms. In Examples 2 and 3, we set $\mu = 12$ for both algorithms. For all three real-world datasets, we used $\mu = 10$ for TS-MR and $\mu = 12$ for Greedy-MR. We have attached the code to the supplementary materials for reproducibility, and we will incorporate these simulation details into the main text in the final version of the paper for clarity.

Additionally, we have conducted simulations to address the concern regarding choosing $\mu$. Specifically, in Appendix I of the revised manuscript, we report the fraction of OFUL actions used throughout the entire time horizon for all simulations. In Appendix J of the revised manuscript, we illustrate the impact of $\mu$ on algorithm performance by varying its value and provide a detailed discussion of its tuning.

The new simulation results show that:

1. OFUL actions are primarily implemented in the early stages of the time horizon, with their fraction remaining low in subsequent stages. This indicates that proper exploration during the initial stage benefits the algorithms' long-term performance.
2. The course-corrected algorithm exhibits robust performance across different choices of $\mu$. Our simulations show that setting $\mu\in[8,12]$ performs well across all simulated scenarios.
3. In practice, we recommend setting $\mu$ to a moderate value, typically within the range $[8,12]$, as validated by our simulation results. The selection of $\mu$ should aim to ensure effective course-corrected exploration during the initial stage: A suitable $\mu$ value is indicated when the fraction of OFUL actions is high at the beginning and gradually decreases to and maintains a low level. If the fraction of OFUL actions remains consistently high, increasing $\mu$ can help reduce computational costs. Conversely, if very few OFUL actions are executed during the initial stage, decreasing $\mu$ helps with exploration. Finally, since algorithmic performance remains robust across moderate values of $\mu$, the precise selection of $\mu$ is unlikely to be a significant practical concern.

We hope our responses have addressed your concerns, and we would be happy to answer any further questions you may have.