Abstract: I show a simple expression of the Mill's ratio of the Student's t-Distribution. I use it to prove Conjecture 1 in P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., 47(2-3):235--256, May 2002.
Introduction
In probability theory and statistics, Mill’s ratio—the ratio of a distribution's survival function to its probability density function (PDF)—is a fundamental tool for characterizing tail behavior. While the Mill’s ratio for the standard Gaussian distribution is well-documented and easily bounded, the Student’s $t$-distribution presents a more significant challenge. Due to its "heavy tails," the $t$-distribution is frequently employed in scenarios where population variance is unknown, making it a staple of robust statistical inference and machine learning.
One critical application of these tail bounds is in the field of Multi-Armed Bandits (MAB). In their seminal 2002 work, Auer, Cesa-Bianchi, and Fischer provided a finite-time analysis of the Upper Confidence Bound (UCB) algorithm. However, their proof relied on a specific tail bound conjecture (Conjecture 1) that lacked a formal, simple proof for over a decade. This paper provides that missing link by deriving a simple, elegant upper bound for the Mill’s ratio of the Student’s $t$-distribution.
Methodology
The derivation relies on a purely analytical approach, utilizing two primary mathematical components to simplify the complex integrals associated with the $t$-distribution.
1. The Technical Lemma
The foundation of the proof is a specific inequality involving exponential functions. The author establishes Lemma 1: $$x \frac{e^{x^2/2}}{\sqrt{e^{x^2}-1}} \leq x+1$$ This inequality serves as the analytical engine required to bound the transformed integral in later steps.
2. Change of Variables
The Student’s $t$-distribution PDF involves polynomial decay, which is traditionally difficult to compare to exponential bounds. To bridge this gap, the author employs a clever change of variables: $$z = \sqrt{\nu \log\left(1 + \frac{x^2}{\nu}\right)}$$ This transformation effectively maps the heavy-tailed $t$-distribution into a space where its behavior can be analyzed using Gaussian-like techniques. By applying this mapping, the author is able to utilize the previously derived lemma to establish a tractable upper bound.
Key Results
The paper yields two primary theoretical contributions that simplify the calculation of tail probabilities for $t$-distributions.
Theorem 1: Upper Bound for Mill's Ratio
The author derives a concrete upper bound for the Mill's ratio of a Student's $t$ random variable with $\nu$ degrees of freedom. For $a \geq 0$, the ratio is bounded by: $$\sqrt{1 + \frac{a^2}{\nu}} \left( \frac{1}{2} + \frac{1}{\sqrt{\nu}} \right)$$ This expression is significantly simpler than the standard formulations involving Gamma functions, providing a clear algebraic tool for researchers.
Corollary 1: Proof of the Auer et al. Conjecture
By applying the derived Mill's ratio bound, the author formally proves the conjecture required for the finite-time analysis of UCB algorithms. Specifically, for a Student’s $t$ random variable $X$: $$P[X \geq a] \leq e^{-a^2/4}$$ This inequality holds for a range of $a$ up to approximately $\sqrt{2\nu}$, which is the exact regime required for the multi-armed bandit proofs in the original 2002 paper. This result confirms that the heuristic bounds used in bandit theory for years are mathematically sound.
Discussion and Conclusion
The primary insight of this work is the "Gaussian-ish" transformation, which provides a bridge between polynomial and exponential decay. While the derived bounds are upper bounds rather than exact expressions, their simplicity makes them highly practical for theoretical computer science and statistics.
Future research may explore whether this specific change of variables can be applied to other heavy-tailed distributions within the Pearson family. While tighter bounds may exist, they often come at the cost of the mathematical elegance and ease of use achieved here. By closing the loop on the Auer et al. conjecture, this paper solidifies the theoretical foundations of one of the most important algorithms in reinforcement learning.
Summary updated