Paper deep dive
The Price of Paranoia: Robust Risk-Sensitive Cooperation in Non-Stationary Multi-Agent Reinforcement Learning
Deep Kumar Ganguly, Chandradithya S Jonnalagadda, Pratham Chintamani, Adithya Ananth
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 97%
Last extracted: 4/27/2026, 6:31:54 PM
Summary
The paper identifies a fundamental problem in Multi-Agent Reinforcement Learning (MARL) where the process of co-learning destabilizes cooperation in coordination games like the Stag Hunt. The authors demonstrate that standard risk-neutral learning and traditional distributional robustness (applying EVaR to returns) actually exacerbate instability by penalizing high-variance cooperative actions. They propose the 'Price of Paranoia' (PoP) framework and a new algorithm, Robust Adaptive Trust-Region Learning (RATTL). RATTL resolves the 'EVaR Paradox' by applying Entropic Value-at-Risk (EVaR) to the policy gradient update variance rather than the return distribution, using an online measure of partner unpredictability to expand the cooperation basin and ensure robust cooperation retention under non-stationarity.
Entities (13)
Relation Signals (8)
EVaR → appliedto → Policy Gradient Update Variance
confidence 100% · robustness should target the policy gradient update variance induced by partner uncertainty, not the return distribution.
Price of Paranoia → isdualof → Price of Anarchy
confidence 100% · we introduce the Price of Paranoia as the structural dual of the Price of Anarchy
Price of Paranoia → isdualof → Price of Anarchy
confidence 100% · we introduce the Price of Paranoia as the structural dual of the Price of Anarchy
Stag Hunt → isinstanceof → Symmetric Coordination Game
confidence 100% · The Stag Hunt (Skyrms, 2004) is the canonical instance [of a symmetric coordination game]
Stag Hunt → isinstantiatedas → Markov Game
confidence 100% · We study a two-player Markov game... instantiated as a repeated Stag Hunt
RATTL → resolves → EVaR Paradox
confidence 100% · This distinction yields an algorithm whose gradient updates are continuously modulated by an online measure of partner unpredictability... This distinction yields an algorithm... [resolving] the EVaR Paradox.
RATTL → targets → Policy Gradient Update Variance
confidence 100% · robustness should target the policy gradient update variance induced by partner uncertainty, not the return distribution.
Robust Adaptive Trust-Region Learning → →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Cooperative equilibria are fragile. When agents learn alongside each other rather than in a fixed environment, the process of learning destabilizes the cooperation they are trying to sustain: every gradient step an agent takes shifts the distribution of actions its partner will play, turning a cooperative partner into a source of stochastic noise precisely where the cooperation decision is most sensitive. We study how this co-learning noise propagates through the structure of coordination games, and find that the cooperative equilibrium, even when strongly Pareto-dominant, is exponentially unstable under standard risk-neutral learning, collapsing irreversibly once partner noise crosses the game's critical cooperation threshold. The natural response to apply distributional robustness to hedge against partner uncertainty makes things strictly worse: risk-averse return objectives penalize the high-variance cooperative action relative to defection, widening the instability region rather than shrinking it, a paradox that reveals a fundamental mismatch between the domains where robustness is applied and instability originates. We resolve this by showing that robustness should target the policy gradient update variance induced by partner uncertainty, not the return distribution. This distinction yields an algorithm whose gradient updates are modulated by an online measure of partner unpredictability, provably expanding the cooperation basin in symmetric coordination games. To unify stability, sample complexity, and welfare consequences of this approach, we introduce the Price of Paranoia as the structural dual of the Price of Anarchy. Together with a novel Cooperation Window, it precisely characterizes how much welfare learning algorithms can recover under partner noise, pinning down the optimal degree of robustness as a closed-form balance between equilibrium stability and sample efficiency.
Tags
Links
- Source: https://arxiv.org/abs/2604.15695v1
- Canonical: https://arxiv.org/abs/2604.15695v1
Trouble viewing inline? Open PDF directly →
Full Text
53,197 characters extracted from source content.
Expand or collapse full text
The Price of Paranoia: Robust Risk-Sensitive Cooperation in Non-Stationary Multi-Agent Reinforcement Learning Deep Kumar Ganguly†,1, Chandradithya S Jonnalagadda‡, Pratham Chintamani♣, Adithya Ananth♣ †Technical University of Munich (TU Munich) ‡Brown University ♣Indian Institute of Technology Tirupati (IIT Tirupati) Correspondence to: deep.ganguly@tum.de†, cjonnala@cs.brown.edu‡ Abstract Cooperative equilibria are fragile. When agents learn alongside each other rather than against a fixed environment, the very process of learning destabilizes the cooperation they are trying to sustain: every gradient step one agent takes shifts the distribution of actions its partner will play, turning a cooperative partner into a source of stochastic noise precisely where the cooperation decision is most sensitive. We study how this co-learning noise propagates through the structure of coordination games, and find that the cooperative equilibrium—even when strongly Pareto-dominant—is exponentially unstable under standard risk-neutral learning, collapsing irreversibly once partner noise crosses the game’s critical cooperation threshold. The natural response, applying distributional robustness to hedge against partner uncertainty, makes things strictly worse: risk-averse return objectives penalize the high-variance cooperative action relative to the safe defection action, widening the instability region rather than shrinking it—a paradox that reveals a fundamental mismatch between the domain where robustness is applied and the domain where instability actually originates. We resolve this by showing that robustness should target the policy gradient update variance induced by partner uncertainty, not the return distribution itself. This distinction yields an algorithm whose gradient updates are continuously modulated by an online measure of partner unpredictability, provably expanding the cooperation basin in any symmetric coordination game. To unify the stability, sample complexity, and welfare consequences of this approach, we introduce the Price of Paranoia as the structural dual of the Price of Anarchy—a game-theoretic quantity that, together with a novel Cooperation Window, precisely characterizes how much welfare any learning algorithm can recover under partner noise, and pins down the optimal degree of robustness as a closed-form balance between equilibrium stability and sample efficiency. 11footnotetext: Supported by the German Research Foundation (DFG) through Research Training Group GRK 2428 ConVeY. 1 Introduction Large-scale cooperation among non-kin is a foundational pillar of human societies—a primary catalyst for ecological and economic success (Fehr and Gintis, 2007; Handley and Mathew, 2020). Societies with robust cooperative frameworks effectively manage shared resources, outcompeting less cohesive groups and scaling in complexity and wealth (Boyd and Richerson, 2009). Conversely, the erosion of cooperation is a precipitating factor in the collapse of complex societies (Ferrarini, 2013): free-riding individuals trigger retaliatory cascades that unravel collective welfare (Wardil et al., 2019; Andreozzi et al., 2020; Griessmair and Hippmann, 2022). Understanding not just how cooperation is established, but how it is sustained, is therefore as consequential for artificial agents as it is for human societies. Researchers model these dynamics via game theory and Multi-Agent Reinforcement Learning (MARL), which captures the temporal dynamics of co-learning and allows agents to adapt to the evolving policies of their peers. While modern MARL algorithms can converge to Pareto-optimal equilibria (Semsar-Kazerooni and Khorasani, 2009; Zhang et al., 2025), they routinely fail to sustain cooperation over repeated interaction. This fragility stems from a source that is both obvious in hindsight and largely unaddressed in the literature: the agents themselves. Every gradient update one agent takes shifts the distribution of actions its partner will play, injecting stochastic noise into the cooperation signal at the exact moment the cooperation decision is most sensitive. Accidental defections during exploration are statistically indistinguishable from hostile policy shifts, provoking retaliation and triggering irreversible defection cascades (Dal Bó and Fréchette, 2011). The Optimist’s Hangover. In the canonical Stag Hunt (Skyrms, 2004), partner exploration noise is statistically indistinguishable from strategic defection to a risk-neutral agent optimizing [R]E[R]. Even transient variance triggers a cascade of negative advantage signals, driving the cooperation probability below the critical threshold p∗p^* and permanently locking the agent into the risk-dominant, suboptimal equilibrium. Optimism-based methods (Palmer et al., 2018; Zhang et al., 2025) excel at discovering cooperation but remain hypersensitive to this variance. We term this the Optimist’s Hangover: cooperation is learned optimistically, then lost paranoiacally. The Adaptivity–Robustness Dilemma. Traditional countermeasures fall short of resolving this sensitivity. Hysteresis (Matignon et al., 2007; Bowling and Veloso, 2002) relies on hand-tuned dampening rather than calibrated uncertainty, while explicit opponent modelling (Albrecht and Stone, 2018; Gmytrasiewicz and Doshi, 2005; Raileanu et al., 2018) requires restrictive parameterized classes. Conversely, applying distributional robustness (Nilim and Ghaoui, 2005; Iyengar, 2005; Zhang et al., 2020; Lu et al., 2024; Shi et al., 2024)—originally designed for adversarial settings—exposes a deeper tension: an agent that adapts too quickly treats partner exploration as defection, while one that is excessively robust suppresses genuine cooperation signals. This adaptivity–robustness dilemma remains fundamentally unresolved in non-stationary cooperative MARL. The EVaR Paradox and Its Resolution. Attempting to resolve this dilemma via standard distributional robustness actually exacerbates the Hangover. We prove that applying Entropic Value-at-Risk (EVaR) (Ahmadi-Javid, 2012) directly to action-conditioned returns strictly increases the critical cooperation threshold for all β>0β>0 (where β is the risk-sensitivity parameter, with β>0β>0 corresponding to risk-aversion; see §3). This EVaR Paradox occurs because return-level risk-aversion disproportionately penalizes the high-variance cooperative action. The paradox resolves, however, when EVaR is applied instead to the policy gradient update variance induced by partner uncertainty. This formulation yields a closed-form trust factor τ(t)=(1+β(t)σp^2(t))−1τ(t)=(1+β(t)\,σ^2_ p(t))^-1, where σp^2(t)σ^2_ p(t) is the Bernoulli variance of an online partner model. Crucially, this mechanism is doubly adaptive: the trust factor continuously modulates gradient updates, while the risk parameter β(t)β(t) adapts online by tracking our novel welfare diagnostic, the Price of Paranoia (PoP). Ultimately, agents do not need prosocial priors (Peysakhovich and Lerer, 2017) or costly punishment mechanisms (Fehr and Gächter, 2000a; Acemoglu and Wolitzky, 2015) to sustain cooperation; they simply require calibrated uncertainty—a state of principled paranoia. The Price of Paranoia. We introduce the PoP as the structural dual of the Price of Anarchy (Papadimitriou and Roughgarden, 2005; Roughgarden, 2015): where PoA quantifies the welfare cost of rational selfishness from below, PoP quantifies the welfare cost of maximin conservatism from above. Together they bracket the achievable welfare space via a Cooperation Window CW(G,ε)CW(G, ), which pins down the optimal risk parameter β∗β^* as a closed-form balance between equilibrium stability and sample-complexity overhead. The dynamic variant PoPDYN(t)PoP_DYN(t) provides a normalized, game-comparable welfare diagnostic—analogous to adaptive regret (Blum and Mansour, 2008)—measuring in real time how completely an adaptive agent recovers cooperative welfare after a perturbation. Contributions. We establish the theoretical foundations for risk-aware cooperative MARL and operationalize them through Robust Adaptive Trust-Region Learning (RATTL), the first doubly-adaptive cooperative MARL algorithm. Our specific contributions are: • The EVaR Paradox (Proposition 4): we prove that applying EVaR directly to return distributions counterintuitively hinders cooperation by widening the basin of instability. • Adaptive trust factor (Definition 3): a zero-communication, closed-form gradient-variance robustification τ(t)=(1+β(t)σp^2(t))−1τ(t)=(1+β(t)σ^2_ p(t))^-1 that resolves the paradox. • Basin-expansion theorem (Theorem 6): a formal proof that RATTL lowers the critical cooperation threshold without altruistic priors, accompanied by a PAC sample-complexity bound (Theorem 8) with polynomial robustness overhead (|j|eβ)O( |A_j |e^β). • Price of Paranoia framework: the Cooperation Window CW(G,ε)CW(G, ) and dimensionally corrected optimal risk formula β∗β^* unifying stability, sample complexity, and welfare. • Online adaptation (Algorithm 1): an adaptive β(t)β(t) rule tracking PoPDYN(t)PoP_DYN(t) in real time. • Empirical validation: RATTL retains near-100% cooperation under severe partner noise where risk-neutral and prosocial baselines collapse, with a transparent failure analysis under extreme non-stationarity that motivates the adaptive β(t)β(t) rule. 2 Related Work Cooperation mechanisms. The tension between individual incentives and collective welfare is traditionally addressed via external sanctioning (Fehr and Gächter, 2000b; a; Acemoglu and Wolitzky, 2015), intrinsic motivation models like guilt (Griessmair and Hippmann, 2022), or reward-shaping mechanisms such as inequity aversion (Hughes et al., 2018) and prosocial reward mixing (Wang et al., 2021; Peysakhovich and Lerer, 2017; McKee et al., 2020). These methods require auxiliary resources, complex credit assignment, or privileged access to partner utilities. RATTL modifies only the gradient update, preserving the original environment and communication protocols. Opponent modelling and shaping. Explicitly modelling opponents (Albrecht and Stone, 2018; Gmytrasiewicz and Doshi, 2005; Raileanu et al., 2018) or differentiating through their learning steps, as in LOLA (Foerster et al., 2018), directly addresses co-learning noise by accounting for how a partner’s policy changes in response to one’s own update. However, LOLA and RATTL operate on fundamentally different axes of the problem. LOLA requires access to the partner’s policy parameters and differentiable learning rule to compute second-order gradient corrections; under high non-stationarity, the estimated partner response itself becomes noisy, potentially amplifying rather than dampening instability. RATTL instead targets the agent’s own gradient variance induced by partner uncertainty, using only observed partner actions via a scalar EMA—no access to θj _j, RjR_j, or the partner’s learning algorithm is needed. The two approaches are complementary: LOLA shapes the partner toward cooperation (an active mechanism), while RATTL makes the agent’s own updates robust to partner noise (a passive mechanism). RATTL’s advantage is minimal information requirements and (1)O(1) computational overhead per update; its limitation is that it cannot actively influence partner behavior. Equilibrium selection. Equilibrium selection in MARL historically struggles with Pareto-optimal coordination in risk-dominant social dilemmas (Claus and Boutilier, 1998; Skyrms, 2004; Harsanyi and Selten, 1988). Hysteretic (Matignon et al., 2007; Palmer et al., 2018; Omidshafiei et al., 2017) and optimistic methods (Zhang et al., 2025) mitigate early defection by filtering negative updates, excelling at cooperation discovery but collapsing under sustained partner variance. RATTL complements these approaches by targeting cooperation retention rather than discovery. Risk-sensitive and robust MARL. While CVaR and EVaR have been explored in single-agent RL (Tamar et al., 2015; Chow et al., 2017; Greenberg et al., 2022), and distributionally robust MARL tackles adversarial uncertainty (Nilim and Ghaoui, 2005; Iyengar, 2005; Panaganti and Kalathil, 2022; Zhang et al., 2020; Shi et al., 2024; Lu et al., 2024), our work uniquely applies EVaR to gradient variance rather than the return distribution, and formally establishes that importing maximin adversarial methods into cooperative settings is counterproductive (Proposition 4). Welfare theory. Our framework builds upon the Price of Anarchy (Papadimitriou and Roughgarden, 2005; Roughgarden, 2015; Awerbuch et al., 2005) and adaptive regret dynamics (Blum and Mansour, 2008). By unifying these with online hyperparameter adaptation (Xu et al., 2018; Omidshafiei et al., 2019), we introduce PoPDYN(t)PoP_DYN(t), a game-theoretically grounded diagnostic for non-stationary cooperative MARL, accompanied by a theoretically derived β(t)β(t) rule that balances equilibrium stability and sample complexity in real time. 3 Preliminaries Markov Games. A two-player Markov game ℳ=(,1,2,P,R1,R2,γ)M=(S,\;A_1,\;A_2,\;P,\;R_1,\;R_2,\;γ) has transition kernel P, bounded rewards Ri∈[Rmin,Rmax]R_i∈[R_ ,R_ ], discount γ∈[0,1)γ∈[0,1), and parameterized policies πθi:→Δ(i) _ _i → (A_i). Each agent maximises Ji(θi;πj)=[∑t≥0γtRi(st,at1,at2)]J_i( _i; _j)=E[ _t≥ 0γ^tR_i(s_t,a_t^1,a_t^2)]. We study stateless repeated games (||=1|S|=1), so all quantities reduce to per-episode expectations over joint action distributions. Agent i’s cooperation probability is p=πθi(S)p= _ _i(S), where S denotes the cooperative action (Stag); agent j’s is q=πθj(S)q= _ _j(S). Assumption 1 (Markov Game). ℳ=(,1,2,P,R1,R2,γ)M=(S,A_1,A_2,P,R_1,R_2,γ) with P:×1×2→Δ()P:S×A_1×A_2→ (S), Ri:×1×2→[Rmin,Rmax]R_i:S×A_1×A_2→[R_ ,R_ ], γ∈[0,1)γ∈[0,1). Agent i has a parameterized policy πθi:→Δ(i) _ _i:S→ (A_i). Policy Gradient and Gradient Variance. Holding πj _j fixed, the policy gradient is: ∇θiJi=[Ai∇θilogπθi(ai)] _ _iJ_i=E[A_i _ _i _ _i(a^i)], where Ai=Ri−bA_i=R_i-b is the advantage over baseline b. The REINFORCE update (Williams, 1992) implements stochastic gradient ascent; PPO (Schulman et al., 2017) stabilizes it with a clipped surrogate, but the gradient structure is unchanged. For the Stag action ai=Sa^i=S with partner cooperation probability q, the partner-induced gradient variance is: Σ(q)=q(1−q)Δ2‖∇θilogπθi(S)‖2 (q)=q(1-q)\, ^2\, \| _ _i _ _i(S) \|^2 (1) where Δ=rc−rs =r_c-r_s is the payoff spread. This variance is non-negligible at the cooperation threshold q=p∗q=p^* and is the direct target of RATTL’s trust factor. Coordination Games and the Stag Hunt. A symmetric game G=(,R)G=(A,R) is a coordination game if it has a payoff-dominant Nash equilibrium NEcNE^c and a risk-dominant Nash equilibrium NEr≠NEcNE^r ^c with SW(NEc)>SW(NEr)SW(NE^c)>SW(NE^r) (Harsanyi and Selten, 1988). The Stag Hunt (Skyrms, 2004) is the canonical instance with =S,HA=\S,H\ and payoffs rc>rh>rsr_c>r_h>r_s (Eq. (4)). The critical cooperation threshold p∗=(rh−rs)/Δ∈(0,1)p^*=(r_h-r_s)/ ∈(0,1) is the unique partner belief q at which agent i is indifferent between S and H. The set (p∗,1](p^*,1] is the Basin of Trust; [0,p∗)[0,p^*) is the Basin of Fear. At threshold, AS(p∗)=0A_S(p^*)=0 while Σ(p∗)>0 (p^*)>0, so the signal-to-noise ratio of the gradient update vanishes exactly where the cooperation decision is hardest—the structural origin of the Optimist’s Hangover. Definition 1 (Symmetric Coordination Game). A symmetric game G=(,R)G=(A,R) with R(ai,aj)=R(aj,ai)R(a_i,a_j)=R(a_j,a_i) is a coordination game if it has a payoff-dominant NE and a risk-dominant NE with strictly higher social welfare at the former. Coherent Risk Measures and EVaR. Let ℙP denote the reference probability measure over trajectories. A functional ρ:→ℝρ:X is a coherent risk measure (Artzner et al., 1999) if it is monotone, sub-additive, positively homogeneous, and translation invariant. The Conditional Value-at-Risk (Rockafellar and Uryasev, 2000) CVaRα(X)=[−X∣−X≥VaRα(X)]CVaR_α(X)=E[-X -X _α(X)] is coherent and widely used in risk-sensitive RL (Tamar et al., 2015; Chow et al., 2017), but its tail bound is loose. The Entropic Value-at-Risk (Ahmadi-Javid, 2012) is the tightest coherent risk measure under Cramér’s large-deviation bound: EVaRβ(X)≔infz>01zlog[e−zX]1−β=supℙ′≪ℙDKL(ℙ′∥ℙ)≤log11−βℙ′[−X]EVaR_β(X) _z>0 \ 1z E[e^-zX]1-β \= _ subarraycP \\ D_KL(P \|P)≤ 11-β subarrayE_P [-X] (2) EVaR dominates CVaR: [−X]≤CVaRα≤EVaRβ≤esssup(−X)E[-X] _α _β \,sup(-X). As β→0β→ 0, EVaRβ→[−X]EVaR_β [-X] (risk-neutral); as β→1β→ 1, EVaRβ→esssup(−X)EVaR_β \,sup(-X) (maximin). Under the Gaussian approximation of the K-step return, EVaRβ(−X)≈−[X]+βVar(X)1/2EVaR_β(-X)≈-E[X]+β\,Var(X)^1/2, so the robust value of a return X (positive=good) is: RVβ(X):=−EVaRβ(−X)≈[X]−βVar(X)1/2.RV_β(X)\;:=\;-EVaR_β(-X)\;≈\;E[X]-β\,Var(X)^1/2. (3) Welfare and the Cooperation Window. The maximin strategy πm=argmaxpminqui(p,q) _m= *arg\,max_p _qu_i(p,q) satisfies πm=0 _m=0 for the Stag Hunt (Hare guarantees rhr_h regardless of partner), giving paranoia floor Wmm=SW(πm,πm)=2rhW_m=SW( _m, _m)=2r_h. The social optimum is W∗=SW(1,1)=2rcW^*=SW(1,1)=2r_c. The cooperation efficiency η(π)=(SW(π)−Wmm)/(W∗−Wmm)∈[0,1]η(π)=(SW(π)-W_m)/(W^*-W_m)∈[0,1] measures what fraction of the welfare surplus above paranoid play an algorithm captures. The Price of Anarchy PoA(G)=W∗/SW(NEworst)=rc/rhPoA(G)=W^*/SW(NE^worst)=r_c/r_h bounds achievable welfare from below at Nash. The Cooperation Window CW(G,ε)=W∗−Wmm(ε)CW(G, )=W^*-W_m( ) is the welfare surplus any algorithm can capture above paranoid play under non-stationarity ε . 4 Problem Formulation We now consolidate the above into the precise mathematical problem that RATTL is designed to solve. Every object introduced in §3 appears below in its operational role. 4.1 Game Environment and the Cooperation Retention Problem We study a two-agent Markov game ℳM (Assumption 1) instantiated as a repeated Stag Hunt (Skyrms, 2004). We consider abstract payoffs rc>rh>rsr_c>r_h>r_s with spread Δ=rc−rs =r_c-r_s: R(ai,aj)=rcai=aj=Srsai=S,aj=Hrhai=HR(a_i,a_j)= casesr_c&a_i=a_j=S\\ r_s&a_i=S,\,a_j=H\\ r_h&a_i=H cases (4) Let p=ℙ(ai=S)p=P(a_i=S), q=ℙ(aj=S)q=P(a_j=S). Social welfare: SW(p,q)=2pqrc+(p+q−2pq)rs+(2−p−q)rhSW(p,q)=2pqr_c+(p+q-2pq)r_s+(2-p-q)r_h. Both agents update policies via gradient ascent on their individual objectives Ji(θi;πj)J_i( _i; _j). Agent i’s observation at each episode t consists solely of the joint action pair (ai(t),aj(t))∈×(a_i^(t),a_j^(t)) ×A and its own reward Ri(ai(t),aj(t))R_i(a_i^(t),a_j^(t)). Agent i has no access to: the partner’s policy parameters θj _j; the partner’s reward RjR_j; the partner’s learning rule; or the non-stationarity radius ε . Agent j operates under non-stationarity (Assumption 2) with radius ε≥0 ≥ 0. Agent i maintains an online estimate of the partner’s cooperation probability: p^(t+1)=(1−α)p^(t)+α 1[aj(t)=S] p(t+1)=(1-α) p(t)+α\,1\! [a_j^(t)=S ] (5) with EMA coefficient α∈(0,1)α∈(0,1). The Bernoulli variance of this estimate is σp^2(t)=p^(t)(1−p^(t))σ^2_ p(t)= p(t)(1- p(t)), which serves as a scalar proxy for the partner’s current unpredictability. Assumption 2 (ε -Non-Stationarity). At each episode t, partner j’s policy is drawn from a Wasserstein ball ℬε(πjnom)=π:W1(π,πjnom)≤εB_ ( _j^nom)=\π:W_1(π, _j^nom)≤ \.111The order-1 Wasserstein distance between distributions μ,νμ,ν over a metric space (X,d)(X,d) is W1(μ,ν)=infγ∈Γ(μ,ν)(x,y)∼γ[d(x,y)]W_1(μ,ν)= _γ∈ (μ,ν)E_(x,y) γ[d(x,y)]. For policies over a finite action space, W1W_1 reduces to total variation up to a constant. The agent observes partner actions but not the drawn policy. Definition 2 (Cooperation Retention). Agent i retains cooperation over horizon T if p(t)≥p∗p(t)≥ p^* for all t∈[t0,t0+T]t∈[t_0,t_0+T]. Retention fails at episode τ>t0τ>t_0 if p(τ)<p∗p(τ)<p^*; by the collapse dynamics of Proposition 3, this is irreversible under risk-neutral gradient learning. Problem (Robust Cooperation Retention). Given a repeated Stag Hunt G=(S,H,R)G=(\S,H\,R) with payoffs rc>rh>rsr_c>r_h>r_s, partner non-stationarity radius ε≥0 ≥ 0, and learning horizon T, find a gradient update rule for agent i that: (1) expands the cooperation basin (Theorem 6); (2) guarantees retention with high probability under ε -non-stationarity (Theorem 9); (3) admits sample-complexity bounds polynomial in the effective action-space dimension (Theorem 8); and (4) operates without privileged information. 4.2 Why Adaptive Agents Lose Cooperation Proposition 1. A risk-neutral agent plays Stag iff partner belief q≥p∗q≥ p^*: p∗=(rh−rs)/(rc−rs)=(rh−rs)/Δp^*=(r_h-r_s)/(r_c-r_s)=(r_h-r_s)/ (6) Lemma 2 (Variance near Threshold). Under Bernoulli partner cooperation q: Var(RS∣q)=q(1−q)Δ2Var(R_S q)=q(1-q) ^2. At q=p∗q=p^*, the signal-to-noise ratio SNR=(p∗Δ−(rh−rs))2/(p∗(1−p∗)Δ2)SNR=(p^* -(r_h-r_s))^2/(p^*(1-p^*) ^2) vanishes, making the agent maximally sensitive to stochastic fluctuations exactly where the cooperation decision is made. Proposition 3 (Exponential Cooperation Collapse). A risk-neutral agent at q=p∗+ϵq=p^*+ε, ϵ>0ε>0 small, under partner exploration rate δ∈(0,1)δ∈(0,1) and policy-gradient learning rate ηlr>0 _lr>0, satisfies: p(t)≈p∗+ϵe−λδt,λ=ηlr(rh−rs)/Δp(t)≈ p^*+ε\,e^-λδ t, λ= _lr(r_h-r_s)\,/\, (7) Once p(t)<p∗p(t)<p^*, the agent irreversibly collapses to Hare. The collapse is irreversible because below p∗p^*, the gradient of the cooperation action is always negative under risk-neutral learning. Adaptation fails precisely because the agent adapts too quickly: it treats partner exploration as a signal about long-run partner intent rather than transient variance. 4.3 The EVaR Paradox: Why Standard Robustness Fails A natural approach to retention is to replace the expected-return objective with an EVaR objective maxθi−EVaRβ(−∑t≥0γtRi(ai(t),aj(t))) _ _i-EVaR_β(- _t≥ 0γ^tR_i(a_i^(t),a_j^(t))). Under the Gaussian approximation Eq. (3), this penalizes the Stag return variance and shifts the risk-adjusted threshold to the following. Proposition 4 (EVaR Paradox). Under the Gaussian approximation (3), replacing the expected Stag return with its robust value RVβ(RS∣q)≈QS(q)−βq(1−q)ΔRV_β(R_S q)≈ Q_S(q)-β q(1-q)\, increases the critical cooperation threshold for all β>0β>0: pβ∗(naive)=p∗+βp∗(1−p∗)/Δ>p∗.p^*_β^(naive)=p^*+β p^*(1-p^*)/ >p^*. (8) Proof. Substitute RVβ(RS∣q)=QS(q)−βq(1−q)ΔRV_β(R_S q)=Q_S(q)-β q(1-q)\, (from Eq. (3) with Var(RS∣q)=q(1−q)Δ2Var(R_S q)=q(1-q) ^2 by Lemma 2) into the indifference condition RVβ(RS∣q∗)=rhRV_β(R_S q^*)=r_h and linearize around p∗p^*. ∎ The cooperative basin (pβ(naive)∗,1](p^*_β^(naive),1] is strictly smaller than the risk-neutral basin (p∗,1](p^*,1]. Distributional robustness applied to rewards narrows the cooperation basin, accelerates Hangover collapse, and makes retention strictly harder for all β>0β>0. The paradox reveals that the domain of EVaR application determines the sign of its effect on cooperation. The correct domain is not the return distribution but the policy gradient update. 5 RATTL: Robust Adaptive Trust-Region Learning We propose RATTL, an algorithm that satisfies all four conditions of the Robust Cooperation Retention problem simultaneously via its trust factor. RATTL’s key insight is to apply EVaR to the partner-induced gradient variance Σ(q) (q) from Eq. (1), not to the return distribution. Formally, the EVaR-regularised gradient update replaces the raw advantage AiA_i with a trust-dampened advantage: A~i(ai;p^,β)=τ(σp^2,β)⋅Ai(ai,aj)ai=SAi(ai,aj)ai=H A_i(a^i;\, p,β)= casesτ(σ^2_ p,β)· A_i(a^i,a^j)&a^i=S\\ A_i(a^i,a^j)&a^i=H cases (9) where the trust factor τ:[0,14]×ℝ→ℝ>0τ:[0, 14]×R _>0 is: τ(σp^2,β)=(1+βσp^2)−1τ(σ^2_ p,β)=(1+β\,σ^2_ p)^-1 (10) Sign convention. Positive β>0β>0 dampens the Stag gradient (τ<1τ<1), filtering partner noise—this is the risk-sensitive regime targeted by our basin-expansion guarantees. Negative β<0β<0 amplifies the Stag gradient (τ>1τ>1), recovering risk-seeking optimism (cf. Zhang et al., 2025); β=0β=0 recovers vanilla policy gradient. The constraint 1+βσp^2>01+βσ^2_ p>0 (equivalently β>−4β>-4 since σp^2≤14σ^2_ p≤ 14) ensures τ remains positive. Dampening applies only to the Stag gradient—the uncertain, noisy direction—leaving the Hare gradient unmodified. Definition 3. Given online estimate p^(t) p(t) of partner cooperation probability with Bernoulli variance σp^2(t)=p^(t)(1−p^(t))σ^2_ p(t)= p(t)(1- p(t)), the adaptive trust factor at episode t is: τ(t)=(1+β(t)σp^2(t))−1∈(0,1]τ(t)= (1+β(t)\,σ^2_ p(t) )^-1∈(0,1] (11) Why Only Stag? The asymmetry in Eq. (9) is principled, not heuristic. The Hare return rhr_h is independent of partner action, so Var(RH∣ai=H)=0Var(R_H a^i=H)=0 and EVaR(RH)β=[RH]=rh_β(R_H)=E[R_H]=r_h for all β. The partner-induced gradient variance is zero for Hare actions; dampening it would introduce bias without variance-reduction justification. Risk-robustness trade-off. Higher β expands the cooperation basin (Theorem 6) but increases sample complexity. We formalize this as a two-term welfare loss: [Loss]≤CW(G,ε)(1−e−βε)⏟(i) equilibrium cost+c|j|eβ/T⏟(i) sample costE[Loss]≤ CW(G, ) (1-e^-β )_(i) equilibrium cost+ c\,|A_j|\,e^β/T_(i) sample cost (12) The optimal risk parameter β∗β^* minimizes Eq. (12) (closed form in Corollary 10). 5.1 Adaptive β(t)β(t): Online Risk Calibration A fixed β is suboptimal: during early training when the partner is erratic, higher β is appropriate; once cooperation stabilizes, lower β accelerates learning. We derive an online update rule from the PoPDYNPoP_DYN diagnostic. Definition 4 (PoPDYNPoP_DYN as Adaptivity Diagnostic). The dynamic Price of Paranoia at episode t is: PoPDYN(t)=SW(πt,q¯)SW(πm,q¯)∈[1,PoPGT]PoP_DYN(t)= SW( _t, q)SW( _m, q)∈[1,\,PoP_GT] (13) PoPDYN(t)=1PoP_DYN(t)=1: agent is fully paranoid (cooperation lost). PoPDYN(t)=PoPGTPoP_DYN(t)=PoP_GT: agent is fully cooperative. Algorithm 1 RATTL with Adaptive β(t)β(t) 1:Action a, reward r, partner action aja_j 2:Params: α, η, ηβ _β, β∗β^* (estimated), β¯,β¯ β, β with β¯14>−1 β\, 14>-1 and β¯<ε−1−1 β< ^-1-1 3:p^←(1−α)p^+α[aj=S] p←(1-α) p+ 1\! [a_j=S ] 4:σp^2←p^(1−p^)σ^2_ p← p(1- p) 5:SW^←2ri SW← 2\,r_i ⊳ Welfare proxy (symmetric game) 6:ΔPoP←SW^−SW^prev ← SW- SW_prev 7:if ΔPoP<0 <0 then ⊳ Cooperation deteriorating 8: β←min(β+ηβ|ΔPoP|,β¯)β← (β+ _β\, | |,\; β) 9:else⊳ Recovering toward β∗β^* 10: β←β−ηβ(β−β∗)+β←β- _β(β-β^*)_+ 11:end if 12:τ←(1+βσp^2)−1τ←(1+β\,σ^2_ p)^-1 13:b←mean(ℋ)b (H); A←(r−b)⋅τ[a=S]A←(r-b)·τ^1\! [a=S ] 14:θ←θ+ηA∇θlogπθ(a)θ←θ+η\,A\, _θ _θ(a) 15:SW^prev←SW SW_prev← SW 16:return θ,βθ,\,β 5.2 The Unified Price of Paranoia Framework Definition 5. PoPGTPoP_GT (Game-Theoretic): Structural welfare ceiling: PoPGT(G,ε)=SW(πrat(ε),q¯ε)/SW(πm,q¯ε)PoP_GT(G, )=SW( _rat( ), q_ )\,/\,SW( _m, q_ ). PoPALGPoP_ALG (Algorithmic): Sample-complexity overhead: PoPALG(,β)=Nrobust(β)/Nstandard≤(|j|eβ)PoP_ALG(A,β)=N_robust(β)\,/\,N_standard ( |A_j |e^β). PoPDYN(t)PoP_DYN(t) (Dynamic): Adaptive diagnostic (Def. 4). Separation: PoPGTPoP_GT is a property of the game, PoPALGPoP_ALG of the algorithm, and PoPDYNPoP_DYN of the learning trajectory. Theorem 5. Define the Cooperation Window: CW(G,ε)=W∗−Wmm(ε)=W∗(1−1/PoPGT(G,ε))CW(G, )=W^*-W_m( )=W^*(1-1/PoP_GT(G, )). Any algorithm achieves welfare W(π)∈[W∗/PoA,W∗]W(π)∈[W^*/PoA,\,W^*]. The dynamic diagnostic PoPDYN(t)PoP_DYN(t) is monotone in η(πt)η( _t), with PoPDYN(t)=1PoP_DYN(t)=1 iff η(πt)=0η( _t)=0 (full collapse to maximin) and PoPDYN(t)=PoPGTPoP_DYN(t)=PoP_GT iff η(πt)=1η( _t)=1 (full cooperative welfare). 6 Theoretical Guarantees 6.1 Adaptive Basin Expansion Theorem 6. For RATTL with adaptive β(t)β(t), payoff spread Δ=rc−rs =r_c-r_s, and risk-neutral threshold p∗=(rh−rs)/Δp^*=(r_h-r_s)/ , the effective cooperation threshold at episode t satisfies: pβ(t)∗=p∗−β(t)p∗(1−p∗)Δ+((β(t))2(p∗)2/Δ2)p^*_β(t)=p^*- β(t)\,p^*(1-p^*) +O((β(t))^2(p^*)^2/ ^2) (14) The expansion Δp∗=β(t)p∗(1−p∗)/Δ p^*=β(t)p^*(1-p^*)/ is maximised at p∗=12p^*= 12. Proof Sketch. The trust-dampened cooperation condition is b+τ(q)(QS(q)−b)≥rhb+τ(q)(Q_S(q)-b)≥ r_h. Taylor-expanding at q=p∗q=p^* with QS(p∗)=rhQ_S(p^*)=r_h, using QS′=ΔQ_S = and τ′(q)|p∗=−β(t)(1−2p∗)(1+β(t)σp^2)−2τ (q)|_p^*=-β(t)(1-2p^*)(1+β(t)σ^2_ p)^-2, the first-order perturbation gives δq=−β(t)p∗(1−p∗)/Δδ q=-β(t)p^*(1-p^*)/ . ∎ Corollary 7. When the adaptive update rule (Algorithm 1) detects ΔPoP<0 <0 and increases β(t)β(t) by ηβ|ΔPoP| _β | |, the cooperation basin expands by δ(Δp∗)=ηβ|ΔPoP|p∗(1−p∗)/Δ>0δ( p^*)= _β | |p^*(1-p^*)/ >0. 6.2 Robustness Guarantees Theorem 8 (PAC Sample Complexity). Under Assumptions 1–2, for any accuracy ϵPAC>0 _PAC>0 and confidence δ∈(0,1)δ∈(0,1), RATTL returns an ϵPAC _PAC-optimal robust policy with probability at least 1−δ1-δ using at most NRATTL=~(||2||H4ϵPAC2⋅|j|eβ⋅log1δ)N_RATTL= O\!\! ( |S |^2 |A |H^4 _PAC^2· |A_j |e^β· 1δ ) (15) episodes (the accuracy parameter ϵPAC _PAC is distinct from the non-stationarity radius ε of Assumption 2). The robustness overhead is PoPALG≤(|j|eβ)PoP_ALG ( |A_j |e^β)—polynomial in |j| |A_j |, not exponential in the full state-action space. Theorem 9 (Welfare Loss Decomposition). Expected per-episode welfare loss decomposes into two adaptive-robustness trade-off terms: [Loss]≤CW(G,ε)(1−e−βε)⏟(i) adaptation cost+c|j|eβ/T⏟(i) robustness overheadE[Loss]≤ CW(G, )(1-e^-β )_(i) adaptation cost+ c\, |A_j |e^β/T_(i) robustness overhead (16) Corollary 10. The optimal fixed risk parameter is: β∗=11+εlog(CW(G,ε)⋅ε⋅Tceff)β^*= 11+ \! ( CW(G, )· · Tc_eff ) (17) where ceff=c|j|c_eff=c |A_j | calibrated empirically. 7 Experiments We first demonstrate that our theoretical framework generalizes across coordination games via predicted threshold analysis (§7.1), and then validate RATTL empirically on the Iterated Stag Hunt (§7.2). 7.1 Theoretical Generalisation Across Games While our empirical evaluation focuses on the Stag Hunt, Theorem 6 applies to any symmetric coordination game satisfying Definition 1. Table 1 instantiates the basin-expansion prediction pβ∗=p∗−βp∗(1−p∗)/Δp^*_β=p^*-β p^*(1-p^*)/ for three canonical games at β=1.0β=1.0. Table 1: Predicted basin expansion across coordination games. p∗p^*: risk-neutral threshold; pβ=1∗p^*_β=1: RATTL threshold (Theorem 6). Expansion denotes the percentage increase in the cooperation basin [p∗,1][p^*,1]. Game (rc,rh,rs)(r_c,r_h,r_s) p∗p^* pβ=1∗p^*_β=1 Expansion Stag Hunt (5,2,−5)(5,2,-5) 0.70 0.58 +17% Chicken (4,2,−1)(4,2,-1) 0.60 0.45 +25% Pure Coord. (3,1,0)(3,1,0) 0.33 0.26 +21% The Chicken game has a smaller payoff spread Δ=5 =5 vs. Δ=10 =10 for the Stag Hunt, making the basin more sensitive to trust-factor dampening. The pure coordination game (rs=0r_s=0) has the lowest threshold and hence the widest initial basin; RATTL still provides a meaningful expansion. Baseline positioning. Our empirical evaluation uses vanilla PPO as the risk-neutral baseline. Hysteretic Q-learning (Matignon et al., 2007) and lenient learning (Palmer et al., 2018) filter negative updates to aid cooperation discovery, but they offer no principled mechanism for cooperation retention—the regime RATTL targets. LOLA (Foerster et al., 2018) addresses co-learning noise via second-order gradient corrections but requires differentiable access to the partner’s learning rule. RATTL’s (1)O(1) scalar trust factor achieves retention guarantees (Theorem 6) under strictly weaker information assumptions. 7.2 Iterated Stag Hunt We train RATTL-PPO in the Iterated Stag Hunt against a stochastic opponent whose mixed strategy is sampled from a standard normal distribution and projected onto the simplex at each timestep. Training runs for 3000 episodes under two configurations: β=−1.0β=-1.0 (risk-averse, amplifies gradient signals) and β=1.0β=1.0 (risk-seeking, dampens noisy gradients via the trust factor). We compare against vanilla PPO (Schulman et al., 2017). (a) Cooperation rate (no reward noise) (b) Outcome space (no reward noise) (c) Cooperation rate (with reward noise) (d) Outcome space (with reward noise) Figure 1: RATTL-PPO in the Iterated Stag Hunt. Top row: no reward noise. Bottom row: standard-normal reward perturbations. Risk-seeking RATTL (β=1.0β=1.0) converges to stable cooperation near the NBS in both conditions; risk-averse (β=−1.0β=-1.0) defaults to Hare; vanilla PPO oscillates. Policies are projected against the Nash Bargaining Solution (NBS), risk-dominant NE, and mixed-strategy NE. As shown in Figure 1(a), risk-seeking RATTL-PPO (β=1.0β=1.0) establishes and maintains stable cooperation, while the risk-averse variant (β=−1.0β=-1.0) converges to Hare, and vanilla PPO settles on a volatile mixed strategy (≈63%≈63\% Stag). Figure 1(b) projects policies into the outcome space against the Nash Bargaining Solution (NBS)—the unique Pareto-optimal point maximizing surplus gains over the disagreement point (Harsanyi and Selten, 1988). Risk-seeking RATTL reliably isolates the cooperative equilibrium near the NBS. The bottom row of Figure 1 confirms that all configurations are robust to standard normal reward perturbations. Table 2 reports PoP and PoA under both conditions: risk-seeking RATTL (β=1.0β=1.0) dominates both metrics regardless of reward noise. Figure 2 (Appendix A) further sweeps five risk profiles across stationary, mild (20%20\%), and high (40%40\%) partner noise: risk-aversion (β∈1,2β\!∈\!\1,2\) collapses sharply under high non-stationarity (final cooperation drops to ∼0.5 0.5), while risk-seeking and risk-neutral retain >0.9>0.9. The Pareto frontier (cooperation vs. stability) confirms that risk-seeking dominates under heavy noise—directly evidencing the EVaR Paradox (Proposition 4). Table 2: PoP and PoA in the Iterated Stag Hunt, with and without reward noise. Risk-seeking RATTL (β=1.0β=1.0) dominates in both conditions. No noise Reward noise Algorithm PoP↑ PoA↓ PoP↑ PoA↓ RATTL (β=−1β=-1) 1.27 4.23 1.34 3.96 RATTL (β=1β=1) 2.88 1.85 2.93 1.82 PPO 2.51 2.13 2.49 2.14 8 Conclusion We address the collapse of cooperation in non-stationary MARL driven by co-learning partner stochasticity. The EVaR Paradox (Proposition 4) shows that standard distributional robustness applied to returns widens the basin of instability; resolving this requires targeting gradient variance instead. This yields RATTL, whose adaptive trust factor τ(t)τ(t) provably expands the cooperation basin and is unified under the Price of Paranoia framework. Empirically, risk-seeking RATTL achieves near-100% cooperation retention where standard baselines collapse. Our framework demonstrates that stable cooperation requires neither opponent modelling nor prosocial priors—only calibrated uncertainty. Future directions include adaptive β(t)β(t) meta-learning, scalable deep RL implementations, and human-AI cooperation studies. Acknowledgments This work has been supported by the German Research Foundation (DFG) through Research Training Group GRK 2428 ConVeY. References D. Acemoglu and A. Wolitzky (2015) Sustaining cooperation: community enforcement vs. specialized enforcement. Working Paper Technical Report 21457, Working Paper Series, National Bureau of Economic Research. External Links: Document, Link Cited by: §1, §2. A. Ahmadi-Javid (2012) Entropic value-at-risk: a new coherent risk measure. Journal of Optimization Theory and Applications 155 (3), p. 1105–1123. Cited by: §1, §3. S. V. Albrecht and P. Stone (2018) Autonomous agents modelling other agents: a comprehensive survey and open problems. Artificial Intelligence 258, p. 66–95. Cited by: §1, §2. L. Andreozzi, M. Ploner, and A. S. Saral (2020) The stability of conditional cooperation: beliefs alone cannot explain the decline of cooperation in social dilemmas. Scientific reports 10 (1), p. 13610. Cited by: §1. P. Artzner, F. Delbaen, J. Eber, and D. Heath (1999) Coherent measures of risk. Mathematical finance 9 (3), p. 203–228. Cited by: §3. B. Awerbuch, Y. Azar, A. Richman, and B. Tsur (2005) Tradeoffs in worst-case equilibria. In Proceedings of APPROX/RANDOM, Cited by: §2. A. Blum and Y. Mansour (2008) From external to internal regret. Journal of Machine Learning Research 8, p. 1307–1324. Cited by: §1, §2. M. Bowling and M. Veloso (2002) Multiagent learning using a variable learning rate. Artificial Intelligence 136 (2), p. 215–250. Cited by: §1. R. Boyd and P. J. Richerson (2009) Culture and the evolution of human cooperation. Philosophical Transactions of the Royal Society B: Biological Sciences 364 (1533), p. 3281–3288. Cited by: §1. Y. Chow, M. Ghavamzadeh, L. Janson, and M. Pavone (2017) Risk-constrained reinforcement learning with percentile risk criteria. Journal of Machine Learning Research 18 (1), p. 167–208. Cited by: §2, §3. C. Claus and C. Boutilier (1998) The dynamics of reinforcement learning in cooperative multiagent systems. In Proceedings of the AAAI Conference on Artificial Intelligence, p. 746–752. Cited by: §2. P. Dal Bó and G. R. Fréchette (2011) The evolution of cooperation in infinitely repeated games: experimental evidence. American Economic Review 101 (1), p. 411–29. External Links: Document, Link Cited by: §1. E. Fehr and S. Gächter (2000a) Cooperation and punishment in public goods experiments. American Economic Review 90 (4), p. 980–994. External Links: Document, Link Cited by: §1, §2. E. Fehr and S. Gächter (2000b) Cooperation and punishment in public goods experiments. American Economic Review 90 (4), p. 980–994. Cited by: §2. E. Fehr and H. Gintis (2007) Human motivation and social cooperation: experimental and analytical foundations. Annu. Rev. Sociol. 33 (1), p. 43–64. Cited by: §1. T. H. Ferrarini (2013) The economics of government and the fall of rome. Social Education 77 (2), p. 60–63. Cited by: §1. J. Foerster, R. Y. Chen, M. Al-Shedivat, S. Whiteson, and P. Abbeel (2018) Learning with opponent-learning awareness. In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), p. 122–130. Cited by: §2, §7.1. P. J. Gmytrasiewicz and P. Doshi (2005) A framework for sequential planning in multi-agent settings. Journal of Artificial Intelligence Research 24, p. 49–79. Cited by: §1, §2. I. Greenberg, Y. Chow, M. Ghavamzadeh, and S. Mannor (2022) Efficient risk-averse reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. M. Griessmair and P. Hippmann (2022) Anger, guilt, and repeated cooperation in social dilemmas.. Emotion 22 (3), p. 444. Cited by: §1, §2. C. Handley and S. Mathew (2020) Human large-scale cooperation as a product of competition between cultural groups. Nature communications 11 (1), p. 702. Cited by: §1. J. C. Harsanyi and R. Selten (1988) A general theory of equilibrium selection in games. MIT Press. Cited by: §2, §3, §7.2. E. Hughes, J. Z. Leibo, M. G. Phillips, K. Tuyls, E. A. Duéñez-Guzmán, A. G. Castañeda, I. Dunning, T. Zhu, K. R. McKee, R. Koster, H. Roff, and T. Graepel (2018) Inequity aversion improves cooperation in intertemporal social dilemmas. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. G. N. Iyengar (2005) Robust dynamic programming. Mathematics of Operations Research 30 (2), p. 257–280. Cited by: §1, §2. M. Lu, H. Zhong, T. Zhang, and J. Blanchet (2024) Distributionally robust reinforcement learning with interactive data collection: fundamental hardness and near-optimal algorithm. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1, §2. L. Matignon, G. J. Laurent, and N. L. Fort-Piat (2007) Hysteretic Q-learning: an algorithm for decentralised reinforcement learning in cooperative multi-agent teams. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 64–69. Cited by: §1, §2, §7.1. K. R. McKee, I. Gemp, B. McWilliams, E. A. Duéñez-Guzmán, E. Hughes, and J. Z. Leibo (2020) Social diversity and social preferences in mixed-motive reinforcement learning. In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), Cited by: §2. A. Nilim and L. E. Ghaoui (2005) Robust control of Markov decision processes with uncertain transition matrices. Operations Research 53 (5), p. 780–798. Cited by: §1, §2. S. Omidshafiei, D. Kim, M. Liu, G. Tesauro, M. Riemer, C. Amato, M. Campbell, and J. P. How (2019) Learning to teach in cooperative multiagent reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, Cited by: §2. S. Omidshafiei, J. Pazis, C. Amato, J. P. How, and J. Vian (2017) Deep decentralised multi-task multi-agent reinforcement learning under partial observability. In Proceedings of the International Conference on Machine Learning (ICML), Cited by: §2. G. Palmer, K. Tuyls, D. Bloembergen, and R. Savani (2018) Lenient multi-agent deep reinforcement learning. arXiv preprint arXiv:1707.04402. Cited by: §1, §2, §7.1. K. Panaganti and D. Kalathil (2022) Sample complexity of robust reinforcement learning with a generative model. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), p. 9582–9602. Cited by: §2. C. H. Papadimitriou and T. Roughgarden (2005) Computing correlated equilibria in multi-player games. In Proceedings of the ACM Symposium on Theory of Computing (STOC), Cited by: §1, §2. A. Peysakhovich and A. Lerer (2017) Prosocial learning agents solve generalised stag hunts better than selfish ones. arXiv preprint arXiv:1709.02865. Cited by: §1, §2. R. Raileanu, E. Denton, A. Szlam, and R. Fergus (2018) Modeling others using oneself in multi-agent reinforcement learning. In Proceedings of the International Conference on Machine Learning (ICML), Cited by: §1, §2. R. T. Rockafellar and S. Uryasev (2000) Optimization of conditional value-at-risk. Journal of Risk 2 (3), p. 21–41. Cited by: §3. T. Roughgarden (2015) Intrinsic robustness of the price of anarchy. Journal of the ACM 62 (5), p. 32:1–32:42. Cited by: §1, §2. J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov (2017) Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. Cited by: §3, §7.2. E. Semsar-Kazerooni and K. Khorasani (2009) Multi-agent team cooperation: a game theory approach. Automatica 45 (10), p. 2205–2213. Cited by: §1. L. Shi, E. Mazumdar, Y. Chi, and A. Wierman (2024) Sample-efficient robust multi-agent reinforcement learning in the face of environmental uncertainty. arXiv preprint arXiv:2404.18909. Cited by: §1, §2. B. Skyrms (2004) The stag hunt and the evolution of social structure. Cambridge University Press. Cited by: §1, §2, §3, §4.1. A. Tamar, Y. Glassner, and S. Mannor (2015) Optimizing the CVaR via sampling. In Proceedings of the AAAI Conference on Artificial Intelligence, Cited by: §2, §3. W. Z. Wang, M. Beliaev, E. Biyik, D. A. Lazar, R. Pedarsani, and D. Sadigh (2021) Emergent prosociality in multi-agent games through gifting. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21), Cited by: §2. L. Wardil, I. R. Silva, and J. K. da Silva (2019) Positive interactions may decrease cooperation in social dilemma experiments. Scientific Reports 9 (1), p. 1017. Cited by: §1. R. J. Williams (1992) Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning 8 (3), p. 229–256. Cited by: §3. Z. Xu, H. van Hasselt, and D. Silver (2018) Meta-gradient reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. K. Zhang, T. Sun, Y. Tao, S. Genc, S. Mallya, and T. Başar (2020) Robust multi-agent reinforcement learning with model uncertainty. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1, §2. R. Zhang, N. Li, A. Ozdaglar, J. Shamma, and G. Zardini (2025) Optimism as risk-seeking in multi-agent reinforcement learning. arXiv preprint arXiv:2509.24047. Note: Accepted to IEEE L-CSS / ACC 2026 Cited by: §1, §1, §2, §5. Appendix A Extended Experimental Results Figure 2: Risk-criteria performance across stationary and non-stationary partner dynamics. Left column: cooperation probability P(Stag)P(Stag) over 200 episodes for five risk profiles (Risk-Free, Risk-Neutral, Risk-Averse β∈1,2β\!∈\!\1,2\, Risk-Seeking β=−1β\!=\!-1) under partner noise ∈0%,20%,40%∈\0\%,20\%,40\%\. Top-right: final cooperation by criterion and environment; risk-aversion collapses sharply under high non-stationarity, while risk-seeking and risk-neutral retain >0.9>0.9. Middle-right: reward standard deviation. Bottom-right: Pareto frontier of cooperation vs. stability; risk-seeking dominates the upper-left under heavy noise. Empirically validates the EVaR Paradox (Proposition 4). We next inject standard normal noise (σ∈0.5,1.0σ∈\0.5,1.0\) directly into the opponent’s mixed strategy, testing resilience to behavioral stochasticity beyond reward perturbations. All configurations show resilience to partner noise, though the nature of that resilience differs sharply across objectives. Risk-seeking RATTL. As shown in Figure 4, RATTL-PPO (β=1.0β=1.0) maintains cooperation (Stag rate >92%>92\%) despite heavy partner noise (Table 3: PoP peaks at 2.88, PoA drops to 1.85 at σ=1.0σ=1.0). The trust factor absorbs partner stochasticity, keeping the policy anchored near the NBS. Risk-averse RATTL and PPO. Risk-averse RATTL (β=−1.0β=-1.0, Figure 3) collapses to Hare (Stag rate ≈0.10≈0.10) across all noise levels (Table 3). Vanilla PPO (Figure 5, same table) converges to a volatile mixed strategy (≈75%≈75\% Stag) but fails to commit to full cooperation. (a) Attempt at coordination (b) Mixed Strategy Nash Equilibria Figure 3: Evaluation of RATTL-PPO (β=−1.0β=-1.0) against a stochastic opponent in the Iterated Stag Hunt where partner strategy is perturbed by standard-normal noise. (a) Attempt at coordination (b) Mixed Strategy Nash Equilibria Figure 4: Evaluation of RATTL-PPO (β=1.0β=1.0) against a stochastic opponent in the Iterated Stag Hunt where partner strategy is perturbed by standard-normal noise. (a) Attempt at coordination (b) Mixed Strategy Nash Equilibria Figure 5: Evaluation of vanilla PPO against a stochastic opponent in the Iterated Stag Hunt where partner strategy is perturbed by standard-normal noise. Table 3: Empirical PoP and PoA across noise σ added to the opponent’s mixed strategy, for RATTL-PPO (β=−1β=-1), RATTL-PPO (β=1β=1), and vanilla PPO. RATTL (β=−1β=-1) RATTL (β=1β=1) PPO σ PoP↑ PoA↓ PoP↑ PoA↓ PoP↑ PoA↓ 0.5 1.16 4.59 2.86 1.86 2.53 2.11 1.0 1.27 4.23 2.88 1.85 2.51 2.13