Contextual Bandits with Linear Payoff Functions

Wei Chu, Lihong C. Li, Lev Reyzin, Robert E. Schapire

2011-01-01article599 citationsclosed

No readable copy stored yet — this record is metadata only.

Advanced Bandit Algorithms Research Reinforcement Learning in Robotics Machine Learning and Algorithms

Abstract

In this paper, we study the contextual bandit problem (also known as the multi-armed bandit problem with expert advice) for linear payoff functions. For T rounds, K actions, and d(√ dimensional feature vectors, we prove an O Td ln 3) (KT ln(T)/δ) regret bound that holds with probability 1 − δ for the simplest known (both conceptually and computationally) efficient upper confidence bound algorithm for this problem. We also prove a lower bound of Ω ( √ Td) for this setting, matching the upper bound up to logarithmic factors. 1

Citations in this library

Stored only when both papers are in the corpus — 599 citations exist upstream.

References

2002Finite-time Analysis of the Multiarmed Bandit Problem

2002The Nonstochastic Multiarmed Bandit Problem

2008Stochastic Linear Optimization Under Bandit Feedback

Cited by

2012Thompson Sampling for Contextual Bandits with Linear Payoffs

2011Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms

2016Collaborative Filtering Bandits

2014Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits

2019Online Decision Making with High-Dimensional Covariates

2011Contextual Gaussian Process Bandit Optimization

2009Contextual Bandits with Similarity Information

2012Optimistic bayesian sampling in contextual-bandit problems