Woodroofe's one-armed bandit problem revisited

DOI10.1214/08-AAP589MaRDI QIDQ835072zbMATH OpenOpenAlexFDO

Authors Alexander Goldenshluger, Assaf Zeevi

Publication date 27 August 2009

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0909.0119

zbMATH Keywords

bandit problemsestimationinferior sampling rateminimaxonline learningrate-optimal policyregretsequential allocation

Mathematics Subject Classification ID

Stopping times; optimal stopping problems; gambling theory (60G40) Minimax procedures in statistical decision theory (62C20) Sequential statistical design (62L05)

Abstract: We consider the one-armed bandit problem of Woodroofe [J. Amer. Statist. Assoc. 74 (1979) 799--806], which involves sequential sampling from two populations: one whose characteristics are known, and one which depends on an unknown parameter and incorporates a covariate. The goal is to maximize cumulative expected reward. We study this problem in a minimax setting, and develop rate-optimal polices that involve suitable modifications of the myopic rule. It is shown that the regret, as well as the rate of sampling from the inferior population, can be finite or grow at various rates with the time horizon of the problem, depending on "local" properties of the covariate distribution. Proofs rely on martingale methods and information theoretic arguments.

Recommendations

• One-armed bandit problems with covariates
• scientific article; zbMATH DE number 4064878
• One-armed bandit process with a covariate
• A linear response bandit problem
• The multi-armed bandit problem with covariates

Cites work

• A Note on Performance Limitations in Bandit Problems With Side Information
• A One-Armed Bandit Problem with a Concomitant Variable
• Applications of the van Trees inequality: A Bayesian Cramér-Rao bound
• Arbitrary side observations in bandit problems
• Asymptotically efficient adaptive allocation rules
• Covariate models for bernoulli bandits
• Deviation probability bound for martingales with applications to statistical estimation
• scientific article; zbMATH DE number 3936286 (Why is no real title available?)
• scientific article; zbMATH DE number 4078557 (Why is no real title available?)
• scientific article; zbMATH DE number 194374 (Why is no real title available?)
• scientific article; zbMATH DE number 4001210 (Why is no real title available?)
• scientific article; zbMATH DE number 3800775 (Why is no real title available?)
• Information inequalities for the Bayes risk
• One-armed bandit problems with covariates
• Optimal aggregation of classifiers in statistical learning.
• Prediction, Learning, and Games
• Pseudo-maximization and self-normalized processes
• Randomized allocation with nonparametric estimation for a multi-armed bandit problem with covariates
• Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws.
• Sequential analysis: Some classical problems and new challenges. (With comments and rejoinder).
• Smooth discrimination analysis
• Some aspects of the sequential design of experiments

Cited in

(13)

• Regret lower bound and optimal algorithm for high-dimensional contextual linear bandit
• Bandit and covariate processes, with finite or non-denumerable set of arms
• The multi-armed bandit problem with covariates
• One-armed bandit process with a covariate
• Nonparametric pricing analytics with customer covariates
• Smooth Contextual Bandits: Bridging the Parametric and Nondifferentiable Regret Regimes
• MULTI-ARMED BANDITS WITH COVARIATES:THEORY AND APPLICATIONS
• A linear response bandit problem
• Mean square convergence rates for maximum quasi-likelihood estimators
• Randomized allocation with arm elimination in a bandit problem with covariates
• Transfer learning for contextual multi-armed bandits
• Adaptive Algorithm for Multi-Armed Bandit Problem with High-Dimensional Covariates
• A non-parametric solution to the multi-armed bandit problem with covariates

This page was built for publication: Woodroofe's one-armed bandit problem revisited

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