Boundary Crossing for General Exponential Families
[edit]
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:151184, 2017.
Abstract
We consider parametric exponential families of dimension $K$ on the real line. We study a variant of boundary crossing probabilities coming from the multiarmed bandit literature, in the case when the realvalued distributions form an exponential family of dimension $K$. Formally, our result is a concentration inequality that bounds the probability that $\mathcal{B}^\psi(\hat \theta_n,\theta^\star)\geq f(t/n)/n$, where $\theta^\star$ is the parameter of an unknown target distribution, $\hat \theta_n$ is the empirical parameter estimate built from $n$ observations, $\psi$ is the logpartition function of the exponential family and $\mathcal{B}^\psi$ is the corresponding Bregman divergence. From the perspective of stochastic multiarmed bandits, we pay special attention to the case when the boundary function $f$ is logarithmic, as it enables to analyze the regret of the stateoftheart KLucb and KLucb+ strategies, whose analysis was left open in such generality. Indeed, previous results only hold for the case when $K=1$, while we provide results for arbitrary finite dimension $K$, thus considerably extending the existing results. Perhaps surprisingly, we highlight that the proof techniques to achieve these strong results already existed three decades ago in the work of T.L. Lai, and were apparently forgotten in the bandit community. We provide a modern rewriting of these beautiful techniques that we believe are useful beyond the application to stochastic multiarmed bandits.
Related Material


