Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年2月4日

查看全文
  • Christian Beck,
  • Arnulf Jentzen,
  • Konrad Kleinberg,
  • Thomas Kruse

摘要

Discrete time stochastic optimal control problems and Markov decision processes (MDPs), respectively, serve as fundamental models for problems that involve sequential decision making under uncertainty and as such constitute the theoretical foundation of reinforcement learning. 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 Bellman equations which characterize the value functions of the MDPs and determine the optimal control strategies. By combining ideas from the full-history recursive multilevel Picard approximation method, which was recently introduced to solve certain nonlinear partial differential equations, and ideas from Q-learning we introduce a class of suitable nonlinear Monte Carlo methods and prove that the proposed methods do not suffer from the curse of dimensionality in the numerical approximation of the solutions of Bellman equations and the associated discrete time stochastic optimal control problems.