Optimal and Practical Batched Linear Bandit Algorithm

Thank you for your time. However, with all due respect, we are very concerned by the current assessment. We sincerely hope to establish some common grounds with our response.

On Computational Cost

To our best knowledge, all prior works on batched linear bandits have not provided theoretical complexity analyses, as exact theoretical complexity analyses for comparisons are challenging due to various optimization subroutines in each algorithm.

For fair comparisons of computational cost, we provided empirical runtime experiments in Appendix E and conducted additional extensive evaluations (Table 2-4 in https://tinyurl.com/3m6f4v5n). Our experiments show that our method significantly improves computational efficiency compared to existing optimal algorithms.

Batch-wise vs. Fully Sequential

Obviously, even optimal batched algorithms will underperform fully sequential ones due to limited information in batched settings. Thus, direct comparison is inherently unfair, as the problem settings are fundamentally different.

Nevertheless, per your request, we conducted additional experiments comparing batched algorithms with the fully sequential LinUCB. Results (Figure 6 in https://tinyurl.com/3m6f4v5n) clearly show that the regret difference between BLAE and LinUCB is the smallest among existing batched algorithms, with competing batched methods exhibiting significantly larger performance gaps.

Regularization Parameters and Elimination Thresholds

The reviewer's comment is incorrect. The regularization parameter $\lambda_\ell$ is explicitly stated in Theorem 1 as $O(1)$ (set to $\lambda_\ell = 1$ in experiments). The elimination threshold $\varepsilon_\ell$ is explicitly stated in Theorem 1 and precisely defined in Lemma 2.

Real-world Datasets?

Regret evaluation in bandit literature typically relies on simulations since offline datasets may not contain feedback for all counterfactual actions that an algorithm can take. Thus, absence of real-world datasets is typically not considered a weakness, particularly for a theoretical work.

Nevertheless, we conducted extra experiments based on real-world dataset MovieLens. The results (Figure 7 in https://tinyurl.com/3m6f4v5n) confirm that BLAE consistently outperforms existing methods, validating its practical effectiveness.

Assume Batch-wise Independence?

No, our proof does not assume "batch-wise least squares estimation independence across batches," irrespective of regularization. Independence is achieved (rather than assumed) solely through our batch-wise design.

There appears to be a clear misunderstanding. This is serious because it may present challenges to the reviewer in evaluating our main results. We sincerely would like to ensure we are on the same page.

Elimination efficiency? We are unaware of any standard notion of "elimination efficiency." Could the reviewer rigorously define what is meant by this term?

Ablation? Altering batch size is unnecessary, as it is proven optimal batch complexity. Additional evaluations on varying regularization $\lambda_\ell$ are provided. (Figure 8 in https://tinyurl.com/3m6f4v5n).

Novelty

We strongly rebut "incremental contribution" comment. The use of G-optimal design or arm elimination in itself should not diminish novelty. By that standard, many impactful papers using optimal design would have been rejected.

To highlight a few of our contributions briefly: our refined analysis (Lemma 3) significantly improves exploration strategies beyond standard G-optimal design. We derived a new bound for this. Existing concentration inequalities in arm elimination inherently depend on $K$, making them suboptimal in large-$K$ scenarios. In contrast, our novel analytical framework utilizes efficient coverings of the unit sphere, providing sharper, more general regret bounds. Crucially, our proposed elimination strategy attains a unified optimal regret bound of $O(d\sqrt{T} \wedge \sqrt{dT\log K})$ using only $O(\log\log T)$ batches. Please refer to our paper for more contributions.

G-optimal Design

A key advantage of our algorithm is that we compute the G-optimal design only $O(\log\log T)$ times across $T$ rounds. Thus, given that computing optimal design requires at most $O(Kd^3)$, the average computational complexity due to G-optimal design in our algorithm is merely $O\left(\frac{K d^3 \log\log T}{T}\right)$, which tends to zero as $T$ increases. This highlights a crucial benefit of our batched update.

Suboptimal in Large-$K$ Cases There might be a misunderstanding. Existing methods being suboptimal in large $K$ case is not about "misidentification of the best arm" in large $K$. Rather, these methods always yield $K$-dependent regret, even for large $K$, but ours don't (see Table 1)

We hope our responses clarified the key points and respectfully ask that the evaluation reflect our contributions.

We appreciate your time and review. However, with all due respect, there appear to be some misunderstandings, which we sincerely hope to clarify in our response.

Batched Learning Setting

In the batched linear bandit setting, the learner chooses both the number of batches and when to update parameters. This is the standard setup in the literature (Esfandiari et al. (2021), Ruan et al. (2021), Hanna et al. (2023), Ren et al. (2024), Zhang et al. (2025)). This is the key aspect of the batched linear bandit problem because one wishes to design an algorithm that can update parameters as infrequently as possible while still achieving provably optimal regret.

Consistency of Parameter Choice in Theory and Experiments

We confirm that the choice of $\varepsilon_\ell$ is consistent across theory and experiments. Its order is defined in Theorem 1 and rigorously maintained throughout the paper, including experiments. The precise definition of $\varepsilon_\ell$ is given in Lemma 2, which depends on parameter $\varepsilon$ (distinct from $\varepsilon_\ell$). $\varepsilon$ is an arbitrary constant in (0,1) (chosen as 0.5 in all experiments which is theoretically valid). Our algorithm BLAE employs identical parameter choices in both theory and practice, ensuring optimality in both domains. There is no "difference in hyperparameters for theory & practice."

Experimental Results for Larger Dimension $d$

We conducted additional experiments with larger $d$ values. Results appear in Figure 4 of Sec. 5 in https://tinyurl.com/3m6f4v5n. These demonstrate that regret difference increases with $d$.

Runtime Comparison of the Main Algorithms

We conducted additional runtime experiments with larger arm counts $K$. Results in Table 2-4 of Sec. 3 in https://tinyurl.com/3m6f4v5n demonstrate that BLAE is the fastest among optimal algorithms, with runtime comparable to suboptimal algorithms even in very large-$K$ settings.

Lemma 1: Our Lemma 1 adaptation explicitly incorporates the regularization term to achieve our specific bound, which is crucial to our analysis. While sharing structural similarities with standard results, its subtle differences merit attention. We will include the relevant previous result related to Lemma 1 in the revision (e.g., Chapter 20 in Lattimore & Szepesvári (2020)).

Effect of Different Choices of Epsilon on Results

As mentioned, the elimination threshold $\varepsilon_\ell$ is defined based on parameter $\varepsilon$ (distinct from $\varepsilon_\ell$). In all experiments, we followed the theoretical guideline for $\varepsilon_\ell$ and $\varepsilon$.

Since theory allows $\varepsilon \in (0,1)$ to be chosen arbitrarily, we tested sensitivity to different $\varepsilon$ values. Results in Figure 5 in https://tinyurl.com/3m6f4v5n show BLAE remains robust across various $\varepsilon$ values. Note again that in all of our experiments the parameter choices satisfy the conditions of the theoretical results.

Clarification on Hyperparameter Selection for Other Algorithms

All experiments were conducted fairly. For $E^4$ (Ren et al., 2024), we used their exact public implementation. All baseline algorithms used theoretically suggested hyperparameter values from previous literature, while BLAE’s hyperparameters followed our theoretical results, ensuring fair and transparent comparisons.

Significance of Contributions

To understand our contributions, it's essential to recognize the limitations in existing batched linear bandit literature:

• Ren et al. (2024): Optimal regret only for small-$K$ regime, exhibit poor practical performance (see Figure 1 of our paper).
• Abbasi-Yadkori et al. (2011) and Esfandiari et al. (2021): Higher batch complexity, making them theoretically suboptimal.
• Ruan et al. (2021), Hanna et al. (2023), and Zhang et al. (2025): Impractical due to excessive runtimes (see Table 2 of our paper).

The key motivation for batched linear bandits is computational efficiency without sacrificing regret or batch complexity. In contrast to previous methods, BLAE is the first algorithm that simultaneously achieves provable optimality in both small-$K$ and large-$K$ regimes, while maintaining practical efficiency in both regret and batch complexity.
Therefore, our contribution addresses a critical gap in existing literature, aligning with the fundamental motivation of batched linear bandits.

Clarifying small-$K$ and large-$K$

It is NOT a matter of whether existing algorithms work or not. The existing algorithms "work" in both small-$K$ and large-$K$ regimes. But, their optimality was proven only in one of the regimes—never in both. In contrast, BLAE uniquely achieves optimality simultaneously in both regimes.

We hope our responses clarified the key points and respectfully ask that the evaluation reflect our contributions.

We sincerely thank you for reviewing our paper and providing valuable feedback. We appreciate your recognition of our work and your constructive comments. Below, we address each of your comments and questions in detail:

Performance in the Large $K$ Regime

We thank the reviewer for raising this important point. We conducted additional experiments with much larger $K$ values, with detailed results available in Table 2-4, and Figure 2 of Section 3 in link.

As shown in Table 2-4, BLAE is the fastest among optimal algorithms, with runtime comparable to that of suboptimal algorithms. Moreover, Figure 2 demonstrates that BLAE consistently achieves significantly lower regret and maintains stable performance even as $K$ becomes very large, confirming the scalability of our approach in large, finite action spaces.

Regarding infinite (continuous) action spaces, we clarify that our theoretical guarantees (and many others) and algorithmic design assume a finite action set. Thus, extending the current method to a continuous action domain is outside the scope of this paper.

To our knowledge, prior studies have not provided experimental evaluations for very large values of $K$ (e.g., $K = 1000, 2000, 5000$). Thus, we strongly believe that our extensive experiments sufficiently demonstrate that our algorithm offers superior performance and robustness, positioning it as the most effective solution for large-$K$ regimes. We would be more than happy to perform further experiments if needed.

Experimental Performance of $E^4$

We thank the reviewer for noting the discrepancy in $E^4$'s results. While Ren et al. (2024) theoretically established a sub-linear regret bound, our experiments exhibited (near-)linear regret behavior.
We emphasize that we used the exact implementation officially provided by Ren et al. (2024).
We identified two primary reasons for this empirical performance discrepancy:

First, $E^4$ occasionally eliminates the optimal arm prematurely. Table 1 of Section 2 in link shows how frequently false elimination of the optimal arm occurs over 20 independent experimental runs.

Second, the batch size in $E^4$ is highly sensitive to hyperparameter $\gamma$. In particular, the third batch size scales as $O((\log T)^{1+\gamma})$. When choosing a relatively large value of $\gamma$ (e.g., $\gamma = 10$, as in the Ren et al. (2024) setup), the third batch size often exhausts the entire horizon, leaving practically no time to effectively exploit information learned in the third batch.
Consequently, the algorithm relies only on information from the first two, relatively short batches. If suboptimal arm identification occurs during these early batches (as frequently observed), this leads directly to linear regret. In contrast, BLAE's $\ell$-th batch size has order $O\left(T^{\frac{2^{\ell}-1}{2^{\ell}}}\right)$, avoiding this issue.

We conducted additional experiments by carefully tuning the hyperparameter $\gamma$ for $E^4$ from 10 down to 0.99, to their advantage. The results of these additional experiments, presented in Figure 3 of Section 4 in link, confirm that careful tuning of $\gamma$ leads to sub-linear regret behavior. However, we also observe that reducing $\gamma$ for the sake of regret performance significantly increases the number of batches.
Hence, there is a clear tradeoff with regard to the control of $\gamma$ in $E^4$.

Moreover, even after the tuning of $\gamma$ in $E^4$ for the sake of regret performance, the performance of $E^4$ still results in noticeably worse regret performance compared to BLAE (Figure 3 in link). Thus, the tuning leads to increased batch complexity although the regret performance increases. Despite careful tuning for $E^4$, overall numerical performances in both regret and batch complexity of $E^4$ still show clearly inferior practical performance compared to BLAE.

Computational Complexity Analysis and Scalability

We thank the reviewer for this insightful question. To the best of our knowledge, all prior works on batched linear bandits have not provided theoretical complexity analyses, as exact theoretical complexity analyses for comparisons are challenging due to various optimization subroutines in each algorithm. Therefore, any derived theoretical complexity bounds would likely be overly crude and may not be suitable for comparisons for their true computational performance in practice.

To evaluate computational cost, we provided empirical runtime experiments in Appendix E and conducted additional extensive evaluations (see Table 2-4 of Section 3 in link).

Our empirical results address scalability when $K$ is very large. Even at large $K$, our experiments show that our method significantly improves computational efficiency compared to existing optimal algorithms.

We sincerely thank you for taking the time to review our paper and for providing thoughtful and valuable feedback. We greatly appreciate your recognition of our work and your constructive comments. Below, we address each of your comments and questions in detail:

Experimental Results in the Small-$K$ Regime

We thank the reviewer for this suggestion. We conducted experiments in the small-$K$ regime with $K = 2, 4, 8, 16$, and the detailed results are in Figure 1 of Section 1 in this link.

As shown in Figure 1, BLAE consistently outperforms existing methods in the small‑$K$ setting. While $E^4$ (Ren et al., 2024) performs competitively for $K=2$, this trivial case is straightforward for any algorithm. Therefore, apart from this trivial case, our results confirm that BLAE remains superior across all small-$K$ regimes considered.

False Elimination of Optimal Arms in $E^4$ (Ren et al., 2024) as a Function of $K$

We appreciate the reviewer’s insightful question. To investigate whether the frequency of mistakenly eliminating the optimal arm in $E^4$ (Ren et al., 2024) increases with $K$, we conducted experiments across a range of $K$ values—from small to large regimes. Each experiment was repeated 20 times, and we tracked the rate at which the optimal arm was falsely eliminated. Detailed results can be found in Table 1 of Section 2 in this link.

The data in Table 1 clearly indicate an increasing trend in the elimination rate as $K$ grows. This trend helps explain why $E^4$ (Ren et al., 2024) performs worse than other batched linear bandit algorithms, particularly in large-$K$ regimes.

Potential Applications of Refined Analysis in Other Settings

We appreciate the reviewer raising this valuable point. Our refined analysis indeed applies naturally to broader settings, including the pure exploration scenario. In pure exploration, the primary goal is to accurately identify optimal arms within a given budget, without explicitly focusing on cumulative regret. Our approach, which combines a regularized G-optimal design with an arm elimination strategy, efficiently discards suboptimal arms with high probability, significantly improving the accuracy and efficiency of exploration.

Furthermore, since best arm identification is a widely-studied and applied setting—where exactly one optimal arm must be correctly identified—our refined analytical methods directly apply here as well. Specifically, our algorithm’s ability to consistently maintain the optimal arm with high probability demonstrates its practical utility for reliable best-arm selection.

Thus, our theoretical refinements meaningfully contribute both to general pure exploration and specifically to the best arm identification problem.