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 typically relied on a natural 'projection' of a well studied linear program for exact dynamic programming. Such programs restrict attention to approximations that are lower bounds to the optimal cost-to-go function. Our program—the 'smoothed approximate linear program'—is distinct from such approaches and relaxes the restriction to lower bounding approximations in an appropriate fashion while remaining computationally tractable. Doing so appears to have several advantages: First, we demonstrate substantially superior bounds on the quality of approximation to the optimal cost-to-go function afforded by our approach. Second, experiments with our approach on a challenging problem (the game of Tetris) show that the approach outperforms the existing LP approach (which has previously been shown to be competitive with several ADP algorithms) by an order of magnitude.
Introduction
Markov Decision Processes (MDPs) provide a robust framework for sequential decision-making under uncertainty. However, the "curse of dimensionality" renders exact solutions computationally impossible for large-scale systems. Approximate Dynamic Programming (ADP) addresses this by estimating the optimal cost-to-go function, $J^*$, using a linear combination of basis functions. A popular technique, Approximate Linear Programming (ALP), formulates this estimation as a linear program. However, ALP imposes a strict point-wise lower-bound constraint on the approximation, which can lead to overly pessimistic results and poor policy performance. This paper introduces a novel relaxation of these constraints to improve approximation quality.
The Smoothed Approximate Linear Program (SALP)
The core innovation of this work is the Smoothed Approximate Linear Program (SALP). Unlike ALP, which requires the approximation to be a lower bound everywhere, SALP introduces "soft" constraints. By incorporating slack variables and a "violation budget" ($\theta$), SALP allows the approximation to exceed $J^*$ in certain regions of the state space, provided the expected violation remains within the budget. This shift from a uniform lower bound to a relaxed, smoothed constraint allows for a much better fit in states that are critical for decision-making.
This relaxation is mathematically implemented using a hinge-loss-like penalty. Despite the added complexity, the authors demonstrate that SALP remains computationally tractable. By exploiting a "diagonal plus rank-one" structure in the Hessian of the optimization problem, SALP can be solved efficiently even for problems with millions of constraints, scaling linearly with the number of samples. This structure is critical for scalability, as it allows for the use of specialized interior-point methods that avoid the cubic complexity typically associated with large-scale linear programming. Furthermore, SALP implicitly automates the search for a Lyapunov function, a task that previously required significant domain expertise in the context of ALP.
Experimental Evaluation: Tetris
The effectiveness of SALP was evaluated on the game of Tetris, a standard benchmark for ADP due to its massive state space ($\sim 10^{60}$). Using a standard set of 22 basis functions, SALP was compared against traditional ALP and other popular ADP methods. The game of Tetris is notoriously difficult due to its lack of obvious structure, making it an ideal test for the robustness of approximation methods.
SALP achieved an average performance of 10,775 lines per game, representing a 10x improvement over standard ALP (~897 lines). Furthermore, SALP outperformed state-of-the-art methods like Policy Gradient (~5,500 lines) and TD-Learning (~4,471 lines) by a factor of two. These results underscore the practical benefits of relaxing the lower-bound constraint.
Conclusion
The Smoothed Approximate Linear Program represents a significant step forward in ADP. By relaxing the rigid lower-bound constraints of ALP, SALP provides tighter approximation bounds and superior empirical performance. The method's ability to maintain computational tractability while providing order-of-magnitude improvements in complex benchmarks like Tetris suggests broad applicability to other high-dimensional control problems. Future work may explore automated hyperparameter tuning for the violation budget and the application of SALP to online learning scenarios using stochastic gradient methods.
Summary updated