Timezone: »

 
Poster
Natural Policy Gradient Primal-Dual Method for Constrained Markov Decision Processes
Dongsheng Ding · Kaiqing Zhang · Tamer Basar · Mihailo Jovanovic

Mon Dec 07 09:00 PM -- 11:00 PM (PST) @ Poster Session 0 #89
in Poster Session 1 »

We study sequential decision-making problems in which each agent aims to maximize the expected total reward while satisfying a constraint on the expected total utility. We employ the natural policy gradient method to solve the discounted infinite-horizon Constrained Markov Decision Processes (CMDPs) problem. Specifically, we propose a new Natural Policy Gradient Primal-Dual (NPG-PD) method for CMDPs which updates the primal variable via natural policy gradient ascent and the dual variable via projected sub-gradient descent. Even though the underlying maximization involves a nonconcave objective function and a nonconvex constraint set under the softmax policy parametrization, we prove that our method achieves global convergence with sublinear rates regarding both the optimality gap and the constraint violation. Such a convergence is independent of the size of the state-action space, i.e., it is~dimension-free. Furthermore, for the general smooth policy class, we establish sublinear rates of convergence regarding both the optimality gap and the constraint violation, up to a function approximation error caused by restricted policy parametrization. Finally, we show that two sample-based NPG-PD algorithms inherit such non-asymptotic convergence properties and provide finite-sample complexity guarantees. To the best of our knowledge, our work is the first to establish non-asymptotic convergence guarantees of policy-based primal-dual methods for solving infinite-horizon discounted CMDPs. We also provide computational results to demonstrate merits of our approach.

Author Information

Dongsheng Ding (University of Southern California)
Kaiqing Zhang (University of Illinois at Urbana-Champaign (UIUC))
Tamer Basar (University of Illinois at Urbana-Champaign)
Mihailo Jovanovic (University of Southern California)

More from the Same Authors