On the Convergence of Natural Policy Gradient and Mirror Descent-Like Policy Methods for Average-Reward MDPs

Yashaswini Murthy; R. Srikant

doi:10.1109/CDC49753.2023.10383691

On the Convergence of Natural Policy Gradient and Mirror Descent-Like Policy Methods for Average-Reward MDPs

Yashaswini Murthy, R. Srikant

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

It is now well known that Natural Policy Gradient (NPG) globally converges for discounted-reward MDPs in the tabular setting, with perfect value function estimates. However, the result cannot be directly used to obtain a corresponding convergence result for average-reward MDPs by letting the discount factor tend to one. In this paper, we prove that NPG also converges for average-reward MDPs in which each policy leads to an irreducible Markov chain. Since NPG can also be interpreted as a mirror descent based policy method, we then discuss extensions to non-tabular settings for mirror descent-based methods.

Original language	English (US)
Title of host publication	2023 62nd IEEE Conference on Decision and Control, CDC 2023
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1979-1984
Number of pages	6
ISBN (Electronic)	9798350301243
DOIs	https://doi.org/10.1109/CDC49753.2023.10383691
State	Published - 2023
Event	62nd IEEE Conference on Decision and Control, CDC 2023 - Singapore, Singapore Duration: Dec 13 2023 → Dec 15 2023

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	62nd IEEE Conference on Decision and Control, CDC 2023
Country/Territory	Singapore
City	Singapore
Period	12/13/23 → 12/15/23

ASJC Scopus subject areas

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Online availability

10.1109/CDC49753.2023.10383691

Library availability

Discover UIUC Full Text

Cite this

Murthy, Y., & Srikant, R. (2023). On the Convergence of Natural Policy Gradient and Mirror Descent-Like Policy Methods for Average-Reward MDPs. In 2023 62nd IEEE Conference on Decision and Control, CDC 2023 (pp. 1979-1984). (Proceedings of the IEEE Conference on Decision and Control). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC49753.2023.10383691

On the Convergence of Natural Policy Gradient and Mirror Descent-Like Policy Methods for Average-Reward MDPs. / Murthy, Yashaswini; Srikant, R.
2023 62nd IEEE Conference on Decision and Control, CDC 2023. Institute of Electrical and Electronics Engineers Inc., 2023. p. 1979-1984 (Proceedings of the IEEE Conference on Decision and Control).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Murthy, Y & Srikant, R 2023, On the Convergence of Natural Policy Gradient and Mirror Descent-Like Policy Methods for Average-Reward MDPs. in 2023 62nd IEEE Conference on Decision and Control, CDC 2023. Proceedings of the IEEE Conference on Decision and Control, Institute of Electrical and Electronics Engineers Inc., pp. 1979-1984, 62nd IEEE Conference on Decision and Control, CDC 2023, Singapore, Singapore, 12/13/23. https://doi.org/10.1109/CDC49753.2023.10383691

@inproceedings{8aae7b1cd09c4beca20d6b322cac1a83,

title = "On the Convergence of Natural Policy Gradient and Mirror Descent-Like Policy Methods for Average-Reward MDPs",

abstract = "It is now well known that Natural Policy Gradient (NPG) globally converges for discounted-reward MDPs in the tabular setting, with perfect value function estimates. However, the result cannot be directly used to obtain a corresponding convergence result for average-reward MDPs by letting the discount factor tend to one. In this paper, we prove that NPG also converges for average-reward MDPs in which each policy leads to an irreducible Markov chain. Since NPG can also be interpreted as a mirror descent based policy method, we then discuss extensions to non-tabular settings for mirror descent-based methods.",

author = "Yashaswini Murthy and R. Srikant",

note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 62nd IEEE Conference on Decision and Control, CDC 2023 ; Conference date: 13-12-2023 Through 15-12-2023",

year = "2023",

doi = "10.1109/CDC49753.2023.10383691",

language = "English (US)",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1979--1984",

booktitle = "2023 62nd IEEE Conference on Decision and Control, CDC 2023",

address = "United States",

}

TY - GEN

T1 - On the Convergence of Natural Policy Gradient and Mirror Descent-Like Policy Methods for Average-Reward MDPs

AU - Murthy, Yashaswini

AU - Srikant, R.

PY - 2023

Y1 - 2023

N2 - It is now well known that Natural Policy Gradient (NPG) globally converges for discounted-reward MDPs in the tabular setting, with perfect value function estimates. However, the result cannot be directly used to obtain a corresponding convergence result for average-reward MDPs by letting the discount factor tend to one. In this paper, we prove that NPG also converges for average-reward MDPs in which each policy leads to an irreducible Markov chain. Since NPG can also be interpreted as a mirror descent based policy method, we then discuss extensions to non-tabular settings for mirror descent-based methods.

AB - It is now well known that Natural Policy Gradient (NPG) globally converges for discounted-reward MDPs in the tabular setting, with perfect value function estimates. However, the result cannot be directly used to obtain a corresponding convergence result for average-reward MDPs by letting the discount factor tend to one. In this paper, we prove that NPG also converges for average-reward MDPs in which each policy leads to an irreducible Markov chain. Since NPG can also be interpreted as a mirror descent based policy method, we then discuss extensions to non-tabular settings for mirror descent-based methods.

UR - http://www.scopus.com/inward/record.url?scp=85184798985&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85184798985&partnerID=8YFLogxK

U2 - 10.1109/CDC49753.2023.10383691

DO - 10.1109/CDC49753.2023.10383691

M3 - Conference contribution

AN - SCOPUS:85184798985

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 1979

EP - 1984

BT - 2023 62nd IEEE Conference on Decision and Control, CDC 2023

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 62nd IEEE Conference on Decision and Control, CDC 2023

Y2 - 13 December 2023 through 15 December 2023

ER -

On the Convergence of Natural Policy Gradient and Mirror Descent-Like Policy Methods for Average-Reward MDPs

Abstract

Publication series

Conference

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this