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

Aayam Kumar Shrestha, Stefan Lee, Prasad Tadepalli, Alan Fern

Offline reinforcement learning (RL) promises to learn optimal policies from fixed, pre-collected datasets without requiring further, potentially dangerous, environment interaction. However, bridging the gap between continuous deep learning representations and robust tabular planning remains a challenge. DeepAveragers introduces a novel approach to offline RL by converting a static dataset into a "Deep Averagers with Costs" MDP (DAC-MDP). By incorporating a distance-based penalty to enforce pessimism and leveraging GPU-accelerated tabular planning, this framework achieves state-of-the-art performance and zero-shot task adaptation without traditional model-free training loops.

The Challenge of Offline RL

Current offline RL approaches typically fall into two camps:

  1. Model-free methods often struggle with "distributional shift." When the agent attempts actions not well-represented in the data, it generates over-optimistic value estimates, leading to catastrophic failures.
  2. Model-based methods use deep neural networks to simulate the environment. However, near-optimal planners tend to exploit inaccuracies in these learned models.

The core gap is a mismatch: continuous, high-dimensional representations learned by deep networks don't easily translate to the discrete, tabular formats required by classic planners. Furthermore, these planners need a mechanism for "pessimism" to avoid trusting the model in sparse data regions.

Introducing the DAC-MDP Framework

The authors address this gap with the Deep Averagers with Costs MDP (DAC-MDP).

The DAC-MDP Pipeline
  • Non-Parametric Modeling: Instead of learning a global transition function via a neural network, the DAC-MDP defines transitions and rewards based on the $k$-nearest neighbors (kNN) in the dataset.
  • The "Core State" Trick: While technically defined over a continuous latent space, the DAC-MDP has a special structure. Its optimal policy can be found by solving a finite, tabular MDP consisting only of the "core" states actually present in the dataset.
  • GPU-Accelerated Value Iteration: To scale this tabular approach, the authors implemented a custom GPU-based Value Iteration (VI) solver, allowing them to solve MDPs with millions of states in seconds.
  • Pessimism via Costs: To prevent the planner from exploiting data "holes," a cost penalty is added to the reward function. This penalty grows linearly with the distance between the current state-action pair and its nearest neighbors in the dataset.

Key Insights and Results

The framework was evaluated across CartPole, Atari 2600 (up to 2.5M transitions), and Gym Mini-World (a 3D navigation environment).

Impact of Cost Parameter on Return
  • Pessimism is Mandatory: As shown in the CartPole experiments, setting the cost penalty ($C$) to zero results in extremely poor performance. Without it, the planner finds "fake" high-reward paths in under-represented areas. Adding the cost forces the agent to stay close to known data.
  • Robust Planning: Because the method uses an explicit planner, it avoids the "deadly triad" of instability common in standard Q-learning (combining function approximation, bootstrapping, and off-policy learning).
  • Scalability and Performance: On the 2.5M transition Atari dataset, DAC-MDPs consistently matched or improved upon the base offline RL algorithms (BCQ and DQN) used to generate the representations. The GPU-optimized VI provided a 20x to 1000x speedup over serial CPU implementations, solving 2.5-million-state MDPs in under 3 minutes.
  • Zero-Shot Flexibility: Because the model is solved via planning, users can change the reward function or action space at test time. In the 3D Mini-World environment, the agent demonstrated zero-shot transfer by successfully navigating a room even after its ability to turn left was artificially disabled, requiring no new training data.

Limitations and Future Directions

While powerful, the DAC-MDP approach has a few limitations:

  • Memory Overhead: As a non-parametric method, memory requirements scale linearly with dataset size. Tens of millions of points could become a bottleneck.
  • kNN Sensitivity: Performance is heavily tied to the distance metric in the latent space. If the representation fails to capture true state similarity, the kNN-based transitions will be inaccurate.

Future work will likely explore sophisticated sub-sampling techniques for larger datasets and investigate how to learn representations specifically optimized for non-parametric planning.

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 Kumar 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