On Interruptible Pure Exploration in Multi-Armed Bandits
On Interruptible Pure Exploration in Multi-Armed Bandits
复制标题
论多臂强盗的可中断纯探索
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Carmel Domshlak
中科院分区：
文献类型：
--
作者：
Alexander Shleyfman;Antonín Komenda;Carmel Domshlak
多臂匪徒(MAB)中的可中断纯探索是序列决策蒙特卡罗树搜索算法的重要组成部分。我们引入了鉴别性分组(DB)，这是一种用于MAB中纯探索的新型策略家族，它允许将非中断策略中的最新进展适应于可中断设置，同时保证随着时间的推移指数速率性能改进。我们的实验评估表明，相应的DB实例与当前流行的UCB1和Epsilon-Greedy策略以及保守的均匀抽样都具有良好的竞争优势。
Interruptible pure exploration in multi-armed bandits (MABs) is a key component of Monte-Carlo tree search algorithms for sequential decision problems. We introduce Discriminative Bucketing (DB), a novel family of strategies for pure exploration in MABs, which allows for adapting recent advances in non-interruptible strategies to the interruptible setting, while guaranteeing exponential-rate performance improvement over time. Our experimental evaluation demonstrates that the corresponding instances of DB favorably compete both with the currently popular strategies UCB1 and Epsilon-Greedy, as well as with the conservative uniform sampling.