Bandit problems with side observations

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

Bandit problems with side observations

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

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

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 regret) and on quantifying how much the additional information helps. Various settings are considered and asymptotically tight lower bounds on the achievable regret are provided.

Original language	English (US)
Pages (from-to)	3988-3993
Number of pages	6
Journal	Proceedings of the IEEE Conference on Decision and Control
Volume	4
State	Published - 2002
Event	41st IEEE Conference on Decision and Control - Las Vegas, NV, United States Duration: Dec 10 2002 → Dec 13 2002

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Keywords

Adaptive
Allocation rule
Asymptotic
Efficient
Regret
Side information
Two-armed bandit

Cite this

@article{e1a538948bd9435eb91210eac6a1e3de,

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 regret) and on quantifying how much the additional information helps. Various settings are considered and asymptotically tight lower bounds on the achievable regret are provided.",

keywords = "Adaptive, Allocation rule, Asymptotic, Efficient, Regret, Side information, Two-armed bandit",

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

year = "2002",

language = "English (US)",

volume = "4",

pages = "3988--3993",

journal = "Proceedings of the IEEE Conference on Decision and Control",

issn = "0191-2216",

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

note = "41st IEEE Conference on Decision and Control ; Conference date: 10-12-2002 Through 13-12-2002",

}

TY - JOUR

T1 - Bandit problems with side observations

AU - Wang, Chih Chun

AU - Kulkarni, Sanjeev R.

AU - Poor, H. Vincent

PY - 2002

Y1 - 2002

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 regret) and on quantifying how much the additional information helps. Various settings are considered and asymptotically tight lower bounds on the achievable regret are provided.

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 regret) and on quantifying how much the additional information helps. Various settings are considered and asymptotically tight lower bounds on the achievable regret are provided.

KW - Adaptive

KW - Allocation rule

KW - Asymptotic

KW - Efficient

KW - Regret

KW - Side information

KW - Two-armed bandit

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

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

M3 - Conference article

AN - SCOPUS:0036991363

SN - 0191-2216

VL - 4

SP - 3988

EP - 3993

JO - Proceedings of the IEEE Conference on Decision and Control

JF - Proceedings of the IEEE Conference on Decision and Control

T2 - 41st IEEE Conference on Decision and Control

Y2 - 10 December 2002 through 13 December 2002

ER -

Bandit problems with side observations

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Other files and links

Fingerprint

Cite this