On optimal foraging and multi-armed bandits
On optimal foraging and multi-armed bandits
复制标题
关于最佳觅食和多臂老虎机
DOI：
10.1109/allerton.2013.6736565
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Naomi Ehrich Leonard
中科院分区：
文献类型：
--
作者：
Vaibhav Srivastava;Paul B. Reverdy;Naomi Ehrich Leonard
我们考虑标准多臂老虎机问题的两种变体，即具有转移成本的多臂老虎机问题和图上的多臂老虎机问题。我们针对这些问题开发了块分配算法，该算法实现了由时间的对数函数一致支配的预期累积遗憾，以及由时间的双对数函数一致支配的从一个臂到另一臂的预期累积转换数量。我们观察到，具有转移成本的多臂老虎机问题和相关的块分配算法捕获了文献中流行的动物觅食模型的关键特征。
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.