On optimal foraging and multi-armed bandits

Vaibhav Srivastava, Paul Reverdy and Naomi Ehich Leonard

Proceedings of the 51st Annual Allerton Conference on Communication, Control and Computing, 2013.
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.

(172 KB pdf)
Back to home page
Back to publications page