Computational complexity of discretized Markov decision processes
研究了离散时间连续状态和动作空间的马尔可夫决策过程的离散化与迭代求解方案，推导了单网格和多网格方法的迭代复杂度与计算复杂度，并通过库存控制实验验证了结果。
Discretization is an important way to handle the difficulty caused by continuous spaces in Markov decision processes (MDPs). While the existing studies have obtained the order of magnitude of complexity for common discretization algorithms, more precise complexity analyses are called for in order to guide the design and selection of such algorithms to meet the often demanding nature of real-world problems. This paper studies the discretization and iterative schemes for solving discrete-time continuous MDPs (MDPs with continuous state and action spaces) with an infinite-horizon expected discounted criterion, as well as the computational complexity resulted therefrom. Specifically, we consider and analyze the procedure of two stages: the uniform discretization of continuous MDPs and the value iteration of discretized MDPs. Concrete forms of complexities, including the iteration complexity and the computational complexity for the single-grid and multigrid methods, are derived. We prove that the multigrid method leads to a lower computational complexity than that of the single-grid method under certain conditions. Finally, we conduct numerical experiments about inventory control to validate our main results, which present some insights into the parameter selection of algorithms for solving continuous MDPs. The accuracy and tightness of our complexity bounds are also demonstrated.