Title: Weighted mesh algorithms for general Markov decision processes: Convergence and tractability Show Chinese title

Title: 加权网格算法在一般马尔可夫决策过程中的收敛性和可处理性

Abstract: We introduce a mesh-type approach for tackling discrete-time, finite-horizon Markov Decision Processes (MDPs) characterized by state and action spaces that are general, encompassing both finite and infinite (yet suitably regular) subsets of Euclidean space. In particular, for bounded state and action spaces, our algorithm achieves a computational complexity that is tractable in the sense of Novak and Wozniakowski, and is polynomial in the time horizon. For unbounded state space the algorithm is "semi-tractable" in the sense that the complexity is proportional to $\epsilon^{-c}$ with some dimension independent $c\geq2$, for achieving an accuracy $\epsilon$, and polynomial in the time horizon with degree linear in the underlying dimension. As such the proposed approach has some flavor of the randomization method by Rust which deals with infinite horizon MDPs and uniform sampling in compact state space. However, the present approach is essentially different due to the finite horizon and a simulation procedure due to general transition distributions, and more general in the sense that it encompasses unbounded state space. To demonstrate the effectiveness of our algorithm, we provide illustrations based on Linear-Quadratic Gaussian (LQG) control problems. Show Chinese abstract

Abstract: 我们介绍了一种基于网格的方法，用于解决离散时间、有限时域的马尔可夫决策过程（MDP），这些 MDP 的状态和动作空间是一般的，包括欧几里得空间中的有限和无限（但适当规则的）子集。 特别是，对于有界的状态和动作空间，我们的算法在 Novak 和 Wozniakowski 的意义上具有可处理的计算复杂性，并且在时间范围上是多项式的。 对于无界状态空间，该算法在某种意义上是“半可处理的”，即为了达到精度 $\epsilon$，复杂度与 $\epsilon^{-c}$ 成正比，其中 $c\geq2$ 与维度无关，并且在时间范围内是多项式，其指数与底层维度线性相关。 因此，所提出的方法具有一些 Rust 随机化方法的特点，该方法处理无限时域 MDP 和紧致状态空间的均匀采样。然而，由于有限时域和一般转移分布导致的仿真程序，本方法本质上有所不同，并且在更广泛的意义上涵盖了无界状态空间。 为了证明我们算法的有效性，我们基于线性二次高斯（LQG）控制问题提供了实例演示。