Provably Good Batch Off-Policy Reinforcement Learning Without Great Exploration

Yao Liu, Adith Swaminathan, Alekh Agarwal, Emma BrunskillNeurIPS 2020 · OpenReview

Batch Reinforcement Learning (RL) involves learning a policy from a fixed dataset without further environment interaction. This paradigm is critical for high-stakes fields like healthcare or autonomous driving, where online "trial and error" is dangerous or expensive.

However, batch RL is notoriously difficult due to the "deadly triad": the combination of off-policy learning, function approximation, and bootstrapping. Standard batch RL algorithms often become overly optimistic, mistakenly assigning high values to actions in states that were rarely visited in the dataset. Existing theoretical guarantees for batch RL usually rely on a strict concentrability assumption, which requires the dataset to cover all possible policies. In practice, this is almost never true. When this assumption fails, traditional error bounds explode.

This paper introduces a new approach that replaces the unrealistic concentrability assumption with a principle of pessimism. By explicitly filtering out state-action pairs with low data support, the authors provide algorithms that are provably guaranteed to find the best policy supported by the available data, rather than failing due to over-optimistic extrapolations.

A Pessimistic Approach to Value Estimation

In online RL, agents use "optimism in the face of uncertainty" to encourage exploration. In offline RL, the opposite is required: agents must use pessimism to stay within the "safe" regions of the data.

The authors propose two main algorithms: Pessimistic Policy Iteration (PPI) and Pessimistic Q Iteration (PQI). The key innovation in these algorithms is the $\zeta$-filter, which modifies standard Bellman operators into a pessimistic version:

  1. Density Estimation: The marginal state-action density $\mu(s, a)$ is estimated from the batch data.
  2. Filtering: A filter $\zeta(s, a)$ is defined, which equals 1 if the density is above a threshold $b$, and 0 otherwise.
  3. Pessimistic Backup: During value estimation, any state-action pair with low support ($\zeta = 0$) is assigned a value of zero—the most pessimistic estimate.

Crucially, while previous methods (like BCQ or BEAR) used pessimism based on the conditional action distribution (how likely an action is given a state), this paper argues for using the marginal distribution (how likely a specific state-action pair is in the whole dataset). If a state itself is extremely rare, value estimates for it are likely wrong, regardless of the conditional action probability. Filtering based on total state-action density prevents the agent from "hallucinating" high rewards in these rare states.

Illustrative toy MDPs: (a) MDP with a rare transition and (b) Combination lock.

Experimental Validation

The authors evaluate their approach across several environments, starting with illustrative toy MDPs specifically designed to expose the flaws of existing algorithms. As shown in the figure above, the "Rare Transition" and "Combination Lock" MDPs feature states that are rare but have high-probability actions.

Success rates of various batch RL algorithms on the toy MDPs across different sample sizes.

In these "unsolvable" MDPs, PPI and PQI successfully found the optimal policy. In contrast, baselines like BCQ and BEAR failed because they bootstrapped values from rare, poorly-estimated states. The success rate plots demonstrate that PQI and PPI maintain a near 100% success rate, while other methods suffer significant performance drops as they fall victim to over-optimism.

Beyond toy problems, the authors tested PQI on CartPole-v0, where it achieved better and more consistent performance than SPIBB or BCQL across varying levels of data coverage. Finally, they implemented a deep RL version called Pessimistic Q-Learning (PQL) using Variational Auto-Encoders (VAEs) for density estimation. On standard D4RL continuous control benchmarks (e.g., MuJoCo tasks), PQL significantly outperformed BEAR and BCQ. For instance, on the Hopper-medium task, PQL scored 75.2 compared to BEAR's 47.6.

Limitations and Future Directions

While highly effective, the method's success relies heavily on the accuracy of the density estimate $\hat{\mu}$. Estimating density in very high-dimensional or continuous spaces remains a difficult problem. Additionally, the threshold $b$ is a critical hyperparameter: setting it too high makes the agent overly conservative, while setting it too low invites over-optimism.

Finally, assigning a value of exactly zero is a "hard" form of pessimism. Future work could explore "softer" uncertainty measures—such as epistemic uncertainty derived from ensembles—integrated into this marginal density framework to provide more nuanced pessimistic bounds.

Summary updated

Abstract

Batch reinforcement learning (RL) is important to apply RL algorithms to many high stakes tasks. Doing batch RL in a way that yields a reliable new policy in large domains is challenging: a new decision policy may visit states and actions outside the support of the batch data, and function approximation and optimization with limited samples can further increase the potential of learning policies with overly optimistic estimates of their future performance. Some recent approaches to address these concerns have shown promise, but can still be overly optimistic in their expected outcomes. Theoretical work that provides strong guarantees on the performance of the output policy relies on a strong concentrability assumption, which makes it unsuitable for cases where the ratio between state-action distributions of behavior policy and some candidate policies is large. This is because, in the traditional analysis, the error bound scales up with this ratio. We show that using \emph{pessimistic value estimates} in the low-data regions in Bellman optimality and evaluation back-up can yield more adaptive and stronger guarantees when the concentrability assumption does not hold. In certain settings, they can find the approximately best policy within the state-action space explored by the batch data, without requiring a priori assumptions of concentrability. We highlight the necessity of our pessimistic update and the limitations of previous algorithms and analyses by illustrative MDP examples and demonstrate an empirical comparison of our algorithm and other state-of-the-art batch RL baselines in standard benchmarks.
BibTeX
@inproceedings{liu2020provably,
  author = {Yao Liu and Adith Swaminathan and Alekh Agarwal and Emma Brunskill},
  title = {{Provably Good Batch Off-Policy Reinforcement Learning Without Great Exploration}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=gK14MDpTBFf},
}
Figure