Monte Carlo Grid Dynamic Programming: Almost Sure Convergence and Probability Constraints

作     者：Ramadan, Mohammad S. Al-Tawaha, Ahmad Shouman, Mohamed Atallah, Ahmed Jin, Ming 

作者机构：Mathematics and Computer Science Division Argonne National Laboratory LemontIL60439 United States Departement of Electrical and Computer Engineering Virginia Tech BlacksburgVA United States  Aichi Nagoya Japan Department of Mechanical & Aerospace Engineering University of California San Diego La Jolla CA92093-0411 United States 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2023年

核心收录：

主　　题：Stochastic models 

摘      要：Dynamic Programming (DP) suffers from the wellknown curse of dimensionality, further exacerbated by the need to compute expectations over process noise in stochastic models. This paper presents a Monte Carlo-based sampling approach for the state space and an interpolation procedure for the resulting value function, dependent on the process noise density, in a self-approximating fashion, eliminating the need for ordering or set-membership tests. We provide proof of almost sure convergence for the value iteration (and consequently, policy iteration) procedure. The proposed meshless sampling and interpolation algorithm alleviates the burden of gridding the state space, traditionally required in DP, and avoids constructing a piecewise constant value function over a grid. Moreover, we demonstrate that the proposed interpolation procedure is wellsuited for handling probabilistic constraints by sampling both infeasible and feasible regions. The curse of dimensionality cannot be avoided, however, this approach offers a practical framework for addressing lower-order stochastic nonlinear systems with probabilistic constraints, while eliminating the need for linear interpolations and set membership tests. Numerical examples are presented to further explain and illustrate the convenience of the proposed algorithms. © 2023, CC BY.