An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support

Abstract

Consider the problem of a controller 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. uniform random variables over some interval $[a_i,b_i]$, with the support (i.e., $a_i,b_i$) unknown to the controller. The objective is to have a policy $\pi$ for deciding, based on available data, from which of the $N$ populations to sample from 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 $\{a_i\}$ and $\{b_i\}$. In this paper, we present a simple inflated sample mean (ISM) type policy that is asymptotically optimal in the sense of its regret achieving the asymptotic lower bound of Burnetas and Katehakis (1996). Additionally, finite horizon regret bounds are given.

arXiv admin note: text overlap with arXiv:1504.05823

References in corpus (6)

• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Near-optimal Reinforcement Learning in Factored MDPs
• Optimality of Thompson Sampling for Gaussian Bandits Depends on Priors
• On Minimax Optimal Offline Policy Evaluation
• Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem
• Asymptotic Behavior of Minimal-Exploration Allocation Policies: Almost Sure, Arbitrarily Slow Growing Regret

Cited by in corpus (4)

• Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem
• Asymptotic Behavior of Minimal-Exploration Allocation Policies: Almost Sure, Arbitrarily Slow Growing Regret
• Asymptotically Optimal Sequential Experimentation Under Generalized Ranking
• Regret Minimization in Heavy-Tailed Bandits