- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies Thompson sampling (TS) for Gamma bandits with unknown means and shapes. It introduces information-tempered matching (ITM) priors that preserve the standard TS decision rule and full shape support. For every fixed η > 0, it proves instancewise asymptotic optimality for fixed finite-arm instances with a unique optimal mean with the exact information-theoretic regret constant (lines 054–061, 098–099, 378–410).
It also characterizes a fixed-sample prior-tail integrability threshold and derives ordinary-TS lockout lower bounds for Jeffreys and matching priors; the matching prior’s coefficient optimality remains unresolved (lines 245–279, 295–319). Frozen-posterior and full-bandit experiments examine the predicted failure mechanism, finite-time regret, and upper-tail losses, with numerical checks of posterior computation (lines 426–474, 1971–1992).
Critical strengths
A sharp Gamma-bandit result supported by substantive uniform analysis. The main contribution is an exact asymptotic guarantee for standard, uncapped TS in a noncompact two-parameter model. Global posterior-integral comparisons and uniform control of both shape boundaries establish summable pessimism odds, overcoming the gap between fixed-sample posterior asymptotics and sequential expected regret (lines 044–047, 340–363, 386–410). These estimates give a principled class of priors attaining the information limit, including globally comparable alternatives (lines 378–384, 1779–1829). This is a concrete theoretical advance for Gamma bandits with unknown shape.
Critical weaknesses
The comparison with prior work does not sufficiently clarify the new insight. The introduction identifies prior-dependent TS results for Gaussian and Pareto bandits—Honda and Takemura (2014, AISTATS), Lee et al. (2023, ICML), and Lee et al. (2024, AAAI)—and distinguishes fixed-shape Gamma analyses (lines 035–047). However, these comparisons are not sufficiently connected to the new uniform posterior bounds and recovery guarantees (lines 340–363, 378–410). Readers must largely reconstruct which insights are inherited, which conclusions are new to Gamma bandits, and which analytical obstacles require new ingredients. This makes the conceptual contribution and its significance harder to assess.
Finite-time prior selection and gains over matching TS remain weakly established. The theorem gives every fixed η > 0 the same asymptotic coefficient, while finite-time constants and empirical rankings depend on η and the instance (lines 378–384, 464–468). For η = .5, paired intervals support improvements in mean regret and CVaR on the five-arm instance, but include zero for both metrics on the two two-arm instances and all six misspecification settings (lines 2053–2058, 2250–2253). Thus, practical guidance on choosing η or preferring ITM to matching TS remains limited.
Questions for authors
1. Clarification of the contribution. Could you distinguish the conclusions already explained by the Gaussian/Pareto analyses from those newly established here, and identify the specific obstacles that prevent the existing arguments from directly yielding your Gamma results (lines 035–047, 340–363, 386–410)? This would help assess the new insight provided by the analysis.
2. Experimental clarification on the choice of η = .5. How was η = .5 selected for the principal paired comparisons? Was it fixed independently of the reported benchmark outcomes, or selected after examining them? This affects the interpretation of the reported improvements (lines 464–468, 2053–2058, 2179–2181).
Optional rebuttal experiment. The main full-bandit benchmarks fix the optimal arm’s shape at 2 (lines 1927–1931). Adding one small-shape and one large-shape setting, while keeping the means, other-arm parameters, and prior settings fixed, would help assess whether the observed benefits of ITM over matching TS persist across different noise levels. Reporting mean regret and CVaR with paired uncertainty intervals would strengthen the finite-time comparison (lines 464–468, 2053–2058).
3 comments
On W1. Thank you for your response. However, I still do not understand why the existing Gaussian and Pareto arguments cannot be applied directly. Showing where the existing methods fail would strengthen the necessity of your analysis and make its contribution clearer.
On W2. Thank you for the additional experiments. However, the choice of remains unexplained. No constructive suggestion for selecting is provided.
Follow-up on Gamma proof steps and choice of eta
Thank you for the follow-up.
W1. Model-specific probability bounds. The general TS regret decomposition works in our case. The model-specific step bounds the optimal-arm posterior pessimism odds uniformly over sample sizes.
In Honda and Takemura (2014), the mean posterior is exactly Student-t (Eq. (4)). Their Lemma 7 uses its reflection symmetry about the sample mean in the step leading to Eq. (17), and the normal/chi-squared sampling laws in Eq. (18). For Gamma rewards, the conditional mean posterior is inverse-Gamma with shape and scale ; its marginal is a mixture over the unknown shape. In our case, however, the Student-t reflection identity does not hold: reflection about the sample mean would send its positive mass above twice that mean to negative means, outside the Gamma parameter space.
Also, some transformations are needed in the initialization when one matches the high-precision tail exponent alone. Under the correspondence , the Gaussian Student-t degrees of freedom are , which is zero at . Such a Gaussian posterior is improper, whereas our Gamma posterior is proper almost surely after two observations for every fixed . ITM keeps the small-shape order unchanged while tempering the high-shape tail.
In Lee et al. (2023), Eq. (8) gives an Erlang posterior for the Pareto shape and Eq. (9) gives the conditional scale CDF as a power of the sample minimum. Appendix C.1, Eqs. (24)-(25), uses the associated Erlang sampling law and CDF bound to control pessimism. The Gamma shape posterior is instead
w(k)\frac{\Gamma(nk)}{\Gamma(k)^n n^{nk}}e^{-nkH_n},$$ and its optimism probability is $p_n(b)=\mathbb E_{q_n}[P(nk,nk\bar x/b)]$, where $P$ is the regularized lower incomplete Gamma function. This shape posterior is not Erlang, and the incomplete-Gamma order $nk$ varies with the integration variable. The Pareto distributional identities therefore cannot be substituted into this expectation.These are the concrete points where the existing probability estimates must be replaced. For the Gamma model, the required sequential statement is $$\sum_{n\ge2}\mathbb E_{\theta^\star} \frac{1-p_n(b)}{p_n(b)}<\infty \qquad(b<\mu^\star).$$ Our frozen-prefix analysis identifies the prior-tail threshold for each fixed $n$. Proving the displayed sum additionally requires bounds uniform in $n$ over the full shape range. Lemma 14 supplies the global shape-integral comparison; Theorem 8 and Lemma 16 control the large- and small-shape sampling-density regimes. These estimates establish the sum used in Theorem 10. **W2. A constructive rule for choosing $\eta$.** Theorem 5 gives a more specific interpretation of $\eta=0.5$ at our two-pull initialization. Let $u=H_2$ and consider the low-mean, nearly equal initial observations covered by that theorem, with $\bar x/b$ in a fixed compact subinterval of $(0,1)$. Since $\tau=1+\eta$ and $(n-1)/2=1/2$, its bound $p_b^{-1}$ is $u^{-(1/2-\eta)}$ when $0<\eta<1/2$, $p_b^{-1} = \log(1/u)$ when $\eta=1/2$ and $p_b^{-1}=1$ otherwise. Hence, $\eta=0.5$ is the smallest tempering exponent that changes the initial inverse-optimism singularity from algebraic to logarithmic. It also makes every fixed positive moment of $p_b^{-1}$ integrable within this initial-prefix regime, because the sampling density is of order $u^{-1/2}$ and $\int_0^\varepsilon u^{-1/2}[\log(1/u)]^q du<\infty$ for every fixed $q>0$. More generally, for a desired finite $q$th moment of the initial inverse optimism, $q>1$, Theorem 5 gives the condition $\eta>\frac{n_0-1}{2}(1-1/q)$. For $0<\eta<d_0=(n_0-1)/2$, this follows by integrating $u^{d_0-1-q(d_0-\eta)}$ near zero. Taking $\eta=(n_0-1)/2$ covers every fixed finite $q$. This yields a concrete default initialization: with $n_0\ge2$ initial observations per arm, one chooses $\eta=(n_0-1)/2$ to ensure that initial inverse optimism has at most a logarithmic singularity near these prefixes; and choose $\eta>(n_0-1)/2$ if bounded inverse optimism as $H_{n_0}\downarrow0$ in the same regime is desired. Our $n_0=2$ setting gives the default $\eta=0.5$. A finite second moment of initial inverse optimism only requires $\eta>1/4$; the default covers all fixed finite orders. Above are our theoretical interpretation of the benchmark value and a prospective selection rule based on initialized-posterior robustness. Finite-horizon regret also depends on the instance. If independent benchmark instances are available, one compares fixed positive values such as {0.25,0.5,1} using the intended mean-regret or CVaR criterion, then fixes $\eta$ before the evaluation runs. Every fixed positive choice retains Theorem 10's sharp asymptotic coefficient.
Response to Reviewer UVtD: Prior dependence, parameter choice, and shape experiments
We thank the reviewer for the helpful comments.
W1 / Q1. Prior dependence and what the Gamma proof adds. Honda and Takemura (2014) show that Gaussian Thompson sampling (TS) can attain or miss the information bound depending on the prior on variance. Under the precision reparameterization of their prior, the optimal range corresponds to a tail exponent τ>1. Lee et al. (2023) establish a related dependence on the prior for Pareto TS, and Lee et al. (2024) study truncation in multiparameter models. These results motivate the question of which shape tails allow recovery in the two-parameter Gamma model.
After n Gamma observations, the sufficient statistics are the sample mean m and log-dispersion Hn=logm−n−1∑i=1nlogXi. The posterior of shape is proportional to w(k)Rn(k)e−nkHn. To obtain the posterior probability of a mean draw above b, the numerator inserts the incomplete-Gamma factor P(nk,nkm/b) under that integral. When m/b is bounded away from zero and one with m<b, this factor suppresses high shapes in the numerator. The normalizer can still grow as Hn↓0. Theorem 5 combines that growth with the small-ball law for Hn and gives the exact criterion τ>1 for local integrability of reciprocal optimism at each fixed n≥2. Theorem 6 carries this mechanism over to ordinary TS by constructing a positive-probability path on which the competing arm keeps updating and its posterior draws stay above the threshold.
The information-tempered matching (ITM) weight in Eq. (2) multiplies matching by [1+e2A(k)]−η, where A(k)=kψ(k)−k−logΓ(k). It preserves first-order probability matching for the mean and the small-shape order, while the high-shape tail changes from k−1 to k−1−η. The fixed-n criterion addresses one source of lockout. To get the exact regret constant, Theorem 10 needs ∑n≥2E[(1−pn(b))/pn(b)]<∞ for every fixed b<μ⋆. Theorem 8 controls the empirical-shape saddlepoint uniformly when it is large, including when both the shape and sample size grow. Lemma 16 bounds the sampling density at the small-shape end. Together with the global comparisons of the shape integrals in Lemma 14, these yield the sequential sum for the full-support ITM priors. Appendix K further quantifies how that sum depends on μ⋆−b and derives a uniform finite-horizon bound on compact classes of true parameters.
W2 / Q2. Choice of η=.5. The original full-bandit experiments compare η=.25,.5,1, with η=.5 used in the main paired contrast. The timing of that original choice is undocumented. The asymptotic coefficient is the same for all three positive values, and the finite-time ordering varies by instance and metric in the original benchmark. For the new study we fixed η=.5 before the runs, retaining the same comparison against matching across all nine cells.
W2 / requested experiment. Optimal-arm shape. In Section 6 (p. 10), we vary k⋆∈{0.5,2,8} while holding means and competitor parameters fixed within each instance. Each cell has 4,096 fresh pairs at T=20,000, with shared reward streams within a pair and separate posterior draws. The differences below (Appendix L, Table 12) are ITM minus matching, with pointwise paired 95% bootstrap intervals. Conditional value at risk (CVaR) averages the 205 largest trial regrets per policy and cell.
Both intervals favor ITM for each optimal shape in the high-shape-competitor instance. At the original k⋆=2 setting, Table 4 gave intervals [-2.77, 4.05] for mean regret and [-51.21, 82.91] for CVaR there. For the small-gap instance, both intervals exclude zero only at k⋆=8. For five arms they both exclude zero at k⋆=2, and only CVaR does at k⋆=8. The original six misspecification comparisons have intervals spanning zero for both outcomes (Tables 10–11). Table 13 in Appendix L reports exact intervals and discordant counts for severe lockouts. In the high-shape-competitor cell at k⋆=0.5, there are 8 matching and 5 ITM events with exact paired p=0.55. Severe lockouts were rare across the nine settings, with exact paired p≥0.25 in each cell.