mlsanityData to 14 Oct 2026

Local and Global Stability in Performative Reinforcement Learning

arXiv 2609.06467 ↗First posted 6 Sep 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

In performative reinforcement learning the deployed policy shapes the environment that generates the learner's future data, and the natural solution concept is a performatively stable policy that is optimal in the environment it induces. Existing convergence guarantees rely on Lipschitz sensitivity assumptions on the environment map π mapsto (Pπ, rπ), which are hard to verify and fail in settings such as multi-agent best-response dynamics. We instead study stability for mixtures of policies, and show that the resulting picture is fundamentally different from performative prediction, where randomization removes the need for any sensitivity assumption. We distinguish local mixed stability, an occupancy-weighted first-order relaxation that we show is equivalent to stationarity, from global mixed stability, which certifies against arbitrary deviating policies. Our first result is that a weighted per-state Hedge dynamic drives the local stability gap to zero at an O(1/√T) rate for an arbitrary, possibly discontinuous, environment map, both with exact and with trajectory feedback. The two notions genuinely differ: we exhibit an instance where local stability is achieved exactly but every mixture has global stability gap bounded away from zero. For global stability we introduce a bounded transition range assumption, strictly weaker than Lipschitz sensitivity, under which unweighted per-state Hedge converges up to a floor of O(γεP/(1-γ)3), and we prove a matching-in-εP lower bound of Omega(γεP/(1-γ)) under trajectory feedback, so this floor is unavoidable. Finally, we extend both notions to n-player performative Markov games, obtaining local stability with no assumption on the joint environment map or game structure, and global stability for performative Markov potential games.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 29 of its 39 references that are in the map. First posted on arXiv 6 Sep 2026.

Builds on

29 of 39 references.

Closest ancestors · 5

Same direction, newest first

  1. 2025Performative Policy Gradient: Optimality in Performative Reinforcement Learning23 Dec
  2. 2025Achieve Performatively Optimal Policy for Performative Reinforcement Learning6 Oct
  3. 2025On Corruption-Robustness in Performative Reinforcement Learning8 May
  4. 2025Independent Learning in Performative Markov Potential Games29 Apr
  5. 2024Performative Reinforcement Learning with Linear Markov Decision Process7 Nov

Other references · 24

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  2. 2020Performative Predictioncited by 327
  3. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  4. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  5. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  6. 2021Outside the Echo Chamber: Optimizing the Performative Riskcited by 96
  7. 2020Stochastic Optimization for Performative Predictioncited by 93
  8. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
  9. 2020Performative Prediction in a Stateful Worldcited by 90
  10. 2017Flow: A Modular Learning Framework for Mixed Autonomy Trafficcited by 73
  11. 2019Degenerate Feedback Loops in Recommender Systemscited by 67
  12. 2020Stochastic optimization with decision-dependent distributionscited by 65
12 more
  1. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  2. 2022Multiplayer Performative Prediction: Learning in Decision-Dependent Gamescited by 44
  3. 2022Multi-agent Performative Prediction: From Global Stability and Optimality to Chaoscited by 33
  4. 2021How to Learn when Data Gradually Reacts to Your Modelcited by 30
  5. 2022Performative Reinforcement Learningcited by 27
  6. 2019Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Gamescited by 25
  7. 2013Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributionscited by 18
  8. 2023Implicit Poisoning Attacks in Two-Agent Reinforcement Learning: Adversarial Policies for Training-Time Attackscited by 14
  9. 2024Performative Reinforcement Learning in Gradually Shifting Environmentscited by 14
  10. 2024Stochastic Optimization Schemes for Performative Prediction with Nonconvex Losscited by 13
  11. 2024Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributionscited by 4
  12. 2026The Stability of Online Algorithms in Performative Predictioncited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Stable but Wrong: When Learning Stabilizes Away from the Truth
  2. 2024Taming "data-hungry" reinforcement learning? Stability in continuous state-action spaces
  3. 2025On the Convergence and Stability of Upside-Down Reinforcement Learning, Goal-Conditioned Supervised Learning, and Online Decision Transformers
  4. 2023Model-based Offline Reinforcement Learning with Local Misspecification
  5. 2026ANO: Robust Policy Optimization via Bounded, Redescending Gain Fields
  6. 2025Stabilizing Reinforcement Learning with LLMs: Formulation and Practices
  7. 2026Geometry of Drifting MDPs with Path-Integral Stability Certificates
  8. 2025State Entropy Regularization for Robust Reinforcement Learning