Title :
On optimal foraging and multi-armed bandits
Author :
Srivastava, Vishnu ; Reverdy, Paul ; Leonard, Naomi Ehrich
Author_Institution :
Dept. of Mech. & Aerosp. Eng., Princeton Univ., Princeton, NJ, USA
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.
Keywords :
behavioural sciences; graph theory; learning (artificial intelligence); animal foraging models; block allocation algorithm; cumulative transitions; double-logarithmic function; graphs; machine learning; multiarmed bandit problem; optimal foraging; transition costs; Algorithm design and analysis; Animals; Biological system modeling; Random variables; Resource management; Search problems; Standards;
Conference_Titel :
Communication, Control, and Computing (Allerton), 2013 51st Annual Allerton Conference on
Conference_Location :
Monticello, IL
Print_ISBN :
978-1-4799-3409-6
DOI :
10.1109/Allerton.2013.6736565