Algorithm for Constrained Markov Decision Process with Linear Convergence

Egor Gladin, Maksim Lavrik-Karmazin, Karina Zainullina, Varvara Rudenko, Alexander Gasnikov, Martin Takac
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:11506-11533, 2023.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-gladin23a, title = {Algorithm for Constrained Markov Decision Process with Linear Convergence}, author = {Gladin, Egor and Lavrik-Karmazin, Maksim and Zainullina, Karina and Rudenko, Varvara and Gasnikov, Alexander and Takac, Martin}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {11506--11533}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/gladin23a/gladin23a.pdf}, url = {https://proceedings.mlr.press/v206/gladin23a.html}, 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.} }
Endnote
%0 Conference Paper %T Algorithm for Constrained Markov Decision Process with Linear Convergence %A Egor Gladin %A Maksim Lavrik-Karmazin %A Karina Zainullina %A Varvara Rudenko %A Alexander Gasnikov %A Martin Takac %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-gladin23a %I PMLR %P 11506--11533 %U https://proceedings.mlr.press/v206/gladin23a.html %V 206 %X 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.
APA
Gladin, E., Lavrik-Karmazin, M., Zainullina, K., Rudenko, V., Gasnikov, A. & Takac, M.. (2023). Algorithm for Constrained Markov Decision Process with Linear Convergence. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:11506-11533 Available from https://proceedings.mlr.press/v206/gladin23a.html.

Related Material