Contextual bandits with linear Payoff functions

Wei Chu; Lihong Li; Lev Reyzin; Robert E. Schapire

Contextual bandits with linear Payoff functions

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

Computer Science

Research output: Contribution to journal › Conference article › peer-review

602 Scopus citations

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 ³(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.

Original language	English (US)
Pages (from-to)	208-214
Number of pages	7
Journal	Journal of Machine Learning Research
Volume	15
State	Published - 2011
Event	14th International Conference on Artificial Intelligence and Statistics, AISTATS 2011 - Fort Lauderdale, FL, United States Duration: Apr 11 2011 → Apr 13 2011

All Science Journal Classification (ASJC) codes

Software
Artificial Intelligence
Control and Systems Engineering
Statistics and Probability

Cite this

@article{d27c5db1f26544bd85031bbafcf9f152,

title = "Contextual bandits with linear Payoff functions",

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.",

author = "Wei Chu and Lihong Li and Lev Reyzin and Schapire, {Robert E.}",

year = "2011",

language = "English (US)",

volume = "15",

pages = "208--214",

journal = "Journal of Machine Learning Research",

issn = "1532-4435",

publisher = "Microtome Publishing",

note = "14th International Conference on Artificial Intelligence and Statistics, AISTATS 2011 ; Conference date: 11-04-2011 Through 13-04-2011",

}

TY - JOUR

T1 - Contextual bandits with linear Payoff functions

AU - Chu, Wei

AU - Li, Lihong

AU - Reyzin, Lev

AU - Schapire, Robert E.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84862295531&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862295531&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:84862295531

SN - 1532-4435

VL - 15

SP - 208

EP - 214

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

T2 - 14th International Conference on Artificial Intelligence and Statistics, AISTATS 2011

Y2 - 11 April 2011 through 13 April 2011

ER -

Contextual bandits with linear Payoff functions

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this