.png){kind=icon}
返回
A Gradient-Aware Search Algorithm for Constrained Markov Decision Processes
.png){kind=icon}
OA
AI
DOI：10.1109/TNNLS.2023.3315598.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The canonical solution methodology for finite constrained Markov decision processes (CMDPs), where the objective is to maximize the expected infinite-horizon discounted rewards subject to the expected infinite-horizon discounted costs' constraints, is based on convex linear programming (LP). In this brief, we first prove that the optimization objective in the dual linear program of a finite CMDP is a piecewise linear convex (PWLC) function with respect to the Lagrange penalty multipliers. Next, we propose a novel, provably optimal, two-level gradient-aware search (GAS) algorithm which exploits the PWLC structure to find the optimal state-value function and Lagrange penalty multipliers of a finite CMDP. The proposed algorithm is applied in two stochastic control problems with constraints for performance comparison with binary search (BS), Lagrangian primal-dual optimization (PDO), and LP. Compared with the benchmark algorithms, it is shown that the proposed GAS algorithm converges to the optimal solution quickly without any hyperparameter tuning. In addition, the convergence speed of the proposed algorithm is not sensitive to the initialization of the Lagrange multipliers.
Keyword:
Constrained Markov decision process (CMDP)
gradient aware search (GAS)
Lagrangian primal-dual optimization (PDO)
piecewise linear convex (PWLC)
期刊
IF:
8.9
论文数:
7.6K
被引数:
7.2W
机构
引用论文
.png){kind=icon}
Optimizing Taxi Driver Profit Efficiency: A Spatial Network-Based Markov Decision Process Approach
OAAI
OAAI分享收藏Event-Triggered Communication Network With Limited-Bandwidth Constraint for Multi-Agent Reinforcement Learning具有有限带宽约束的事件触发通信网络，用于多智能体强化学习
PREAI
分享收藏
查看更多内容