The multi-armed bandit problem with covariates

DOI10.1214/13-AOS1101zbMATH Open1360.62436arXiv1110.6084OpenAlexW3100895096WikidataQ56675681 ScholiaQ56675681MaRDI QIDQ355096FDOQ355096

Authors: Vianney Perchet, Philippe Rigollet 

Publication date: 24 July 2013

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

Abstract: We consider a multi-armed bandit problem in a setting where each arm produces a noisy reward realization which depends on an observable random covariate. As opposed to the traditional static multi-armed bandit problem, this setting allows for dynamically changing rewards that better describe applications where side information is available. We adopt a nonparametric model where the expected rewards are smooth functions of the covariate and where the hardness of the problem is captured by a margin parameter. To maximize the expected cumulative reward, we introduce a policy called Adaptively Binned Successive Elimination (abse) that adaptively decomposes the global problem into suitably "localized" static bandit problems. This policy constructs an adaptive partition using a variant of the Successive Elimination (se) policy. Our results include sharper regret bounds for the se policy in a static bandit problem and minimax optimal regret bounds for the abse policy in the dynamic problem.

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

Recommendations

• A non-parametric solution to the multi-armed bandit problem with covariates
• Randomized allocation with nonparametric estimation for a multi-armed bandit problem with covariates
• Randomized allocation with arm elimination in a bandit problem with covariates
• Kernel estimation and model combination in a bandit problem with covariates
• Bandit and covariate processes, with finite or non-denumerable set of arms

zbMATH Keywords

multi-armed banditregret boundscontextual banditadaptive partitionnonparametric banditsequential allocationsuccessive elimination

Mathematics Subject Classification ID

Nonparametric regression and quantile regression (62G08) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Sequential statistical design (62L05) Sequential estimation (62L12)

Cites Work

• Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems
• Prediction, Learning, and Games
• Smooth discrimination analysis
• Asymptotically efficient adaptive allocation rules
• Title not available (Why is that?)
• Some aspects of the sequential design of experiments
• Finite-time analysis of the multiarmed bandit problem
• Regret bounds and minimax policies under partial monitoring
• An Asymptotic Minimax Theorem for the Two Armed Bandit Problem
• Optimal aggregation of classifiers in statistical learning.
• UCB revisited: improved regret bounds for the stochastic multi-armed bandit problem
• Fast learning rates for plug-in classifiers
• Randomized allocation with nonparametric estimation for a multi-armed bandit problem with covariates
• Contextual bandits with similarity information
• A One-Armed Bandit Problem with a Concomitant Variable
• A Note on Performance Limitations in Bandit Problems With Side Information
• Online Learning with Prior Knowledge
• Woodroofe's one-armed bandit problem revisited

Cited In (42)

• One-armed bandit problems with covariates
• Learning the distribution with largest mean: two bandit frameworks
• Randomized allocation with nonparametric estimation for a multi-armed bandit problem with covariates
• time-decaying bandits for non-stationary problems
• Bayesian adaptive bandit-based designs using the Gittins index for multi-armed trials with normally distributed endpoints
• Adaptive Algorithm for Multi-Armed Bandit Problem with High-Dimensional Covariates
• A Bayesian two-armed bandit model
• Batched bandit problems
• Reward maximization under uncertainty: leveraging side-observations on networks
• Arbitrary side observations in bandit problems
• Online decision making with high-dimensional covariates
• Bandit and covariate processes, with finite or non-denumerable set of arms
• Dynamic assortment personalization in high dimensions
• Technical note—Knowledge gradient for selection with covariates: Consistency and computation
• Title not available (Why is that?)
• Statistical inference for online decision making: in a contextual bandit setting
• Nonparametric pricing analytics with customer covariates
• Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
• A linear response bandit problem
• A Single-Index Model With a Surface-Link for Optimizing Individualized Dose Rules
• Online learning of Nash equilibria in congestion games
• Transfer learning for contextual multi-armed bandits
• The \(k\)-nearest neighbour UCB algorithm for multi-armed bandits with covariates
• Randomized allocation with arm elimination in a bandit problem with covariates
• Ranking and Selection with Covariates for Personalized Decision Making
• Treatment recommendation with distributional targets
• Kernel estimation and model combination in a bandit problem with covariates
• A revised approach for risk-averse multi-armed bandits under CVaR criterion
• Infinite Arms Bandit: Optimality via Confidence Bounds
• Multi-armed bandit problem with online clustering as side information
• Smoothness-Adaptive Contextual Bandits
• Smooth Contextual Bandits: Bridging the Parametric and Nondifferentiable Regret Regimes
• An adaptive multiclass nearest neighbor classifier
• Functional sequential treatment allocation with covariates
• Title not available (Why is that?)
• Woodroofe's one-armed bandit problem revisited
• Learning in repeated auctions
• One-armed bandit process with a covariate
• Gaussian process bandits with adaptive discretization
• Randomized allocation with nonparametric estimation for contextual multi-armed bandits with delayed rewards
• A non-parametric solution to the multi-armed bandit problem with covariates
• Instrument-armed bandits

This page was built for publication: The multi-armed bandit problem with covariates

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