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.

本文提出了一种新的算法 OPDVR 用于离线强化学习中的方差缩减，其能够证明在离线数据情况下，在有限时间内获得最优策略，同时在某些环境设定下具有最优样本复杂度，为离线强化学习的发展提供了新方案。