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 π↦(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 Ω(γε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.
Figures & tables
Setting
Assumptions
Speed of convergence
Convergence floor
Local stability
None
O((1−γ)21TSlnA) ( Theorem 1 )
0
Global stability
Bounded transition range (Assn. 1 )
O((1−γ)21Tln(SA)) ( Theorem 3 )
Θ((1−γ)3γϵP)
Multi-agent local stability
None
O((1−γ)21TSlnAmax) ( Theorem 6 )
0
Multi-agent global stability
Markov potential game (Assn. 2 , 3 )
O(κT(1−γ)Sn) ( Theorem 7 )
Θ(κSnϵL)
Table 1: Summary of our stability guarantees. Here ϵP is the bounded-transition-range parameter of Assumption 1 , ϵL is the potential-sensitivity parameter of Assumption 3 , Amax:=maxiAi , and κ is the distribution mismatch coefficient of Theorem 7 . “Convergence floor” is the residual stability gap that persists as T→∞ . “None” means the guarantee holds for an arbitrary, possibly discontinuous, environment map.
Figure 1: The survival chain of Definition 4 with H stages. From each sh the process either advances one step, with the continuation probability ℓM(b) of the action b taken, or drops to the absorbing failure state ⊥ ; the reward is 0 on the chain. The only reward is the unit stream collected on absorption in ⊤ , so a policy’s value is κ=γH/(1−γ) times its probability of surviving all H stages. The two models differ only in which action is safe, and the environment map M(⋅) of Definition 5 assigns to each policy whichever model it survives less well in.
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
The use of algorithmic predictions in decision-making leads to a feedback loop where the models we deploy actively influence the data distributions we see, and later use to retrain on. This dynamic was formalized by Perdomo et al. 2020 in their work on performative prediction. Our main result is an unconditional reduction showing that any no-regret algorithm deployed in performative settings converges to a (mixed) performatively stable equilibrium: a solution in which models actively shape data distributions in ways that their own predictions look optimal in hindsight. Prior to our work, all positive results in this area imposed strong restrictions on how models influenced distributions. By using a martingale argument and allowing randomization, we avoid any assumption on how populations respond to predictions and sidestep recent hardness results showing that deterministic stable models are in general PPAD-hard to compute. Lastly, on a more conceptual note, our connection sheds light on why common algorithms, like gradient descent, are naturally stabilizing and prevent runaway feedback loops. We hope our work enables future technical transfer of ideas between online optimization and performativity.
When algorithmic predictions inform people's decisions, the models we deploy are performative and actively shape the data we see. This feedback loop between algorithms and their broader environments introduces a challenge in the mechanics of social prediction: If different predictive models induce different distributions, is it possible to efficiently learn a prediction rule that is optimal for the distribution that it induces? Formally, this solution concept is known as performative stability. A core challenge in learning a performatively stable predictor is that, unlike supervised learning where distributions are fixed, the learner must deploy different predictors and observe their induced distributions. The main contribution of our work is a new algorithmic procedure that, in the high-accuracy regime, finds a performatively stable model in nearly the minimum number of model deployments without making any assumptions regarding how predictions shape distributions. In particular, our procedure succeeds at finding a randomized performatively stable predictor using exponentially fewer model deployments than prior approaches. Our second main contribution is a structural result showing how this recent randomized notion of stability achieved by our algorithm can be derandomized into a single predictor satisfying the prior deterministic notion if one is willing to assume that the loss is well-conditioned and that performative effects are weak, as in early work in this area. On a technical level, our results come from building on an underexplored technical connection between performative stability and expected variational inequalities.
Reinforcement learning algorithms are commonly analyzed (and designed) under the Markov assumption. This is unrealistic, as most environments encountered in practice are either partially observable, or require function approximation that restricts the agent to access non-Markovian state features. We consider the problem of learning an optimal reactive policy in a finite environment with deterministic observations (or equivalently, hard state aggregation). We introduce a new algorithm, Committed Q-learning, and prove almost-sure convergence to the optimal reactive policy under an intuitive assumption we call rewire-robustness. This assumption is strictly weaker than the q⋆-realizability condition used in prior work. Our algorithm is a variant of classical Q-learning in which the behavior policy commits to a single action upon entering a feature, and only resamples actions when the observed feature changes. A crucial part of our analysis is the introduction of quasi-Markov environments.
Onno Eberhard, Claire Vernade, Michael Muehlebach
Max Planck Institute for Intelligent Systems, Tübingen, Germany · University of Tübingen · University of Technology Nuremberg.