Asymptotic optimality theory of confidence intervals of the mean

Achal Bassamboo; Sandeep Juneja; Vikas Deep

REVIEW 3 major objections 5 minor 1 cited by

Asymptotic optimality theory of confidence intervals of the mean

T0 review · 3 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Confidence intervals built by inverting KL-divergence concentration inequalities achieve the minimum possible limiting width for a mean, under a stability assumption.

desk verdict Sharp CI-width benchmark at N = k log(1/delta) with proven KL-inversion optimality for stable policies; the abstract overclaims by dropping 'stable,' and three theorem statements have a limit typo. read the letter →

arxiv 2501.19126 v4 pith:EMCACR44 submitted 2025-01-31 math.ST stat.TH

Vikas Deep , Achal Bassamboo , Sandeep Juneja This is my paper · ORCID

classification math.STstat.TH MSC 62F2562F1262B10

keywords confidenceintervalsmeanestimationKullback-Leiblerdivergenceasymptoticoptimalitylearningregimesexponentialfamilyconcentrationinequalitiesrandomsamplingcosts

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks how narrow a confidence interval for a distribution's mean can be in the limit where the error tolerance $\delta$ tends to zero and the sample size $N_\delta$ grows. It identifies three regimes: if $N_\delta$ grows slower than $\log(1/\delta)$, no interval can beat the full support; if $N_\delta/\log(1/\delta)\to k\in(0,\infty)$, every stable interval must have limiting width at least $\mu^*_R(\mu,k)-\mu^*_L(\mu,k)$, where $d(\mu,\mu^*_R)=d(\mu,\mu^*_L)=1/k$ for the family's KL divergence $d$; and if $N_\delta$ grows faster, the width can go to zero. The sharp part is that intervals built by inverting a KL-divergence concentration inequality achieve the lower bound in the middle regime and the fastest rate in the last regime. This matters because it turns the question of choosing a concentration inequality into a precise distribution-dependent floor that no stable method can cross, with extensions to bounded-support and heavy-tailed families and to random sampling costs.

What carries the argument

The load-bearing object is the rate function $d(\mu,x)$, the KL divergence between the exponential-family member with true mean $\mu$ and the member with mean $x$, which is strictly quasi-convex in $x$. The lower-bound proof uses the data-processing inequality to force any stable interval to exclude alternative means: if $\tilde\mu$ lies outside the limiting interval, then $N_\delta d(\mu,\tilde\mu)$ must be at least about $\log(1/\delta)$, giving the thresholds $1/k$. The achievability side inverts the concentration inequality $P_\mu(n d(\hat\mu_n,\mu)\ge\log(2/\delta))\le\delta$, so the interval endpoints are exactly the points where the empirical KL distance equals the threshold. For nonparametric families the same construction works with $\mathrm{KLinf}(\nu,\mathcal{P},x)$ in place of $d$.

What would settle it

Engineer a confidence-interval policy whose endpoints do not converge to constants in the $\delta\to0$ limit, for instance by adding a random offset whose size does not vanish, and test whether it maintains $1-\delta$ coverage with limiting width smaller than $\mu^*_R(\mu,k)-\mu^*_L(\mu,k)$; such a policy would break the paper's abstract-level claim that the lower bound applies to all confidence intervals.

Watch

Extended reading notes

Core claim

In the paper's own terms, the central discovery is a sharp change-of-measure lower bound: for a canonical single-parameter exponential family such as Bernoulli, Poisson, or Gaussian with known variance, whenever $N_\delta/\log(1/\delta)\to k\in(0,\infty)$ and the policy is stable, any confidence interval that covers the true mean $\mu$ with probability at least $1-\delta$ must satisfy $\mu^R-\mu^L\ge\mu^*_R(\mu,k)-\mu^*_L(\mu,k)$, with $d(\mu,\mu^*_R)=d(\mu,\mu^*_L)=1/k$. The paper further proves that the KL-inversion policy $\pi_1$ has exactly this limiting interval, so the bound is attainable. In the complete-learning regime the same policy's width collapses to zero at the rate $8\sigma^2(\mu)\log(1/\delta)/N_\delta$, which is shown to be fastest among stable policies satisfying mild technical conditions. Nonparametric families are handled by replacing $d$ with the KL infimum, and random per-sample costs replace $k$ by $k/c$, where $c$ is the mean cost.

Load-bearing premise

The paper's lower bounds assume 'stability': as the error tolerance shrinks, the interval's endpoints must settle down to fixed numbers rather than keep randomly moving; common methods like Hoeffding or empirical Bernstein satisfy this, but the paper does not prove every confidence-interval method does.

Editorial extensions

If this is right

In the sufficient-learning regime, the theorem identifies a distribution-dependent resolution limit: no stable confidence interval can be narrower than $[\mu^*_L(\mu,k),\mu^*_R(\mu,k)]$, and the KL-inversion policy attains it exactly.
For a fixed sample budget, the optimal width decreases as $k=N_\delta/\log(1/\delta)$ grows, and the paper gives the precise functional form through the inverse KL divergence.
In the complete-learning regime, the rate of shrinking is not arbitrary: for stable policies satisfying the technical conditions, $\mathrm{width}^2\,N_\delta/\log(1/\delta)$ must be at least $8\sigma^2(\mu)$, and $\pi_1$ achieves equality.
If each sample costs a random amount with mean $c$, the same three regimes hold with the effective sample rate $C_\delta/\log(1/\delta)$ divided by $c$, and the cost distribution's shape does not enter the limit.
For bounded-support and $(1+\epsilon)$-moment-bounded families, KLinf-based inversion intervals are asymptotically optimal in the same sense, giving a uniform recipe across parametric and nonparametric settings.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's 'any CI' language is formally restricted to stable policies, so the key open question is whether every admissible confidence-interval policy is stable or whether an adaptive unstable rule can beat the bound; that question is directly testable.
Because the lower bound uses only the data-processing inequality, the same three-regime picture should transfer to other estimation targets such as variance, quantiles, or linear functionals whenever a KL-type rate function exists.
In finite samples, the complete-learning constant $8\sigma^2$ gives a practical target: compare a candidate interval's squared width times $N_\delta/\log(1/\delta)$ against this constant to detect suboptimal methods before the asymptotic regime fully sets in.
The cost-invariance result suggests that in simulation or cloud-sampling applications, effort spent reshaping the distribution of per-sample costs will not change the limiting confidence-interval width; only reducing the average cost will.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the take: this is the first sharp characterization of how fast confidence intervals for a mean can shrink when N grows like k log(1/delta), and the KL-inversion policy pi_1 provably attains it. The DPI-based lower bound is real, the stability condition is what makes it work, and the factor-two improvement over Shekhar-Ramdas in the Gaussian case checks out. It deserves a serious referee.

What's genuinely good: the three-regime picture is clean and correct as stated for stable policies. The stability assumption (Definition 1) is the right tool to make the limiting width a deterministic constant, and it is genuinely mild in practice—Hoeffding, Bernstein, and empirical Bernstein all satisfy it. The lower-bound proof via data processing inequality is coherent: choose alternate environments on both sides, combine left and right deviations, get d(mu, endpoints) >= 1/k. The upper bound uses existing KL concentration inequalities and matches. The random-cost extension with renewal theory and anytime-valid confidence sequences is a solid bonus, and the numerical experiments confirm the comparison you'd expect.

Where it's soft: the abstract and introduction advertise the result for 'any CI construction method,' but Theorem 1 is for stable policies only. That is not a trivial restriction. The proof's step (14) needs P_nu(E_delta) -> 1, which follows from endpoint convergence to constants; if a policy's endpoints converge to a random pair, the DPI argument gives a weaker bound and the contradiction fails. The appendix shows popular methods are stable, but it does not prove stability is without loss of generality. I don't think the stable-policy theorem is wrong, but the universal claim in the abstract is not established. That's the main thing to fix before publication.

Second, Theorems 4(c), 8(c), and 9(c) state the complete-learning condition as C_delta/log(1/delta) -> 0, which is exactly the no-learning regime; the proofs and the rest of the paper clearly require -> infinity. This is a typo, but it's in three theorem statements and would confuse a reader.

Minor: several proofs defer to external results, and the rate-optimal theorem in the complete-learning regime is restricted to the extra class Pi_sr_CI with its own technical assumptions. That's not a fatal flaw, but it's a narrower result than the introduction implies.

Who it's for: anyone working on confidence intervals, concentration inequalities, or bandit-style learning. The core contribution is the sharp benchmark and the KL-inversion optimality. I would send it to a good statistics journal. My recommendation: accept the stable-policy theorem as a real result, but make the authors either extend the no-stability case or clearly state that the lower bound applies only within the stable class. Fix the typos. Then it's publishable.

Referee Report

3 major / 5 minor

Summary. The paper studies the minimal achievable asymptotic width of confidence intervals for the mean under the scaling N_delta / log(1/delta) tending to 0, to k in (0, infinity), or to infinity. For canonical single-parameter exponential families and, later, bounded-support and (1+epsilon)-moment families, it proves lower bounds on the limiting width for policies satisfying a stability assumption (Definition 1), and shows that the KL-divergence-inversion policy pi_1 attains the lower bound in the sufficient-learning regime and has zero limiting width in the complete-learning regime. The framework is extended to random sampling costs, where the cost budget C_delta replaces the sample size and the limiting width depends only on the mean cost, and to one-sided intervals. The core proof uses the data-processing inequality with alternate distributions together with endpoint convergence from stability.

Significance. If the stated theorems are read for the class of stable policies, the paper gives a sharp, distribution-dependent lower bound on limiting CI width in the log(1/delta) regime and identifies a simple KL-based construction that matches it. This is a genuinely useful refinement of the loose non-asymptotic bound of Shekhar and Ramdas, and the factor-of-two improvement in the Gaussian case is clearly explained. The random-cost generalization, showing invariance to the cost distribution beyond its mean, is a nice addition. The paper is careful in several places: it states the stability assumption explicitly, proves that pi_1 is stable and matches the bound, and provides explicit verification of stability for Hoeffding, Bernstein, and empirical-Bernstein intervals. However, the advertised claim in the abstract and introduction that the characterization holds for 'any CI' is not supported: the proofs and theorems apply to the proper subclass Pi^s_CI of stable policies, and no without-loss-of-generality argument is supplied.

major comments (3)

[Abstract, Section 1, Definition 1, Theorem 1] The paper consistently advertises the result as applying to 'any CI construction method/policy', but the theorems are for the class Pi^s_CI of stable policies defined in Definition 1. The load-bearing step is Eq. (14) in the proof of Theorem 1, where lim P_nu(E_delta)=1 is used; this follows from the stability requirement that the endpoints converge in probability to constants. For a policy whose endpoints converge in distribution to a non-degenerate random pair, P_nu(E_delta) can stay bounded below 1, and the DPI argument no longer yields d(mu, mu_L) >= 1/k. The appendix shows that Hoeffding, Bernstein, and empirical-Bernstein intervals are stable, but it does not prove that stability is without loss of generality or exhibit an unstable policy with smaller width. The abstract and introduction should be revised to claim optimality only for stable policies, or a WLOG argument for stability must be provided.
[Theorems 4(c), 8(c), 9(c)] These three statements give the complete-learning condition as lim C_delta/log(1/delta) -> 0 and then claim the limiting width is zero. This is inconsistent with the rest of the paper: part (b) of each theorem treats the sufficient regime where the ratio tends to k in (0, infinity), Remark 1 identifies the complete regime as the ratio tending to infinity, and Theorem 2(c) states the corresponding condition as N_delta/log(1/delta) -> infinity. As printed, the three parts are false; the proofs and surrounding text indicate that the intended condition is lim C_delta/log(1/delta) -> infinity. This is a theorem-statement error that must be corrected before publication.
[Appendix C, Theorems 6-7] The claim that pi_1 achieves the fastest rate of convergence in the complete-learning regime is established only on the restricted class Pi^sr_CI, which adds assumptions on the scaled distance between the estimator and the interval endpoints. The paper does not prove that these assumptions hold for all stable policies or that every reasonable CI policy belongs to this class. The text in Section 4.1 and the conclusions states 'under certain technical assumptions', which is accurate, but the abstract's broader wording about the fastest rate should be aligned with the actual quantification over Pi^sr_CI.

minor comments (5)

[Appendix A] The proof of Theorem 1 cites 'Lemma 0.1 in Kaufmann (2020)', but the reference list does not include Kaufmann (2020); only Kaufmann and Koolen (2021) is listed.
[Appendix E] The proof following Theorem 8 is headed 'Proof of Theorem 9' and refers to 'the proof of and Theorem 4'; both appear to be typographical errors and should be corrected to 'Proof of Theorem 8' and 'the proof of Theorem 4'.
[Section 8, Table 1] The notation 'max 95% CI width: 0.0001' is unclear; it presumably indicates Monte Carlo standard error or a confidence bound on the reported average widths, but this should be stated explicitly.
[Appendix, 'Discussion on stable policies'] The stability verification for the Bernstein interval writes the limiting half-width as sigma sqrt(2/k) + 2/(3k), which follows from the displayed formula, but the intermediate expression '4/(3k)' for the full width could be made clearer by explicitly identifying the half-width.
[Section 1 and Section 4] The phrase 'the limiting width of the CI collapses to zero' in the introduction applies to the optimal policy pi_1, not to every stable policy; a policy that always outputs the full support is stable and has nonzero limiting width, so the wording should be qualified.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: lower and upper bounds are independently derived; stability restriction and theorem typos are scope or correctness issues, not circular reductions.

full rationale

The derivation chain is self-contained against external benchmarks. The lower bound (Theorem 1(b)) is obtained from the data processing inequality (13), with alternate environments whose means lie outside the limiting interval; the stability assumption is used only to get P_nu(E_delta) to 1 and hence phi/log(1/delta) to 1, forcing d(mu, mu_L), d(mu, mu_R) >= 1/k. No fitted quantity appears: the threshold 1/k is the limit N_delta/log(1/delta), not an estimated parameter. The matching upper bound (Theorem 2(b)) uses the standard KL concentration inequality P(n d(muhat_n, mu) >= log(2/delta)) <= delta from Menard-Garivier and Busa-Fekete et al.; beta(delta) = log(2/delta) is the known finite-sample threshold, not chosen to match the lower bound. The nonparametric extensions similarly rest on KLinf concentration inequalities of Agrawal, Orabona-Jun, and Jourdan et al. The only self-citation is Glynn and Juneja (2013), used as background on large deviations in random-cost settings; it is not load-bearing. The stability restriction is explicit (Definition 1), and the paper does not claim to prove every CI policy is stable; the abstract's 'any CI' phrasing is looser than the theorem, but this is a scope or correctness gap, not circularity. Theorems 4(c), 8(c), and 9(c) state the complete-learning condition as C_delta/log(1/delta) -> 0 where the proofs require -> infinity; this is a typo in the stated limit, again a correctness issue rather than a circular reduction. No step reduces by definition or by self-citation to its own input.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No free parameters are fitted to data: k, c, delta, epsilon, and Gamma are inputs or family parameters; the central claim does not depend on fitted constants. The central claim rests on standard information-theoretic inequalities plus the paper's stability assumption and external concentration bounds; no new physical or statistical entities are introduced.

assumptions (7)

standard math Data processing inequality in the change-of-measure form N_delta d(mu, mu_tilde) >= phi(P_nu(E_delta), P_nu_tilde(E_delta))
This is Eq. (1) and Eq. (13) in the proof of Theorem 1, and it is the key lower-bound engine.
domain assumption Stable policy assumption: CI endpoints converge in probability to deterministic constants mu_pi_L(nu) and mu_pi_R(nu) as delta tends to 0
Definition 1 and Definition 2 restrict the policy class, and all lower-bound theorems apply only to this class.
domain assumption Canonical single-parameter exponential family S with strictly convex b(theta), and d(mu, x) strictly quasi-convex and jointly continuous
Section 3 states these properties, and they guarantee unique solutions to d(mu, mu*_L) = d(mu, mu*_R) = 1/k.
domain assumption KL_inf(nu, P, x) is strictly convex and jointly continuous for P = B and P = H
Appendix F and G cite Honda-Takemura, Jourdan et al., and Agrawal for these properties, which are needed for Theorems 5, 8, and 9.
domain assumption Anytime-valid concentration inequalities: P_nu(exists n: n d(mu_hat_n, mu) >= beta(n, delta)) <= delta, and the analogous KL_inf version
Eq. (25) from Kaufmann-Koolen and Eq. (29) from Agrawal are used to prove coverage of pi_hat_1 and pi^h_1.
standard math Renewal theorem and Wald's lemma: E[tau_delta]/C_delta tends to 1/c, and the data processing inequality holds at the stopping time tau_delta + 1
Eq. (21) and (23) in the proof of Theorem 3 convert the cost budget into an effective sample size.
domain assumption Rate conditions in the class Pi^sr_CI: the estimator satisfies a central limit theorem and interval endpoints converge at the rate sqrt(log(1/delta)/N_delta)
Appendix C introduces these conditions to derive the complete-learning rate lower bound in Theorem 6.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Asymptotic optimality theory of confidence intervals of the mean." pith.science (2026). https://pith.science/paper/EMCACR44

@misc{pith2026250119126,
  author       = {Pith},
  title        = {Pith review of: Asymptotic optimality theory of confidence intervals of the mean},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EMCACR44}},
  note         = {Machine review of arXiv:2501.19126}
}

abstract

We address the classical problem of constructing confidence intervals (CIs) for the mean of a distribution, given $N$ i.i.d. samples, such that the CI contains the true mean with probability at least $1 - \delta$, where $\delta \in (0,1)$. We characterize three distinct learning regimes based on the minimum achievable limiting width of any CI as the sample size $N_{\delta} \to \infty$ and $\delta \to 0$. In the first regime, where $N_{\delta}$ grows slower than $\log(1/\delta)$, the limiting width of any CI equals the width of the distribution's support, precluding meaningful inference. In the second regime, where $N_{\delta}$ scales as $\log(1/\delta)$, we precisely characterize the minimum limiting width, which depends on the scaling constant. In the third regime, where $N_{\delta}$ grows faster than $\log(1/\delta)$, complete learning is achievable, and the limiting width of the CI collapses to zero, converging to the true mean. We demonstrate that CIs derived from concentration inequalities based on Kullback--Leibler (KL) divergences achieve asymptotically optimal performance, attaining the minimum limiting width in both sufficient and complete learning regimes for distributions in two families: single-parameter exponential and bounded support. Additionally, these results extend to one-sided CIs, with the width notion adjusted appropriately. Finally, we generalize our findings to settings with random per-sample costs, motivated by practical applications such as stochastic simulators and cloud service selection. Instead of a fixed sample size, we consider a cost budget $C_{\delta}$, identifying analogous learning regimes and characterizing the optimal CI construction policy.

Figures

Figures reproduced from arXiv: 2501.19126 by the authors.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Beyond First-order Asymptotics in Sequential Mean Testing
stat.ME 2026-06 unverdicted novelty 7.0 of 10

Establishes CLT for stopping time of KL_inf sequential test for bounded means, with sqrt(log(1/alpha))-scaled convergence to explicit Gaussian variance.

Reference graph

Works this paper leans on

35 extracted references · 26 canonical work pages · cited by 1 Pith paper

[1]

Agrawal, S. (2022). Bandits with heavy tails algorithms analysis and optimality

work page 2022
[2]

Amin, K., Kearns, M., Key, P., and Schwaighofer, A. (2012). Budget optimization for sponsored search: Censored learning in mdps. arXiv preprint arXiv:1210.4847

arXiv 2012
[3]

Audibert, J.-Y., Munos, R., and Szepesv \'a ri, C. (2009). Exploration--exploitation tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science , 410(19):1876--1902

work page 2009
[4]

Bennett, G. (1962). Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association , 57(297):33--45

work page 1962
[5]

Bickel, P. J. and Doksum, K. A. (2015). Mathematical statistics: basic ideas and selected topics, volumes I--II package . Chapman and Hall/CRC

work page 2015
[6]

and Gassiat, E

Boucheron, S. and Gassiat, E. (2009). A bernstein-von mises theorem for discrete probability distributions

work page 2009
[7]

Busa-Fekete, R., Fotakis, D., Sz \"o r \'e nyi, B., and Zampetakis, M. (2019). Optimal learning of mallows block model. In Proceedings of the Conference on Learning Theory , pages 529--532. PMLR

work page 2019
[8]

and Berger, R

Casella, G. and Berger, R. L. (2024). Statistical Inference . CRC Press

work page 2024

Show all 35 references

[9]

Catoni, O. (2012). Challenging the empirical mean and empirical variance: a deviation study. In Annales de l'IHP Probabilit \'e s et statistiques , volume 48, pages 1148--1185

2012
[10]

Chen, P., Jin, X., Li, X., and Xu, L. (2021). A generalized catoni’s m-estimator under finite -th moment assumption with (1, 2) . Electronic Journal of Statistics , 15(2):5523--5544

2021
[11]

Chick, S. E. and Inoue, K. (2001). New two-stage and sequential procedures for selecting the best simulated system. Operations Research , 49(5):732--743

2001
[12]

Cover, T. M. and Thomas, J. A. (1991). Elements of Information Theory . Wiley-Interscience, New York

1991
[13]

and Capp \'e , O

Garivier, A. and Capp \'e , O. (2011). The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory , pages 359--376. JMLR Workshop and Conference Proceedings

2011
[14]

Glynn, P. W. and Juneja, S. (2013). Asymptotic simulation efficiency based on large deviations. ACM Transactions on Modeling and Computer Simulation (TOMACS) , 23(3):1--16

2013
[15]

Gupta, S., Lee, J., Price, E., and Valiant, P. (2023). Minimax-optimal location estimation. Advances in Neural Information Processing Systems , 36:900--915

2023
[16]

Hoeffding, W. (1994). Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding , pages 409--426

1994
[17]

and Takemura, A

Honda, J. and Takemura, A. (2010). An asymptotically optimal bandit algorithm for bounded support models. In COLT , pages 67--79. Citeseer

2010
[18]

Jourdan, M., Degenne, R., Baudry, D., de Heide, R., and Kaufmann, E. (2022). Top two algorithms revisited. Advances in Neural Information Processing Systems , 35:26791--26803

2022
[19]

Kaufmann, E. (2020). Contributions to the Optimal Solution of Several Bandit Problems . PhD thesis, Universit \'e de Lille

2020
[20]

and Koolen, W

Kaufmann, E. and Koolen, W. M. (2021). Mixture martingales revisited with applications to sequential tests and confidence intervals. Journal of Machine Learning Research , 22(246):1--44

2021
[21]

and Pontil, M

Maurer, A. and Pontil, M. (2009). Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.3740

2009 arXiv
[22]

and Garivier, A

M \'e nard, P. and Garivier, A. (2017). A minimax and asymptotically optimal algorithm for stochastic bandits. In Proceedings of the International Conference on Algorithmic Learning Theory , pages 223--237. PMLR

2017
[23]

and Jun, K.-S

Orabona, F. and Jun, K.-S. (2023). Tight concentrations and confidence sequences from the regret of universal portfolio. IEEE Transactions on Information Theory

2023
[24]

and Ramdas, A

Shekhar, S. and Ramdas, A. (2023). On the near-optimality of betting confidence sets for bounded means. arXiv preprint arXiv:2310.01547

2023 arXiv
[25]

R., and Key, P

Tran-Thanh, L., Stavrogiannis, L., Naroditskiy, V., Robu, V., Jennings, N. R., and Key, P. (2014). Efficient regret bounds for online bid optimisation in budget-limited sponsored search auctions. In uai2014, 30th Conf. on Uncertainty in AI

2014
[26]

and Ramdas, A

Waudby-Smith, I. and Ramdas, A. (2024). Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society Series B: Statistical Methodology , 86(1):1--27

2024
[27]

Xia, Y., Li, H., Qin, T., Yu, N., and Liu, T.-Y. (2015). Thompson sampling for budgeted multi-armed bandits. arXiv preprint arXiv:1505.00146

2015 arXiv
[28]

Agrawal, S. (2022). Bandits with Heavy Tails: Algorithms, Analysis and Optimality . PhD thesis, Tata Institute of Fundamental Research, Mumbai

2022
[29]

Cai, T. T. (2005). One-sided confidence intervals in discrete distributions. Journal of Statistical Planning and Inference , 131(1):63--88

2005
[30]

and Berger, R

Casella, G. and Berger, R. (2024). Statistical Inference . CRC Press

2024
[31]

T. M. Cover and J. A. Thomas, Elements of Information Theory , Wiley-Interscience, New York, 1991

1991
[32]

Kaufmann, E., Capp \'e , O., and Garivier, A. (2016). On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research , 17(1):1--42

2016
[33]

and Szepesv \'a ri, C

Lattimore, T. and Szepesv \'a ri, C. (2020). Bandit algorithms . Cambridge University Press

2020
[34]

Ménard and A

P. Ménard and A. Garivier, ``A minimax and asymptotically optimal algorithm for stochastic bandits,'' in Proceedings of the International Conference on Algorithmic Learning Theory, pp. 223--237, PMLR, 2017

2017
[35]

Busa-Fekete, D

R. Busa-Fekete, D. Fotakis, B. Szörényi, and M. Zampetakis, ``Optimal learning of Mallows block model,'' in Proceedings of the Conference on Learning Theory, pp. 529--532, PMLR, 2019

2019

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [1]

Agrawal, S. (2022). Bandits with heavy tails algorithms analysis and optimality

work page 2022

[2] [2]

Amin, K., Kearns, M., Key, P., and Schwaighofer, A. (2012). Budget optimization for sponsored search: Censored learning in mdps. arXiv preprint arXiv:1210.4847

arXiv 2012

[3] [3]

Audibert, J.-Y., Munos, R., and Szepesv \'a ri, C. (2009). Exploration--exploitation tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science , 410(19):1876--1902

work page 2009

[4] [4]

Bennett, G. (1962). Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association , 57(297):33--45

work page 1962

[5] [5]

Bickel, P. J. and Doksum, K. A. (2015). Mathematical statistics: basic ideas and selected topics, volumes I--II package . Chapman and Hall/CRC

work page 2015

[6] [6]

and Gassiat, E

Boucheron, S. and Gassiat, E. (2009). A bernstein-von mises theorem for discrete probability distributions

work page 2009

[7] [7]

Busa-Fekete, R., Fotakis, D., Sz \"o r \'e nyi, B., and Zampetakis, M. (2019). Optimal learning of mallows block model. In Proceedings of the Conference on Learning Theory , pages 529--532. PMLR

work page 2019

[8] [8]

and Berger, R

Casella, G. and Berger, R. L. (2024). Statistical Inference . CRC Press

work page 2024