Weighted mesh algorithms for general Markov decision processes: Convergence and tractability

我们提出了一种网格型方法来解决离散时间、有限时间段的马尔可夫决策过程（MDPs），其状态和动作空间是一般性的，包括欧几里得空间的有限和无限（但适当规则的）子集。特别地，对于有界状态和动作空间，我们的算法在 Novak 和 Wozniakowski 的意义下实现了可处理的计算复杂度，并且在时间视角上是多项式的。对于无界状态空间，该算法在某种程度上是“半可处理的”，即为了达到精度 $\epsilon$，复杂度与 $\epsilon^{-c}$ 成比例，其中一些维度独立的 $c \geq 2$，并且在基础维度上呈线性多项式。因此，所提出的方法具有 Rust 的随机化方法的某些特点，该方法处理具有无限时间段和在紧致状态空间中进行均匀采样的 MDPs。然而，由于有限时间段和具有一般转移分布的模拟过程，因此本方法本质上是不同的，并且在包含无界状态空间方面更为一般。为了展示我们算法的有效性，我们提供了基于线性二次高斯（LQG）控制问题的说明。

本文旨在解决具有一般状态和动作空间的离散时间、有限时间段的马尔可夫决策过程（MDPs）问题，并提供一种可行的计算复杂度算法。

本文提出了一种网格类型的方法来解决离散时间、有限时间段的MDPs问题，其特点是状态和动作空间是一般的，包括欧几里得空间的有限和无限（但适当正则化）子集。对于有界状态和动作空间，本算法在Novak和Wozniakowski的意义下实现了可计算的复杂度，并且在时间视角上是多项式的。对于无界状态空间，本算法的复杂度是“半可计算的”，即实现精度ε的复杂度与维度无关，为ε^{-c}，其中c≥2，且在时间视角上是线性维度的多项式。这种方法与Rust的随机化方法有些相似，后者处理无限时间段的MDPs和紧凑状态空间中的均匀采样。然而，由于有限时间段和一般的转移分布，本方法在本质上是不同的，并且在包含无界状态空间方面更为一般。

为了证明算法的有效性，本文提供了基于线性-二次高斯（LQG）控制问题的案例研究。本文的亮点包括算法的计算复杂度可行性、针对一般状态和动作空间的解决方案、对无界状态空间的处理、以及与Rust方法的比较等。本文使用LQG控制问题进行了实验，并提供了详细的实验设计和数据集信息，但没有公开代码。这篇论文为进一步研究提供了方向。

近期在这个领域中，还有一些相关研究，例如“Solving Large-Scale Markov Decision Processes Using Coordinated Exploration”，“A Reinforcement Learning Approach to Solving Constrained Markov Decision Processes”，“A Deep Reinforcement Learning Framework for the Financial Portfolio Management Problem”等。