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

Nan Chen (), Xiang Ma (), Yanchu Liu () and Wei Yu ()
Additional contact information
Nan Chen: Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Hong Kong
Xiang Ma: High-Flyer Quant, Hangzhou, China
Yanchu Liu: Lingnan College, Sun Yat-sen University, Guangzhou, China
Wei Yu: World Quant (Singapore), Singapore 048948

Operations Research, 2024, vol. 72, issue 6, 2302-2320

Abstract: We use the technique of information relaxation to develop a duality-driven iterative approach (DDP) to obtain and improve confidence interval estimates for the true value of finite-horizon stochastic dynamic programming problems. Each iteration of the algorithm solves an optimization-expectation procedure. We show that the sequence of dual value estimates yielded from the proposed approach 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 assess the quality of heuristic policies and, more importantly, 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 using an optimal order execution problem with market friction. The experiments show that our method can significantly improve various heuristics commonly used in the literature to obtain new policies with a satisfactory performance guarantee. When we implement DDP in the numerical example, some local optimization routines are used in the optimization step. Inspired by the work of Brown and Smith [Brown DB, Smith JE (2014) Information relaxations, duality and convex stochastic dynamic programs. Oper. Res . 62:1394–1415.], we propose an ex-post method for smooth convex dynamic programs to assess how the local optimality of the inner optimization impacts the convergence of the DDP algorithm.

Keywords: Financial Engineering; stochastic dynamic programming; information relaxation; duality; regression-based Monte Carlo method; optimal execution (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.0464 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:6:p:2302-2320

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().