Time-varying stochastic multi-armed bandit problems

Sattar Vakili; Qing Zhao; Yuan Zhou

doi:10.1109/ACSSC.2014.7094845

Time-varying stochastic multi-armed bandit problems

Sattar Vakili, Qing Zhao, Yuan Zhou

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

7 Scopus citations

Abstract

In this paper, we consider a time-varying stochastic multi-armed bandit (MAB) problem where the unknown reward distribution of each arm can change arbitrarily over time. We obtain a lower bound on the regret order and demonstrate that an online learning algorithm achieves this lower bound. We further consider a piece-wise stationary model of the arm reward distributions and establish the regret performance of an online learning algorithm in terms of the number of change points experienced by the reward distributions over the time horizon.

Original language	English
Title of host publication	Conference Record of the 48th Asilomar Conference on Signals, Systems and Computers
Editors	Michael B. Matthews
Pages	2103-2107
Number of pages	5
ISBN (Electronic)	9781479982974
DOIs	https://doi.org/10.1109/ACSSC.2014.7094845
State	Published - Apr 24 2015
Event	48th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015 - Pacific Grove, United States Duration: Nov 2 2014 → Nov 5 2014

Publication series

Name	Conference Record - Asilomar Conference on Signals, Systems and Computers
Volume	2015-April
ISSN (Print)	1058-6393

Conference

Conference	48th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015
Country/Territory	United States
City	Pacific Grove
Period	11/2/14 → 11/5/14

Bibliographical note

Publisher Copyright:
© 2014 IEEE.

ASJC Scopus subject areas

Signal Processing
Computer Networks and Communications

Access to Document

10.1109/ACSSC.2014.7094845

Cite this

Vakili, S., Zhao, Q., & Zhou, Y. (2015). Time-varying stochastic multi-armed bandit problems. In M. B. Matthews (Ed.), Conference Record of the 48th Asilomar Conference on Signals, Systems and Computers (pp. 2103-2107). Article 7094845 (Conference Record - Asilomar Conference on Signals, Systems and Computers; Vol. 2015-April). https://doi.org/10.1109/ACSSC.2014.7094845

@inproceedings{5fc7e29f65da4226a67411a26c30ec77,

title = "Time-varying stochastic multi-armed bandit problems",

abstract = "In this paper, we consider a time-varying stochastic multi-armed bandit (MAB) problem where the unknown reward distribution of each arm can change arbitrarily over time. We obtain a lower bound on the regret order and demonstrate that an online learning algorithm achieves this lower bound. We further consider a piece-wise stationary model of the arm reward distributions and establish the regret performance of an online learning algorithm in terms of the number of change points experienced by the reward distributions over the time horizon.",

author = "Sattar Vakili and Qing Zhao and Yuan Zhou",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 48th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015 ; Conference date: 02-11-2014 Through 05-11-2014",

year = "2015",

month = apr,

day = "24",

doi = "10.1109/ACSSC.2014.7094845",

language = "English",

series = "Conference Record - Asilomar Conference on Signals, Systems and Computers",

pages = "2103--2107",

editor = "Matthews, {Michael B.}",

booktitle = "Conference Record of the 48th Asilomar Conference on Signals, Systems and Computers",

}

Vakili, S, Zhao, Q & Zhou, Y 2015, Time-varying stochastic multi-armed bandit problems. in MB Matthews (ed.), Conference Record of the 48th Asilomar Conference on Signals, Systems and Computers., 7094845, Conference Record - Asilomar Conference on Signals, Systems and Computers, vol. 2015-April, pp. 2103-2107, 48th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015, Pacific Grove, United States, 11/2/14. https://doi.org/10.1109/ACSSC.2014.7094845

Time-varying stochastic multi-armed bandit problems. / Vakili, Sattar; Zhao, Qing; Zhou, Yuan.
Conference Record of the 48th Asilomar Conference on Signals, Systems and Computers. ed. / Michael B. Matthews. 2015. p. 2103-2107 7094845 (Conference Record - Asilomar Conference on Signals, Systems and Computers; Vol. 2015-April).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Time-varying stochastic multi-armed bandit problems

AU - Vakili, Sattar

AU - Zhao, Qing

AU - Zhou, Yuan

PY - 2015/4/24

Y1 - 2015/4/24

N2 - In this paper, we consider a time-varying stochastic multi-armed bandit (MAB) problem where the unknown reward distribution of each arm can change arbitrarily over time. We obtain a lower bound on the regret order and demonstrate that an online learning algorithm achieves this lower bound. We further consider a piece-wise stationary model of the arm reward distributions and establish the regret performance of an online learning algorithm in terms of the number of change points experienced by the reward distributions over the time horizon.

AB - In this paper, we consider a time-varying stochastic multi-armed bandit (MAB) problem where the unknown reward distribution of each arm can change arbitrarily over time. We obtain a lower bound on the regret order and demonstrate that an online learning algorithm achieves this lower bound. We further consider a piece-wise stationary model of the arm reward distributions and establish the regret performance of an online learning algorithm in terms of the number of change points experienced by the reward distributions over the time horizon.

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

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

U2 - 10.1109/ACSSC.2014.7094845

DO - 10.1109/ACSSC.2014.7094845

M3 - Conference contribution

AN - SCOPUS:84940535838

T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers

SP - 2103

EP - 2107

BT - Conference Record of the 48th Asilomar Conference on Signals, Systems and Computers

A2 - Matthews, Michael B.

T2 - 48th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015

Y2 - 2 November 2014 through 5 November 2014

ER -

Time-varying stochastic multi-armed bandit problems

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this