Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems
Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems
复制标题
DOI：
--
复制
发表时间：
2006-12
期刊：
影响因子：
--
通讯作者：
Eyal Even-Dar;Shie Mannor;Y. Mansour
中科院分区：
文献类型：
--
作者：
Eyal Even-Dar;Shie Mannor;Y. Mansour
我们在多臂强盗和强化学习问题中引入了统计置信区间。在bandit问题中，我们证明了给定n个手臂，它足以拉动手臂总共O（（n/e2）log（1/δ））次，以找到概率至少为1-δ的e-最优手臂。这个界限与Mannor和Tsitsiklis（2004）的下限相匹配，直到常数。我们还设计了强化学习算法中的动作消除程序。我们描述了一个框架，该框架基于学习值函数或Q函数周围的置信区间，并消除非最佳（高概率）的操作。我们提供了一种基于模型和一种无模型的变量消除方法。我们进一步推导出停止条件，保证学习的政策是近似最优的高概率。仿真结果表明，相当大的加速和增加的鲁棒性比e-greedy Q-学习。
We incorporate statistical confidence intervals in both the multi-armed bandit and the reinforcement learning problems. In the bandit problem we show that given n arms, it suffices to pull the arms a total of O((n/e2)log(1/δ)) times to find an e-optimal arm with probability of at least 1-δ. This bound matches the lower bound of Mannor and Tsitsiklis (2004) up to constants. We also devise action elimination procedures in reinforcement learning algorithms. We describe a framework that is based on learning the confidence interval around the value function or the Q-function and eliminating actions that are not optimal (with high probability). We provide a model-based and a model-free variants of the elimination method. We further derive stopping conditions guaranteeing that the learned policy is approximately optimal with high probability. Simulations demonstrate a considerable speedup and added robustness over e-greedy Q-learning.