Normal bandits of unknown means and variances

Abstract

Consider the problem of sampling sequentially from a finite number of N ≥ 2 populations, specified by random variables Xki, i = 1,...,N; and k = 1,2,..., where Xki denotes the outcome from population i the kth time it is sampled. It is assumed that for each fixed i, {Xki}k≥1 is a sequence of i.i.d. normal random variables, with unknown mean µi and unknown variance σi2. The objective is to have a policy π for deciding from which of the N populations to sample from at any time t = 1,2, ... so as to maximize the expected sum of outcomes of n total samples or equivalently to minimize the regret due to lack on information of the parameters µi and σi2. 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 (1996b). Additionally, finite horizon regret bounds are given.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 63 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.