Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Ming Yin;Yu Bai;Yu-Xiang Wang
中科院分区：
文献类型：
--
作者：
Ming Yin;Yu Bai;Yu-Xiang Wang
我们考虑离线强化学习（RL）的问题-一种动机良好的RL设置，旨在仅使用历史数据进行策略优化。尽管其广泛的适用性，离线RL的理论理解，如其最佳的样本复杂性，仍然在很大程度上开放，即使在基本的设置，如马尔可夫决策过程（MDP）。在本文中，我们提出了Off-Policy双方差减少（OPDVR），一个新的基于方差减少的离线RL算法。我们的主要结果表明，OPDVR可证明确定一个$\widetilde{O}（H^2/d_m\epsilon^2）$情节的离线数据在有限的地平线平稳过渡设置，其中$H$是地平线的长度和$d_m$是最小的边际状态-动作分布的行为策略诱导的最优策略。这提高了最好的已知上限的一个因素$H$。此外，我们建立了一个信息理论的下限$\欧米茄（H^2/d_m\epsilon^2）$证明OPDVR是最佳的对数因子。最后，我们表明，OPDVR也实现了速率最优的样本复杂度下的替代设置，如有限地平线MDP与非平稳过渡和无限地平线MDP折扣奖励。
We consider the problem of offline reinforcement learning (RL) -- a well-motivated setting of RL that aims at policy optimization using only historical data. Despite its wide applicability, theoretical understandings of offline RL, such as its optimal sample complexity, remain largely open even in basic settings such as \emph{tabular} Markov Decision Processes (MDPs). In this paper, we propose Off-Policy Double Variance Reduction (OPDVR), a new variance reduction based algorithm for offline RL. Our main result shows that OPDVR provably identifies an $\epsilon$-optimal policy with $\widetilde{O}(H^2/d_m\epsilon^2)$ episodes of offline data in the finite-horizon stationary transition setting, where $H$ is the horizon length and $d_m$ is the minimal marginal state-action distribution induced by the behavior policy. This improves over the best known upper bound by a factor of $H$. Moreover, we establish an information-theoretic lower bound of $\Omega(H^2/d_m\epsilon^2)$ which certifies that OPDVR is optimal up to logarithmic factors. Lastly, we show that OPDVR also achieves rate-optimal sample complexity under alternative settings such as the finite-horizon MDPs with non-stationary transitions and the infinite horizon MDPs with discounted rewards.