Boundary crossing probabilities for general exponential families

DOI10.3103/S1066530718010015zbMATH Open1395.62248arXiv1705.08814WikidataQ115488668 ScholiaQ115488668MaRDI QIDQ722599FDOQ722599

Authors: Odalric-Ambrym Maillard 

Publication date: 27 July 2018

Published in: Mathematical Methods of Statistics (Search for Journal in Brave)

Abstract: We consider parametric exponential families of dimension $K$ on the real line. We study a variant of extit{boundary crossing probabilities} coming from the multi-armed bandit literature, in the case when the real-valued distributions form an exponential family of dimension $K$. Formally, our result is a concentration inequality that bounds the probability that $mathcal{B}^{p}si(hathet{a}_n,het{a}^{s}tar)geqf(t/n)/n$, where $het{a}^{s}tar$ is the parameter of an unknown target distribution, $hathet{a}_n$ is the empirical parameter estimate built from $n$ observations, $psi$ is the log-partition function of the exponential family and $mathcal{B}^{p}si$ is the corresponding Bregman divergence. From the perspective of stochastic multi-armed bandits, we pay special attention to the case when the boundary function $f$ is logarithmic, as it is enables to analyze the regret of the state-of-the-art KLUCB and KLUCBp 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 multi-armed bandits.

Full work available at URL: https://arxiv.org/abs/1705.08814

Recommendations

• Boundary crossing for general exponential families
• Boundary crossing probabilities and statistical applications
• scientific article; zbMATH DE number 1218890
• Boundary crossing probability for Brownian motion and general boundaries
• On boundary crossing probabilities for diffusion processes
• Approximations for the boundary crossing probabilities of moving sums of random variables
• Boundary crossing probabilities for locally Poisson processes

zbMATH Keywords

optimalityexponential familiesmulti-armed banditsBregman concentration

Mathematics Subject Classification ID

Sequential statistical analysis (62L10) Sequential estimation (62L12) Stopping times; optimal stopping problems; gambling theory (60G40)

Cites Work

• Exploration-exploitation tradeoff using variance estimates in multi-armed bandits
• Sequential Tests of Statistical Hypotheses
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotically efficient adaptive allocation rules
• Title not available (Why is that?)
• Some aspects of the sequential design of experiments
• Finite-time analysis of the multiarmed bandit problem
• Sample mean based index policies by O(log n) regret for the multi-armed bandit problem
• Kullback-Leibler upper confidence bounds for optimal sequential allocation
• Regret analysis of stochastic and nonstochastic multi-armed bandit problems
• Adaptive treatment allocation and the multi-armed bandit problem
• Optimal Adaptive Policies for Markov Decision Processes
• On a Criterion for the Rejection of Observations and the Distribution of the Ratio of Deviation to Sample Standard Deviation
• Boundary crossing problems for sample means
• Dominant measures and Sanov's theorem

Cited In (3)

• Boundary crossing random variables related to quantile convergence
• Boundary crossing problems for sample means
• Boundary crossing for general exponential families

This page was built for publication: Boundary crossing probabilities for general exponential families

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722599)