Nonlinear Monte Carlo methods with polynomial runtime for high-dimensional iterated nested expectations

The approximate calculation of iterated nested expectations is a recurring challenging problem in applications. Nested expectations appear, for example, in the numerical approximation of solutions of backward stochastic differential equations (BSDEs), in the numerical approximation of solutions of semilinear parabolic partial differential equations (PDEs), in statistical physics, in optimal stopping problems such as the approximate pricing of American or Bermudan options, in risk measure estimation in mathematical finance, or in decisionmaking under uncertainty. Nested expectations which arise in the above-mentioned applications often consist of a large number of nestings. However, the computational effort of standard nested Monte Carlo approximations for iterated nested expectations grows exponentially in the number of nestings and it has remained an open question whether it is possible to approximately calculate multiply iterated high-dimensional nested expectations in polynomial time. In this article we tackle this problem by proposing and studying a new class of full-history recursive multilevel Picard (MLP) approximation schemes for iterated nested expectations. Specifically, we prove under suitable assumptions that these MLP approximation schemes can approximately calculate multiply iterated nested expectations with a computational effort growing at most polynomially in the number of nestings K ∈ ℕ = 1, 2, 3, …, in the problem dimension d ∈ ℕ, and in the reciprocal 1/ε of the desired approximation accuracy ε ∈ (0, ∞). In particular, the proposed MLP approximation schemes can approximately calculate nested expectations arising in the numerical approximation of solutions of BSDEs and semilinear parabolic PDEs with a computational effort growing at most polynomially in K, d, and 1/ε.