Approximate Dynamic Programming via a Smoothed Linear Program

Vijay V. Desai, Vivek F. Farias, Ciamac Cyrus Moallemi

TL;DR

This paper introduces a novel "smoothed" approximate linear programming (SALP) approach for dynamic programming problems. SALP offers significantly improved approximation quality and policy performance compared to existing methods, particularly in complex, high-dimensional scenarios like the game of Tetris, achieving an order of magnitude improvement.

What Problem Does This Paper Address?

Dynamic programming (DP) is a powerful tool for solving sequential decision-making problems, but it suffers from the "curse of dimensionality," making it computationally intractable for problems with many states. Approximate Dynamic Programming (ADP) aims to overcome this by finding good approximations to the optimal cost-to-go function. A popular ADP method is Approximate Linear Programming (ALP), which formulates the problem as a linear program (LP) but restricts approximations to be lower bounds of the optimal cost-to-go function. This paper questions whether this lower-bound restriction is ideal and proposes a "smoothed" version of ALP (SALP) that relaxes this constraint, aiming for better approximations and policy performance while remaining computationally tractable.

Methods

The core contribution is the Smoothed Approximate Linear Program (SALP). Unlike the standard ALP, which enforces strict lower bounds on the cost-to-go function approximation, SALP introduces a "violation budget" ($\theta$) and a "constraint violation distribution" ($\pi$). This allows for controlled violations of the ALP constraints, effectively relaxing the strict lower-bound requirement. SALP is formulated as an LP with additional slack variables and a hinge-loss-like penalty on constraint violations. The paper also develops theoretical guarantees for SALP, including approximation and performance bounds, and analyzes its sample complexity, showing it can be solved efficiently using sampled states.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Relaxing Lower Bounds is Beneficial: The strict lower-bound constraint in ALP, while providing theoretical guarantees, can limit the quality of approximations. SALP demonstrates that allowing controlled "violations" can lead to substantially better approximations and, crucially, better policies.
  • Tetris as a Challenging Testbed: The game of Tetris is used as a notoriously difficult, unstructured MDP. Its complexity makes it an excellent benchmark for ADP algorithms, and the significant performance improvement of SALP on Tetris highlights its practical efficacy.
  • SALP Automates Parameter Tuning: The SALP formulation implicitly handles the selection of a "Lyapunov-like" function (or weighting function $\psi$) that is crucial for good performance in ALP. This suggests SALP automates a critical, often ad-hoc, tuning step.
  • Tractability with Sampling: While SALP can have many constraints, the paper shows that a "sampled" version, using a subset of states, remains tractable and provides a good approximation to the full SALP solution. The sample complexity scales favorably with the number of basis functions and problem parameters, not the state space size.

Key Results

  • Theoretical Guarantees: SALP provides stronger approximation and performance guarantees compared to ALP.
  • Tetris Performance: On the game of Tetris, SALP achieved an order of magnitude improvement in performance over ALP. The best SALP policy achieved a performance of 10,775 lines cleared, compared to ALP's 897.
  • Computational Efficiency: The paper demonstrates that SALP can be solved efficiently, even for large numbers of sampled states, by exploiting the structure of the resulting linear programs.

Limitations and Future Work

  • Idealized Assumptions: The theoretical analysis of SALP, like many ADP algorithms, relies on idealized assumptions, such as access to a specific idealized sampling distribution. Loosening these assumptions for specific classes of MDPs is an open research direction.
  • Parameter Selection: While the paper provides a recipe for practical implementation, choosing the sampling distribution and the number of samples still requires careful consideration. The choice of state relevance weights ($v$) in SALP is also non-trivial and may require iterative refinement.
  • Online Learning: The paper suggests exploring online update rules for SALP weights, leading to "data-driven" ADP methods that could perform on par with SALP solutions while retaining online learning benefits.
  • Average Cost DP: Extending the SALP framework to average-cost dynamic programming problems is another promising avenue.
  • Bootstrapping Procedures: Investigating the dynamics of "bootstrapping" procedures, where SALP is solved iteratively using policies from previous iterations, is also suggested.

Summary updated

Abstract

We present a novel linear program for the approximation of the dynamic programming cost-to-go function in high-dimensional stochastic control problems. LP approaches to approximate DP have typicall...
BibTeX
@article{desai2012approximate,
  author = {Vijay V. Desai and Vivek F. Farias and Ciamac Cyrus Moallemi},
  title = {{Approximate Dynamic Programming via a Smoothed Linear Program}},
  journal = {Oper. Res.},
  year = {2012},
  doi = {10.1287/opre.1120.1044},
}
Figure