Algorithm for Constrained Markov Decision Process with Linear Convergence

Authors

Egor Gladin, Humboldt University of Berlin, Moscow Institute of Physics and Technology, Institute for Information Transmission Problems RAS, Germany
Maksim Lavrik-Karmazin, Moscow Institute of Physics and Technology, Russian Federation
Karina Zainullina, Moscow Institute of Physics and Technology, Russian Federation
Varvara Rudenko, Moscow Institute of Physics and Technology, HSE University, Russian Federation
Alexander Gasnikov, Moscow Institute of Physics and Technology, ISP RAS Research Center for Trusted Artificial Intelligence, HSE University, Russian Federation
Martin Takac, Mohamed Bin Zayed University of Artificial IntelligenceFollow

Document Type

Article

Publication Title

arXiv

Abstract

The problem of constrained Markov decision process is considered. An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs (the number of constraints is relatively small). A new dual approach is proposed with the integration of two ingredients: entropy regularized policy optimizer and Vaidya's dual optimizer, both of which are critical to achieve faster convergence. The finite-time error bound of the proposed approach is provided. Despite the challenge of the nonconcave objective subject to nonconcave constraints, the proposed approach is shown to converge (with linear rate) to the global optimum. The complexity expressed in terms of the optimality gap and the constraint violation significantly improves upon the existing primal-dual approaches. Copyright © 2022, The Authors. All rights reserved.

DOI

10.48550/arXiv.2206.01666

Publication Date

6-3-2022

Keywords

Machine learning, Constrained Markov decision process, Discounted reward, Dual approach, Error bound, Fast convergence, Finite-time, Linear convergence, Linear rate, Multiple constraint, Optimizers, Markov processes, Machine Learning (cs.LG), Optimization and Control (math.OC)

Comments

IR Deposit conditions: non-described

Preprint available on arXiv

Recommended Citation

E. Gladin, M. Lavrik-Karmazin, K. Zainullina, V. Rudenko, A. Gasnikov, and M. Takac, "Algorithm for Constrained Markov Decision Process with Linear Convergence", 2022, arXiv:2206.01666