acceptodds
Under review as a conference paper at ICLR 2027

Information-Tempered Priors for Gamma Thompson Sampling

Abstract

Nearly equal pessimistic observations can make the optimal-arm posterior falsely precise in Gamma Thompson sampling (TS) with unknown means and shapes. Skipping the arm then freezes its posterior. Information-tempered matching (ITM) priors with fixed retain full support and first-order probability matching with tail . Global posterior-integral comparisons, high-shape saddlepoint control, and a small-shape carrier bound establish summable pessimism odds for these priors. For every fixed finite-arm Gamma instance with a unique optimal mean, uncapped ITM-TS is uniformly efficient and attains the Burnetas–Katehakis regret constant. Regular priors globally comparable to ITM share this guarantee. For weights , , as , reciprocal optimism near these histories is locally integrable exactly when for every fixed sample size . With two initial pulls per arm, ordinary TS incurs lockout regret under Jeffreys' prior and a distinct coefficient constraint under the matching prior. Full-bandit experiments with 1,024 trials per instance support lower mean regret and CVaR for ITM () than matching TS on the five-arm instance; both two-arm instances have paired intervals containing zero.

Primary area:
reinforcement learning
Keywords:
Thompson sampling, multi-armed bandits, Gamma bandits, probability-matching priors, asymptotic regret optimality

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_UVtDOpenReview ↗
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
AuthorsOpenReview ↗

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\tau > 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 nn Gamma observations, the sufficient statistics are the sample mean mm and log-dispersion Hn=log⁡m−n−1∑i=1nlog⁡XiH_n=\log m-n^{-1}\sum_{i=1}^n\log X_i. The posterior of shape is proportional to w(k)Rn(k)e−nkHnw(k)R_n(k)e^{-nkH_n}. To obtain the posterior probability of a mean draw above bb, the numerator inserts the incomplete-Gamma factor P(nk,nkm/b)P(nk,nkm/b) under that integral. When m/bm/b is bounded away from zero and one with m<bm < b, this factor suppresses high shapes in the numerator. The normalizer can still grow as Hn↓0H_n\downarrow0. Theorem 5 combines that growth with the small-ball law for HnH_n and gives the exact criterion τ>1\tau > 1 for local integrability of reciprocal optimism at each fixed n≥2n\ge2. 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)]−η[1+e^{2A(k)}]^{-\eta}, where A(k)=kψ(k)−k−log⁡Γ(k)A(k)=k\psi(k)-k-\log\Gamma(k). It preserves first-order probability matching for the mean and the small-shape order, while the high-shape tail changes from k−1k^{-1} to k−1−ηk^{-1-\eta}. The fixed-nn criterion addresses one source of lockout. To get the exact regret constant, Theorem 10 needs ∑n≥2E[(1−pn(b))/pn(b)]<∞\sum_{n\ge2}\mathbb E[(1-p_n(b))/p_n(b)] < \infty for every fixed b<μ⋆b < \mu^\star. 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\mu^\star-b and derives a uniform finite-horizon bound on compact classes of true parameters.

W2 / Q2. Choice of η=.5\eta=.5. The original full-bandit experiments compare η=.25,.5,1\eta=.25,.5,1, with η=.5\eta=.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\eta=.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}k^\star\in\{0.5,2,8\} while holding means and competitor parameters fixed within each instance. Each cell has 4,096 fresh pairs at T=20,000T=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.

Instancek⋆k^\starMean regret differenceCVaR difference
High-shape competitor0.5-4.48 [-7.83, -1.64]-79.52 [-146.36, -23.89]
High-shape competitor2-1.44 [-2.94, -0.37]-24.14 [-53.74, -3.24]
High-shape competitor8-1.26 [-3.05, -0.24]-26.54 [-62.23, -6.28]
Small gap0.5-0.10 [-0.38, 0.16]0.40 [-0.41, 1.25]
Small gap2-0.22 [-0.48, 0.03]-0.80 [-3.50, 1.88]
Small gap8-0.43 [-0.71, -0.17]-5.63 [-10.78, -0.87]
Five arms0.5-0.96 [-2.74, 0.62]-13.53 [-44.06, 15.00]
Five arms2-1.11 [-2.16, -0.20]-25.22 [-45.67, -8.01]
Five arms8-0.52 [-1.42, 0.13]-17.34 [-35.12, -4.69]

Both intervals favor ITM for each optimal shape in the high-shape-competitor instance. At the original k⋆=2k^\star=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⋆=8k^\star=8. For five arms they both exclude zero at k⋆=2k^\star=2, and only CVaR does at k⋆=8k^\star=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.5k^\star=0.5, there are 8 matching and 5 ITM events with exact paired p=0.55p=0.55. Severe lockouts were rare across the nine settings, with exact paired p≥0.25p\ge0.25 in each cell.

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 η=0.5\eta=0.5 remains unexplained. No constructive suggestion for selecting η\eta is provided.

AuthorsOpenReview ↗

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 nknk and scale kSkS; 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 α=−η\alpha=-\eta, the Gaussian Student-t degrees of freedom are n−2η−1n-2\eta-1, which is zero at n=2,η=0.5n=2,\eta=0.5. Such a Gaussian posterior is improper, whereas our Gamma posterior is proper almost surely after two observations for every fixed η>0\eta>0. ITM keeps the small-shape order k−1k^{-1} 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.
Reviewer_VerPOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies Thompson Sampling for Gamma bandits with unknown means and shapes, showing that a few low, nearly identical observations can make the algorithm overconfident and cause it to neglect the optimal arm. The authors propose an information tempered matching (ITM) prior that reduces weight on extremely large shape parameters while preserving the standard sampling rule. They prove that any fixed positive tempering parameter yields asymptotically optimal regret, matching the information-theoretic lower-bound constant. Experiments support the proposed mechanism, although clear improvements over the original matching prior appear only in the five-arm setting.

Critical strengths

Strength: The paper identifies a clear failure mechanism in Gamma Thompson Sampling and characterizes the precise prior-tail threshold for local recovery. It also presents an asymptotic optimality guarantee for a simple prior modification that preserves the standard Thompson Sampling rule without truncating the parameter space.

Critical weaknesses
  1. Limited empirical benefit. For ITM with (\eta=0.5), statistically supported improvements over matching TS occur in only one of the three Gamma benchmarks. Neither mean regret nor CVaR shows a statistically supported improvement in any of the six model-misspecification settings. These results do not establish a consistent practical advantage.
  2. Incomplete performance characterization. The fixed-instance asymptotic guarantee leaves worst-case finite-horizon performance unresolved. The paper provides no gap independent bound over a suitably restricted model class, so its optimality result offers no uniform guarantee as arm gaps shrink.
  3. Weak practical motivation. The paper does not identify concrete applications that justify the Gamma reward assumption. The practical significance of this distribution specific prior modification therefore remains insufficiently demonstrated.
  4. Restricted scope. The analysis is confined to a fixed finite set of arms. It does not establish whether the proposed prior design or proof techniques extend to structured bandits with infinite or continuous action spaces, limiting the demonstrated generality of the contribution.
Questions for authors

I find the contribution too narrowly scoped and its significance insufficiently established. Although the paper presents a sharp asymptotic result, the practical motivation for the Gamma setting is weak, and worst-case finite-horizon performance remains uncharacterized. The experiments do not establish a consistent advantage over matching TS, leaving insufficient evidence that the proposed prior delivers meaningful benefits beyond its specialized theoretical guarantee.

Can you address these issues in your revision?

2 comments
AuthorsOpenReview ↗

Response to Reviewer VerP: Finite-horizon guarantee and empirical results

We thank the reviewer for the helpful comments.

W2. Finite-horizon guarantee. Theorem 20 (Appendix K) proves the bound stated on p. 8 for the same uncapped information-tempered matching Thompson sampling (ITM-TS) policy. Fix η>0\eta > 0 and a compact rectangle Θ0=[μ‾,μ‾]×[k‾,k‾]⊂(0,∞)2\Theta_0=[\underline\mu,\overline\mu]\times[\underline k,\overline k]\subset(0,\infty)^2 for the true means and shapes. Uniformly over instances in that class with a unique best mean, the expected pseudo-regret satisfies

RT≤Cη,Θ0KTlog⁡(eT).R_T\le C_{\eta,\Theta_0}\sqrt{KT\log(eT)}.

The policy samples the exact posterior on the full positive quadrant and takes neither the rectangle nor the gaps as inputs.

For a threshold b∈[μ‾,μ⋆)b\in[\underline\mu,\mu^\star), let pn(b)p_n(b) be the best-arm posterior probability of drawing a mean at least bb after nn samples and put d=μ⋆−bd=\mu^\star-b. Lemma 21 gives the quantitative estimate

\le C_{\eta,\Theta_0}\bigl[1+d^{-2}\log(e+d^{-1})\bigr].$$ In the $m\le b$ part of the proof, with $m$ the sample mean, the lower incomplete-Gamma bound retains the factor $1+(1-m/b)\sqrt{nk}$ in its denominator. After integrating over the empirical mean and the shape saddlepoint, the two central terms are bounded by $C e^{-cnd^2}[(d\sqrt n)^{-1}+(nd^2)^{-1}]$. The latter produces the logarithm in the recovery bound. On $m > b$, the two Gamma divergence terms in Appendix K give exponential control in $nd^2$ on the compact central region, with a uniformly summable bound outside it. For each suboptimal arm $a$, use $b=(\mu_a+\mu^\star)/2$. A selection with a draw below $b$ is paid for by the recovery bound. Draws above $b$ are controlled with the suboptimal arm's posterior tail, with atypical histories charged at most once per sample index because a selection increments that index. Eq. (125) gives the resulting expected pull bound of order $1+\Delta_a^{-2}[\log(eT)+\log(e+\Delta_a^{-1})]$ for $T\ge2K$. With $\varepsilon=\sqrt{K\log(eT)/T}$, gaps below $\varepsilon$ contribute at most $T\varepsilon$. Summing the pull bound for the other arms gives at most $CK\log(eT)/\varepsilon$. For $T < 2K$ the bounded range of means supplies the result directly. The bound thus covers arbitrarily small positive gaps. **W1. Evidence for finite-time gains.** Section 6 (p. 10) varies the optimal shape at fixed means and competitor distributions, with 4,096 fresh pairs per cell at $T=20{,}000$. Each pair shares rewards and uses separate posterior draws. Table 12 in Appendix L gives ITM ($\eta=.5$) minus matching for the high-shape competitor, with pointwise 95% intervals from 10,000 paired resamples. Conditional value at risk (CVaR) averages the 205 largest regrets per policy and cell. | $k^\star$ | Mean regret difference | CVaR difference | |---:|---:|---:| | 0.5 | -4.48 [-7.83, -1.64] | -79.52 [-146.36, -23.89] | | 2 | -1.44 [-2.94, -0.37] | -24.14 [-53.74, -3.24] | | 8 | -1.26 [-3.05, -0.24] | -26.54 [-62.23, -6.28] | In the original high-shape cell at $k^\star=2$, the 1,024 pairs gave mean and CVaR differences of $0.24$ [-2.77, 4.05] and $7.69$ [-51.21, 82.91]. The second row gives the fresh estimates. With the high-shape competitor, both intervals lie below zero at all three tested shapes. In the original five-arm cell, the two differences were $-1.15$ [-2.39, -0.16] and $-21.52$ [-44.48, -4.39] (Table 4). In the small-gap instance, both intervals exclude zero only at $k^\star=8$. The five-arm cell at $k^\star=2$ supports both improvements, while at $k^\star=8$ the CVaR interval alone excludes zero. Under all six original model-misspecification settings, both intervals include zero (Tables 10–11). For example, the high-shape lognormal intervals are [-1.62, 0.64] for mean regret and [-29.90, 13.26] for CVaR. Severe lockouts were rare at the 5,000-round threshold, with exact paired $p\ge0.25$ across the nine settings (Appendix L, Table 13). **W3. Application.** Section 1 (p. 1) uses total energy received on the selected link over a fixed measurement window as a reward. The sum of $m$ independent exponential contributions with a common scale is Gamma with shape $m$. A Gamma model for repeated window totals treats $\mu$ and $k$ as unknown, with $\operatorname{Var}(X)/\mu^2=1/k$. Theorem 5 gives the prior-tail threshold for recovery near low, nearly constant prefixes. The shape sweep in Section 6 uses simulated rewards. **W4. Action-space scope.** Theorem 20 assumes finitely many independently modeled arms. Its regret decomposition uses a posterior draw and a sample count per arm, and the final step sums the large-gap costs over at most $K-1$ arms. A continuous-action analogue would require a shared model for means and shapes across actions and corresponding controls on optimism and recovery with data shared across those actions. The uniform result here concerns the finite-action model, including vanishing gaps on the specified compact class.
Reviewer_VerPOpenReview ↗

I will keep my score

I am keeping my score.

Reviewer_9qQbOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the lockout phenomenon in Gamma Thompson Sampling with unknown mean and shape parameters, where pessimistic and nearly identical initial observations can cause the optimal arm's posterior to become overconfident, leading to prolonged under-exploration. Such a phenomenon is attributed to the heavy tails of conventional priors, such as Jeffreys and matching priors, over the shape parameter. To address this problem, this paper proposes the Information-Tempered Matching (ITM) prior, which introduces a larger tail exponent to suppress excessively large shape values and mitigate posterior overconfidence. Through theoretical analysis and experiments, the paper demonstrates the effectiveness of ITM in alleviating the lockout phenomenon and establishes its asymptotically optimal regret guarantee.

Critical strengths
  1. This paper provides an insightful analysis of the lockout phenomenon in Gamma Thompson Sampling. It establishes a clear connection between prior tail behavior, posterior overconfidence, and prolonged under-exploration of the optimal arm.
  2. This paper derives regret lower bounds for Jeffreys, Matching and ITM priors, and proves that the proposed ITM prior achieves asymptotically optimal regret in Gamma Thompson sampling with unknown mean and shape parameters.
Critical weaknesses
  1. The methodological novelty seems to be relatively limited. Honda & Takemura (2014) and Lee et al. (2023) have proved that Jeffreys priors can lead to polynomial regret in Gaussian and Pareto cases and that more conservative priors can restore asymptotic optimality. The proposed ITM prior follows a similar principle.
  2. The experimental results provide limited evidence of the advantages of ITM priors over the matching prior, as the improvements are relatively modest in the full-bandit settings. Furthermore, all experiments are conducted on synthetic data, without evaluation on real-world datasets or applications.
Questions for authors
  1. Experiments can be further improved. It would be useful to investigate how the relative performance of ITM and matching priors varies with the shape parameters, reward gaps, and variance of the optimal arm, providing stronger evidence of how the theoretical advantages translate into actual Thompson Sampling performance.
  2. In Table 3, severe lockout events occur only once or twice in several settings among 1,024 trials. How reliable are comparisons of severe-lockout frequencies under such low event counts? Would additional trials provide a clearer distinction between ITM and matching priors?
1 comment
AuthorsOpenReview ↗

Response to Reviewer 9qQb: Gamma recovery and optimal-arm shape

We thank the reviewer for the helpful comments.

W1. What is specific to unknown-shape Gamma rewards? Honda and Takemura (2014) and Lee et al. (2023) establish that prior choice matters for Gaussian and Pareto Thompson sampling (TS). For Gamma rewards, both the mean and shape are learned. After a low and nearly constant prefix, the shape posterior puts considerable mass on large shape values. Conditional on a large shape, the mean posterior concentrates around the low sample mean. Theorem 5 gives the exact recovery threshold for this mechanism. For fixed n≥2n\ge2 and a proper posterior with shape weight w(k)∼Ck−τw(k)\sim Ck^{-\tau}, reciprocal optimism is integrable exactly for τ>1\tau > 1 when the sample-mean to threshold ratio lies in a compact subinterval of (0,1)(0,1).

The frozen calculation uses a ratio of shape integrals. Its numerator includes an incomplete-Gamma probability and remains bounded near zero empirical dispersion, while the normalizer is sensitive to the high-shape weight. The full-bandit upper bound requires summing the expected pessimism odds over all sample sizes. Theorem 8 and Lemma 16 control the high- and low-shape density regimes, respectively. Theorem 10 combines them with posterior-integral comparisons to obtain the sharp information constant for uncapped information-tempered matching (ITM) TS. Theorem 6 also transfers the frozen calculation into an ordinary-TS lower bound with a competing arm that continues updating its posterior. This yields Ω(T)\Omega(\sqrt T) for Jeffreys and a separate Ω(log⁡T)\Omega(\log T) lockout contribution for matching after two initial observations per arm.

W2 / Q1. Effect of optimal-arm shape and variance. Section 6 (p. 10) varies k⋆∈{0.5,2,8}k^\star\in\{0.5,2,8\} in each benchmark instance, holding all means and competitor distributions fixed. The best-arm variance is (μ⋆)2/k⋆(\mu^\star)^2/k^\star, so the two extremes differ by a factor of 16. The high-shape and small-gap two-arm instances have mean gaps 0.20 and 0.02. The sweep controls shape within each instance, while comparisons across instances also change competitor parameters. We use 4,096 fresh trial pairs per cell at T=20,000T=20{,}000 with shared reward streams and separate posterior draws. The paired bootstrap recomputes conditional value at risk (CVaR), the mean of the largest 205 regrets per policy and cell, in each of 10,000 resamples. Table 12 in Appendix L gives ITM minus matching with pointwise 95% intervals.

Instancek⋆k^\starMean regret differenceCVaR difference
High-shape competitor0.5-4.48 [-7.83, -1.64]-79.52 [-146.36, -23.89]
High-shape competitor2-1.44 [-2.94, -0.37]-24.14 [-53.74, -3.24]
High-shape competitor8-1.26 [-3.05, -0.24]-26.54 [-62.23, -6.28]
Small gap0.5-0.10 [-0.38, 0.16]0.40 [-0.41, 1.25]
Small gap2-0.22 [-0.48, 0.03]-0.80 [-3.50, 1.88]
Small gap8-0.43 [-0.71, -0.17]-5.63 [-10.78, -0.87]
Five arms0.5-0.96 [-2.74, 0.62]-13.53 [-44.06, 15.00]
Five arms2-1.11 [-2.16, -0.20]-25.22 [-45.67, -8.01]
Five arms8-0.52 [-1.42, 0.13]-17.34 [-35.12, -4.69]

Both intervals favor ITM across the three shapes with a high-shape competitor. At the original k⋆=2k^\star=2 setting in this instance, the 1,024-pair intervals were [-2.77, 4.05] for mean regret and [-51.21, 82.91] for CVaR (Table 4). The second row gives the fresh estimates. The small-gap cells at k⋆=0.5k^\star=0.5 and 22 have intervals spanning zero for both metrics.

Q2. Reliability of rare lockout counts. Severe lockouts were rare across the nine settings (Section 6, p. 10). An event is at least 5,000 consecutive rounds without an optimal-arm pull. Table 13 (Appendix L) gives counts, exact marginal binomial intervals, and discordant pairs. With a high-shape competitor at k⋆=0.5k^\star=0.5, matching and ITM record 8 and 5 events out of 4,096, with marginal 95% intervals of [0.084, 0.384]% and [0.040, 0.285]%. Seven pairs have an event only under matching and four only under ITM (two-sided exact paired p=0.55p=0.55). With zero observed events, the exact upper 95% endpoint is 0.090%. Counts range from 0 to 20 per policy and cell. The exact paired tests give p≥0.25p\ge0.25 in all nine cells and leave the frequency differences unresolved. In the high-shape-competitor cell at k⋆=0.5k^\star=0.5, the 95th percentile of the longest waiting time is 129 rounds for matching and 115 for ITM, both below the severe threshold.

W2. Application. The link-selection example in Section 1 (p. 1) takes XX to be the total energy received on the selected link during a fixed measurement window. A sum of mm independent exponential contributions with a common scale is Gamma with shape mm. A Gamma model for repeated window totals treats the mean μ\mu and shape kk as unknown, with Var⁡(X)/μ2=1/k\operatorname{Var}(X)/\mu^2=1/k. The shape sweep in Section 6 uses simulated rewards.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.