Asymptotic Behavior of Minimal-Exploration Allocation Policies: Almost Sure, Arbitrarily Slow Growing Regret

Abstract

The purpose of this paper is to provide further understanding into the structure of the sequential allocation ("stochastic multi-armed bandit", or MAB) problem by establishing probability one finite horizon bounds and convergence rates for the sample (or "pseudo") regret associated with two simple classes of allocation policies $\pi$. For any slowly increasing function $g$, subject to mild regularity constraints, we construct two policies (the $g$-Forcing, and the $g$-Inflated Sample Mean) that achieve a measure of regret of order $O(g(n))$ almost surely as $n\to \infty$, bound from above and below. Additionally, almost sure upper and lower bounds on the remainder term are established. In the constructions herein, the function $g$ effectively controls the "exploration" of the classical "exploration/exploitation" tradeoff.

References in corpus (3)

• Optimality of Thompson Sampling for Gaussian Bandits Depends on Priors
• An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support
• Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem

Cited by in corpus (4)

• An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support
• Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem
• Asymptotically Optimal Sequential Experimentation Under Generalized Ranking
• On First-Order Bounds, Variance and Gap-Dependent Bounds for Adversarial Bandits