Thompson Sampling for 1-Dimensional Exponential Family Bandits
Thompson Sampling has been demonstrated in many complex bandit models, however the theoretical guarantees available for the parametric multi-armed bandit are still limited to the Bernoulli case. Here we extend them by proving asymptotic optimality of the algorithm using the Jeffreys prior for 1-dimensional exponential family bandits. Our proof builds on previous work, but also makes extensive use of closed forms for Kullback-Leibler divergence and Fisher information (and thus Jeffreys prior) available in an exponential family. This allow us to give a finite time exponential concentration inequality for posterior distributions on exponential families that may be of interest in its own right. Moreover our analysis covers some distributions for which no optimistic algorithm has yet been proposed, including heavy-tailed exponential families.
Code (0)
등록된 구현이 없습니다.
Tasks
Thompson SamplingSimilar Papers 제목 키워드 기반
Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits
We study the regret of Thompson sampling (TS) algorithms for exponential family bandits, where the reward distribution is from a one-dimensional exponential family, which covers many common reward distributions including…
Multi-Armed BanditsThompson SamplingSPRT-based Efficient Best Arm Identification in Stochastic Bandits
This paper investigates the best arm identification (BAI) problem in stochastic multi-armed bandits in the fixed confidence setting. The general class of the exponential family of bandits is considered. The existing algo…
Multi-Armed BanditsThompson SamplingAchieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling
We study the problem of $K$-armed bandits with reward distributions belonging to a one-parameter exponential distribution family. In the literature, several criteria have been proposed to evaluate the performance of such…
Multi-Armed BanditsThompson SamplingGeneralized Thompson Sampling for Contextual Bandits
Thompson Sampling, one of the oldest heuristics for solving multi-armed bandits, has recently been shown to demonstrate state-of-the-art performance. The empirical success has led to great interests in theoretical unders…
Multi-Armed BanditsThompson SamplingThompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox
We consider Thompson Sampling (TS) for linear combinatorial semi-bandits and subgaussian rewards. We propose the first known TS whose finite-time regret does not scale exponentially with the dimension of the problem. We …
Thompson Sampling