On optimal foraging and multi-armed bandits

Vaibhav Srivastava; Paul Reverdy; Naomi E. Leonard

doi:10.1109/Allerton.2013.6736565

On optimal foraging and multi-armed bandits

Vaibhav Srivastava, Paul Reverdy, Naomi E. Leonard

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

25 Scopus citations

Abstract

We consider two variants of the standard multi-armed bandit problem, namely, the multi-armed bandit problem with transition costs and the multi-armed bandit problem on graphs. We develop block allocation algorithms for these problems that achieve an expected cumulative regret that is uniformly dominated by a logarithmic function of time, and an expected cumulative number of transitions from one arm to another arm uniformly dominated by a double-logarithmic function of time. We observe that the multi-armed bandit problem with transition costs and the associated block allocation algorithm capture the key features of popular animal foraging models in literature.

Original language	English (US)
Title of host publication	2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
Publisher	IEEE Computer Society
Pages	494-499
Number of pages	6
ISBN (Print)	9781479934096
DOIs	https://doi.org/10.1109/Allerton.2013.6736565
State	Published - 2013
Externally published	Yes
Event	51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013 - Monticello, IL, United States Duration: Oct 2 2013 → Oct 4 2013

Publication series

Name	2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013

Conference

Conference	51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
Country/Territory	United States
City	Monticello, IL
Period	10/2/13 → 10/4/13

ASJC Scopus subject areas

Computer Networks and Communications
Control and Systems Engineering

Access to Document

10.1109/Allerton.2013.6736565

Cite this

Srivastava, V., Reverdy, P., & Leonard, N. E. (2013). On optimal foraging and multi-armed bandits. In 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013 (pp. 494-499). Article 6736565 (2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013). IEEE Computer Society. https://doi.org/10.1109/Allerton.2013.6736565

On optimal foraging and multi-armed bandits. / Srivastava, Vaibhav; Reverdy, Paul; Leonard, Naomi E.
2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013. IEEE Computer Society, 2013. p. 494-499 6736565 (2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013).

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

Srivastava, V, Reverdy, P & Leonard, NE 2013, On optimal foraging and multi-armed bandits. in 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013., 6736565, 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013, IEEE Computer Society, pp. 494-499, 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013, Monticello, IL, United States, 10/2/13. https://doi.org/10.1109/Allerton.2013.6736565

@inproceedings{6194edbb16d047b9b330a1cd14ae201c,

title = "On optimal foraging and multi-armed bandits",

abstract = "We consider two variants of the standard multi-armed bandit problem, namely, the multi-armed bandit problem with transition costs and the multi-armed bandit problem on graphs. We develop block allocation algorithms for these problems that achieve an expected cumulative regret that is uniformly dominated by a logarithmic function of time, and an expected cumulative number of transitions from one arm to another arm uniformly dominated by a double-logarithmic function of time. We observe that the multi-armed bandit problem with transition costs and the associated block allocation algorithm capture the key features of popular animal foraging models in literature.",

author = "Vaibhav Srivastava and Paul Reverdy and Leonard, {Naomi E.}",

year = "2013",

doi = "10.1109/Allerton.2013.6736565",

language = "English (US)",

isbn = "9781479934096",

series = "2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013",

publisher = "IEEE Computer Society",

pages = "494--499",

booktitle = "2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013",

note = "51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013 ; Conference date: 02-10-2013 Through 04-10-2013",

}

TY - GEN

T1 - On optimal foraging and multi-armed bandits

AU - Srivastava, Vaibhav

AU - Reverdy, Paul

AU - Leonard, Naomi E.

PY - 2013

Y1 - 2013

N2 - We consider two variants of the standard multi-armed bandit problem, namely, the multi-armed bandit problem with transition costs and the multi-armed bandit problem on graphs. We develop block allocation algorithms for these problems that achieve an expected cumulative regret that is uniformly dominated by a logarithmic function of time, and an expected cumulative number of transitions from one arm to another arm uniformly dominated by a double-logarithmic function of time. We observe that the multi-armed bandit problem with transition costs and the associated block allocation algorithm capture the key features of popular animal foraging models in literature.

AB - We consider two variants of the standard multi-armed bandit problem, namely, the multi-armed bandit problem with transition costs and the multi-armed bandit problem on graphs. We develop block allocation algorithms for these problems that achieve an expected cumulative regret that is uniformly dominated by a logarithmic function of time, and an expected cumulative number of transitions from one arm to another arm uniformly dominated by a double-logarithmic function of time. We observe that the multi-armed bandit problem with transition costs and the associated block allocation algorithm capture the key features of popular animal foraging models in literature.

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

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

U2 - 10.1109/Allerton.2013.6736565

DO - 10.1109/Allerton.2013.6736565

M3 - Conference contribution

AN - SCOPUS:84897584848

SN - 9781479934096

T3 - 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013

SP - 494

EP - 499

BT - 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013

PB - IEEE Computer Society

T2 - 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013

Y2 - 2 October 2013 through 4 October 2013

ER -

On optimal foraging and multi-armed bandits

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this