Source-linked AI summary
Local and Global Stability in Performative Reinforcement Learning
Debmalya Mandal
TL;DR
Performative reinforcement learning studies policies that alter the environments generating their future data, while existing convergence guarantees rely on sensitivity assumptions that may be difficult to verify. This paper analyzes local and global stability for policy mixtures, finding unconditional local stability but conditional global guarantees and extending the analysis to multi-agent games.
Problem
Existing performative-RL convergence guarantees assume sensitivity of reward and transition maps, assumptions that are hard to verify and may fail in multi-agent best-response settings.
Source: §1 · p. 1Method
The paper studies mixtures under local first-order and global arbitrary-deviation stability, using per-state Hedge and extending both notions to performative Markov games.
Source: §1 · p. 2, §1.1 · p. 2Results
Local stability converges unconditionally; under Bounded Transition Range, global stability has an O(γϵP /(1 − γ)3) floor, with local trajectory feedback lower-bounded by Ω(γϵP /(1 −γ)).
Source: §1 · p. 2, §1.1 · p. 2Takeaways & Limitations
Randomization alone does not ensure global stability in reinforcement learning, while potential-game structure supports a global guarantee in multi-agent settings.
Source: §1 · p. 2Extensions to linear MDPs or general function approximation, and to deployment protocols without resampling, remain future directions.
Source: §7 · p. 13
Abstract
from arXiv · showhide
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 $\pi \mapsto (P_\pi, r_\pi)$, 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/\sqrt{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(\gamma\epsilon_P/(1-\gamma)^3)$, and we prove a matching-in-$\epsilon_P$ lower bound of $\Omega(\gamma\epsilon_P/(1-\gamma))$ 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.
1 Introduction
The introduction argues that policy-dependent environments make sensitivity-based convergence assumptions difficult to rely on, and distinguishes local from global mixed stability. It previews assumption-free local stability, more conditional global guarantees, and extensions to performative Markov games.
1 Introduction
- Existing convergence guarantees for policies optimal in their induced environments rely on strong sensitivity assumptions that are hard to verify and may fail in multi-agent settings.Best-response dynamics may be discontinuous, and opponents may respond adversarially to policy changes.Source: §1 · pp. 1–2
- Local stability is a first-order relaxation equivalent to stationarity, whereas global stability must hold against arbitrary deviating policies.The paper asks how much sensitivity is needed for online learning to reach a stable mixture, and whether the answer depends on the stability target.Source: §1 · p. 2
1.1 Overview of the main contributions
- Weighted per-state Hedge targets local stability without assumptions on the environment map, with a finite-sample version for sampled-trajectory feedback.The overview also describes the local guarantee as applying to arbitrary local stability.Source: §1.1 · p. 2
- A survival-chain instance achieves local stability exactly while every policy mixture has global stability gap bounded away from zero.This establishes a strict separation between the two stability notions in reinforcement learning, unlike the cited performative-prediction result [FP26].Source: §1.1 · p. 2
- Under Bounded Transition Range, unweighted per-state Hedge attains global stability up to O(γϵP /(1 − γ)3), while local trajectory feedback has a lower bound of Ω(γϵP /(1 −γ)).The assumption is strictly weaker than sensitivity of the transition map [MTR23].Source: §1.1 · p. 2
- Independent weighted per-state Hedge achieves local stability in n-player games without joint-map sensitivity or game-structure assumptions; independent projected policy gradient gives global stability for potential games.The overview contrasts its local result with multiplayer performative-prediction guarantees requiring such conditions [NFD+23].Source: §1.1 · pp. 2–3
1.2 Related work
- The related-work discussion frames local stability as transferring mixture-based, sensitivity-free guarantees from performative prediction to reinforcement learning and connects global analysis to policy-gradient methods for changing potentials.It distinguishes local stability from stronger performative-optimality guarantees that require regularity conditions.Source: §1.2 · pp. 3–4
2 Setting and notation
The section formalizes policy-dependent MDPs and mixed stability, distinguishing occupancy-weighted local stability from stability against global deviations. A survival-chain construction shows that exact local stability can coexist with a constant global gap.
2.1 Two solution concepts
- A performatively stable policy is optimal in its induced MDP, while mixed stability compares deviations within each policy-induced MDP without giving the comparator its own performative effect.For a point-mass mixture, this mixed notion reduces to performative stability of a policy.Source: §2.1 · p. 5
- Local mixed stability weights statewise first-order advantages by the deployed policy’s occupancy and generalizes stationary performative stability to mixtures.For a point-mass distribution, local and stationary performative stability coincide.Source: §2.1 · pp. 5–6
2.2 The instance
- The instance uses two H-stage models with opposing safe actions and assigns each policy the model in which it survives less well.The chain gives reward only after absorption in the success state.Source: Figure 1 · p. 6, §2.2 · pp. 6–7
- The survival-chain instance has zero local gap, yet every mixture has a global gap bounded below by a universal constant; H≥2 is needed because at H=1 the value is linear and the notions coincide.Source: §2.1 · p. 6, §2.2 · p. 7
3 Local stability without any assumption
Weighted per-state Hedge uses deployed-policy occupancies to update policies and target local stability. The section also presents a trajectory-based finite-sample version with a probability guarantee.
3 Local stability without any assumption
- Weighted per-state Hedge updates each state’s policy from its action values and deployed-policy occupancy, aligning regret with the local occupancy-weighted objective.Source: §3 · p. 7
- For an arbitrary environment map, the uniform mixture of policies generated by weighted per-state Hedge has an unconditional local-stability guarantee.Source: §3 · p. 7
3.1 A finite-sample algorithm
- The finite-sample algorithm estimates occupancies from rollouts and action values at occupancy-sampled states, using fresh randomness for the value samples.The theorem states a local-stability guarantee with probability at least 1−δ.Source: §3.1 · p. 8
- The total number of value and occupancy samples required by the finite-sample algorithm is Tn(1+kA).Source: §3.1 · p. 8
4 Global Stability Under Bounded Transition Range
Global mixed stability becomes achievable under a bounded transition range, even when the environment map is discontinuous within that range. The section presents unweighted per-state Hedge and a finite-sample counterpart.
4 Global Stability Under Bounded Transition Range
- Bounded transition range restricts the range of induced transition kernels, not the regularity of the policy-to-kernel map, and imposes no reward-map assumption.The assumption is strictly weaker than transition-map sensitivity and permits arbitrary discontinuity within the bounded range.Source: §4 · pp. 8–9
- Unweighted per-state Hedge generates a globally stable mixture under this assumption, whereas occupancy-weighted Hedge does not directly yield the global guarantee.The global objective lacks the time-varying occupancy weights appearing in the weighted-Hedge regret bound.Source: §4 · p. 9
- Gapglob(μ̂) converges to a floor of Θ(γϵP/(1−γ)^3) under bounded transition range, with an additional finite-iteration term.The theorem’s bound includes a term decreasing with T, while the transition-range term remains as the floor.Source: §4 · p. 9
4.1 A Finite-Sample Algorithm
- With probability at least 1−δ, the finite-sample corollary reaches Gapglob(μ̂)≤ε for ε≥3γϵP/(1−γ)^3 using TSAk value and occupancy samples.The value-sample procedure draws k samples for each state-action pair; the sample total is TSAk.Source: §4.1 · p. 9
5 Lower Bound on Global Stability
The section establishes a trajectory-feedback lower bound for global stability using hidden-action instances. Its dependence on ϵP matches the earlier upper bound up to a factor in 1−γ.
5 Lower Bound on Global Stability
- Under local feedback, the learner observes trajectories from deployed policies but never rewards at unvisited state-action pairs or environments for policies it has not deployed.The learner outputs the uniform mixture of its deployed policies after N trajectories.Source: §5 · p. 10
- The lower-bound construction uses K actions with one hidden action and transition probabilities defined relative to a reference kernel, satisfying bounded transition range.The passage identifies ϵP=2ϵ for the instance.Source: §5 · p. 10
- With O(K/ϵP^2) trajectories, some hidden-action instance forces expected Gapglob(μ̂)≥Ω(γϵP/(1−γ)), matching the upper bound in ϵP up to O(1/(1−γ)^2).The instance has one state and a hidden contrarian action rewarded exactly when the learner underweights it.Source: §5 · p. 10
6 Multi-Agent Setting
The multi-agent extension defines stability for mixtures over joint policy profiles, which may correlate players’ policies. It establishes unconditional local stability and gives a conditional global guarantee for performative Markov potential games.
6.2 Multi-Agent Local Stability without any assumption
- Independent weighted per-state Hedge achieves local stability for every player in an arbitrary performative Markov game, without assumptions on joint-map sensitivity or game structure.The guarantee’s bound depends on the largest individual action-set size rather than the joint action-space size.Source: §6.2 · p. 11
6.3 Global Stability for Markov Potential Games
- A two-player survival-chain game separates global from local stability even with no performative effects, because deviation occupancies vary with opponents’ policies.In the constructed fixed game, ϵP=0.Source: §6.3 · p. 11
- For global stability, independent projected policy gradient ascent is analyzed for performative Markov potential games under potential smoothness and environment sensitivity assumptions.The potential-game definition requires unilateral utility changes to match potential changes.Source: §6.3 · p. 12
- With O(ϵL^-2) iterations, the global-stability bound depends on the distribution mismatch coefficient and grows with the square root of the number of players, not the action count.The distribution mismatch coefficient also appears in analyses of Markov potential games [DWZJ22].Source: §6.3 · p. 12
7 Conclusion and Future Work
The conclusion distinguishes the assumptions needed for local versus global mixed stability and identifies open questions about algorithms, rates, deployment, and multi-agent scope.
7 Conclusion and Future Work
- Local stability needs no environment-map assumption, while global stability requires bounded transition range and converges only up to a stated floor.The global upper floor is O(γϵ_P/(1−γ)^3), and a trajectory-feedback lower bound is Ω(γϵ_P/(1−γ)).Source: §7 · p. 13
- The local and global guarantees use different per-state Hedge algorithms, leaving open whether one algorithm can attain both.Weighted Hedge handles local stability; unweighted Hedge handles global stability up to a non-vanishing floor.Source: §7 · p. 13
- The upper and lower global-stability bounds match in ϵ_P, but retain an O(1/(1−γ)^2) gap in effective horizon.Closing it may require a sharper occupancy-transfer argument or a lower-bound instance with a longer horizon.Source: §7 · p. 13
- The current convergence rate implies mixtures supported on O(1/ε^2) policies, and improving that support bound remains open.A faster rate under additional environment-map assumptions is suggested as one possible direction.Source: §7 · p. 13
- The sample complexities scale with SA and require resampling the induced environment after each deployment; function approximation and no-resampling protocols remain future directions.Multi-agent open questions include global stability beyond potential games and finite-sample analysis without exact potential gradients.Source: §7 · p. 13
A.1 Local Stability of the Survival Chain Instance
The survival-chain analysis evaluates local stability using an equal mixture of two nearby stationary policies and reduces the deviation calculation to statewise action quantities.
A.1 Local Stability of the Survival Chain Instance
- The mixture assigns equal probability to two stationary policies with action-1 probabilities 1/2+η and 1/2−η at each survival-chain state.Source: §A.1 · p. 17
- The local-gap calculation uses Proposition 2 and the identity ℓA(a)+ℓB(a)=2−2ε for every action.Source: §A.1 · p. 17
- For this mixture, q̄μ(s,a) is action-independent, and Proposition 2 reduces the statewise maximization to max_a q̄μ(s,a).Source: §A.1 · pp. 17–18
A.2 Global Stability of the Survival Chain Instance
The global-stability lower-bound proof compares an arbitrary policy with a mixture of two fixed policies and uses case-specific bounds in the survival-chain instance.
A.2 Global Stability of the Survival Chain Instance
- The proof tests the global gap against ν=1/2δπA+1/2δπB, where πA and πB choose actions 1 and 2, respectively, at every survival-chain state.Source: §A.2 · pp. 18–19
- One case assumes M(π)=M_A, equivalently F_A(y)≤F_B(y), to bound the comparison for an arbitrary policy.Source: §A.2 · p. 18
- A Bernoulli-trial identity cancels odd-k terms; the case bounds use g(y)'s maximum at 1/2 and yield f(ϵ,H)≥1/4 in the stated regime.Source: §A.2 · p. 19
A.3 Local Stability without Any Assumption
This section develops local and global stability, including assumption-free local guarantees, finite-sample analyses, bounded-transition-range global guarantees, and a local-feedback lower bound. It also presents a multi-agent example separating local from global stability and analyzes stability in performative Markov potential games.
A.3 Local Stability without Any Assumption
- Weighted per-state Hedge drives the local stability gap to O(1/sqrt T) for arbitrary environment sequences, with the bound holding simultaneously and deterministically across states.The argument applies to every comparator policy, so the resulting bound also holds for the maximum over comparators.Source: §A.3 · p. 20
A.4 Finite Sample Analysis of Local Stability
- The finite-sample local analysis accounts for n occupancy samples and at most nkA value samples per iteration.It analyzes the local stability gap using empirical occupancy and value estimates.Source: §A.4 · p. 22
A.5 Global Stability Under Bounded Transition Range
- Under bounded transition range, per-state Hedge yields a global stability guarantee with a vanishing term and a floor of O(γϵP/(1−γ)^3).The proof controls occupancy differences using a simulation bound of γϵ/(1−γ).Source: §A.5 · p. 25
A.6 Finite Sample Analysis of Global Stability
- The conditional second moment E[ζ_t(s,a)^2|F_{t−1}] equals Var(bQ_t(s,a)) and is at most 1/[k(1−γ)^2]; substituting the two bounds in Equation (23) gives probability at least 1−2δ.Source: §A.6 · pp. 27–28
A.7 Lower bound under Local Feedback
- The local-feedback lower-bound setup uses hidden-action instances and a trajectory budget, with each instance’s global stability gap bounded in magnitude by 2X, where X=γϵ/(1−γ).The algorithm outputs the uniform mixture over its realized policies.Source: §A.7 · p. 28
- The hidden-action construction yields a trajectory-feedback global-stability lower bound scaling as γϵ_P/(1−γ).The proof bounds the divergence between the null and hidden-action trajectory laws by 3ϵ²E₀[N_j].Source: §A.7 · p. 29
A.8 Multi-Agent Setting
- Per-player Hedge regret bounds yield a deterministic upper bound on the local stability gap in the multi-agent setting.The proof applies Hedge to each player's realized gains at each state, then sums over states and maximizes across players.Source: §A.8 · p. 30
- A multi-agent mixture can have zero local gap for both players while player 1 still gains globally by deviating.The example shows local indifference state by state, but a globally beneficial comparator for player 1.Source: §A.8 · p. 30
A.9 Performative Markov Potential Games
- In performative Markov potential games, the proof bounds the Frank–Wolfe gap and derives a stability bound using projected-gradient progress.The argument invokes Assumption 3 and a step size α ≤ 1/L_Φ.Source: §A.9 · pp. 31–33