Efficient Algorithms for Budget-Constrained Markov Decision Processes
Efficient Algorithms for Budget-Constrained Markov Decision Processes
复制标题
预算受限马尔可夫决策过程的高效算法
DOI：
--
复制
发表时间：
2014
影响因子：
6.8
通讯作者：
D. Morton
中科院分区：
文献类型：
--
作者：
C. Caramanis;N. Dimitrov;D. Morton
贴现、离散时间、离散状态空间、离散动作空间马尔可夫决策过程 (MDP) 形成了控制、博弈论和学习中的经典主题，因此在超大规模应用中得到越来越广泛的应用。人们已经开发了许多算法来解决大规模 MDP。基于值迭代的算法特别受欢迎，因为它们比通用线性规划方法更有效，在 MDP 的状态数量上高出一个数量级。然而，在预算受限的 MDP 的情况下，没有比线性规划更有效的算法了。理论上线性规划较慢的运行时间可能会限制受限 MDP 的可扩展性；然而，从理论上讲，它引发了这样的问题：这种增长是否是内在的。在本技术说明中，我们证明事实并非如此，并为预算受限的 MDP 提供了两种与值迭代一样高效的算法。用 VI 表示值迭代的运行时间，用 U 表示输入的大小，对于具有 m 个预期预算约束的 MDP，我们的第一个算法的运行时间为 O(poly(m, log U) · VI)。给定预先指定的精度 η，为了满足预算约束，我们的第二个算法运行时间为 O(log m · poly(log U) · (1/η2) · VI)，但可能会产生以 1 + η 的乘法因子过度利用 m 个预算中每一个的解决方案。事实上，可以用任何算法代替值迭代，该算法可能是专门为特定 MDP 设计的，可以快速求解 MDP 以实现类似的理论保证。两种算法都将注意力限制在折扣成本下的受限无限范围 MDP 上。
Discounted, discrete-time, discrete state-space, discrete action-space Markov decision processes (MDPs) form a classical topic in control, game theory, and learning, and as a result are widely applied, increasingly, in very large-scale applications. Many algorithms have been developed to solve large-scale MDPs. Algorithms based on value iteration are particularly popular, as they are more efficient than the generic linear programming approach, by an order of magnitude in the number of states of the MDP. Yet in the case of budget constrained MDPs, no more efficient algorithm than linear programming is known. The theoretically slower running times of linear programming may limit the scalability of constrained MDPs piratically; while, theoretically, it invites the question of whether the increase is somehow intrinsic. In this technical note we show that it is not, and provide two algorithms for budget-constrained MDPs that are as efficient as value iteration. Denoting the running time of value iteration by VI, and the magnitude of the input by U, for an MDP with m expected budget constraints our first algorithm runs in time O(poly(m, log U) · VI). Given a pre-specified degree of precision, η, for satisfying the budget constraints, our second algorithm runs in time O(log m · poly(log U) · (1/η2) · VI), but may produce solutions that overutilize each of the m budgets by a multiplicative factor of 1 + η. In fact, one can substitute value iteration with any algorithm, possibly specially designed for a specific MDP, that solves the MDP quickly to achieve similar theoretical guarantees. Both algorithms restrict attention to constrained infinite-horizon MDPs under discounted costs.