Is Pessimism Provably Efficient for Offline RL?

Ying Jin, Zhuoran Yang, Zhaoran Wang

Abstract

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.

Introduction

Reinforcement Learning (RL) has traditionally relied on active exploration—the "trial and error" process—to discover optimal behaviors. However, in many real-world applications such as precision medicine, autonomous driving, or industrial control, active exploration is often too risky, unethical, or expensive. This necessitates Offline RL, where an agent must learn an optimal policy from a fixed, pre-collected dataset without further environment interaction.

The primary obstacle in offline RL is distribution shift. Unlike online RL, where the agent can visit states to verify its beliefs, an offline agent is limited to the provided data. If the dataset lacks "coverage"—meaning it doesn't adequately sample all relevant state-action pairs—the agent may encounter spurious correlations. It might observe a high reward in a poorly sampled region and mistakenly conclude that a suboptimal action is optimal. Most existing theoretical frameworks bypass this by assuming "concentrability" (sufficient coverage), an assumption that rarely holds in practice.

Methodology: Pessimistic Value Iteration (PEVI)

To address the challenge of insufficient coverage, the authors introduce Pessimistic Value Iteration (PEVI). The algorithm's core philosophy is a direct inversion of the "Optimism in the Face of Uncertainty" principle used in online RL (e.g., Upper Confidence Bounds).

The Uncertainty Quantifier and Penalty

PEVI operates through three main steps:

  1. Uncertainty Estimation: For every state-action pair $(s, a)$, the algorithm computes an uncertainty quantifier, $\Gamma(s, a)$, which represents the statistical confidence in the estimated value.
  2. Pessimistic Penalty: Instead of adding this uncertainty as a "bonus" to encourage exploration, PEVI subtracts it as a penalty. The value update effectively penalizes actions with high uncertainty.
  3. Policy Selection: The agent chooses actions that maximize this penalized value, effectively becoming "pessimistic" about actions it hasn't seen enough of in the dataset.
Figure 1: This figure illustrates how actions with low data coverage (small $N(a)$) can lead to over-optimistic value estimates, justifying the need for a pessimistic penalty to avoid spurious correlations.

As shown in Figure 1, actions with a large number of samples ($N(a_1), N(a_2)$) have small uncertainty intervals. However, actions with few samples ($N(a_{|\mathcal{A}|})$) exhibit large variance. Without the pessimistic penalty, the estimated value $\widehat{\mu}(a_{|\mathcal{A}|})$ might be significantly higher than the true value $\mu(a_{|\mathcal{A}|})$ due to noise, leading the agent to select a suboptimal action based on a spurious correlation.

Theoretical Results

The paper provides a rigorous mathematical foundation for PEVI across different MDP structures.

General MDPs and Linear MDPs

For general MDPs, the authors establish a data-dependent upper bound on suboptimality. This bound is "adaptive," meaning it scales with the uncertainty specifically along the path of the optimal policy, rather than the entire state space. This implies that if the dataset covers the optimal path well, PEVI will perform well regardless of the rest of the data.

When specialized to Linear MDPs, the results are even more powerful. The authors prove that PEVI's suboptimality matches the information-theoretic lower bound (up to factors of dimension $d$ and horizon $H$). This establishes that pessimism is not just a heuristic but is minimax optimal.

The "Hard Instance"

To prove these bounds are tight, the authors construct a synthetic "Hard Instance"—a specific linear MDP designed to be as difficult as possible for any offline learner. By showing that no algorithm can outperform PEVI on this instance, they confirm its optimality.

Key Insights

  • Flipping the Script: The transition from online to offline RL can be viewed mathematically as a sign flip. The same UCB tools used for exploration are repurposed for safety and robustness.
  • The Oracle Property: PEVI exhibits an "oracle-like" property where it performs as well as the data allows for the optimal policy. It effectively ignores "lucky" outliers in poorly sampled regions.
  • Eliminating Spurious Correlations: Pessimism acts as a statistical filter. By penalizing uncertainty, the algorithm ensures that high-value estimates are backed by sufficient evidence, preventing the agent from being "tricked" by sparse data regions.

Conclusion and Future Work

This work demonstrates that pessimism is a fundamental requirement for provably efficient offline RL. By systematically penalizing uncertainty, PEVI achieves minimax optimality in linear settings and provides strong guarantees for general MDPs.

However, challenges remain. While the theory extends to Reproducing Kernel Hilbert Spaces (RKHS), applying these tight bounds to non-linear function approximators like deep neural networks is an open problem. Additionally, the computational cost of maintaining uncertainty estimates can be high, and the sensitivity of the penalty scaling factor $\beta$ requires careful tuning in practical applications.

Summary updated

Abstract

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.
BibTeX
@inproceedings{jin2021is,
  author = {Ying Jin and Zhuoran Yang and Zhaoran Wang},
  title = {{Is Pessimism Provably Efficient for Offline RL?}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=Q91pUftYWw},
}
Figure