DeepAveragers: Offline Reinforcement Learning by Solving Derived Non-Parametric MDPs

Aayam Shrestha, Stefan Lee, Prasad Tadepalli, Alan Fern

Introduction

Offline Reinforcement Learning (RL) presents a unique challenge: learning an optimal policy from a fixed dataset without any further environment interaction. This setting typically suffers from two major issues. First, there is a representation mismatch between the deep, continuous latent spaces used in modern RL and the discrete, tabular models required by powerful planning algorithms like Value Iteration. Second, planners tend toward over-optimism, exploiting inaccuracies in the model—specifically in regions with sparse data—to find "hallucinated" high-reward paths that fail in practice.

DeepAveragers addresses these hurdles by introducing the Deep Averagers with Costs MDP (DAC-MDP) framework. This approach transforms a static dataset into a finite, tabular model using deep representations and k-Nearest Neighbors (kNN), enabling the use of classic, rigorous planning algorithms directly on top of deep latent features.

The DAC-MDP Framework

The transition from a raw experiential dataset to a deployable policy follows a structured four-step process:

  1. Representation Learning: Observations are mapped into a latent space using a neural network, such as the penultimate layer of a pre-trained DQN.
  2. Model Compilation: The dataset is treated as a non-parametric model. For any state-action pair, the reward and next-state distribution are computed as an average of its $k$ nearest neighbors in the latent space.
  3. Pessimism via Costs: To counteract over-optimism, a cost $C$ is subtracted from the reward, proportional to the distance to the neighbors. This ensures the planner remains within well-supported regions of the state space.
  4. GPU-Accelerated Planning: The resulting finite MDP is solved using a custom GPU implementation of Value Iteration (VI), producing an optimal policy for the dataset's "core" states. This policy is then extended to unseen states online via a one-step look-ahead.
The DAC-MDP pipeline: from an experiential dataset to a solved model capable of handling unseen states online.

Key Insights: The Necessity of Pessimism

A central finding of this work is that pessimism is non-negotiable. Without the cost factor ($C=0$), the planner essentially "hallucinates" high rewards in data-sparse regions, leading to catastrophic performance. By introducing a distance-based penalty, the agent is incentivized to stay near the data it has actually seen.

Average return vs. cost parameter C across different dataset qualities. Performance is near zero when C=0, highlighting the critical role of pessimism.

Beyond pessimism, the authors demonstrate that tabular planning is surprisingly scalable. Utilizing sparse transition matrices and GPU acceleration, MDPs with millions of states can be solved in under 30 seconds. This efficiency allows for zero-shot adaptability; for instance, if an agent's environment or constraints change (e.g., an actuator failure), the DAC-MDP can be re-solved with new penalties in seconds without retraining the underlying neural network.

Results and Performance

The framework was evaluated on Atari 2600 games and 3D navigation tasks in Gym Mini-World. On the Atari benchmark, DAC-MDPs generally matched or outperformed strong offline baselines like BCQ and DQN. In navigation tasks, the model-based nature of the approach allowed for flexible adjustments to horizons and safety requirements simply by tuning planning parameters—a feat difficult for standard model-free offline RL.

Conclusion and Future Work

DeepAveragers bridges the gap between deep representation learning and classical planning. While the method shows great promise in performance and flexibility, it faces challenges regarding memory overhead, as the footprint scales linearly with dataset size. Future work may focus on moving kNN lookups to the GPU to further reduce compilation time and exploring representations specifically optimized for the DAC-MDP structure.

Summary updated

Abstract

We study an approach to offline reinforcement learning (RL) based on optimally solving finitely-represented MDPs derived from a static dataset of experience. This approach can be applied on top of any learned representation and has the potential to easily support multiple solution objectives as well as zero-shot adjustment to changing environments and goals. Our main contribution is to introduce the Deep Averagers with Costs MDP (DAC-MDP) and to investigate its solutions for offline RL. DAC-MDPs are a non-parametric model that can leverage deep representations and account for limited data by introducing costs for exploiting under-represented parts of the model. In theory, we show conditions that allow for lower-bounding the performance of DAC-MDP solutions. We also investigate the empirical behavior in a number of environments, including those with image-based observations. Overall, the experiments demonstrate that the framework can work in practice and scale to large complex offline RL problems.
BibTeX
@inproceedings{shrestha2021deepaveragers,
  author = {Aayam Shrestha and Stefan Lee and Prasad Tadepalli and Alan Fern},
  title = {{DeepAveragers: Offline Reinforcement Learning by Solving Derived Non-Parametric MDPs}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=eMP1j9efXtX},
}
Figure