A Partitioning Algorithm for Markov Decision Processes with Applications to Market Microstructure

Ningyuan Chen (), Steven Kou () and Chun Wang ()
Additional contact information
Ningyuan Chen: Department of Industrial Engineering and Logistics Management, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong
Steven Kou: Risk Management Institute, National University of Singapore, Singapore 119077
Chun Wang: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027

Management Science, 2018, vol. 64, issue 2, 784-803

Abstract: We propose a partitioning algorithm to solve a class of linear-quadratic Markov decision processes with inequality constraints and nonconvex stagewise cost; within each region of the partitioned state space, the value function and the optimal policy have analytical quadratic and linear forms, respectively. Compared to grid-based numerical schemes, the partitioning algorithm gives the closed-form solution without discretization error, and in many cases does not suffer from the curse of dimensionality. The algorithm is applied to two applications. In the main application, we present a model for limit order books with stochastic market depth to study the optimal order execution problem; stochastic market depth is consistent with empirical studies and necessary to accommodate various order activities. The optimal execution policy obtained by the algorithm significantly outperforms that of a deterministic market depth model in numerical examples. In the second application, we use the algorithm to compute the exact optimal solution to the renewable electricity management problem, for which previously only an approximate solution was known. As a comparison, we show that the approximate solution can be quite inaccurate for some initial states and thus demonstrate an advantage of the exact solution. The online appendix is available at https://doi.org/10.1287/mnsc.2016.2639 . This paper was accepted by Yinyu-Ye, optimization.

Keywords: Markov chains; large order execution; electricity trading/production; partitioning; quadratic stochastic programming (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/mnsc.2016.2639 (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:ormnsc:v:64:y:2018:i:2:p:784-803

Access Statistics for this article

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