Maximizing the length of a success run for many-armed bandits

Donald A. Berry; Bert Fristedt

doi:10.1016/0304-4149(83)90039-X

Maximizing the length of a success run for many-armed bandits

Donald A. Berry
, Bert Fristedt

School of Mathematics

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

1 Scopus citations

Abstract

One of a number of Bernoulli processes is selected at each of a number of stages. A success at stage i is worth α_i and the problem is to maximize the expected payoff before the first failure. Results of Berry and Viscusi (1981) are generalized. In particular, we show that there is always an optimal strategy that uses a single process exclusively and indefinitely whenever the arms are independent and the discount sequence (α₁, α₂,...) is superregular. There is not always a similar reduction in the number of strategies when the discount sequence is not superregular.

Original language	English (US)
Pages (from-to)	317-325
Number of pages	9
Journal	Stochastic Processes and their Applications
Volume	15
Issue number	3
DOIs	https://doi.org/10.1016/0304-4149(83)90039-X
State	Published - Aug 1983

Bibliographical note

Funding Information:
* The first author’s research was supported research by NSF Grant No. MCS78-01168.

Funding Information:
by NSF Grant No. MCSSO-01800

Keywords

Bernoulli processes
Many-armed bandits
gambling with discounting
sequential decisions
single-arm strategies
stay-on-a-winner rule

Publisher link

10.1016/0304-4149(83)90039-X

Find It

Find It at U of M Libraries

Cite this

@article{6200c7eee93547cca8302a1bc00dce4d,

title = "Maximizing the length of a success run for many-armed bandits",

abstract = "One of a number of Bernoulli processes is selected at each of a number of stages. A success at stage i is worth αi and the problem is to maximize the expected payoff before the first failure. Results of Berry and Viscusi (1981) are generalized. In particular, we show that there is always an optimal strategy that uses a single process exclusively and indefinitely whenever the arms are independent and the discount sequence (α1, α2,...) is superregular. There is not always a similar reduction in the number of strategies when the discount sequence is not superregular.",

keywords = "Bernoulli processes, Many-armed bandits, gambling with discounting, sequential decisions, single-arm strategies, stay-on-a-winner rule",

author = "Berry, \{Donald A.\} and Bert Fristedt",

note = "Funding Information: * The first author{\textquoteright}s research was supported research by NSF Grant No. MCS78-01168. Funding Information: by NSF Grant No. MCSSO-01800",

year = "1983",

month = aug,

doi = "10.1016/0304-4149(83)90039-X",

language = "English (US)",

volume = "15",

pages = "317--325",

journal = "Stochastic Processes and their Applications",

issn = "0304-4149",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Maximizing the length of a success run for many-armed bandits

AU - Berry, Donald A.

AU - Fristedt, Bert

N1 - Funding Information: * The first author’s research was supported research by NSF Grant No. MCS78-01168. Funding Information: by NSF Grant No. MCSSO-01800

PY - 1983/8

Y1 - 1983/8

N2 - One of a number of Bernoulli processes is selected at each of a number of stages. A success at stage i is worth αi and the problem is to maximize the expected payoff before the first failure. Results of Berry and Viscusi (1981) are generalized. In particular, we show that there is always an optimal strategy that uses a single process exclusively and indefinitely whenever the arms are independent and the discount sequence (α1, α2,...) is superregular. There is not always a similar reduction in the number of strategies when the discount sequence is not superregular.

AB - One of a number of Bernoulli processes is selected at each of a number of stages. A success at stage i is worth αi and the problem is to maximize the expected payoff before the first failure. Results of Berry and Viscusi (1981) are generalized. In particular, we show that there is always an optimal strategy that uses a single process exclusively and indefinitely whenever the arms are independent and the discount sequence (α1, α2,...) is superregular. There is not always a similar reduction in the number of strategies when the discount sequence is not superregular.

KW - Bernoulli processes

KW - Many-armed bandits

KW - gambling with discounting

KW - sequential decisions

KW - single-arm strategies

KW - stay-on-a-winner rule

UR - https://www.scopus.com/pages/publications/48749147060

UR - https://www.scopus.com/pages/publications/48749147060#tab=citedBy

U2 - 10.1016/0304-4149(83)90039-X

DO - 10.1016/0304-4149(83)90039-X

M3 - Article

AN - SCOPUS:48749147060

SN - 0304-4149

VL - 15

SP - 317

EP - 325

JO - Stochastic Processes and their Applications

JF - Stochastic Processes and their Applications

IS - 3

ER -

Maximizing the length of a success run for many-armed bandits

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this