Dec, 2016
随机原始对偶方法和强化学习样本复杂性
Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning
Yichen Chen, Mengdi Wang
TL;DR本文研究了马尔可夫决策过程 (MDP) 的最优策略在线估计问题，并提出了一类基于随机原始对偶法的方法，利用 Bellman 方程的内在极小极大对偶性进行优化。 这些方法具有小的存储空间和低的计算复杂度，通过观察新的状态转移更新值和策略估计的少数坐标。 对于无限时间折扣奖励 MDP，这些 SPD 方法使用 O (|S|^4 |A|^2σ^2/(1-γ)^6ε^2) 的迭代 / 样本数可以高概率地找到绝对 ε- 最优策略，对于有限时间 MDP，迭代次数为 O (|S|^4 |A|^2H^6σ^2/ε^2)。