PAC Bounds for Discounted MDPs
PAC Bounds for Discounted MDPs
复制标题
折扣 MDP 的 PAC 界限
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Marcus Hutter
中科院分区：
文献类型：
--
作者：
Tor Lattimore;Marcus Hutter
我们研究了有限状态折扣马尔可夫决策过程（mdps）中学习近优行为的样本复杂度的上界和下界。我们证明了一个新的上限置信度强化学习（ucrl）的修改版本，只有三次依赖的地平线上。的界限是不可改进的，在所有参数，除了状态/动作空间的大小，在那里它线性地依赖于非零转移概率的数量。下限通过更一般（适用于所有政策）和更严格来加强以前的工作。如果转移矩阵不是太密集，则上界和下界匹配到对数因子。
We study upper and lower bounds on the sample-complexity of learning near-optimal behaviour in finite-state discounted Markov Decision Processes (mdps). We prove a new bound for a modified version of Upper Confidence Reinforcement Learning (ucrl) with only cubic dependence on the horizon. The bound is unimprovable in all parameters except the size of the state/action space, where it depends linearly on the number of non-zero transition probabilities. The lower bound strengthens previous work by being both more general (it applies to all policies) and tighter. The upper and lower bounds match up to logarithmic factors provided the transition matrix is not too dense.