深度神经网络可无维度灾难地求解马尔可夫决策问题的贝尔曼方程
Deep neural networks can provably solve Bellman equations for Markov decision processes without the curse of dimensionality
- 用带漏失修正线性单元的深度网络逼近贝尔曼方程解
- 参数量随维度和精度要求呈多项式增长，突破维度灾难
- 为强化学习理论提供数学基础，适合相关研究者阅读
离散时间随机最优控制问题与马尔可夫决策过程（MDPs）是不确定性下序列决策的基本模型，也是强化学习理论的数学框架。求解MDPs的核心工具是贝尔曼方程及其解——$Q$-函数。本文构造了无限时域、有限控制集 $A$ 的MDP对应的 $Q$-函数的深度神经网络（DNN）近似。具体而言，若收益函数和随机转移动态能被带漏失修正线性单元（leaky ReLU）激活的DNN良好逼近，则其关联贝尔曼方程的解 $Q_d rom bR^d o bR^{|A|}$ 也可在 $L^2$ 意义下由相同激活函数的DNN近似，且参数数量在状态空间维度 $d$ 与预定误差倒数 $1/$ 上均至多多项式增长。证明依赖于最近提出的全历史递归多级固定点（MLFP）逼近方法。
原文摘要 · Abstract (English)
Discrete time stochastic optimal control problems and Markov decision processes (MDPs) are fundamental models for sequential decision-making under uncertainty and as such provide the mathematical framework underlying reinforcement learning theory. A central tool for solving MDPs is the Bellman equation and its solution, the so-called $Q$-function. In this article, we construct deep neural network (DNN) approximations for $Q$-functions associated to MDPs with infinite time horizon and finite control set $A$. More specifically, we show that if the the payoff function and the random transition dynamics of the MDP can be suitably approximated by DNNs with leaky rectified linear unit (ReLU) activation, then the solutions $Q_d\colon \mathbb R^d\to \mathbb R^{|A|}$, $d\in \mathbb{N}$, of the associated Bellman equations can also be approximated in the $L^2$-sense by DNNs with leaky ReLU activation whose numbers of parameters grow at most polynomially in both the dimension $d\in \mathbb{N}$ of the state space and the reciprocal $1/\varepsilon$ of the prescribed error $\varepsilon\in (0,1)$. Our proof relies on the recently introduced full-history recursive multilevel fixed-point (MLFP) approximation scheme.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。