The multi-armed bandit problem: an efficient nonparametric solution

DOI10.1214/19-AOS1809MaRDI QIDQ2176624zbMATH OpenOpenAlexFDO

Authors Hock Peng Chan

Publication date 5 May 2020

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.08285, https://projecteuclid.org/euclid.aos/1581930138

zbMATH Keywords

efficiencyKL-UCBsubsamplingThompson samplingupper confidence bound (UCB)

Mathematics Subject Classification ID

Compound decision problems in statistical decision theory (62C25) Nonparametric tolerance and confidence regions (62G15) Sequential statistical design (62L05) Optimal stopping in statistics (62L15)

Abstract: Lai and Robbins (1985) and Lai (1987) provided efficient parametric solutions to the multi-armed bandit problem, showing that arm allocation via upper confidence bounds (UCB) achieves minimum regret. These bounds are constructed from the Kullback-Leibler information of the reward distributions, estimated from specified parametric families. In recent years there has been renewed interest in the multi-armed bandit problem due to new applications in machine learning algorithms and data analytics. Non-parametric arm allocation procedures like $epsilon$-greedy, Boltzmann exploration and BESA were studied, and modified versions of the UCB procedure were also analyzed under non-parametric settings. However unlike UCB these non-parametric procedures are not efficient under general parametric settings. In this paper we propose efficient non-parametric procedures.

Review text

The author treats the multi-armed bandit problem in the formulation which can be found in [\textit{T. L. Lai} and \textit{H. Robbins}, Adv. Appl. Math. 6, 4--22 (1985; Zbl 0568.62074)]. \textit{T. L. Lai} [Ann. Stat. 15, 1091--1114 (1987; Zbl 0643.62054)] provided efficient parametric solutions to the multi-armed bandit problem, showing that arm allocation via upper confidence bounds (UCB) achieves minimum regret. These bounds are constructed from the Kullback-Leibler information of the reward distributions, estimated from specified parametric families. The subject of this paper is a new nonparametric an arm allocation procedure subsample-mean comparison (SSMC) which is efficient when the reward distributions are from an unspecified one-dimensional exponential family. It achieves this by comparing subsample means of the leading arm with the sample means of its competitors. It is empirical in its approach, using more informative subsample means rather than full-sample means alone, for better decision-making.

Recommendations

• Nonparametric bandit methods
• scientific article; zbMATH DE number 4064878
• Adaptive treatment allocation and the multi-armed bandit problem
• The Nonstochastic Multiarmed Bandit Problem
• Kullback-Leibler upper confidence bounds for optimal sequential allocation

Cites work

• A Bernoulli Two-armed Bandit
• A new approach to the design of reinforcement schemes for learning automata
• Adaptive treatment allocation and the multi-armed bandit problem
• Asymptotically efficient adaptive allocation rules
• Asymptotically efficient adaptive allocation schemes for controlled Markov chains: finite parameter space
• Asymptotically Efficient Adaptive Choice of Control Laws inControlled Markov Chains
• Finite-time analysis of the multiarmed bandit problem
• scientific article; zbMATH DE number 1614382 (Why is no real title available?)
• scientific article; zbMATH DE number 4078557 (Why is no real title available?)
• scientific article; zbMATH DE number 3638998 (Why is no real title available?)
• Kullback-Leibler upper confidence bounds for optimal sequential allocation
• Nonparametric bandit methods
• Optimal adaptive policies for sequential allocation problems
• Optimal learning and experimentation in bandit problems.
• Optimal stopping and dynamic allocation
• Reinforcement learning. An introduction
• Sample mean based index policies by O(log n) regret for the multi-armed bandit problem
• Some Remarks on the Two-Armed Bandit

Cited in

(18)

• Strategy under the unknown stochastic environment: The nonparametric lop-pass problem
• The Irrevocable Multiarmed Bandit Problem
• On Solving Finite State Multi-Armed Bandit Problem by Linear Programming
• Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback
• A Simple Distribution-Free Approach to the Max k-Armed Bandit Problem
• Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
• The Nonstochastic Multiarmed Bandit Problem
• A Structured Multiarmed Bandit Problem and the Greedy Policy
• scientific article; zbMATH DE number 7380836 (Why is no real title available?)
• On the bias, risk, and consistency of sample means in multi-armed bandits
• Infinite Arms Bandit: Optimality via Confidence Bounds
• Optimal exploration-exploitation in a multi-armed bandit problem with non-stationary rewards
• Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits
• Adaptive Algorithm for Multi-Armed Bandit Problem with High-Dimensional Covariates
• Dealing with unknown variances in best-arm identification
• Nonparametric bandit methods
• A non-parametric solution to the multi-armed bandit problem with covariates
• A comparative study of ad hoc techniques and evolutionary methods for multi-armed bandit problems

This page was built for publication: The multi-armed bandit problem: an efficient nonparametric solution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2176624)