Bandit problems with side observations

Chih Chun Wang; Sanjeev R. Kulkarni; H. Vincent Poor

doi:10.1109/TAC.2005.844079

Bandit problems with side observations

Chih Chun Wang, Sanjeev R. Kulkarni, H. Vincent Poor

Research output: Contribution to journal › Article › peer-review

90 Scopus citations

Abstract

An extension of the traditional two-armed bandit problem is considered, in which the decision maker has access to some side information before deciding which arm to pull. At each time t, before making a selection, the decision maker is able to observe a random variable X_t that provides some information on the rewards to be obtained. The focus is on finding uniformly good rules (that minimize the growth rate of the inferior sampling time) and on quantifying how much the additional information helps. Various settings are considered and for each setting, lower bounds on the achievable inferior sampling time are developed and asymptotically optimal adaptive schemes achieving these lower bounds are constructed.

Original language	English (US)
Pages (from-to)	338-355
Number of pages	18
Journal	IEEE Transactions on Automatic Control
Volume	50
Issue number	3
DOIs	https://doi.org/10.1109/TAC.2005.844079
State	Published - Mar 2005

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Computer Science Applications
Electrical and Electronic Engineering

Keywords

Adaptive
Allocation rule
Asymptotic
Efficient
Inferior sampling time
Side information
Two-armed bandit

Access to Document

10.1109/TAC.2005.844079

Cite this

@article{5cddbd7ee47c4833875fed8f05c29fde,

title = "Bandit problems with side observations",

abstract = "An extension of the traditional two-armed bandit problem is considered, in which the decision maker has access to some side information before deciding which arm to pull. At each time t, before making a selection, the decision maker is able to observe a random variable Xt that provides some information on the rewards to be obtained. The focus is on finding uniformly good rules (that minimize the growth rate of the inferior sampling time) and on quantifying how much the additional information helps. Various settings are considered and for each setting, lower bounds on the achievable inferior sampling time are developed and asymptotically optimal adaptive schemes achieving these lower bounds are constructed.",

keywords = "Adaptive, Allocation rule, Asymptotic, Efficient, Inferior sampling time, Side information, Two-armed bandit",

author = "Wang, {Chih Chun} and Kulkarni, {Sanjeev R.} and Poor, {H. Vincent}",

note = "Funding Information: Manuscript received November 15, 2002; revised November 1, 2004. Recommended by Associate Editor D. Li. This work was supported in part by the National Science Foundation under Grants ANI-0338807 and ECS-9873451, the Army Research Office under Contract DAAD19-00-1-0466, the Office of Naval Research under Grant N00014-03-1-0102, and the New Jersey Center for Pervasive Information Technologies.",

year = "2005",

month = mar,

doi = "10.1109/TAC.2005.844079",

language = "English (US)",

volume = "50",

pages = "338--355",

journal = "IEEE Transactions on Automatic Control",

issn = "0018-9286",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}

TY - JOUR

T1 - Bandit problems with side observations

AU - Wang, Chih Chun

AU - Kulkarni, Sanjeev R.

AU - Poor, H. Vincent

N1 - Funding Information: Manuscript received November 15, 2002; revised November 1, 2004. Recommended by Associate Editor D. Li. This work was supported in part by the National Science Foundation under Grants ANI-0338807 and ECS-9873451, the Army Research Office under Contract DAAD19-00-1-0466, the Office of Naval Research under Grant N00014-03-1-0102, and the New Jersey Center for Pervasive Information Technologies.

PY - 2005/3

Y1 - 2005/3

N2 - An extension of the traditional two-armed bandit problem is considered, in which the decision maker has access to some side information before deciding which arm to pull. At each time t, before making a selection, the decision maker is able to observe a random variable Xt that provides some information on the rewards to be obtained. The focus is on finding uniformly good rules (that minimize the growth rate of the inferior sampling time) and on quantifying how much the additional information helps. Various settings are considered and for each setting, lower bounds on the achievable inferior sampling time are developed and asymptotically optimal adaptive schemes achieving these lower bounds are constructed.

AB - An extension of the traditional two-armed bandit problem is considered, in which the decision maker has access to some side information before deciding which arm to pull. At each time t, before making a selection, the decision maker is able to observe a random variable Xt that provides some information on the rewards to be obtained. The focus is on finding uniformly good rules (that minimize the growth rate of the inferior sampling time) and on quantifying how much the additional information helps. Various settings are considered and for each setting, lower bounds on the achievable inferior sampling time are developed and asymptotically optimal adaptive schemes achieving these lower bounds are constructed.

KW - Adaptive

KW - Allocation rule

KW - Asymptotic

KW - Efficient

KW - Inferior sampling time

KW - Side information

KW - Two-armed bandit

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

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

U2 - 10.1109/TAC.2005.844079

DO - 10.1109/TAC.2005.844079

M3 - Article

AN - SCOPUS:15844389867

SN - 0018-9286

VL - 50

SP - 338

EP - 355

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

IS - 3

ER -

Bandit problems with side observations

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this