acceptodds
Under review as a conference paper at ICLR 2027

Local and Global Stability in Performative Reinforcement Learning

Abstract

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, 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, from *global* mixed stability, which certifies against arbitrary deviating policies. 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. We show that a weighted per-state Hedge dynamic drives the local stability gap to zero at an rate for an *arbitrary*, possibly discontinuous, environment map. For global stability we introduce a weaker bounded transition range () assumption, under which unweighted per-state Hedge converges up to a floor of . This floor is unavoidable as we prove a matching-in- lower bound under trajectory feedback. Finally, we extend both notions to -player Markov games, obtaining local stability with no assumption on the environment map or game structure, and global stability for Markov potential games.

Primary area:
reinforcement learning
Keywords:
Performative Reinforcement Learning, Online Algorithm, Multi-Agent Learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_1H9yOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies performative reinforcement learning, in which the deployed policy affects the environment, and distinguishes local stability from global stability for mixtures of policies. The authors introduce an algorithm based on Hedge that achieves local stability under a possibly discontinuous environment response. They also use a counterexample to show that global stability may not be achievable. Under the bounded transition range assumption, the authors further provide an approximate global stability guarantee. The analysis is also extended to n-player Markov games. The results are supported by theoretical proofs, counterexamples, and finite-sample analysis.

Critical strengths
  1. The authors provide local stability guarantees for mixtures of policies without requiring the environment response to be continuous. This relaxes the sensitivity assumptions in previous performative RL work and extends the analysis to environments with discontinuous responses.

  2. The authors use a counterexample to separate local stability from global stability and provide approximate global stability guarantees under bounded transition range. These results help readers understand the capabilities and limitations of policy mixtures in RL and the conditions needed for stronger stability guarantees.

Critical weaknesses

The finite-sample guarantees in the appendix need correction. The step sizes in Theorem 7 and its proof differ by a factor of S\sqrt S. Theorem 8 also appears to omit an optimization error term independent of batch size. Consider a fixed environment with one state, two actions, and deterministic rewards of 0 and 1. With γ=0\gamma=0, n=k=T=105n=k=T=10^5, δ=0.1\delta=0.1, and the specified step size, all conditions are satisfied, but the local stability gap is approximately 9.33×10−49.33\times10^{-4}, exceeding the stated bound of 2.54×10−42.54\times10^{-4}. These issues appear fixable without changing the main results.

Questions for authors

The lower bound in Theorem 6 requires N≤K/(24ϵP2)N\le K/(24\epsilon_P^2), where NN is the total number of trajectories. Could the authors explain how this finite-sample bound supports the claim of an unavoidable error floor linear in ϵP\epsilon_P as the sample size goes to infinity with the problem size fixed?

If the authors can resolve the finite-sample issues and clarify the asymptotic lower-bound claim, I would consider raising my rating to 4.

4 comments

Dear Reviewer 1H9y,

Thank you for your feedback and further questions. Below we provide our response. We would be happy to answer any further questions you might have.

Re. Weakness: The finite-sample guarantees in the appendix need correction.

Thank you for pointing out the errors. Both are typos. For theorem 7 (original version), the step size η\eta does not include the S\sqrt{S} factor and the proof establishes that. The theorem statement has a typo. For theorem 8 (original version), the batch-size independent terms are included, however the local stability gap included a factor of A\sqrt{A} which should not be present. Both typos have been corrected in the recently uploaded version.

Re. Question: Could the authors explain how this finite-sample bound supports the claim of an unavoidable error floor linear in ϵP\epsilon_P as the sample size goes to infinity with the problem size fixed?

This is an important question! We have managed to find a new counter-example (lines 374-394) that establishes an unconditional lower bound of Ω(γϵP/(1−γ))\Omega(\gamma \epsilon_P/(1-\gamma)) on the achievable global stability gap. This lower bound doesn't impose any restriction on the number of samples.

Our previous unconditional lower bound on global stability was Ω(ϵP2)\Omega(\epsilon_P^2) (instance of Lemma 4) and in order to obtain a linear floor, we imposed the restriction on the number of samples. However, this is not necessary as the new counter-example shows. We probably failed to find the example earlier because we were mainly searching for counter-examples in the family of survival chain instances and the new example goes beyond that family.

Best, Authors

Thank you for the new counterexample. It answers my question about the linear error floor. For Theorem 8, should the simplified bound retain the optimization term from the preceding inequality?

Dear Reviewer,

Thank you for the follow-up! We are glad to see that the new counter-example has answered your question.

Regarding theorem 8 (theorem 10 in the updated manuscript, line 1216) we are not sure which term you are referring as the optimization term. The proof upper bounds the local stability gap by two terms : term (I) is similar to the loss from exact gradient and term (II) is the loss due to bias in gradient estimation (g^t≠gt\hat{g}_t \neq g_t). The term (II) is bounded by O~(ST)\tilde{O}(\sqrt{ST}) by Martingale concentration inequalities.

If you could provide a bit more context regarding the optimization term you are referring to, we would be happy to clarify.

Thank you for the responses and the new counterexample. My main question about the linear error floor has been addressed. I will maintain my rating of weak acceptance, with a minor concern remaining about the simplified bound in Theorem 8.

Reviewer_fnNmOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates the stability problem in performative reinforcement learning. The authors introduce two concepts, local mixed stability and global mixed stability, and establish a strict separation between them by constructing a counterexample on which local stability is exactly achievable while every mixture suffers a global stability gap bounded away from zero. They further show that local mixed stability can be attained without any assumption on the environment map, and that global mixed stability is attainable under a bounded-transition-range assumption that is strictly weaker than the sensitivity condition.

Critical strengths
  1. The paper establishes a strict separation between local and global stability in performative RL.

  2. A weighted per-state Hedge algorithm is proposed and proved to achieve local stability unconditionally, with a finite sample complexity of O(SA/(1−γ)4ε2)O(SA/(1-\gamma)^4\varepsilon^2).

  3. An unweighted per-state Hedge algorithm is proposed to achieve the global stability under the bounded-transition-range assumption, which is strictly weaker than the sensitivity assumption.

Critical weaknesses
  1. Theorem 3 provides an upper bound of γεP/(1−γ)3\gamma\varepsilon_P/(1-\gamma)^3, whereas the lower bound is γεP/(1−γ)\gamma\varepsilon_P/(1-\gamma). These two bounds do not match, leaving a gap of order 1/(1−γ)21/(1-\gamma)^2.

  2. It would be helpful to include a table comparing the bounds in Theorems 1–3 with those of related works, making the improvement in assumptions and rates clear to the reader.

  3. Algorithm 1 requires the ability to draw a batch of independent samples for each state-action pair under the current policy πt\pi_t. This requires a generative model/simulator. Can the algorithm and its analysis be extended to the setting where the learner only has access to trajectory data?

Questions for authors

see Weakness

2 comments

Dear Reviewer fnNm,

Thank you for your feedback and further questions. Below we provide our response. We would be happy to answer any further questions you might have.

Re. W1: Gap between upper and lower bound of order 1/(1−γ)21/(1-\gamma)^2.

Thank you for this observation! In this work, we primarily focused on matching the upper and lower bound in terms of ϵP\epsilon_P the parameter used to quantify the bounds in transition range. The primary source of the factor 1/(1−γ)21/(1-\gamma)^2 is the variance of the estimator Q^t(s,a)\widehat{Q}_t(s,a) which is 1/(1−γ)21/(1-\gamma)^2.

The upper bound on the variance is used to apply Freedman's inequality in order to bound the sum of dependent random variables ∑t=1T(Qt(s,a)−Q^t(s,a))\sum_{t=1}^T (Q_t(s,a) - \widehat{Q}_t(s,a)).

The issue can be mitigated to some extent by also building an estimator of the variance of Q^t(s,a)\widehat{Q}_t(s,a) and using variance-aware version of online hedge algorithm. However, the analysis is complex and we haven't yet managed to completely resolve the gap of O(1/(1−γ)2)O(1/(1-\gamma)^2). Besides, we believe the strength of our result lies in demonstrating that simple online algorithm can indeed converge to global mixed stability.

Re. W2: It would be helpful to include a table comparing the bounds in Theorems 1–3 with those of related works.

Ours is the first work to consider mixed stability in performative RL. Prior work [1] considered stability of a single deterministic policy. The main benefit of our approach is that the response map M(π)M(\mathbf {\pi}) can be arbitrarily discontinuous. We also improved the analysis of multi-agent setting and the current result (theorem 7, line 502) only requires bounded transition range and reward instead of the Lipschitzness of the potential function. If the reviewer prefers, we can add the following comparison table in the paper.

SettingAssumptionsTypeResult
Local StabilityNoneMixedThm 1
Global StabilityBounded transition (A.1)MixedThm 3
Global StabilityLipschitz reward and transitionDeterministic[1]
Multi-Agent Local StabilityPotential GameMixedThm 5
Multi-Agent Global StabilityPotential Game+Bounded transition & reward (A.4)MixedThm 7
Multi-Agent Global StabilityPotential Game+Lipschitz transition & rewardDeterministic[2]

Note that Assumption A.1 and A.4 are significantly weaker than Lipschitz reward and transition assumed in the prior literature.

Re. W3. Can the algorithm and its analysis be extended to the setting where the learner only has access to trajectory data?

This is an interesting question! Yes, we can estimate state-action function Qt(⋅,⋅)Q_t(\cdot,\cdot) using trajectories collected from deploying policy πt\pi_t in the environment M(πt)M(\pi_t). The problem is easier than off-policy evaluation since the target policy is also πt\pi_t rather than a policy different than the deployment policy. The current proof only uses that Q^t(s,a)\widehat{Q}_t(s,a) is an unbiased estimator of Qt(s,a)Q_t(s,a). If we build estimator using trajectory data then it will be biased. However, with ntn_t trajectories collected at iteration tt the bias is expected to be of order 1/nt1/\sqrt{n_t} and as long as ntn_t is large enough, online hedge based on the new estimator can achieve global stability.

References:

[1] Mandal, Triantafylliou, Radanovic. Performative Reinforcement Learning, ICML-2023.

[2] Sahitaj et. al. Independent Learning in Performative Markov Potential Games, AIStats-2025.

Best,

Authors

I appreciate the authors' efforts in revising the paper. Although some of my comments have not been addressed, I understand that addressing them requires complicated revision and it is difficult to complete within a short time. I would like to keep my positive score.

Reviewer_zUJDOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies performative reinforcement learning, where the deployed policy shapes the environment the learner subsequently encounters. It considers performative stability: a policy should be optimal in the environment it induces, with that environment held fixed when evaluating alternatives.

The authors study mixtures of policies and distinguish local mixed stability, a first-order criterion, from global mixed stability, which evaluates actual performance gains from alternative policies. They construct a survival-chain example in which the local gap can be made arbitrarily small while the global gap remains bounded away from zero for every mixture.

The paper then shows that weighted per-state Hedge achieves a vanishing local stability gap under arbitrary environment maps. For global stability, it replaces Lipschitz sensitivity assumptions with a bounded transition range assumption and obtains convergence up to a residual depending on the transition range. Finally, it extends the analysis to multiagent local stability in general Markov games and global stability under additional potential-game and regularity assumptions.

Critical strengths
  1. The distinction between local and global mixed stability is interesting. The survival-chain example illustrates how small first-order improvement opportunities can coexist with substantial global policy improvements, highlighting a limitation of local stability guarantees.

  2. The bounded transition range result is conceptually useful. It permits discontinuous environmental responses while controlling the global stability gap. Together with the unconditional local result, it helps clarify which guarantees are attainable under different assumptions on the environment.

Critical weaknesses
  1. The significance of local mixed stability needs stronger motivation. If the intended objective is performative stability in the sense of having no profitable policy replacement, global stability appears to be the more directly relevant criterion. The paper’s own separation example shows that a small local gap need not imply a small global gap. While the unconditional local guarantee is mathematically interesting, it remains unclear what operational benefit it provides or in which applications it would constitute a satisfactory learning outcome.

  2. The multiagent global result requires stronger structure and regularity than the single-agent bounded-range result. In particular, Assumption 3 requires smoothness of each induced potential and Lipschitz sensitivity of the potential to changes in the deployed policy profile. This limits the extent to which the single-agent message about accommodating discontinuous responses carries over to the multiagent setting. A clearer explanation of the role and necessity of these assumptions would strengthen the contribution.

Questions for authors
  1. Are there useful stability concepts beyond the paper’s first-order local criterion that remain more tractable than global stability; for example, second-order conditions or guarantees against small but finite policy updates? It would be helpful to discuss whether such notions address the failure illustrated by the separation example, and how they relate to the global definition for mixtures.

  2. Could the authors provide more motivation for performative stability as an objective in RL, particularly in relation to performative optimality? A performatively optimal policy maximizes its return while accounting for the environment induced by its own deployment:

πPO∈arg⁡max⁡πVM(π)(π).\pi_{\mathrm{PO}} \in \arg\max_{\pi} V_{M(\pi)}(\pi).

By contrast, a performatively stable policy is optimal in the environment it induces, with that environment held fixed when evaluating alternatives:

πPS∈arg⁡max⁡π′VM(πPS)(π′).\pi_{\mathrm{PS}} \in \arg\max_{\pi'} V_{M(\pi_{\mathrm{PS}})}(\pi').

In applications where long-run deployed performance is the primary objective, performative optimality seems more directly relevant. In which settings is stability itself the appropriate target, and do the proposed stability guarantees provide any information about performance relative to a performatively optimal policy? A discussion of this distinction would be valuable.

  1. For the Markov potential-game result, is the Lipschitz sensitivity requirement in Assumption 3 essential, or primarily needed by the proof? Could bounded transition range, possibly together with additional restrictions on rewards or potentials, support a comparable global stability guarantee?
1 comment

Dear Reviewer zUJD,

Thank you for your feedback and further questions. Below we provide our response. We would be happy to answer any further questions you might have.

Re. W1: The significance of local mixed stability needs stronger motivation.

We are not the first to introduce the concept of local stability. As Lemma 2 (line 229) shows this notion is equivalent to the existing definition of stationary performative stability [1]. With nonconvex loss function and a deterministic policy, this is the only notion of stability that can be guaranteed to exist. Moving to mixture policies allows us to consider globally stable solution.

Additionally, the literature on performative prediction (mixed or deterministic) mainly consider convex loss and cannot distinguish between local and global notions. Our main motivation was to differentiate them by moving to mixtures but the preferred concept is of course, global mixed stability.

Re. Q1: Are there useful stability concepts beyond the paper's first-order local criterion that remain more tractable than global stability

Thank you for the suggestion of incorporating second-order conditions while defining stability! In general, a second-order condition based locally stable point need not be globally stable, and similar separation results can be derived. In order to see this, suppose there is no performative effect. Then stability coincides with optimality. However, for a general nonconvex function (e.g. value function) a positive definite Hessian matrix can only guarantee local optimality in a neighbourhood and not global optimality.

Re. Q2 Comparison with Performative optimality:

In this paper, our focus was on performative stability which might not exist for discontinuous environment map, and we introduced the general notion of mixed stability. Note that performatively optimal policy πPO\pi_{\text{PO}} always exists and several recent work [2, 3] have already studied optimization methods for performative optimality in RL.

Performative optimality is appropriate when the learner cares about the immediate or one-step effect of the policy. Policy π\pi is deployed and the value function is measured in the changed MDP M(π)M(\pi). However, for long-term repeated deployment, stability is the preferred objective since if the learner deploys πPO\pi_{\text{PO}} then the learner would want to re-optimize in the new environment M(πPO)M(\pi_{\text{PO}}). Stable points are designed to eliminate such re-optimizations.

Re. W3 and Q3 (part a) Lipschitz sensitivity assumption of the Markov potential function:

Thank you for this question! The Lipschitz sensitivity assumption of the potential function (assumption 3) is not necessary for achieving the desired global stability gap. We have added a new analysis of the independent policy gradient algorithm (theorem 7, line 502) that only requires boundedness of transition range and reward functions (assumption 4, line 500). This allows the response map M(⋅)M(\cdot) to be arbitrarily discontinuous and the potential function ΦM(π)(σ)\Phi_{M(\boldsymbol{\pi})}(\sigma) can be a discontinuous function of π\boldsymbol{\pi}.

Re. Q3 (part b) Could bounded transition range, possibly together with additional restrictions on rewards or potentials, support a comparable global stability guarantee?

Bounded transition range together with bounded reward functions is sufficient for the analysis. The new global stability gap O(κSn (ϵr/(1−γ)2+ϵP/(1−γ)3))O(\kappa \sqrt{S}n \ (\epsilon_r/(1-\gamma)^2 + \epsilon_P/(1-\gamma)^3)) is comparable to the earlier stability gap of O(κSnϵL)O(\kappa \sqrt{Sn} \epsilon_L). This is because if the potential function were Lipschitz, we would expect the gradient norm of each agent to be O(poly(1/(1−γ))O(\text{poly}(1/(1-\gamma)) and there are nn agents in total.

A natural question is whether the bounded reward range assumption is necessary since bounded transition range is sufficient for a single agent. We believe this is the case for a fully decentralized and independent learning algorithm. For the independent policy gradient ascent and weighted/unweighted hedge, we could construct counter-examples where the achievable global stability gap is Ω(ϵr)\Omega(\epsilon_r) even with ϵP=0\epsilon_P=0 i.e. fixed transition.

References

[1] Le, Wai. Stochastic Optimization Schemes for Performative Prediction with Nonconvex loss. NeurIPS-2024.

[2] Basu, Das, Driss, Mukherjee. Performative Policy Gradient: Optimality in Performative Reinforcement Learning, ICML-2026.

[3] Chen, Huang. Achieve Performatively Optimal Policy for Performative Reinforcement Learning. 2026.

Best,

Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.