Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem

Abstract

Consider the problem of sampling sequentially from a finite number of $N\ge 2$ populations, specified by random variables $X_k^i$, $i=1,\dots ,N,$ and $k=1,2,\dots$; where $X_k^i$ denotes the outcome from population $i$ the $k^{th}$ time it is sampled. It is assumed that for each fixed $i$, $\{X_k^i{\}}_{k\ge 1}$ is a sequence of i.i.d. normal random variables, with unknown mean ${\mu }_i$ and unknown variance ${\sigma }_i^2$. The objective is to have a policy $\pi$ for deciding from which of the $N$ populations to sample form at any time $n=1,2,\dots$ so as to maximize the expected sum of outcomes of $n$ samples or equivalently to minimize the regret due to lack on information of the parameters ${\mu }_i$ and ${\sigma }_i^2$. In this paper, we present a simple inflated sample mean (ISM) index policy that is asymptotically optimal in the sense of Theorem 4 below. This resolves a standing open problem from Burnetas and Katehakis (1996). Additionally, finite horizon regret bounds are given.

arXiv comment15 pages 3 figures

References in corpus (7)

• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• The best of both worlds: stochastic and adversarial bandits
• Near-optimal Reinforcement Learning in Factored MDPs
• Optimality of Thompson Sampling for Gaussian Bandits Depends on Priors
• An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support
• On Minimax Optimal Offline Policy Evaluation
• Asymptotic Behavior of Minimal-Exploration Allocation Policies: Almost Sure, Arbitrarily Slow Growing Regret

Cited by in corpus (4)

• An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support
• Asymptotic Behavior of Minimal-Exploration Allocation Policies: Almost Sure, Arbitrarily Slow Growing Regret
• Online A-Optimal Design and Active Linear Regression
• Asymptotically Optimal Sequential Experimentation Under Generalized Ranking