Near-Optimal Offline Reinforcement Learning via Double Variance Reduction

By Ming Yin, Yu Bai, Yu-Xiang Wang. 2021

71 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Reinforcement Learning

Citations in the corpus

Offline Reinforcement Learning as One Big Sequence Modeling Problem (2021, background): “Modeling the states and actions jointly already provides a bias toward generating in-distribution actions, which avoids the need for explicit pessimism (Fujimoto et al., 2019; Kumar et al., 2019a; Ghasemipour et al., 2021; Nair et al., 2020; Jin et al., 2021; Yin et al., 2021; Dadashi et al., 2021).”
Provably efficient representation selection in Low-rank Markov Decision Processes: from online to offline RL (2021, background): “There is also a brunch of work leveraging the variance information in offline RL [Min et al., 2021, Yin et al., 2021, 2022].”
Representation Learning for Online and Offline RL in Low-rank MDPs (2021, background): “On the theoretical side, pessimism allows us to obtain the PAC guarantee on various models when a comparator policy is covered by offline data in some forms (Jin et al., 2020b; Rashidinejad et al., 2021; Yin et al., 2021; Zanette et al., 2021b; Zhang et al., 2021b; Chang et al., 2021).”
Reinforcement Learning as One Big Sequence Modeling Problem (2021, background): “Modeling the states and actions jointly already provides a bias toward generating in-distribution actions, which avoids the need for explicit pessimism [16, 31, 17, 42, 27, 66, 12].”
Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism (2021, background): “For instance, Yin et al. [54] requires a uniformly lower bounded data distribution that traces an optimal policy, which implies that optimal actions should be included in states not visited by the optimal policy.”