Adaptive Sampling for Best Policy Identification in Markov Decision Processes
Adaptive Sampling for Best Policy Identification in Markov Decision Processes
复制标题
马尔可夫决策过程中最佳策略识别的自适应采样
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
A. Proutière
中科院分区：
文献类型：
--
作者：
Aymen Al Marjani;A. Proutière
我们研究了折扣马尔可夫决策过程（MDP）的最佳策略识别问题时，学习者有机会获得一个生成模型。我们的目标是设计一个学习算法返回的最佳政策，尽可能早。我们首先推导出一个特定于问题的样本复杂度的下界满足任何学习算法。这个下限对应于一个最佳的样本分配，解决了一个非凸的程序，因此，很难利用在设计有效的算法。然后，我们提供了一个简单的和严格的样本复杂度下限的上限，其相应的接近最优的样本分配变得明确。上界取决于MDP的特定泛函，例如次优间隙和下一状态值函数的方差，从而真正捕获MDP的硬度。最后，我们设计KLB-TS（KL球跟踪和停止），跟踪这个接近最优的分配算法，并提供渐近保证其样本复杂性（几乎肯定和预期）。KLB-TS对国家的最先进的算法的优势进行了讨论和数值说明。
We investigate the problem of best-policy identification in discounted Markov Decision Processes (MDPs) when the learner has access to a generative model. The objective is to devise a learning algorithm returning the best policy as early as possible. We first derive a problem-specific lower bound of the sample complexity satisfied by any learning algorithm. This lower bound corresponds to an optimal sample allocation that solves a non-convex program, and hence, is hard to exploit in the design of efficient algorithms. We then provide a simple and tight upper bound of the sample complexity lower bound, whose corresponding nearly-optimal sample allocation becomes explicit. The upper bound depends on specific functionals of the MDP such as the sub-optimality gaps and the variance of the next-state value function, and thus really captures the hardness of the MDP. Finally, we devise KLB-TS (KL Ball Track-and-Stop), an algorithm tracking this nearly-optimal allocation, and provide asymptotic guarantees for its sample complexity (both almost surely and in expectation). The advantages of KLB-TS against state-of-the-art algorithms are discussed and illustrated numerically.
DOI：
10.1287/opre.2023.2451
发表时间：
2020-05
期刊：
Oper. Res.
影响因子：
--
作者：
Gen Li;Yuting Wei;Yuejie Chi;Yuantao Gu;Yuxin Chen
通讯作者：
Gen Li;Yuting Wei;Yuejie Chi;Yuantao Gu;Yuxin Chen