Nonlinear Monte Carlo Methods with Polynomial Runtime for Bellman Equations of Discrete Time High-Dimensional Stochastic Optimal Control Problems

Discrete time <i>stochastic optimal control</i> problems and <i>Markov decision processes</i> (MDPs), respectively, serve as fundamental models for problems that involve sequential decision making under uncertainty and as such constitute the theoretical foundation of <i>reinforcement learning</i>. In this article we study the numerical approximation of MDPs with infinite time horizon, finite control set, and general state spaces. Our set-up in particular covers infinite-horizon optimal stopping problems of discrete time Markov processes. A key tool to solve MDPs are <i>Bellman equations</i> which characterize the value functions of the MDPs and determine the optimal control strategies. By combining ideas from the <i>full-history recursive multilevel Picard approximation method</i>, which was recently introduced to solve certain nonlinear partial differential equations, and ideas from <i>Q</i> <i>-learning</i> we introduce a class of suitable <i>nonlinear Monte Carlo methods</i> and prove that the proposed methods do not suffer from the <i>curse of dimensionality</i> in the numerical approximation of the solutions of Bellman equations and the associated discrete time stochastic optimal control problems.