Optimal Regret Is Achievable with Bounded Approximate Inference Error: An Enhanced Bayesian Upper Confidence Bound Framework

Summary

In this paper, the authors consider Bayesian bandit algorithms where exact posterior is not available and only approximations are available. The authors prove that if $\alpha_1$-divergence and $\alpha_2$-divergence between the exact posterior and approximation are small, then a modification of Bayesian UCB (EBUCB) achieves $O(\log T)$ regret. In the previous work, it is known that Thompson sampling with approximate inference has $\Omega(T)$ regret. The authors also show negative results for EBUCB and Thompson sampling under the condition on only one $\alpha$-divergence. Finally, in synthetic environments the authors confirm their theoretical findings.

Strengths

1. This paper solves an important problem (Bayesian bandit algorithms using an approximation of the posterior) and provides a nice result (the upper bound has $O(\log T)$-regret and the dominant term does not depend on $\varepsilon$, which is surprising). 2. Although the environments are simple and synthetic, they conducted experiments.

Weaknesses

1. In Corollary 3.8, the dependence of $\varepsilon$ is hidden (not discussed). 2. The optimal parameters of the algorithm are not known in practice.

Questions

1. In Corollary 3.8, does the small $o$ notation hides $\varepsilon$? Could you briefly discuss its dependence?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed 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

Limitations are not discussed.

Summary

This paper studies Bayesian bandits with approximate inference errors. The authors proposed an algorithm called the Enhanced Bayesian Upper Confidence Bound (EBUCB). Under a two-bounded $\alpha$-divergence assumption, the authors show that EBUCB can achieve the optimal logarithmic regret. The authors also show that with sub-linear regret cannot be achieved with only one-bounded $\alpha$-divergence.

Strengths

The authors provide the first $\log(T)$-type of regret for Bayesian bandits with constant approximation error (under 2-bounded $\alpha$-approximation). This result is obtained based on a novel sensitivity analysis of quantile shift. Both the result and the analysis look interesting to me. The authors also show that, under 1-bounded $\alpha$-approximation, one cannot obtain sub-linear regret; this negative result further justifies the necessity of 2-bounded $\alpha$-approximation (Assumption 3.3).

Weaknesses

My main concern is that the developed results are only for Bernoulli bandits, not for more general distributions (not even for the Gaussian distribution). Can authors comment on why Bernoulli is needed in the current analysis? Or what prevents the derived results from being extended to other distributions? Another question I have is regarding the constant approximation error for the 2-bounded $\alpha$-approximation (i.e., the $\epsilon$ term in Assumption 3.3). It seems a bit weird to me that the regret bound doesn't depend (too much) on the $\epsilon$ (e.g., in Corollary 3.8). Can authors comment on the reasons behind this?

Questions

See the weaknesses part.

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

N/A

Summary

This paper considers the standard multi armed bandit problem with a prior on rewards, allowing the design of Bayesian algorithms such as Thompson sampling and Bayesian UCB. The problem of interest is when the exact posterior distributions are not available. Rather an approximate posterior is available. It has been known that even with a small constant alpha divergence error between the true and approximate posterior, Thompson sampling does not converge. This paper shows that with a two bounded alpha divergence (see Assumption 3.3) Bayesian UCB achives order optimal regret bound.

Strengths

The problem of designing Bayesian optimization algorithms which find the optimal action in the presence of approximate distributions is very interesting.

Weaknesses

The setting is motivated with the difficulty of obtaining true distributions that often arises in complex models and when using methods such as variationally inference. The results are however proven on a system of Bernoulli distributions where the posterior is available in closed form. I think this break the logic on motivation to a great extent. While I tried to read all the proofs and details, I could not obtain a good intuition into why small alpha divergence is not enough and two alpha divergence works; how can this be used when applied to for example MCMC or variational inference.

Questions

1. Could authors provide more intuition into the significance of their results for the complex settings where the distributions are approximated. It seems the results are limited to simple settings where the posterior is easily obtained. Could authors intuitively explain why small alpha divergence is not enough and two alpha divergence works. 2. As small alpha divergence is not enough and only two alpha divergence works in this setting, one would expect Theorem 3.7 to fail when $\alpha_1=\alpha_2$. In line 254, it is stated that we may choose $\zeta=\frac{1}{\tilde{\alpha}_2}$. If, in addition, we set $\alpha_1=\alpha_2$, implying $\tilde{\alpha}_1=\tilde{\alpha}_2$, the upper bound in Theorem 3.7 still seems to work. Could authors explain what happens here when $\alpha_1=\alpha_2$ and if the Theorem fails.

Rating

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

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

2 fair

Limitations

As mentioned above, the main limitation of the paper seems to be the simple setting, where the posteriors are available in closed form. The results do not seem to be extendable to more complex setting where approximate distributions are actually relevant.

Response

I thank the authors for their rebuttal. I'd like to keep my current scores and suggest the authors add related discussion into the paper during revision.