Approximate Dynamic Programming By Minimizing Distributionally Robust Bounds

Marek Petrik

Overview

Solving large-scale Markov Decision Processes (MDPs) is a cornerstone of reinforcement learning, but it is frequently plagued by the "curse of dimensionality." To find near-optimal policies, researchers typically rely on Approximate Dynamic Programming (ADP). However, existing ADP methods face significant hurdles, including weak theoretical guarantees (often relying on overly conservative $L_\infty$ error bounds) and instability during training.

This paper introduces Distributionally Robust Approximate Dynamic Programming (DRADP), a novel framework designed to address these shortcomings. By framing the problem as an optimization of a pessimistic lower bound on policy return, DRADP achieves tighter theoretical error bounds based on the $L_1$ norm and demonstrates superior empirical performance compared to classic methods like Least-Squares Policy Iteration (LSPI) and Approximate Linear Programming (ALP).

Methodology: The DRADP Framework

The core innovation of DRADP lies in applying distributionally robust optimization to state occupancy frequencies.

  • Pessimistic Bounds: Instead of attempting to find a universal value function that works for every possible starting state, DRADP focuses on a specific initial distribution. It maximizes a simple lower bound on the return, which mathematically equates to minimizing the worst-case policy loss.
  • Superset Approximation: Previous dual methods attempted to approximate the set of valid occupancy frequencies using a subset. DRADP flips this by using a superset. This robust approach ensures the solution is immunized against uncertainty in state transitions.
  • Mathematical Programming: DRADP can be formulated as a separable bilinear program. Because bilinear programs are notoriously difficult to solve, the authors reformulate it into a Mixed Integer Linear Program (MILP). This allows the problem to be solved efficiently using industrial-grade solvers like IBM CPLEX.
  • Weighted $L_1$ Norm: Unlike algorithms that minimize $L_2$ or $L_\infty$ errors, DRADP provides theoretical guarantees in terms of a weighted $L_1$ norm. This is crucial because $L_1$ bounds are often much tighter and more representative of the actual expected return.

Key Insights

  • Leveraging the Initial Distribution: DRADP recognizes that if the agent's starting distribution is known, the "approximation budget" can be focused on the states the agent is actually likely to visit, yielding a much better policy than globally focused methods.
  • Removing the Discount Penalty: In many RL algorithms, the error bound is penalized by a factor related to the discount rate $\gamma$ (often $1/(1-\gamma)^2$). DRADP provides a bound that completely removes this factor, making it significantly more efficient for long-horizon tasks.
  • Optimization over Simulation: By turning policy improvement into a direct MILP optimization problem, DRADP reduces the need for the massive amounts of simulation data typically required by iterative methods.

Experimental Setup and Results

The authors evaluated DRADP on two primary benchmarks: a classic Inverted Pendulum control task (using 9 radial basis functions and a constant term) and a Synthetic Chain Problem (a 30-state environment tested across 1,000 random instantiations).

Sample Efficiency and Performance

On the Inverted Pendulum task, DRADP proved exceptionally sample-efficient. It reached a near-perfect balancing state (3,000 steps) using significantly fewer training samples than LSPI, ALP, or Approximate Bilinear Programming (ABP).

DRADP achieves near-perfect balancing on the Inverted Pendulum task with significantly fewer training samples than LSPI, ALP, and ABP.

Superior Expected Return

Across the benchmarks, DRADP consistently outperformed ALP and ABP. The authors note that ALP and ABP often underperform in practice because their $L_\infty$ bounds are too conservative. DRADP's theoretical guarantees translated into reliable empirical success, yielding higher expected returns and greater stability.

DRADP demonstrates a higher expected return and greater stability compared to API, ALP, and ABP baselines.

Limitations and Future Work

While DRADP offers strong theoretical and empirical advantages, it is not without limitations:

  • Computational Complexity: Solving a MILP is NP-hard. While manageable for the feature counts and sample sizes typically used in standard ADP, scaling to extremely high-dimensional feature spaces may require further optimization techniques.
  • Sampling Analysis: The current framework assumes samples are provided and focuses on the optimization step. Future work could explore how active learning or specific sampling strategies interact with the DRADP objective.
  • Policy Representation: The paper focuses on policies that are greedy with respect to the approximate value function. Exploring alternative policy representations could yield even stronger theoretical properties.

Summary updated

Abstract

Approximate dynamic programming is a popular method for solving large Markov decision processes. This paper describes a new class of approximate dynamic programming (ADP) methods--distributionally robust ADP--that address the curse of dimensionality by minimizing a pessimistic bound on the policy loss. This approach turns ADP into an optimization problem, for which we derive new mathematical program formulations and analyze its properties. DRADP improves on the theoretical guarantees of existing ADP methods--|it guarantees convergence and L1 norm-based error bounds. The empirical evaluation of DRADP shows that the theoretical guarantees translate well into good performance on benchmark problems.
BibTeX
@inproceedings{petrik2012approximate,
  author = {Marek Petrik},
  title = {{Approximate Dynamic Programming By Minimizing Distributionally Robust Bounds}},
  booktitle = {International Conference on Machine Learning},
  year = {2012},
  url = {https://openreview.net/forum?id=S1ZSPhbOZr},
}
Figure