Finite-Time Logarithmic Bayes Regret Upper Bounds

Summary

This paper proves logarithmic (in horizon $n$) regret bounds for Bayesian bandits using the BayesUCB algorithm. They specifically study the settings of Gaussian MABs and Gaussian linear bandits. This improves on prior works which show the more standard $\sqrt{n}$ bounds on regret.

Strengths

- Generally the writing is good. Problem setup and results are clear, as well as points of comparison with classical asymptotic guarantees. - The proofs are simple and easy to understand. - Numerical simulations are run to back up the validity of the theory.

Weaknesses

- On the technical side, I'm not sure where the contributions are. The abstract states that "our proofs mark a technical departure from prior works". Can this be made more explicit in the technical discussion? - Several questions about the experiments, see next section. Generally the scope of the experiments is rather limited (which may be fine since this is primarily a theoretical work). Some comments on writing: - line 65: "any bounded $\theta$": since we have not specified a specific parametric model here (it is not even clear that $\theta$ must lie in some Euclidean space) a description of $\theta$ being bounded seems premature here. - as a matter of writing style, it is a bit strange to put part of the inequality inline and the other half in display equations (such as line 120).

Questions

1. Can the authors elaborate on how the techniques in the paper differ from prior works, and/or are clearer and simpler to understand? a) From my understanding, the main parts of the analysis seem pretty similar to the standard frequentist analysis (i.e., the construction of confidence intervals and bounding the regret when the confidence interval event holds). 2. The parameter $\epsilon$ seems a bit mysterious to me. It seems like it is a parameter that is used only in the analysis. Perhaps the results could be more clearly stated in the main text by just setting $\epsilon$ to the canonical values. 3. The bounds that are obtained are not that easy to interpret. a) Any intuition for what the $\xi_a$ functions accomplish (e.g., in line 225)? Can one improve the range for $\xi_a$ to be $\Theta(1/\mathrm{poly}(n))$? A slightly unsatisfying aspect of the claim when one takes $n\to \infty$ is that $1/\sqrt{\log n}$ goes to zero very slowly. b) What is the intuition for the $\sum_a \int_{\theta_{-a}}$ term? It seems like this comes from prior analysis. Why does it capture the dependence on the prior? c) The linear gaussian bandit bound can be used to recover (a version) of the gaussian MAB bound. Can you discuss this? Is this tight in the relevant problem parameters? If not, why? 4. line 147-148: the claim about the setting where $\sigma_0 \to \infty$ is not clear to me why the complexity term should approach zero. Can this be formalized? 5. Can the ideas be extended beyond Gaussian settings, and/or can they handle some degree of model misspecification (e.g., what happens if the rewards are close to gaussian in some distance metric). 6. Experiments: a) Did you tune the confidence widths for the BayesUCB and UCB1 algorithm? b) Can confidence bands be plotted? c) I think the most interesting part is the comparison between BayesUCB and UCB1. Your theory suggests that BayesUCB improves over UCB1 because it takes into account the prior. Can this be demonstrated more robustly, i.e. for a range of experimental parameters. Also, we would expect this to happen in well-specified settings where the rewards are actually Gaussian. It would be interesting to see if this phenomena is robust and holds for real-world datasets (otherwise, in some sense, it might not be interesting to study BayesUCB...) d) Why are your plotted bounds not monotone in $\sigma_0 and \Delta_0$? (Taking a step back, is this something that one should expect?) e) In some regimes, your bounds for the linear setting are worse than the established $\sqrt{n}$ bounds. Why is this so? Does this point to some looseness in the analysis? 7) At a high level, why is BayesUCB interesting to study, and how does it compare to other Bayesian approaches, e.g., Thompson sampling? Which should one choose to use in practice?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

None.

Summary

This paper considers a Bayesian setting of the multi-armed bandit problem and provides finite-time regret bounds. For the Gaussian bandits with independent priors, the authors provide regret analyses for BayesUCB and UCB1 algorithms. Both bounds scale as $O(c_h \log^2 n)$ and match the lower bound by Lai (1987) up to constant factors. For the Linear bandits with Gaussian rewards, the authors provide an analysis for BayesUCB and the bound scales as $ O(c_\Delta \text{polylog}n)$. The empirical results corroborate the tightness of the bounds.

Strengths

This paper gives the first finite time bound for the Bayesian regret minimization problem with logarithmic regret for Gaussian reward and Gaussian prior setting. In the case of the multi-armed (unstructured) bandit setting, for both BayesUCB and UCB1, the order of $O(c_h \log^2 n)$ Bayesian regret bound is given. For the linear Gaussian bandit case with bounded inverse gap, the bound does not scale with the number of arms and scales as $O(c_\Delta \text{polylog} n)$.

Weaknesses

Lai (1987) provides an upper bound that exactly matches the lower bound, including the universal constants. The authors' bound does not seem to match it asymptotically. There is an assumption that the prior is factored. (Lai (1987) has weaker condition on the prior distribution (3.16) - (3.18) in Theorem 3.) I believe this assumption should be more explicitly stated/discussed in the main theorem.

Questions

If possible, - Could you provide the reasoning/intuition behind why it would be difficult to have matching upper bounds with constants asymptotically together with the finite round bounds? - Why the factored assumption is necessary or may not be? - Could you make contrast your proof with the proof of Lai (1987)? What techniques/devices make it possible to bound with a finite sample? - Why would it be difficult to get a lower bound with the linear bandit setting? - Would it be possible to get Bayesian regret bound for the linear bandit setting by integrating the complexity term without finite inverse gap assumption?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See the Weaknesses section.

Summary

The authors consider the Bayesian bandits problem and provide first finite-time logarithmic regret upper bounds by analyzing the BayesUCB algorithm from a new perspective, departing from previous studies. Their theoretical results demonstrate the significance of the prior. Additionally, the authors showcase the versatility of their analysis techniques by applying them to linear bandits. Furthermore, they substantiate the tightness of their bounds through numerical evaluations.

Strengths

The authors provide first finite-time logarithmic regret upper bounds for Bayesian bandits, which improve the existing $\tilde{O}(\sqrt{n})$ bounds and highlight the significance of the prior. The authors provide experimental results for both Gaussian bandits and linear bandits with Gaussian rewards. The experimental results substantiate the theoretical findings. The results and the addressed problem hold substantial significance and are likely to capture the interest of a broad audience in Neurips.

Weaknesses

I have two primary concerns regarding this work and would like to request the authors to provide additional clarifications. ==Weakness 1== While the authors present finite-time logarithmic regret upper bounds for Bayesian bandits, it is worth noting that Lai [1987] provide both asymptotic logarithmic upper and lower bounds. Therefore, it would be beneficial for the authors to explicitly highlight the key challenges associated with analyzing the finite-time case. This clarification would help readers better understand the distinctive aspects of the two settings. ==Weakness 2== From a theoretical standpoint, the authors demonstrate the tightness of their results by comparing them with the asymptotic lower bound presented in Lai [1987]. This may raise concerns about the rigors. Additionally, it introduces a logical paradox concerning the contribution of the paper. If the theoretical analysis between the finite-time and asymptotic cases significantly differs, the comparison may not be sufficiently robust. On the other hand, if the comparison holds, it might suggest that the current results have somewhat limited contributions. ==Minor Comment== Regarding the title, I suggest revising it to "Finite-Time Logarithmic Bayes Regret Upper Bounds" instead of the current title "Logarithmic Bayes Regret Bounds." This change may be appropriate because Lai [1987] already covers both asymptotic logarithmic upper and lower bounds for Bayesian bandits. Reference Tze Leung Lai. Adaptive treatment allocation and the multi-armed bandit problem. The Annals of Statistics, 15(3):1091–1114, 1987.

Questions

Please see the points mentioned in the weaknesses above and provide comments on them.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

I don't see any issue on societal impact.

Summary

This paper derives a finite-time regret bound for BayesUCB in Bayesian bandits. In Gaussian bandits, the bound grows linearly in $c_h \log^2(n)$, where $n$ is the time horizon, and $c_h$ is a constant determined by the prior. The bound matches that given by Lai (1987). A regret bound of BayesUCB in linear bandit is also established. Numerical experiments have also been conducted to support the theoretical findings.

Strengths

The paper studies an important problem and derives useful regret bounds. The paper is also well-organized and easy to follow.

Weaknesses

In terms of presentation/ writing, I wish the paper could be more polished. Some of the examples are listed in “Questions.”

Questions

There are some minor issues in writing. Below are a couple examples: 1. In line 57, the paper reads “$A_t \in \mathcal{A}$.” However, $A_t$ is a random variable taking values in $\mathcal{A}$, so the statement is not precise. 2. In line 83, it reads” $C_{t,a}$ is a confidence interval.” However, $C_{t,a}$ should be half the length of the confidence interval. 3. Typo in line 97: should remove “a” from “the posterior distribution is a Gaussian.”

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

The paper studies the multi-arm bandit (MAB) problem, which is an online learning problem where a learner interacts with an environment over multiple rounds. In each round the learner would make an action, and each different action will incur a reward sampled from some distribution parametrized by an unknown $\theta$. The goal is to get highest expected cumulative reward overtime, or in other words, to minimize the cumulative "regret" of not choosing the best action in each round. Here "best" means an action incurring the highest expected reward. The paper focuses on Bayesian MAB, where the unknown parameter $\theta$ itself is generated from some known prior. The paper proves several improved regret bounds for various Bayesian MAB settings, including: proving finite-time logarithmic Bayesian regret bounds for a Bayesian UCB algorithm in a Gaussian bandit, deriving a finite-time logarithmic Bayesian regret bound for a frequentist UCB algorithm to demonstrate the value of the prior as side information, proving a Bayesian regret bound for a Bayesian linear bandit algorithm, and empirically comparing the tightness of the bounds to prior bounds.

Strengths

The authors provide a logarithmic regret bounds for some basic Bayesian MAB problems, which improves exponentially on previous best result and matches an asymptotic lower bound. This seems to me a breakthrough.

Weaknesses

N/A

Questions

First, The paper under consideration falls outside my domain and I never bid for it (Regrettably I wasn't given any alternative submissions to assess). Despite my limited familiarity with MAB, the problems delineated in the manuscript, such as the Gaussian bandits, seem both intuitive and natural. The lower bound result referenced, by Lai et al., dates back several decades. Given this context, I presume these matters have been thoroughly examined within the domain. Given this, one thing that appears perplexing to me is the paper's claim of exponential improvements over prior best results. Such a significant leap over such basic problems, usually suggests the introduction of some truly innovative ideas in the analysis. However, the proof seems quite innocuous and it's not immediately clear to me what is the core idea that leads to the improvement. It will be very helpful if the authors can add one or two paragraphs elucidating previous results. Specifically, what is the major barrier that prevents them from achieving this logarithmic bound, and how the authors manages to overcome that barrier.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Thanks for your reply.

*This is analogous to the relation of frequentist gap-dependent and gap-free bounds in bandits.* Can you point me to a reference for this fact? Also, how do your results compare to other works on instance-dependent learning: [1] Andrew Wagenmaker, Dylan J. Foster. "Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory."

Thanks

Thank you for acknowledging that we answered your questions. If anything else arises later, please let us know. Sincerely, The authors

Thanks

Thank you for letting us know that our rebuttal answered your questions. If anything else arises later, please let us know. Sincerely, The authors