- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes OnlineTS for generalized linear bandits by combining an existing Bayesian one-pass estimator with Thompson sampling. The algorithm starts with batch MAP and Laplace updates, then switches to recursive Gaussian updates based on a local quadratic approximation of the likelihood. The main theoretical contribution is a high-probability concentration analysis under adaptive data collection, leading to a claimed regret bound under a cumulative-curvature assumption. Experiments on synthetic logistic and Poisson bandits compare regret and runtime with existing GLB algorithms and examine sensitivity to the warm-start length and misspecified norm bounds.
Critical strengths
-
Simple and efficient online updates. After the warm-start phase, OnlineTS updates its Gaussian approximation using only the current observation, with computation and memory. The update does not require a known parameter norm bound or curvature lower bound. This offers a useful practical approach to approximate Thompson sampling for GLBs.
-
Promising empirical performance. Experiments cover both logistic and Poisson rewards and show competitive regret at substantially lower runtime than batch-based randomized methods. The appendix also includes comparisons with correctly specified baseline parameters, supporting the practical value beyond robustness to misspecified bounds.
Critical weaknesses
-
Limited theoretical improvement over GLB-OMD. OnlineTS requires the additional information-growth assumption A3, while its regret bound contains a leading term that retains dependence on worst-case local curvature. GLB-OMD does not require A3 and confines worst-case curvature dependence to lower-order terms. Thus, the shared rate obscures substantial differences in the guarantees.
-
Limited experimental validation. The evaluation focuses on small synthetic settings without real-world datasets. Figure 6 also appears to show OnlineTS running slightly slower than GLB-OMD, leaving its practical computational advantage unclear. Since only OnlineTS receives batch initialization, the comparisons do not isolate the contribution of warm-starting from that of the subsequent online method.
Questions for authors
-
Clarification of theoretical dependencies. Could you make the dependence hidden in and the warm-start threshold explicit? Under the truncated Gaussian design, introduces worst-case local curvature into the leading regret term. How should Table 1’s comparison with GLB-OMD be interpreted given this dependence and the additional assumption A3?
-
Clarification of the claim about implementation without problem-dependent constants. Although the updates do not explicitly require constants such as and , the theoretically sufficient warm-start length depends on them through . Does the method therefore avoid specifying these constants only in the updates, while still requiring their knowledge to select a provably valid ? Please clarify this distinction. Without an implementable adaptive stopping rule or an instance-independent tuning guarantee, the practical claim appears stronger than what the theory establishes.
-
Clarification of runtime measurements. Appendix I.3 reports . Does Figure 6 include all batch initialization costs? What fraction of OnlineTS’s runtime comes from warm-starting, posterior updates, and sampling/action selection? This breakdown would help explain why OnlineTS appears slightly slower than GLB-OMD despite its lower stated estimator-update complexity.
-
Additional validation of the warm-start contribution. Does OnlineTS retain its regret advantage when GLB-OMD and other applicable baselines receive a comparable warm-up? It seems that in Figure 2, the warm start can be critical to the performance of OnlineTS, especially in the Poisson bandit case. GLB-OMD paper also discusses warm-up strategies in Sections 3.3 and 6, making this comparison particularly relevant. So is it possible to add warm-up to other baselines like GLB-OMD for fair comparison?
-
Additional validation of scalability and applicability. Could you provide results across larger dimensions and parameter norms, together with a real-world benchmark such as Covertype? These would materially strengthen the evidence for computational scalability and performance beyond the current synthetic settings.