Approximate Dynamic Programming By Minimizing Distributionally Robust Bounds

Marek Petrik

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 $L_1$ norm based error bounds. The empirical evaluation of DRADP shows that the theoretical guarantees translate well into good performance on benchmark problems.

Introduction

Solving large-scale Markov Decision Processes (MDPs) is a fundamental challenge in reinforcement learning, often hindered by the "curse of dimensionality." As state spaces grow, computing an exact optimal policy becomes computationally intractable. Researchers typically turn to Approximate Dynamic Programming (ADP) to find near-optimal policies using limited features or samples. However, traditional ADP methods like Approximate Linear Programming (ALP) and Least-Squares Policy Iteration (LSPI) face significant hurdles: they often rely on conservative $L_\infty$ error bounds that assume a policy must perform well across all possible states, or they lack the stability and convergence guarantees required for complex environments.

This paper introduces Distributionally Robust Approximate Dynamic Programming (DRADP), a novel framework that shifts the optimization objective from global $L_\infty$ bounds to tighter, distribution-specific $L_1$ bounds. By minimizing a pessimistic bound on policy loss, DRADP provides a theoretically grounded and practically efficient alternative to existing algorithms.

The DRADP Framework

The core innovation of DRADP lies in its use of Robust Optimization and a shift in perspective from value functions to occupancy frequencies. While standard methods focus on how much reward a state is worth, DRADP analyzes how often a policy visits specific states.

Superset Approximation and Pessimism

Existing dual methods for ADP often attempt to approximate the set of possible occupancy frequencies from the "inside" (a subset). In contrast, DRADP approximates these frequencies from the "outside" (a superset). This allows the algorithm to calculate a pessimistic lower bound on the policy's return. By maximizing this distributionally robust lower bound, DRADP ensures that the resulting policy is "immunized" against the uncertainty and errors introduced by function approximation.

$L_1$ Optimization

By focusing on a specific initial distribution ($\alpha$), the paper derives error bounds based on the weighted $L_1$ norm. This is significantly tighter than the $L_\infty$ norm because it ignores errors in states that the policy is unlikely to visit. This shift from global accuracy to distributional robustness allows for a $1/(1-\gamma)$ factor improvement in the error bound compared to standard Approximate Policy Iteration (API) bounds.

Mathematical Formulation

To make the distributionally robust objective solvable, the authors formulate DRADP as a Separable Bilinear Program. Because these programs are generally NP-hard, the paper provides a refinement into a Mixed Integer Linear Program (MILP) using McCormick inequalities. This formulation allows the problem to be solved efficiently using industrial-strength solvers like IBM CPLEX, bridging the gap between complex theoretical optimization and real-world engineering constraints.

Empirical Evaluation

The paper evaluates DRADP against two primary benchmarks to test its efficiency and robustness:

  1. Inverted Pendulum: In this classic continuous control task, DRADP reached maximum performance (3,000 balancing steps) using significantly fewer training samples than LSPI. Other methods, such as ALP and Approximate Bilinear Programming (ABP), failed to solve the problem effectively using the standard radial basis function features.
  2. Synthetic Chain Problem: Tested over 1,000 random instantiations, DRADP consistently outperformed LSPI and other linear programming approaches. It maintained a higher expected return across varying initial distributions, proving its stability in stochastic environments.

Despite the underlying NP-hard nature of the optimization, the MILP formulation allowed the researchers to find high-quality policies within a 60-second time limit, demonstrating the method's viability for practical application.

Conclusion and Future Work

DRADP represents a significant step forward in ADP by providing a method that is both theoretically robust and empirically superior to many standard benchmarks. By leveraging $L_1$ norms and pessimistic bounds, it offers a more nuanced approach to function approximation in large MDPs.

Future research directions include:

  • Scaling: Adapting the MILP approach to handle massive feature sets, such as those found in deep neural networks.
  • Online Learning: Extending the current "batch" setting to an online environment where the agent learns through active interaction.
  • Parameter Estimation: Developing methods to estimate the "concentration coefficients" of MDPs, which are currently required for the tightest theoretical bounds but are difficult to calculate in practice.

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