# An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support

arXiv: https://arxiv.org/abs/1505.01918 · HTML: https://mlsanity.com/paper/1505.01918/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2015.

## Built on by (most cited first, 4 of 4)

- [Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2102.03734/) (2021)
- [Extreme Value Monte Carlo Tree Search for Classical Planning](https://mlsanity.com/paper/2405.18248/) (2024)
- [The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models](https://mlsanity.com/paper/2302.14407/) (2023)
- [Reliable Scale-Free Bandits via Empirical Likelihood](https://mlsanity.com/paper/2610.18055/) (2026)

## Abstract (arXiv)

Consider the problem of a controller sampling sequentially from a finite number of N ≥ 2 populations, specified by random variables Xik,  i = 1,ldots , N, and k = 1, 2, ldots; where Xik denotes the outcome from population i the kth time it is sampled. It is assumed that for each fixed i,  Xik k ≥ 1 is a sequence of i.i.d. uniform random variables over some interval [ai, bi], with the support (i.e., ai, bi) unknown to the controller. The objective is to have a policy π for deciding, based on available data, from which of the N populations to sample from at any time n=1,2,ldots 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  ai  and  bi . 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.