WIAS Preprint No. 2957, (2022)

Primal-dual regression approach for Markov decision processes with general state and action space


  • Belomestny, Denis
  • Schoenmakers, John G. M.
    ORCID: 0000-0002-4389-8266

2020 Mathematics Subject Classification

  • 90C40 65C05 62G08


  • Markov decision processes, dual representation, pseudo regression


We develop a regression based primal-dual martingale approach for solving finite time horizon MDPs with general state and action space. As a result, our method allows for the construction of tight upper and lower biased approximations of the value functions, and, provides tight approximations to the optimal policy. In particular, we prove tight error bounds for the estimated duality gap featuring polynomial dependence on the time horizon, and sublinear dependence on the cardinality/dimension of the possibly infinite state and action space. From a computational point of view the proposed method is efficient since, in contrast to usual duality-based methods for optimal control problems in the literature, the Monte Carlo procedures here involved do not require nested simulations.

Download Documents