Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Run Time
Mengdi Wang Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ email:
Abstract
We propose a novel randomized linear programming algorithm for approximating the optimal policy of the discounted Markov decision problem. By leveraging the value-policy duality and binary-tree data structures, the algorithm adaptively samples state-action-state transitions and makes exponentiated primal-dual updates. We show that it finds an $\epsilon$ -optimal policy using nearly-linear run time in the worst case. When the Markov decision process is ergodic and specified in some special data formats, the algorithm finds an $\epsilon$ -optimal policy using run time linear in the total number of state-action pairs, which is sublinear in the input size. These results provide a new venue and complexity benchmarks for solving stochastic dynamic programs.
中文速览
折扣马尔可夫决策过程（Discounted MDP）的传统求解方法（值迭代、策略迭代、线性规划）在状态和动作空间很大时计算代价极高，难以高效近似最优策略。这项工作提出了一种随机线性规划算法：将贝尔曼方程转化为鞍点问题，利用"值-策略"对偶结构，借助二叉树数据结构在近乎常数时间内完成状态转移采样和指数乘性策略更新，从而自适应地探索状态-动作-状态转移路径。在最坏情况下，算法以近线性时间找到ε-最优策略；当MDP满足遍历性（ergodic）条件且输入已整理成二叉树或累积和格式时，所需运行时间甚至低于输入规模，实现了首个亚线性时间复杂度结果——也就是说，无需读取全部输入数据就能计算出近优策略。这一成果不仅为随机动态规划提供了全新的算法思路，还揭示了一个反直觉的现象：MDP的计算复杂度与输入数据的存储格式密切相关。
原文 arXiv:1704.01869;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1704.01869v3