Improved Regret of Linear Ensemble Sampling

Our contributions

Dear Reviewer vWv8 We again thank you for recognizing the value of work. To put our contributions in perspective, let's compare the face value of our results with those in the relevant literature: | Paper | Regret Bound | Ensemble Size | Publication | |--------------------- |----------------------------------------------- |--------------- |------------------------------------------ | | Lu and Van Roy [15] | Invalid | Invalid | *NeurIPS 2017* | | Phan et al. [A] | Invalid (Lemma 13) | Invalid | *NeurIPS 2019* | | Qin et al. [20] | $O(\sqrt{dT\log{K}})$ **Bayesian** regret | $O(KT)$ | *NeurIPS 2022* | | Janz et al. [8] | $O(d^{5/2}\sqrt{T})$ **Frequentist** regret | $O(d\log{T})$ | - | | **Our work** | $O(d^{3/2}\sqrt{T})$ **Frequentist** regret | $O(K\log{T})$ | Currently under review at *NeurIPS 2024* | ##### (Phan et al. [A] contains an extended result on ensemble sampling in their appendix using the results from Lu and Van Roy [15], but since the latter is incorrect, so is the former). Even when considering just the face value of the results presented in each paper, overlooking our work would discourage further progress in the field of ensemble sampling. ### Key Points: - **Prior to our work, none of the previous studies in ensemble sampling (Lu and Van Roy [15], Phan et al. [A], Qin et al. [20], or Janz et al. [8]) had achieved the $O(d^{3/2}\sqrt{T})$ frequentist regret bound with sublinear $T$ dependence on ensemble size.** - **Simply plugging in an ensemble size of $O(K \log T)$ into previous results (e.g., instead of $O(d \log T)$ as in Janz et al. [8]) does not trivially achieve the $O(d^{3/2}\sqrt{T})$ frequentist regret bound. In fact, regardless of how the ensemble size is chosen (whether $O(d \log T)$, $O(K \log T)$ or even $O(KT)$) and what algorithmic tweaks are applied (such as symmetrization in Janz et al. [8]), our $O(d^{3/2}\sqrt{T})$ bound remains the sharpest frequentist regret bound.** - **This is the key contribution of our work: No prior analysis in ensemble sampling had successfully achieved the $O(d^{3/2}\sqrt{T})$ frequentist regret bound (with sublinear ensemble size in $T$). We presented and proved a novel method to reach this bound for the first time.** Even at face value, our results clearly stand out compared to the existing literature. We sincerely and kindly ask you to reconsider these points when evaluating our submission. Beyond the face value of our primary results, which we believe are already significant, we also introduce a general regret analysis framework (Theorem 2) for linear bandit algorithms. This framework not only generalizes the regret analysis for randomized algorithms like ensemble sampling but also applies to other optimism-based deterministic algorithms. This could be of significant interest beyond ensemble sampling, which we would like to bring your attention to. Considering the significant value of these contributions, we strongly believe in the value of our work and the potential impact for the future research. Thank you for your support. If you have any questions, please let us know. Sincerely, Authors --- **Reference:** - #### Phan et al. [A]: Phan, M., Abbasi Yadkori, Y., & Domke, J. (2019). Thompson sampling and approximate inference. Advances in Neural Information Processing Systems, 32.

Our contributions

Dear Reviewer TPGY, To put our contributions in perspective, let's compare the face value of our results with those in the relevant literature: | Paper | Regret Bound | Ensemble Size | Publication | |--------------------- |----------------------------------------------- |--------------- |------------------------------------------ | | Lu and Van Roy [15] | Invalid | Invalid | *NeurIPS 2017* | | Phan et al. [A] | Invalid (Lemma 13) | Invalid | *NeurIPS 2019* | | Qin et al. [20] | $O(\sqrt{dT\log{K}})$ **Bayesian** regret | $O(KT)$ | *NeurIPS 2022* | | Janz et al. [8] | $O(d^{5/2}\sqrt{T})$ **Frequentist** regret | $O(d\log{T})$ | - | | **Our work** | $O(d^{3/2}\sqrt{T})$ **Frequentist** regret | $O(K\log{T})$ | Currently under review at *NeurIPS 2024* | ##### (Phan et al. [A] contains an extended result on ensemble sampling in their appendix using the results from Lu and Van Roy [15], but since the latter is incorrect, so is the former). Even when considering just the face value of the results presented in each paper, overlooking our work would discourage further progress in the field of ensemble sampling. ### Key Points: - **Prior to our work, none of the previous studies in ensemble sampling (Lu and Van Roy [15], Phan et al. [A], Qin et al. [20], or Janz et al. [8]) had achieved the $O(d^{3/2}\sqrt{T})$ frequentist regret bound with sublinear $T$ dependence on ensemble size.** - **Simply plugging in an ensemble size of $O(K \log T)$ into previous results (e.g., instead of $O(d \log T)$ as in Janz et al. [8]) does not trivially achieve the $O(d^{3/2}\sqrt{T})$ frequentist regret bound. In fact, regardless of how the ensemble size is chosen (whether $O(d \log T)$, $O(K \log T)$ or even $O(KT)$) and what algorithmic tweaks are applied (such as symmetrization in Janz et al. [8]), our $O(d^{3/2}\sqrt{T})$ bound remains the sharpest frequentist regret bound.** - **This is the key contribution of our work: No prior analysis in ensemble sampling had successfully achieved the $O(d^{3/2}\sqrt{T})$ frequentist regret bound (with sublinear ensemble size in $T$). We presented and proved a novel method to reach this bound for the first time.** Even at face value, our results clearly stand out compared to the existing literature. We sincerely and kindly ask you to reconsider these points when evaluating our submission. Beyond the face value of our primary results, which we believe are already significant, we also introduce a general regret analysis framework (Theorem 2) for linear bandit algorithms. This framework not only generalizes the regret analysis for randomized algorithms like ensemble sampling but also applies to other optimism-based deterministic algorithms. This could be of significant interest beyond ensemble sampling, although it seems to have been overlooked in the reviews. Considering the significant value of these contributions, we strongly believe our work deserves more recognition than just a "Borderline accept." We are eager to clarify any points further. Please feel free to reach out with any questions. Sincerely, Authors --- **Reference:** - #### Phan et al. [A]: Phan, M., Abbasi Yadkori, Y., & Domke, J. (2019). Thompson sampling and approximate inference. Advances in Neural Information Processing Systems, 32.

Our contributions

Dear Reviewer QJqu, To put our contributions in perspective, let's compare the face value of our results with those in the relevant literature: | Paper | Regret Bound | Ensemble Size | Publication | |--------------------- |----------------------------------------------- |--------------- |------------------------------------------ | | Lu and Van Roy [15] | Invalid | Invalid | *NeurIPS 2017* | | Phan et al. [A] | Invalid (Lemma 13) | Invalid | *NeurIPS 2019* | | Qin et al. [20] | $O(\sqrt{dT\log{K}})$ **Bayesian** regret | $O(KT)$ | *NeurIPS 2022* | | Janz et al. [8] | $O(d^{5/2}\sqrt{T})$ **Frequentist** regret | $O(d\log{T})$ | - | | **Our work** | $O(d^{3/2}\sqrt{T})$ **Frequentist** regret | $O(K\log{T})$ | Currently under review at *NeurIPS 2024* | ##### (Phan et al. [A] contains an extended result on ensemble sampling in their appendix using the results from Lu and Van Roy [15], but since the latter is incorrect, so is the former). Even when considering just the face value of the results presented in each paper, overlooking our work would discourage further progress in the field of ensemble sampling. ### Key Points: - **Prior to our work, none of the previous studies in ensemble sampling (Lu and Van Roy [15], Phan et al. [A], Qin et al. [20], or Janz et al. [8]) had achieved the $O(d^{3/2}\sqrt{T})$ frequentist regret bound with sublinear $T$ dependence on ensemble size.** - **Simply plugging in an ensemble size of $O(K \log T)$ into previous results (e.g., instead of $O(d \log T)$ as in Janz et al. [8]) does not trivially achieve the $O(d^{3/2}\sqrt{T})$ frequentist regret bound. In fact, regardless of how the ensemble size is chosen (whether $O(d \log T)$, $O(K \log T)$ or even $O(KT)$) and what algorithmic tweaks are applied (such as symmetrization in Janz et al. [8]), our $O(d^{3/2}\sqrt{T})$ bound remains the sharpest frequentist regret bound.** - **This is the key contribution of our work: No prior analysis in ensemble sampling had successfully achieved the $O(d^{3/2}\sqrt{T})$ frequentist regret bound (with sublinear ensemble size in $T$). We presented and proved a novel method to reach this bound for the first time.** Even at face value, our results clearly stand out compared to the existing literature. We sincerely and kindly ask you to reconsider these points when evaluating our submission. Beyond the face value of our primary results, which we believe are already significant, we also introduce a general regret analysis framework (Theorem 2) for linear bandit algorithms. This framework not only generalizes the regret analysis for randomized algorithms like ensemble sampling but also applies to other optimism-based deterministic algorithms. This could be of significant interest beyond ensemble sampling, although it seems to have been overlooked in the reviews. Considering the significant value of these contributions, we strongly believe our work deserves more recognition than just a "Borderline accept." We are eager to clarify any points further. Please feel free to reach out with any questions. Sincerely, Authors --- **Reference:** - #### Phan et al. [A]: Phan, M., Abbasi Yadkori, Y., & Domke, J. (2019). Thompson sampling and approximate inference. Advances in Neural Information Processing Systems, 32.

Borderline Accept -> accept

Thank you for your nice rebuttal. The authors have sufficiently emphasized the significance of their work and addressed my mathematical concern on Corollary 1. Given the line of (precedent) theoretical works on ensemble sampling, and the technical contributions of this paper, I have raised my score to 7. - By the way, I kindly encourage the authors to delete the last column of the penultimate line of the markdown table in their rebuttal text in that "pointing out that certain cited paper, i.e., xxx et al. has been submitted to XXX 2024" does not quite conform to the double-blind principle.

Concerns on the misleading arguments

Dear Authors, Thank you for your detailed rebuttal. While I appreciate your efforts to clarify your contributions, I still have concerns about some of the claims and comparisons made in your response. 1. **Comparison with Previous Ensemble Sampling (ES) Analysis:** Your justification for the dependency on $K$ and $d$ is not sufficiently rigorous. A proper comparison of complexity bounds must consider all dominant factors across different regimes. It's only valid to claim superiority in specific regimes of these factors. For instance, consider the following scenarios: a) For $d = 2$ and $K = 8$ (omitting constants and logarithmic terms): - Your analysis: ES with ensemble size 8 achieves a regret bound of $2^{3/2}\sqrt{T}$. - ES [Janz et al., 2023]: ES with ensemble size 2 achieves a regret bound of $2^{5/2}\sqrt{T}$. b) For $d = 2$ and $K = 10000$: - Your analysis: ES with ensemble size 10000 achieves a regret bound of $2^{3/2}\sqrt{T}$. - ES [Janz et al., 2023]: ES with ensemble size 2 achieves a regret bound of $2^{5/2}\sqrt{T}$. These comparisons highlight that **it's misleading to claim your analysis leads to improved results compared to ES [Janz et al., 2023].** The improvement appears to be regime-dependent, and this nuance should be clearly stated. 2. **Ensemble Size Scaling:** regard the usefulness of the analysis The implication that the ensemble size needs to **scale linearly with $K$ is counter-intuitive** and potentially makes the ES algorithm impractical for large action spaces. This requirement significantly limits the usefulness of ES in real-world scenarios with large $K$. **Empirical evidence of how the ensemble size scales with $K$ in practice would be valuable to support your theoretical claims and demonstrate real-world applicability.** From Author rebuttal pdf, it looks like the empirical scaling of $K$ is with a substantially lower order of $O(K)$. As from this empirical evidence, we might not say the analysis in this work -- leading to $\tilde{O}(K)$ scaling -- justifies the usefulness of ES. **And more importantly, it is misleading to claim that theory-practice gap is closed.** 3. **Comparison with Exact TS:** To claim that your regret order matches exact TS, your analysis should match or improve upon the existing analysis of exact TS across all regimes. A more comprehensive result would be of the form with the same ensemble size configuration: $$\min(\tilde{\mathcal{O}}(d^{3/2}\sqrt{T}), \tilde{\mathcal{O}}(d\sqrt{T \log K}))$$ This would demonstrate matching performance across different regimes of $d$ and $K$. **Without such a result, the claim of matching exact TS performance is overstated and misleading.** 4. **Practical Implications and Theory-Practice Gap:** While you mention practical applications of ES variants in online recommendation and deep reinforcement learning, your current analysis doesn't directly address how these theoretical improvements translate to practical benefits in these complex settings. To substantiate your claim of closing the theory-practice gap, it would be beneficial to provide: a) Empirical results demonstrating the practical advantages of your approach over existing analysis. Does your analysis provides more accurate characterization of practical performance? b) A clear explanation of how your theoretical improvements address specific challenges in real-world applications. In conclusion, while your work provides interesting insights into ES, the claims of matching exact TS performance and improving upon previous ES analyses need more nuanced and regime-specific statements. I encourage you to: 1. Refine your comparisons to accurately reflect the specific conditions under which your results hold and improve upon existing work, for both computation and regret considerations. 2. Provide matching results between empirical evidence and theoretical claims, especially regarding the scaling of ensemble size with $K$ in the future revision if you want to claim closing theory-practice gap. 3. Clarify how your work concretely **addresses the theory-practice gap** in ensemble sampling applications. These additions would significantly strengthen your paper and provide a more comprehensive understanding of your contributions to the field. Sincerely, Reviewer QBvS

Fundamental Disagreements with and Concerns about Reviewer QBvS's comments (1/3)

Dear Reviewer QBvS, We appreciate your very quick (in about 2 hours) and enthusiastically prepared responses to our rebuttal. We are grateful for the opportunity to discuss our work with you. We sincerely hope we can communicate with rationality and reason, without unnecessarily hurting others. We respectfully urge you to reconsider your evaluation of our work. **Before accusing us of misleading or mischaracterizing our research, we sincerely ask that you reflect on whether you might be unintentionally (or intentionally, which would be a serious ethical issue) misinterpreting or misrepresenting our hard and proud work**. With all due respect, we fundamentally disagree with your comments on almost every point. However, we understand that there can be disagreements, and we sincerely hope you also understand this. Our goal is to find some common ground through constructive dialogue. First, let us clarify some fundamental points. We have a few simple yet crucial questions: - ### **Q1: Prior to our work, do you agree that none of the previous works in ensemble sampling (Lu and Van Roy [15], Qin et al. [20], or Janz et al. [8]) had achieved $O(d^{3/2}\sqrt{T})$ frequentist regret with sublinear $T$ dependence on ensemble size?** - The answer to **Q1** should be **Yes**. When we began this research, our goal was to prove that ensemble sampling could achieve $O(d^{3/2}\sqrt{T})$ with sublinear dependence on $T$. Achieving this rate has long been considered an open problem. We achieved this goal with a new way of treating ensembles and a novel analysis technique, resulting in the tightest known frequentist regret bound for ensemble sampling. - ### **Q2: Do you agree that by simply plugging in an ensemble size of $O(K \log T)$ (instead of $O(d \log T)$ as in Janz et al. [8]), the previous analysis does not trivially achieve $O(d^{3/2}\sqrt{T})$ regret?** - The answer to **Q2** should be **Yes**. Since the previous analysis does not allow for a tighter regret, we devised novel techniques to derive a new and improved bound. - ### **Q3: Setting aside how ensemble size is chosen (whether $O(d \log T)$ or $O(K \log T)$) and what algorithmic tweaks are applied, do you agree that $O(d^{3/2}\sqrt{T})$ regret is an improved and currently the sharpest regret in terms of $d$ and $T$ (with no dependence on $K$)?** - The answer to **Q3** should be **Yes**. ### All three questions (Q1-Q3) above are not rhetorical. They are simple binary questions. If your answers to all three questions are "Yes," we can further discuss our paper. Otherwise, we would be very concerned that we may not be on the same page at a fundamental level. This is the **key point of our contribution: prior to our work, no previous works in ensemble sampling had provided a successful analysis to achieve $O(d^{3/2}\sqrt{T})$ regret. We presented and proved a new way of doing it**. We feel that there is mischaracterization in your comments in "1. Comparison with Previous Ensemble Sampling (ES) Analysis." We have been very clear about the bound on the ensemble size. Using your logic, one could argue the opposite by comparing different values of $d$ and $K$. However, such comparison is NOT our main point. Our main goal is simple yet fundamental: **whether one can get $O(d^{3/2}\sqrt{T})$ regret with sublinear (even logarithmic) dependence on $T$ in ensemble size**. This had been an open question, and **we aimed to close this well-defined gap!** You are imposing your own definition or agenda of a "gap" -- which is not well-defined nor do we have any reason to commit to -- onto our goal. If your intention is not adversarial, please refrain from doing so. ### **FACT:** Our analysis of ensemble sampling with $O(K \log T)$ ensemble size achieves $O(d^{3/2}\sqrt{T})$ frequentist regret for the first time. Previous approaches, with any choice of ensemble size, did not achieve this. That is a fact. Our resulting $O(d^{3/2}\sqrt{T})$ regret is smaller than $O(d^{5/2}\sqrt{T})$. If that is not an improved regret, then what else is it? Can Janz et al. [8] achieve $O(d^{3/2}\sqrt{T})$ regret with any modification to their analysis and algorithm? No! We do not understand your motivation of earnestly defending the result of Janz et al. [8] and adversarially discrediting our contribution by distorting the facts. --- ## **On Ensemble Size** We respectfully disagree with your argument here. Even your comment that "The implication that the ensemble size needs to scale linearly is counter-intuitive" is simply false. There is NO implication that the ensemble size “needs to scale linearly” because the ensemble size condition is a **sufficient condition**, not a **necessary condition**. We are sure you as an expert understand the difference. What you are asking for is for us to show that what is only proven to be sufficient is somehow empirically manifested as necessary. Your assertion is problematic and what you request of us as empirical evidence is unreasonable.

Concerns about Reviewer QBvS's comments (Continued 2/3)

## **On Matching Regret of LinTS** Another very concerning assertion is forced by Reviewer QBvS, which we truly believe that requires the wisdom of the community. Reviewer QBvS argues that in order to claim that our result matches the regret bound of LinTS [2, 3] we need to match both $min( \tilde{O}(d^{3/2}\sqrt{T}), \tilde{O}(d\sqrt{T \log K}) )$ "across different regimes of $d$ and $K$" and states without it, the claim is “overstated and misleading.” Who sets such a rule? (By the way, what is “exact TS” that the reviewer keeps referring to anyway? We never used it in our manuscript. We only want to match with the regret of LinTS, particularly $\tilde{O}(d^{3/2}\sqrt{T})$ that was the goal to start with.) **Such an assertion is contrary to what is practiced in the literature. As many of us know, it is conventionally accepted that if you match one of the terms (not both), it is said that you have the same order and matching bound as LinTS.** Let us show some examples in the literature: - “this bound is of order $\tilde{O}(d^{3/2}\sqrt{T})$ and it **entirely matches** the result of Agrawal and Goyal [2012b].” Abeille, M., & Lazaric, A. (2017,). Linear thompson sampling revisited. In International Conference on Artificial Intelligence and Statistics (pp. 176-184). PMLR. => **Not** $min( \tilde{O}(d^{3/2}\sqrt{T}), \tilde{O}(d\sqrt{T \log K})$, but **only** $\tilde{O}(d^{3/2}\sqrt{T})$ - “[regret] of GP-TS is $\tilde{O}(d^{3/2}\sqrt{T})$, which **recovers** the regret bounds of their linear, parametric analogues … Linear Thompson sampling (Agrawal and Goyal, 2013)” Chowdhury, S. R., & Gopalan, A. (2017). On kernelized multi-armed bandits. In International Conference on Machine Learning (pp. 844-853). PMLR. => **Not** $min( \tilde{O}(d^{3/2}\sqrt{T}), \tilde{O}(d\sqrt{T \log K})$, but **only** $\tilde{O}(d^{3/2}\sqrt{T})$ - “Theorem 2 establishes $\tilde{O}(d^{3/2}\sqrt{T})$ worst-case regret, which **matches** the regret bounds of TS methods for linear contextual bandits [Agrawal and Goyal 2013, Abeille et al. 2017] up to logarithmic factor.” Oh, M. H., & Iyengar, G. (2019). Thompson sampling for multinomial logit contextual bandits. Advances in Neural Information Processing Systems, 32. => **Not** $min( \tilde{O}(d^{3/2}\sqrt{T}), \tilde{O}(d\sqrt{T \log K})$, but **only** $\tilde{O}(d^{3/2}\sqrt{T})$ - “We note that the regret of Term I ( $\tilde{O}(d^{3/2}\sqrt{T})$) has the **same bound** as that of Abeille et al. (2017)” Moradipari, A., Thrampoulidis, C., & Alizadeh, M. (2020). Stage-wise conservative linear bandits. Advances in neural information processing systems, 33, 11191-11201. => **Not** $min( \tilde{O}(d^{3/2}\sqrt{T}), \tilde{O}(d\sqrt{T \log K})$, but **only** $\tilde{O}(d^{3/2}\sqrt{T})$ - “Agrawal and Goyal [2013b] also extended the analysis of multi-armed Thompson Sampling to the linear contextual setting and proved a regret bound of $\tilde{O}(d^{3/2}\sqrt{T})$ where d is the dimension of the context vectors. In this paper, we develop the first variants of Batch Thompson Sampling that **achieve the aforementioned regret bounds**.” Karbasi, A., Mirrokni, V., & Shadravan, M. (2021). Parallelizing thompson sampling. Advances in Neural Information Processing Systems, 34, 10535-10548. => **Not** $min( \tilde{O}(d^{3/2}\sqrt{T}), \tilde{O}(d\sqrt{T \log K})$, but **only** $\tilde{O}(d^{3/2}\sqrt{T})$ - “Theorem 3.5 implies the regret of NeuralTS is on the order of $\tilde{O}(\tilde{d}\sqrt{T})$ (here there is additional $\log K$ factor hidden in $\tilde{O}$, hence it is $\tilde{O}(d\sqrt{T \log K})$),. This result **matches** the state-of-the-art regret bound in Chowdhury & Gopalan (2017); Agrawal & Goyal (2013); Zhou et al. (2019); Kveton et al. (2020).” Zhang, W., Zhou, D., Li, L., & Gu, Q. (2021). Neural thompson sampling. ICLR 2021. => **Not** $min( \tilde{O}(d^{3/2}\sqrt{T}), \tilde{O}(d\sqrt{T \log K})$, but **only** $\tilde{O}(d\sqrt{T \log K})$ - “The regret upper bound is also stipulated to be of the order $\tilde{O}(d^{3/2}(1+\sqrt{\sum_{t=1}^T \sigma_t^2}))$, considering $R$ as a constant. Notably, in scenarios where the variance is constant, our LinNATS algorithm recovers the regret guarantee of $\tilde{O}(d^{3/2}\sqrt{T})$ for for linear TS (Agrawal and Goyal, 2013; Abeille and Lazaric, 2017)” Xu, R., Min, Y., & Wang, T. (2023). Noise-adaptive thompson sampling for linear contextual bandits. Advances in Neural Information Processing Systems, 36. => **Not** $min( \tilde{O}(d^{3/2}\sqrt{T}), \tilde{O}(d\sqrt{T \log K})$, but **only** $\tilde{O}(d^{3/2}\sqrt{T})$

Concerns about Reviewer QBvS's comments (Continued 3/3)

- “we present the following corollary in linear bandits, whose main regret $\tilde{O}(d^{3/2}\sqrt{T})$ is **optimal for PS (posterior sampling) algorithms**.” Kuang, N. L., Yin, M., Wang, M., Wang, Y. X., & Ma, Y. (2023). Posterior sampling with delayed feedback for reinforcement learning with linear function approximation. Advances in Neural Information Processing Systems, 36, 6782-6824. => **Not** $min( \tilde{O}(d^{3/2}\sqrt{T}), \tilde{O}(d\sqrt{T \log K})$, but **only** $\tilde{O}(d^{3/2}\sqrt{T})$ - “We propose data-dependent perturbations … that allow EVILL to **match** the performance of Thompson-sampling-style parameter-perturbation methods.” “the regret of EVILL enjoys guarantees that **parallel** those available for Thompson sampling.” In the paper, their regret bound is $\tilde{O}(d^{3/2}\sqrt{T})” Janz, D., Liu, S., Ayoub, A., & Szepesvári, C. (2024). Exploration via linearly perturbed loss minimisation. In International Conference on Artificial Intelligence and Statistics (pp. 721-729). PMLR. => **Not** $min( \tilde{O}(d^{3/2}\sqrt{T}), \tilde{O}(d\sqrt{T \log K})$, but **only** $\tilde{O}(d^{3/2}\sqrt{T})$ The list goes on. Note that all of the papers above are NeurIPS, AISTATS, ICLR publications or equivalent. As you can see, to claim the regret matches the regret bound of LinTS, only one of them mostly $\tilde{O}(d^{3/2}\sqrt{T})$ is considered sufficient to claim to match the regret of LinTS. Against all these conventions, **Reviewer QBvS’s refusal to admit such a convention is not only harsh but also appears to be a deliberate devaluation of our work. Many bandit researchers would agree with this standard, which makes this stance particularly concerning**. In fact, $\tilde{O}(d^{3/2}\sqrt{T})$ regret bound serves as a gold standard for TS-based and randomized exploration algorithms that even Janz et al. [8] says the following: “the regret scales with $d^{5/2}\sqrt{T}$ up to logarithmic-in-T factors. The latter scaling is slightly worse than that obtained for Thompson sampling (cf. Theorem 17), where the regret scales with $d^{3/2}\sqrt{T}$, again, up to logarithmic-in-T factors.” Janz, D., Litvak, A. E., & Szepesvári, C. (2023). Ensemble sampling for linear bandits: small ensembles suffice. arXiv preprint arXiv:2311.08376. If $\tilde{O}(d^{3/2}\sqrt{T})$ is not a gold standard, why not compare with even tighter bounds such as minimax optimal regret for linear bandit $\tilde{O}(d\sqrt{T})$ in Janz et al. [8]? Reviewer QBvS’s logic and request are more than just demanding, becoming unnecessarily adversarial. Based on convention, we strongly believe that our result deserves credit. It is unreasonable to spend energy arguing about this widely accepted consensus. If the reviewer does not admit it, then they can take the face value: our result achieves $\tilde{O}(d^{3/2}\sqrt{T})$ for the first time for ensemble sampling. That is a fact. We sincerely hope that the reviewer and we can come to some common ground (we really do), although such hope is diminishing.

Analysis of Ensemble Sampling: Balancing Computation and Regret

## **Motivation for Studying Ensemble Sampling** In the context of this discussion in linear function approximation, "exact Thompson Sampling" (TS) refers specifically to Linear Thompson Sampling (LinTS). Ensemble Sampling (ES) has emerged as a method to approximate TS, aiming to scale up exploration in complex environments where no conjugacy can be utilized by exact TS. The ultimate goal of scalable exploration is twofold: achieving bounded per-step computation complexity and sublinear regret in complex environment. While there is already extensive research on linear contextual bandits, including comprehensive analyses of TS in both Bayesian and Frequentist settings, I acknowledge that it is valuable to study the theoretical aspects of ES with linear function approximation. It's worth noting that linear Thompson sampling already offers bounded per-step computation and near-optimal regret. ## **Current Status of ES Theory and Paths for Advancement** Given the motivation behind ES and existing analyses, to further advance the community's understanding and potentially design better algorithms, we should consider: 1. **Regret Analysis**: Continue to refine either Bayesian or Frequentist regret bounds for ES. 2. **Ensemble Size Optimization**: Investigate how the choice of ensemble size affects both computational complexity and regret bounds. This aspect is crucial for practical implementations and should not be overlooked in theoretical analyses. 3. **Comparative Studies**: Conduct rigorous comparisons between ES and other methods (e.g., LinTS) across various regimes of problem parameters (such as dimension $d$ and number of arms $K$). 4. **Computational Complexity**: Analyze the per-step computation time of ES in relation to problem parameters and ensemble size. 5. **Empirical Validation**: Provide empirical evidence to support theoretical claims, especially regarding the scaling of ensemble size with problem parameters. 6. **Practical Implications**: Clearly articulate how theoretical improvements in ES translate to benefits in real-world applications, particularly in complex environments where exact TS is computationally infeasible. By addressing these aspects comprehensively, future research can provide a more holistic understanding of ES, potentially leading to algorithmic improvements that balance theoretical guarantees with practical applicability. **These relevant points emphasize again the previous concern on Ensemble Size Scaling**

Problem-dependent Nature of Thompson Sampling

# Problem-dependent Nature of Thompson Sampling Thompson Sampling (TS) has gained popularity in the bandit community and beyond due to its simplicity and inherent ability to adapt to various problem setups. This adaptability is evident in both Bayesian and Frequentist analyses of TS. ## Bayesian Perspective ### Information Ratio and Adaptive Bounds [Russo and Van Roy, 2016] introduced the concept of the information ratio, which demonstrates that **without modifying the TS policy specifically for each problem setups**, the information ratio automatically adapts to different problem setups. This led to a class of problem-dependent bounds for TS in their work and inspired many follow-up studies, including tight bound in finite $K$-arm setting, infinite arm setting and even changing action set setting. A notable extension of this approach is found in [Neu et al., 2022], which further develops the information-theoretic analysis of TS for contextual bandits in many problem setups. **Key Reference:** - Russo and Van Roy, 2016. Information Theoretic Analysis of Thompson Sampling - Neu, G., et al. (2022). Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits. - Hamidi, N., & Bayati, M. (2023). The elliptical potential lemma for general distributions with an application to linear thompson sampling. Operations Research, 71(4), 1434-1439. ## Frequentist Perspective ### Linear Thompson Sampling (LinTS) Analysis [Agrawal & Goyal, 2013] established a pioneering work in the analysis of frequentist regret for LinTS. Their comprehensive study covers both finite arm settings and infinite arm settings (compact action set). The elegance of their analysis lies in its problem-dependent nature, featuring a term $\min(\sqrt{d}, \sqrt{\log K})$ throughout the proof. This leads to their Theorem 1, which provides adaptive bounds **without modifying the LinTS algorithm specifically for each problem setups**. **Key Reference:** - Agrawal, S., & Goyal, N. (2013, May). Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning (pp. 127-135). PMLR. ## Implications The problem-dependent nature of TS, as demonstrated in both Bayesian and Frequentist analyses, underscores its versatility and efficiency across various bandit problems. This adaptability contributes significantly to TS's popularity and effectiveness in real-world applications. **These facts emphasize my previous concern on the claim on matching regret performance of TS.**

Seriously Misleading. Qin et al., 2023 studies Bayesian regret while our results are all in frequentist regret.

Dear Reviewer QBvS, There is another serious issue in your argument (https://openreview.net/forum?id=6SSzMq3WTn&noteId=TYYoKwGxDU). You are quoting **Qin et al., 2023's Bayesian regret bound to argue that it is sharper than our frequentist regret bound**. **This is highly concerning**, as Bayesian regret and frequentist regret are two distinct measures and are not directly comparable. **This is just simply WRONG**. We believe you understand that Bayesian regret is generally considered a weaker notion than frequentist regret. Our manuscript and rebuttal clearly state that the results in Qin et al., 2023 are in the Bayesian regret setting. Note that throughout all our paper and discussions (even the quotes on LinTS from the literature) the notion of regret we study are all in frequentist regret setting. **Sadly, this discrepancy suggests either a serious misunderstanding or a deliberate misrepresentation of our work, which is very troubling**. Reviewer QBvS, we believe that you have experienced being an author in submitted papers. Many in our community have faced similar challenges, where reviews do not accurately reflect the value of their work. This is particularly problematic for theoretical papers, where significant effort and rigorous results can be easily overlooked due to ignorance or mistakes. Lastly, we respectfully and sincerely urge you to reconsider your evaluation of our work and ensure that it is judged fairly based on its theoretical contributions and merits.

Clarification on the Fair Assessment of Ensemble Sampling Research

## Key Points from the Reviewer's Perspective 1. **Comprehensive Analysis Requirements** - Analysis of Ensemble Sampling **must consider both computation and regret**. The issue on how ensemble size is chosen cannot be setting aside. - The problem-dependent nature of Thompson Sampling (LinTS) should be taken into account. 2. **Regret Metrics and Bounds** - Bayesian regret is widely accepted in the analysis of randomized exploration algorithms. - Frequentist and Bayesian regrets are different metrics and should not be directly compared. - For finite action problems, a matching bound with LinTS in finite action setting is necessary. This is already achieved by [Qin et al., 2022] if setting aside how ensemble size is chosen. - Problem-dependent bounds for Ensemble Sampling would be preferable. 3. **Limitations of the Current Work** - Achieving a matching performance of the infinite-action Frequentist regret bound of LinTS in a finite action setting, while setting aside how ensemble size is chosen, is **not sufficient to be considered a "holy grail" in the line of Ensemble Sampling research**. - The work does not explain the usefulness of Ensemble Sampling with linear function approximation, particularly due to the ensemble size scaling linearly with K, which **contradicts empirical evidence a lot**. ## Reviewer's Assessment and Recommendations 1. **Holistic Evaluation**: The analysis should consider both computational aspects and regret bounds. Setting aside the computation issue (how ensemble size is chosen) is not sufficient for a comprehensive evaluation. 2. **Problem-Dependent Analysis**: Encourage the development of problem-dependent bounds for Ensemble Sampling, similar to those existing for Thompson Sampling. 3. **Practical Implications**: The theory should aim to explain the effectiveness and usefulness of the existing algorithm, especially when empirical evidence contradicts theoretical predictions about ensemble size scaling. 4. **Advancement of the Field**: These assessments are intended to advance the community's understanding, not to be adversarial. The bandit community has already seen numerous bounds in linear function approximation and general function approximation. 5. **Criteria for Significant Contribution**: Given the motivation behind Ensemble Sampling and existing analysis of Ensemble Sampling under linear function approximation, a truly groundbreaking ("holy grail") theoretical work should either predict better algorithm design or provide significantly better understanding on the effectiveness/usefulness of existing algorithms. ## Conclusion While the achievement of certain regret bounds is noteworthy, a fair assessment must consider the broader context of both theoretical advancements and practical implications due to the motivation behind Ensemble Sampling. The reviewer emphasizes the need for problem-dependent analysis, explanation of empirical observations, and consideration of computational aspects alongside regret bounds. These points are crucial for advancing the field of Ensemble Sampling and ensuring that theoretical work translates into practical improvements in algorithm design and performance -- the motivation behind the line of research around Ensemble Sampling.

Addressing Misleading Claims and Mischaracterizations in Reviewer Feedback

### **Reviewer QBvS's Incorrect Claim Regarding Regret Bounds** ### Reviewer QBvS continues to falsely suggest that $\tilde{O}(d^{3/2}\sqrt{T})$ is not a valid finite-arm frequentist regret bound for LinTS. **This is simply false.** The more concerning issue is that the reviewer appears to be making this statement intentionally. Despite our clear explanation and presentation of evidence showing that both $\tilde{O}(d^{3/2}\sqrt{T})$ and $\tilde{O}(d\sqrt{T \log{K}})$ are valid frequentist regret bounds for LinTS in finite-arm settings, the reviewer persists in making this incorrect claim. **We have already provided ample evidence showing how this is widely accepted in the published literature.** Please note that the proof of the $\tilde{O}(d^{3/2}\sqrt{T})$ bound for LinTS in [3] does not require the number of arms in the problem setup to be infinite. The $\tilde{O}(d^{3/2}\sqrt{T})$ frequentist regret bound is valid for both infinite and **finite arms**. **Reviewer QBvS’s argument that $\tilde{O}(d^{3/2}\sqrt{T})$ is not a frequentist regret bound for finite arms is mathematically incorrect.** --- ### **Reviewer QBvS's Incorrect Claim, and then Inconsistent Statements** ### Previously, Reviewer QBvS incorrectly claimed that the Bayesian regret bound of Qin et al. (2023) is sharper than our frequentist regret bound. As we pointed out, these two measures are **not** comparable. Now, the reviewer appears to acknowledge that “Frequentist and Bayesian regrets are different metrics and should not be directly compared.” This raises concerns about the consistency of the review. We are not sure whether this mean that Reviewer QBvS acknowledges the earlier mistake of inappropriately comparing two incomparable regret measures. Because we have seen that Reviewer QBvS cannot agree on simple facts. --- ### **Reviewer QBvS's Mischaracterizing Our Results** ### Reviewer QBvS attempts to argue that the ensemble size $O(K\log{T})$ in our work is inherently inferior to the ensemble size $O(d\log{T})$ in Janz et al. [8], which is not only misleading but also unfair. To argue against our result, the reviewer chooses parameter values like $d = 2$ and $K = 10000$. In all fairness, please consider the opposite: $d = 10000$ and $K = 2$. Even with much smaller values, like $d = 50$ and $K = 2$, the results differ significantly. - Our analysis: ES with ensemble size **$2\log{T}$** achieves a regret bound of **$50^{3/2}\sqrt{T} \approx 354\sqrt{T}$** - Janz et al. (2023): ES with ensemble size **$50\log{T}$** achieves a regret bound of **$50^{5/2}\sqrt{T} \approx 17678\sqrt{T}$** Right, this scenario seems unfair to Janz et al. (2023), as we are sure that everyone can see. **But, this is exactly what Reviewer QBvS did by showing only one side**. So, let’s be fairer and consider $d = 50$ and $K = 50$ where $K\log{T} = d\log{T}$. - Our analysis: ES with ensemble size $50\log{T}$ achieves a regret bound of $50^{3/2}\sqrt{T} \approx 354\sqrt{T}$ - Janz et al. (2023): ES with ensemble size $50\log{T}$ achieves a regret bound of $50^{5/2}\sqrt{T} \approx 17678\sqrt{T}$ What do you see? ### **FACT**: For any combination of $d$ and $K$, our regret bound is always sharper than Janz et al. [8]. When it comes to the sufficient condition for ensemble size, $O(K\log{T})$ and $O(d\log{T})$ are apples and oranges. Is one theoretically higher than the other? No. ### Please note, **our aim in this example is not to show that our analysis requires a smaller number of ensembles**, as that number varies by the problem setting. **What we aim to highlight is how Reviewer QBvS selectively showed one side of the comparison, knowingly distorting the facts and our main focus to sharpen the regret bound**. --- We understand that the review process can sometimes be challenging and that authors may occasionally receive feedback that doesn't fully capture the true value of their work. However, this situation goes beyond mere noise, and we find it deeply concerning. **Despite our best efforts to engage in a rational and constructive dialogue with Reviewer QBvS, we have been met with a series of false claims, and it seems these may be influencing other reviewers**. It seems there may be an underlying adversarial approach in Reviewer QBvS's feedback. We do not wish to endlessly argue with Reviewer QBvS, especially when it is unfortunately evident that there is no common understanding. Communicating with Reviewer QBvS has become extremely challenging (not because the questions themselves are challenging but because despite our continued efforts to build some common ground on simple facts, we couldn't), and **we would prefer to cease further communication with Reviewer QBvS**.

Addressing Key Concerns and Clarifying Expectations for Ensemble Sampling Research

Dear Authors, ACs, SACs and PCs, I appreciate the authors' passion for their work and their desire to have it fairly evaluated. However, I feel it's necessary to clarify some points and address potential misunderstandings: 1. **Theoretical vs. Practical Implications**: While achieving a $\tilde{O}(d^{3/2}\sqrt{T})$ frequentist regret bound is a noteworthy theoretical result, we must be cautious about claiming that this closes the gap between theory and practice. The ensemble size scaling linearly with K in your analysis still contradicts empirical evidence, as reported in your own simulations. This discrepancy needs to be addressed for a comprehensive understanding of Ensemble Sampling's practical utility. 2. **Specific Regimes of Improvement**: It's crucial to clearly state the specific regimes where your result shows improvement. As emphasized in my previous comments, a fair comparison should consider various problem settings, including both finite and infinite action scenarios, as well as different relationships between ambient dimension $d$ and number of actions $K$. Presenting improvements in specific regimes would provide a more nuanced understanding of your contribution. **Current result in this work is not sufficient to be entitled "Improved regret of Linear Ensemble Sampling". The first sentence in the abstract is indeed misleading.** >"In this work, we close the fundamental gap of theory and practice by providing an improved regret bound for linear ensemble sampling." 3. **Problem-Dependent Nature of Thompson Sampling**: The analysis of Thompson Sampling-type algorithms, including Ensemble Sampling, should carefully consider the problem-dependent nature, particularly regarding the size of the action set. The regimes where d >> K, d ≈ K, and d << K may lead to different insights and bounds. This good tradition on the analysis Thompson sampling algorithm should be inherited to Ensemble sampling (serving as the need to approximate Thompson sampling). A comprehensive analysis addressing these various regimes would strengthen the paper's contribution. 4. **Holistic Evaluation**: A fair assessment of Ensemble Sampling research should consider both computational aspects and regret bounds. The issue of how ensemble size is chosen is integral to the algorithm's practicality and shouldn't be set aside in the analysis. 5. **Advancement of the Field**: Given the existing body of work on linear function approximation in bandits, a truly groundbreaking contribution should either predict better algorithm design or provide significantly better understanding of the effectiveness of existing algorithms across various regimes. 6. **Consistency in Evaluation**: If I were the reviewer of [Janz et al., 2023], I would give the same suggestions and assessment. My critiques are not specific to your work but reflect my consistent standards for evaluating research in this field. I hope these clarifications help in understanding my perspective. My intention is not to undermine the work but to ensure that we advance our field with rigorous, comprehensive, and practically relevant research. I encourage the authors to address these points in future revision, which could significantly strengthen the paper's contribution to the bandit community and even more broader field. Sincerely, Reviewer QBvS

Seeking Fair and Fact-Based Evaluation

Dear Reviewer QBvS, We respectfully disagree with the reviewer's claim that "your analysis still contradicts empirical evidence, as reported in your own simulations." Our simulations, conducted during the rebuttal, demonstrate that ensemble sampling performs comparably to, or even outperforms, widely used and provably efficient algorithms such as LinUCB and LinTS when a **sufficiently large** number of ensembles is used. Our analysis does not contradict empirical evidence. A significant issue arises from the reviewer's focus on requesting an empirical case where ensemble size specifically requires linearly increasing $K$ ensembles, leading to the assertion that "our analysis still contradicts empirical evidence." **This claim by the reviewer is logically flawed because, as clearly stated in our paper and reiterated during the discussion, the condition on the ensemble size of $K\log T$ is a sufficient condition, not a necessary condition**. The reviewer seems to conflate sufficient and necessary conditions, persisting in this misunderstanding even after we clarified it during the discussion. **Please think about the following question: why would we even perform and present additional results during the rebuttal if our analysis indeed contradicted empirical evidence?** It is disappointing to see non-contradictory results being used to challenge our theoretical contributions, without valid backing (with confusion between the necessary condition and sufficient condition). Furthermore, our results are presented in terms of frequentist regret, which hence addresses the worst-case setting. The ensemble size condition we provide is indeed a sufficient condition under this worst-case framework. It is important to recognize that **asking for empirical evidence to prove the necessity of a condition that is only proven to be sufficient in the worst case is not logically sound**. We also challenge the reviewer's implication that "d >> K, d ≈ K, and d << K may lead to different insights and bounds." As we have clearly stated, our frequentist regret bound of $O(d^{3/2}\sqrt{T})$ holds regardless of the relationship between $d$ and $K$ (whether $d \gg K$, $d \approx K$, or $d \ll K$). This is a factual statement, and it would be misleading to suggest otherwise. We sincerely and respectfully ask the reviewer to acknowledge the factual errors and inconsistent claims made in the review and throughout the previous comments. We understand that reviewers can sometimes make mistakes or overlook certain contributions, and we are open to constructive feedback. However, doubling down on these mistakes without any acknowledgment of the errors should not be the way forward. Our active discussion would have been much more constructive if the reviewer and we had agreed upon simple facts. We are, of course, willing to make minor edits to the presentation and framing if reasonably suggested. If the reviewer's intention is to help strengthen our paper, we would welcome any suggestions, provided that the feedback is grounded in agreed-upon facts. Please note that we stand firm by our rigorously proven theoretical results.