A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints
A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints
复制标题
DOI：
10.1609/aaai.v35i9.16979
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
K. C. Kalagarla;Rahul Jain;P. Nuzzo
中科院分区：
文献类型：
--
作者：
K. C. Kalagarla;Rahul Jain;P. Nuzzo
约束马尔可夫决策过程（CMDP）形式化了顺序决策问题，其目标是在满足各种成本函数的约束的同时最小化成本函数。在本文中，我们考虑情景固定范围 CMDP 的设置。我们提出了一种在线算法，该算法利用有限范围 CMDP 的重复乐观规划的线性规划公式，为确保接近最优策略所需的事件数提供大概正确性 (PAC) 保证，即最终的目标值接近最优值，并以高概率满足低容差内的约束。所需的情节数量被证明与状态和动作空间的大小具有线性依赖关系，并且与时间范围和状态动作对的可能后继状态数量的上限具有二次依赖关系。因此，如果可能的后继状态数量的上限远小于状态空间的大小，则所需的情节数量与状态和动作空间的大小成线性关系，并且与时间范围成二次关系。
Constrained Markov decision processes (CMDPs) formalize sequential decision-making problems whose objective is to minimize a cost function while satisfying constraints on various cost functions. In this paper, we consider the setting of episodic fixed-horizon CMDPs. We propose an online algorithm which leverages the linear programming formulation of repeated optimistic planning for finite-horizon CMDP to provide a probably approximately correctness (PAC) guarantee on the number of episodes needed to ensure a near optimal policy, i.e., with resulting objective value close to that of the optimal value and satisfying the constraints within low tolerance, with high probability. The number of episodes needed is shown to have linear dependence on the sizes of the state and action spaces and quadratic dependence on the time horizon and an upper bound on the number of possible successor states for a state-action pair. Therefore, if the upper bound on the number of possible successor states is much smaller than the size of the state space, the number of needed episodes becomes linear in the sizes of the state and action spaces and quadratic in the time horizon.