Independent Learning in Performative Markov Potential Games

• URL: http://arxiv.org/abs/2504.20593v1
• Date: Tue, 29 Apr 2025 09:46:16 GMT
• Title: Independent Learning in Performative Markov Potential Games
• Authors: Rilind Sahitaj, Paulius Sasnauskas, Yiğit Yalın, Debmalya Mandal, Goran Radanović,
• Abstract summary: We study multi-agent PRL by incorporating performative effects into Markov Potential Games (MPGs)<n>We show that independent policy gradient ascent (IPGA) and independent natural policy gradient (INPG) converge to an approximate gradient the best-iterate sense.
• Score: 4.433315630787158
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Performative Reinforcement Learning (PRL) refers to a scenario in which the deployed policy changes the reward and transition dynamics of the underlying environment. In this work, we study multi-agent PRL by incorporating performative effects into Markov Potential Games (MPGs). We introduce the notion of a performatively stable equilibrium (PSE) and show that it always exists under a reasonable sensitivity assumption. We then provide convergence results for state-of-the-art algorithms used to solve MPGs. Specifically, we show that independent policy gradient ascent (IPGA) and independent natural policy gradient (INPG) converge to an approximate PSE in the best-iterate sense, with an additional term that accounts for the performative effects. Furthermore, we show that INPG asymptotically converges to a PSE in the last-iterate sense. As the performative effects vanish, we recover the convergence rates from prior work. For a special case of our game, we provide finite-time last-iterate convergence results for a repeated retraining approach, in which agents independently optimize a surrogate objective. We conduct extensive experiments to validate our theoretical findings.

Related papers

• Policy Gradient with Active Importance Sampling [55.112959067035916]
  Policy gradient (PG) methods significantly benefit from IS, enabling the effective reuse of previously collected samples. However, IS is employed in RL as a passive tool for re-weighting historical samples. We look for the best behavioral policy from which to collect samples to reduce the policy gradient variance.
  arXiv  Detail & Related papers  (2024-05-09T09:08:09Z)
• Learning Optimal Deterministic Policies with Stochastic Policy Gradients [62.81324245896716]
  Policy gradient (PG) methods are successful approaches to deal with continuous reinforcement learning (RL) problems. In common practice, convergence (hyper)policies are learned only to deploy their deterministic version. We show how to tune the exploration level used for learning to optimize the trade-off between the sample complexity and the performance of the deployed deterministic policy.
  arXiv  Detail & Related papers  (2024-05-03T16:45:15Z)
• Truncating Trajectories in Monte Carlo Reinforcement Learning [48.97155920826079]
  In Reinforcement Learning (RL), an agent acts in an unknown environment to maximize the expected cumulative discounted sum of an external reward signal. We propose an a-priori budget allocation strategy that leads to the collection of trajectories of different lengths. We show that an appropriate truncation of the trajectories can succeed in improving performance.
  arXiv  Detail & Related papers  (2023-05-07T19:41:57Z)
• Revisiting Estimation Bias in Policy Gradients for Deep Reinforcement Learning [0.0]
  We revisit the estimation bias in policy gradients for the discounted episodic Markov decision process (MDP) from Deep Reinforcement Learning perspective. One of the major policy biases is the state distribution shift. We show that, despite such state distribution shift, the policy gradient estimation bias can be reduced in the following three ways.
  arXiv  Detail & Related papers  (2023-01-20T06:46:43Z)
• Entropy Augmented Reinforcement Learning [0.0]
  We propose a shifted Markov decision process (MDP) to encourage the exploration and reinforce the ability of escaping from suboptimums. Our experiments test augmented TRPO and PPO on MuJoCo benchmark tasks, of an indication that the agent is heartened towards higher reward regions.
  arXiv  Detail & Related papers  (2022-08-19T13:09:32Z)
• Performative Reinforcement Learning [8.07595093287034]
  We introduce the concept of performatively stable policy. We show that repeatedly optimizing this objective converges to a performatively stable policy.
  arXiv  Detail & Related papers  (2022-06-30T18:26:03Z)
• Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computation [93.52573037053449]
  H-MARL (Hallucinated Multi-Agent Reinforcement Learning) learns successful equilibrium policies after a few interactions with the environment. We demonstrate our approach experimentally on an autonomous driving simulation benchmark.
  arXiv  Detail & Related papers  (2022-03-14T17:24:03Z)
• False Correlation Reduction for Offline Reinforcement Learning [115.11954432080749]
  We propose falSe COrrelation REduction (SCORE) for offline RL, a practically effective and theoretically provable algorithm. We empirically show that SCORE achieves the SoTA performance with 3.1x acceleration on various tasks in a standard benchmark (D4RL)
  arXiv  Detail & Related papers  (2021-10-24T15:34:03Z)
• Independent Natural Policy Gradient Always Converges in Markov Potential Games [18.43622733760659]
  We study mixed cooperative/competitive games called Markov Potential Games (MPGs) We prove that Independent Natural Policy Gradient always converges in MPGs using constant learning rates. We complement our theoretical results with experiments that indicate that Natural Policy Gradient outperforms Policy Gradient in routing games and congestion games.
  arXiv  Detail & Related papers  (2021-10-20T15:15:10Z)
• Variance-Aware Off-Policy Evaluation with Linear Function Approximation [85.75516599931632]
  We study the off-policy evaluation problem in reinforcement learning with linear function approximation. We propose an algorithm, VA-OPE, which uses the estimated variance of the value function to reweight the Bellman residual in Fitted Q-Iteration.
  arXiv  Detail & Related papers  (2021-06-22T17:58:46Z)
• On Proximal Policy Optimization's Heavy-tailed Gradients [150.08522793940708]
  We study the heavy-tailed nature of the gradients of the Proximal Policy Optimization surrogate reward function. In this paper, we study the effects of the standard PPO clippings, demonstrating that these tricks primarily serve to offset heavy-tailedness in gradients. We propose incorporating GMOM, a high-dimensional robust estimator, into PPO as a substitute for three clipping tricks.
  arXiv  Detail & Related papers  (2021-02-20T05:51:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.