Information Relaxation and A Duality-Driven Algorithm for Stochastic Dynamic Programs

Nan Chen, Xiang Ma, Yanchu Liu, Wei YuarXiv 2020 · DOI · arXiv

Introduction

Stochastic Dynamic Programming (SDP) serves as the mathematical foundation for sequential decision-making under uncertainty, with applications ranging from inventory management to high-frequency trading. However, solving these problems optimally is notoriously difficult due to the "curse of dimensionality"—the exponential growth of computational requirements as state variables increase. Consequently, practitioners often rely on heuristics. While these rules of thumb are functional, they leave two critical questions unanswered: how far is the heuristic from the optimal solution, and how can it be systematically improved?

The Duality-Driven Approach

This research introduces the Duality-Driven Dynamic Programming (DDP) algorithm, an iterative method designed to obtain and improve confidence interval estimates for the true value of finite-horizon SDPs. The approach is built upon the concept of information relaxation.

In a relaxed version of a stochastic problem, a decision-maker is granted "perfect foresight" (the ability to see future realizations of uncertainty). To prevent this from becoming trivial, a penalty is applied to the objective function to punish the use of this future information. The authors demonstrate that with an appropriately chosen penalty, the solution to this relaxed dual problem matches the solution to the original, complex SDP.

Algorithmic Framework

The DDP algorithm begins with a sub-optimal policy and iteratively constructs increasingly refined penalties. A key theoretical contribution of this work is the proof that for finite-horizon problems, the sequence of dual value estimates yielded by this process monotonically converges to the true optimal value function within a finite number of iterations.

To address high-dimensional applications where exact computation is impossible, the authors implement a regression-based Monte Carlo algorithm. This implementation involves:

  1. State Sampling: Using a "state sampler" to explore the state space comprehensively, avoiding the pitfall of getting stuck in sub-optimal regions of data.
  2. Function Approximation: Utilizing basis functions (such as polynomials or splines) to approximate the value function across the sampled states.
  3. Deterministic Inner Problems: Once a sample path of randomness is fixed, the optimization problem becomes deterministic. This allows the use of efficient off-the-shelf solvers (like Difference-of-Convex programming), significantly reducing computational overhead.

Experimental Validation

The effectiveness of the DDP algorithm was tested on several challenging problems in Operations Research, known for being difficult to solve for optimality:

  • Optimal Order Execution: In a scenario involving market frictions and price impact, a standard Linear-Quadratic heuristic initially showed an 18.8% duality gap (the distance from the theoretical best). The DDP algorithm reduced this gap to just 1.28% after a few iterations.
  • Inventory Management: In a "lost sales" model with a 10-period lead time, the initial heuristic’s 9.5% gap was brought down to 1.02%.
  • Linear-Quadratic Control (LQC): The algorithm was verified against this mathematical benchmark, successfully reaching the known analytical optimum.

Key Insights and Convergence

A significant finding of the paper is the "embarrassingly parallel" nature of the algorithm. Since expectations are calculated over independent sample paths, the method is highly compatible with modern multi-core and cloud computing architectures.

Furthermore, the researchers provide a rigorous convergence analysis regarding the trade-off between the number of basis functions ($M$) and the number of sampled states ($L$). They identify that to prevent overfitting and ensure convergence, the number of samples must grow significantly faster than the number of basis functions (theoretically $L \approx M^6$). However, empirical results suggest a more relaxed ratio ($L \approx M^{1.5}$) may suffice in practice, indicating the theoretical bound is conservative.

Conclusion

The DDP algorithm provides a robust framework for both assessing and improving heuristic policies in stochastic environments. By bridging the gap between theoretical information relaxation and practical policy improvement, it offers a path toward near-optimal decision-making in complex, high-dimensional systems. Future work may involve automating the selection of basis functions, perhaps through deep learning architectures, to further enhance the algorithm's accessibility for engineers.

Summary updated

Abstract

We use the technique of information relaxation to develop a duality-driven iterative approach to obtaining and improving confidence interval estimates for the true value of finite-horizon stochastic dynamic programming problems. We show that the sequence of dual value estimates yielded from the proposed approach in principle monotonically converges to the true value function in a finite number of dual iterations. Aiming to overcome the curse of dimensionality in various applications, we also introduce a regression-based Monte Carlo algorithm for implementation. The new approach can be used not only to assess the quality of heuristic policies, but also to improve them if we find that their duality gap is large. We obtain the convergence rate of our Monte Carlo method in terms of the amounts of both basis functions and the sampled states. Finally, we demonstrate the effectiveness of our method in an optimal order execution problem with market friction and in an inventory management problem in the presence of lost sale and lead time. Both examples are well known in the literature to be difficult to solve for optimality. The experiments show that our method can significantly improve the heuristics suggested in the literature and obtain new policies with a satisfactory performance guarantee.
BibTeX
@misc{chen2020information,
  author = {Nan Chen and Xiang Ma and Yanchu Liu and Wei Yu},
  title = {{Information Relaxation and A Duality-Driven Algorithm for Stochastic Dynamic Programs}},
  year = {2020},
  eprint = {2007.14295},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2007.14295},
}
Figure