Provable Policy Gradient Methods for Average-Reward Markov Potential Games

2024-03-09 · Min Cheng, Ruida Zhou, P. R. Kumar, Chao Tian

We study Markov potential games under the infinite horizon average reward criterion. Most previous studies have been for discounted rewards. We prove that both algorithms based on independent policy gradient and independent natural policy gradient converge globally to a Nash equilibrium for the average reward criterion. To set the stage for gradient-based methods, we first establish that the average reward is a smooth function of policies and provide sensitivity bounds for the differential value functions, under certain conditions on ergodicity and the second largest eigenvalue of the underlying Markov decision process (MDP). We prove that three algorithms, policy gradient, proximal-Q, and natural policy gradient (NPG), converge to an $\epsilon$-Nash equilibrium with time complexity $O(\frac{1}{\epsilon^2})$, given a gradient/differential Q function oracle. When policy gradients have to be estimated, we propose an algorithm with $\tilde{O}(\frac{1}{\min_{s,a}\pi(a|s)\delta})$ sample complexity to achieve $\delta$ approximation error w.r.t~the $\ell_2$ norm. Equipped with the estimator, we derive the first sample complexity analysis for a policy gradient ascent algorithm, featuring a sample complexity of $\tilde{O}(1/\epsilon^5)$. Simulation studies are presented.

📄 PDF Abstract BibTeX arXiv:2403.05738

Code (0)

등록된 구현이 없습니다.

Tasks

Policy Gradient Methods

Methods 이 논문이 사용한 방법론

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning

2020-07-16 · NeurIPS 2020 12 · Alekh Agarwal, Mikael Henaff, Sham Kakade, Wen Sun

Direct policy gradient methods for reinforcement learning are a successful approach for a variety of reasons: they are model free, they directly optimize the performance metric of interest, and they allow for richly para…

Policy Gradient Methods Q-Learning

Off-Policy Average Reward Actor-Critic with Deterministic Policy Search

2023-05-20 · Naman Saxena, Subhojyoti Khastigir, Shishir Kolathaya, Shalabh Bhatnagar

The average reward criterion is relatively less studied as most existing works in the Reinforcement Learning literature consider the discounted reward criterion. There are few recent works that present on-policy average …

MuJoCo

On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes

2024-03-11 · Navdeep Kumar, Yashaswini Murthy, Itai Shufaro, Kfir Y. Levy 외

We present the first finite time global convergence analysis of policy gradient in the context of infinite horizon average reward Markov decision processes (MDPs). Specifically, we focus on ergodic tabular MDPs with fini…

Incremental Policy Gradients for Online Reinforcement Learning Control

2021-01-01 · Kristopher De Asis, Alan Chan, Yi Wan, Richard S. Sutton

Policy gradient methods are built on the policy gradient theorem, which involves a term representing the complete sum of rewards into the future: the return. Due to this, one usually either waits until the end of an epis…

Policy Gradient Methods reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Policy Optimization with Demonstrations

2018-07-01 · ICML 2018 7 · Bingyi Kang, Zequn Jie, Jiashi Feng

Exploration remains a significant challenge to reinforcement learning methods, especially in environments where reward signals are sparse. Recent methods of learning from demonstrations have shown to be promising in…

Policy Gradient Methods Reinforcement Learning Reinforcement Learning (RL)