论文标题
在马尔可夫决策过程中规划依赖于差距的样本复杂性
Planning in Markov Decision Processes with Gap-Dependent Sample Complexity
论文作者
论文摘要
我们提出了MDP-Gape，这是一种新的基于轨迹的蒙特卡洛树搜索算法，用于在马尔可夫决策过程中进行计划，其中过渡具有有限的支持。我们证明了对MDP-Gape所需的生成模型的调用数量的上限，以识别具有高概率的近乎最佳动作。这种依赖问题的样本复杂性结果是根据探索过程中访问的状态行动对的次要差距表示的。我们的实验表明，与其他在固定信心环境中保证的其他算法相比，MDP-A-A-sa-sa-sa-sale也是有效的。
We propose MDP-GapE, a new trajectory-based Monte-Carlo Tree Search algorithm for planning in a Markov Decision Process in which transitions have a finite support. We prove an upper bound on the number of calls to the generative models needed for MDP-GapE to identify a near-optimal action with high probability. This problem-dependent sample complexity result is expressed in terms of the sub-optimality gaps of the state-action pairs that are visited during exploration. Our experiments reveal that MDP-GapE is also effective in practice, in contrast with other algorithms with sample complexity guarantees in the fixed-confidence setting, that are mostly theoretical.
