Gap-free bounds for stochastic multi-armed bandit

Anatoly Juditsky; Alexander V. Nazin; Alexander Tsybakov; Nicolas Vayatis

doi:10.3182/20080706-5-KR-1001.2585

Gap-free bounds for stochastic multi-armed bandit

Anatoly Juditsky
, Alexander V. Nazin
, Alexander Tsybakov
, Nicolas Vayatis

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

Abstract

We consider the stochastic multi-armed bandit problem with unknown horizon. We present a randomized decision strategy which is based on updating a probability distribution through a stochastic mirror descent/exponentiated gradient type algorithm. We consider separately two assumptions: nonnegative losses or arbitrary losses with an exponential moment condition. We prove optimal (up to logarithmic factors) gap-free bounds on the excess risk of the average over time of the instantaneous losses induced by the choice of a specific action.

Original language	English
Title of host publication	Proceedings of the 17th World Congress, International Federation of Automatic Control, IFAC
Edition	1 PART 1
DOIs	https://doi.org/10.3182/20080706-5-KR-1001.2585
Publication status	Published - 1 Dec 2008
Event	17th World Congress, International Federation of Automatic Control, IFAC - Seoul, Korea, Republic of Duration: 6 Jul 2008 → 11 Jul 2008

Publication series

Name	IFAC Proceedings Volumes (IFAC-PapersOnline)
Number	1 PART 1
Volume	17
ISSN (Print)	1474-6670

Conference

Conference	17th World Congress, International Federation of Automatic Control, IFAC
Country/Territory	Korea, Republic of
City	Seoul
Period	6/07/08 → 11/07/08

Keywords

Learning theory
Randomized methods
Stochastic control

Access to Document

10.3182/20080706-5-KR-1001.2585

Cite this

@inproceedings{1ffb765b75534ba481ca981597539fb5,

title = "Gap-free bounds for stochastic multi-armed bandit",

abstract = "We consider the stochastic multi-armed bandit problem with unknown horizon. We present a randomized decision strategy which is based on updating a probability distribution through a stochastic mirror descent/exponentiated gradient type algorithm. We consider separately two assumptions: nonnegative losses or arbitrary losses with an exponential moment condition. We prove optimal (up to logarithmic factors) gap-free bounds on the excess risk of the average over time of the instantaneous losses induced by the choice of a specific action.",

keywords = "Learning theory, Randomized methods, Stochastic control",

author = "Anatoly Juditsky and Nazin, \{Alexander V.\} and Alexander Tsybakov and Nicolas Vayatis",

year = "2008",

month = dec,

day = "1",

doi = "10.3182/20080706-5-KR-1001.2585",

language = "English",

isbn = "9783902661005",

series = "IFAC Proceedings Volumes (IFAC-PapersOnline)",

number = "1 PART 1",

booktitle = "Proceedings of the 17th World Congress, International Federation of Automatic Control, IFAC",

edition = "1 PART 1",

note = "17th World Congress, International Federation of Automatic Control, IFAC ; Conference date: 06-07-2008 Through 11-07-2008",

}

Juditsky, A, Nazin, AV, Tsybakov, A & Vayatis, N 2008, Gap-free bounds for stochastic multi-armed bandit. in Proceedings of the 17th World Congress, International Federation of Automatic Control, IFAC. 1 PART 1 edn, IFAC Proceedings Volumes (IFAC-PapersOnline), no. 1 PART 1, vol. 17, 17th World Congress, International Federation of Automatic Control, IFAC, Seoul, Korea, Republic of, 6/07/08. https://doi.org/10.3182/20080706-5-KR-1001.2585

Gap-free bounds for stochastic multi-armed bandit. / Juditsky, Anatoly; Nazin, Alexander V.; Tsybakov, Alexander et al.
Proceedings of the 17th World Congress, International Federation of Automatic Control, IFAC. 1 PART 1. ed. 2008. (IFAC Proceedings Volumes (IFAC-PapersOnline); Vol. 17, No. 1 PART 1).

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

TY - GEN

T1 - Gap-free bounds for stochastic multi-armed bandit

AU - Juditsky, Anatoly

AU - Nazin, Alexander V.

AU - Tsybakov, Alexander

AU - Vayatis, Nicolas

PY - 2008/12/1

Y1 - 2008/12/1

N2 - We consider the stochastic multi-armed bandit problem with unknown horizon. We present a randomized decision strategy which is based on updating a probability distribution through a stochastic mirror descent/exponentiated gradient type algorithm. We consider separately two assumptions: nonnegative losses or arbitrary losses with an exponential moment condition. We prove optimal (up to logarithmic factors) gap-free bounds on the excess risk of the average over time of the instantaneous losses induced by the choice of a specific action.

AB - We consider the stochastic multi-armed bandit problem with unknown horizon. We present a randomized decision strategy which is based on updating a probability distribution through a stochastic mirror descent/exponentiated gradient type algorithm. We consider separately two assumptions: nonnegative losses or arbitrary losses with an exponential moment condition. We prove optimal (up to logarithmic factors) gap-free bounds on the excess risk of the average over time of the instantaneous losses induced by the choice of a specific action.

KW - Learning theory

KW - Randomized methods

KW - Stochastic control

U2 - 10.3182/20080706-5-KR-1001.2585

DO - 10.3182/20080706-5-KR-1001.2585

M3 - Conference contribution

AN - SCOPUS:79961019787

SN - 9783902661005

T3 - IFAC Proceedings Volumes (IFAC-PapersOnline)

BT - Proceedings of the 17th World Congress, International Federation of Automatic Control, IFAC

T2 - 17th World Congress, International Federation of Automatic Control, IFAC

Y2 - 6 July 2008 through 11 July 2008

ER -

Gap-free bounds for stochastic multi-armed bandit

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this