Is Pessimism Provably Efficient for Offline RL?

By Ying Jin, Zhuoran Yang, Zhaoran Wang. 2020

437 citations recorded by the source corpus.

We study offline reinforcement learning (RL), which aims to learn an optimal policy based on a dataset collected a priori. Due to the lack of further interactions with the environment, offline RL suffers from the insufficient coverage of the dataset, which eludes most existing theoretical analysis. In this paper, we propose a pessimistic variant of the value iteration algorithm (PEVI), which incorporates an uncertainty quantifier as the penalty function. Such a penalty function simply flips the sign of the bonus function for promoting exploration in online RL, which makes it easily implementable and compatible with general function approximators. Without assuming the sufficient coverage of the dataset, we establish a data-dependent upper bound on the suboptimality of PEVI for general Markov decision processes (MDPs). When specialized to linear MDPs, it matches the information-theoretic lower bound up to multiplicative factors of the dimension and horizon. In other words, pessimism is not only provably efficient but also minimax optimal. In particular, given the dataset, the learned policy serves as the"best effort"among all policies, as no other policies can do better. Our theoretical analysis identifies the critical role of pessimism in eliminating a notion of spurious correlation, which emerges from the"irrelevant"trajectories that are less covered by the dataset and not informative for the optimal policy.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Statistical Learning Theory

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 Management Science and Operations Research

In Reinforcement Learning

In Statistical Learning Theory

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).”
Continuous Doubly Constrained Batch Reinforcement Learning (2021, methodology): “We use these three aspects to design a penalty for Q-value updates to be more pessimistic (Buckman et al., 2021; Jin et al., 2020).”
COMBO: Conservative Offline Model-Based Policy Optimization (2021, background): “Note that in general, the required value of β may be quite large similar to prior works, which typically utilize a large constant β, which may be in the form of a penalty on a regularizer [36, 29] or as constants in theoretically optimal algorithms [23, 49].”
Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, background): “Another line of work studies the sample complexity of offline policy optimization in conjunction with function approximation (Chen & Jiang, 2019; Xie & Jiang, 2020b,a; Jin et al., 2020).”
RAFT: Reward rAnked FineTuning for Generative Foundation Model Alignment (2023, background): “The reason behind this observation lies in the offline RL theory (see, e.g., (Xie et al., 2021; Jin et al., 2021; Xiong et al., 2022)), which suggests that the model’s performance in offline learning heavily depends on the coverage of the offline dataset.”
Provably efficient representation selection in Low-rank Markov Decision Processes: from online to offline RL (2021, background): “As for the ϵ -greedy algorithm, although the greedy policy can learn very fast at the beginning, it eventually had a much higher cumulative regret since it could not explore the environment well.”
Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint (2023, background): “…(similar to the practical choice of different model variants and temperature) for the fixed π 1 t , thus facilitating the learning of the main agent (similar idea was considered in the study of two-player zero-sum Markov game (Jin et al., 2021a; Huang et al., 2021; Xiong et al., 2022b)).”
Representation Learning for Online and Offline RL in Low-rank MDPs (2021, methodology): “The representation φ in a low-rank MDP not only linearizes the optimal state-action value function of the MDP (Jin et al., 2020a), but also linearizes the transition operator.”
Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons (2023, background): “The idea of introducing pessimism for offline RL has been studied in recent year (Jin et al., 2021; Rashidinejad et al., 2021; Li et al., 2022; Xie et al., 2021b; Zanette, 2022; Zanette et al., 2021; Xie et al., 2021a).”
Bellman-consistent Pessimism for Offline Reinforcement Learning (2021, methodology): “To make it concrete, that is O ( Careful readers may notice that Jin et al. [2021] compete with π ⋆ whereas we can only compete with the best policy in Π Φ , but this can be easily addressed without changing the order of our error bound: in Appendix B.2 we show that selecting a large policy radius…”
Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism (2021, methodology): “A similar algorithm design has recently appeared in [17].”