Paper deep dive
Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximation
Jake Gonzales, Max Horwitz, Eric Mazumdar, Lillian J. Ratliff
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/13/2026, 12:07:34 AM
Summary
The paper introduces RQRE-OVI, an optimistic value iteration algorithm for computing Risk-Sensitive Quantal Response Equilibrium (RQRE) in multi-agent reinforcement learning with linear function approximation. It addresses the computational intractability and instability of Nash equilibria by incorporating bounded rationality and risk sensitivity, providing finite-sample regret guarantees, Lipschitz stability, and improved robustness in cross-play scenarios.
Entities (5)
Relation Signals (3)
RQRE-OVI → computes → Risk-Sensitive Quantal Response Equilibrium
confidence 100% · We propose RQRE-OVI, an optimistic value iteration algorithm for computing RQRE
RQRE-OVI → uses → Linear Function Approximation
confidence 100% · optimistic value iteration algorithm for computing RQRE with linear function approximation
Risk-Sensitive Quantal Response Equilibrium → improvesrobustnessover → Nash Equilibrium
confidence 95% · RQRE-OVI achieves competitive performance under self-play while producing substantially more robust behavior under cross-play compared to Nash-based approaches.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Provably efficient and robust equilibrium computation in general-sum Markov games remains a core challenge in multi-agent reinforcement learning. Nash equilibrium is computationally intractable in general and brittle due to equilibrium multiplicity and sensitivity to approximation error. We study Risk-Sensitive Quantal Response Equilibrium (RQRE), which yields a unique, smooth solution under bounded rationality and risk sensitivity. We propose \texttt{RQRE-OVI}, an optimistic value iteration algorithm for computing RQRE with linear function approximation in large or continuous state spaces. Through finite-sample regret analysis, we establish convergence and explicitly characterize how sample complexity scales with rationality and risk-sensitivity parameters. The regret bounds reveal a quantitative tradeoff: increasing rationality tightens regret, while risk sensitivity induces regularization that enhances stability and robustness. This exposes a Pareto frontier between expected performance and robustness, with Nash recovered in the limit of perfect rationality and risk neutrality. We further show that the RQRE policy map is Lipschitz continuous in estimated payoffs, unlike Nash, and RQRE admits a distributionally robust optimization interpretation. Empirically, we demonstrate that \texttt{RQRE-OVI} achieves competitive performance under self-play while producing substantially more robust behavior under cross-play compared to Nash-based approaches. These results suggest \texttt{RQRE-OVI} offers a principled, scalable, and tunable path for equilibrium learning with improved robustness and generalization.
Tags
Links
- Source: https://arxiv.org/abs/2603.09208v1
- Canonical: https://arxiv.org/abs/2603.09208v1
Trouble viewing inline? Open PDF directly →
Full Text
194,958 characters extracted from source content.
Expand or collapse full text
Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximation Jake Gonzales1 Max Horwitz1 Eric Mazumdar2 Lillian J. Ratliff1 Abstract Provably efficient and robust equilibrium computation in general-sum Markov games remains a core challenge in multi-agent reinforcement learning. Nash equilibrium is computationally intractable in general and brittle due to equilibrium multiplicity and sensitivity to approximation error. We study Risk-Sensitive Quantal Response Equilibrium (RQRE), which yields a unique, smooth solution under bounded rationality and risk sensitivity. We propose RQRE-OVI, an optimistic value iteration algorithm for computing RQRE with linear function approximation in large or continuous state spaces. Through finite-sample regret analysis, we establish convergence and explicitly characterize how sample complexity scales with rationality and risk-sensitivity parameters. The regret bounds reveal a quantitative tradeoff: increasing rationality tightens regret, while risk sensitivity induces regularization that enhances stability and robustness. This exposes a Pareto frontier between expected performance and robustness, with Nash recovered in the limit of perfect rationality and risk neutrality. We further show that the RQRE policy map is Lipschitz continuous in estimated payoffs, unlike Nash, and RQRE admits a distributionally robust optimization interpretation. Empirically, we demonstrate that RQRE-OVI achieves competitive performance under self-play while producing substantially more robust behavior under cross-play compared to Nash-based approaches. These results suggest RQRE-OVI offers a principled, scalable, and tunable path for equilibrium learning with improved robustness and generalization. 1Department of Electrical & Computer Engineering, University of Washington 2Computing & Mathematical Sciences, California Institute of Technology ∗Corresponding author: jakegonz@uw.edu 1 Introduction Modeling multiple strategic decision-makers in dynamic, real-world environments remains a central challenge in artificial intelligence. Multi-agent reinforcement learning provides a principled framework for such settings, where agents learn policies by interacting with the environment and adapting to the behavior of others (Zhang et al., 2021). This has enabled advances in domains ranging from autonomous driving (Cusumano-Towner et al., 2025), high-frequency trading (Mohl et al., 2025), multi-robot control (Gu et al., 2023), and alignment of large language models (Munos et al., 2024). Despite these empirical successes, developing principled algorithms with rigorous theoretical guarantees for multi-agent reinforcement learning remains an open challenge, particularly in settings with continuous or large state spaces, where equilibrium selection and brittleness lead to poor generalization and robustness. Towards addressing scalability, Cisneros-Velarde and Koyejo (2023) proposed Nash Q-learning with Optimistic Value Iteration (NQOVI), extending the frameworks of Hu and Wellman (2003) and Liu et al. (2021) to the linear function approximation regime and providing finite-sample regret bounds that scale with feature dimension rather than the size of the state space. While this represents significant progress, a fundamental bottleneck persists: the algorithm requires solving for a Nash equilibrium at every stage game and every episode. This not only inherits the computational intractability of Nash equilibria in general-sum games but also exposes the learning process to the inherent instability of the Nash correspondence (as we demonstrate in Example 3), where arbitrarily small perturbations in estimated payoffs can produce discontinuous jumps in the selected equilibrium strategy. In the function approximation setting, where Q-values are necessarily estimated with error, this brittleness is especially problematic: it means that the equilibrium computation at the core of the algorithm is ill-conditioned with respect to the approximation errors that the algorithm itself introduces. These limitations motivate equilibrium concepts that are simultaneously computationally tractable, stable under payoff perturbations, and amenable to scalable reinforcement learning with formal guarantees. This leads to our central research question: Can we achieve provably sample-efficient learning of computationally tractable and robust equilibria in general-sum Markov games with linear function approximation? To address this question, we study the Risk-Sensitive Quantal Response Equilibrium (RQRE), a solution concept introduced in Mazumdar et al. (2025) which models agents as both boundedly rational and risk-averse. The RQRE combines two behavioral modeling choices, each of which independently contributes desirable properties for multi-agent learning while also capturing behaviors inherent to natural learning agents (as opposed to algorithmic ones). Indeed, bounded rationality replaces exact best responses with smooth, regularized response mappings, yielding well-posed and often unique equilibria while mitigating discontinuities and equilibrium multiplicity (McKelvey and Palfrey, 1995; Erev and Roth, 1998; Goeree and Holt, 1999). In multi-agent reinforcement learning, this framework improves stability under approximation error and non-stationarity, providing a principled tradeoff between optimality and robustness that aligns naturally with regularized learning objectives. At the same time, incorporating risk sensitivity addresses key limitations of purely expected-value objectives by discouraging policies that achieve high average performance at the expense of rare but catastrophic outcomes. In multi-agent settings, risk-sensitive formulations act as a principled form of robustification—reducing sensitivity to modeling error, noise, and opponent misspecification (Mazumdar et al., 2025; Lanzetti et al., 2025)—thereby promoting more stable, predictable, and generalizable equilibria. Contributions. The main contributions of this work are summarized as follows: • Finite-sample guarantees. We perform regret analysis for a novel algorithm, RQRE-OVI, and establish that regret satisfies reg(K)≤~(LBKd3H3)+KH(ε+L(ε+ε))reg(K)≤ O (L_ env\,B\, K\,d^3\,H^3 )+KH ( _ env+L_ env( _ pol+ _ eq) ), where ε,ε,ε _ env, _ pol, _ eq capture environment-risk, policy-risk, and stage-equilibrium approximation errors. The bound explicitly characterizes how sample complexity scales with the rationality and risk-sensitivity parameters: the value range B=H(1+log|A|/ϵ)B=H(1+ |A|/ε) depends on the rationality parameter ϵε, while the solver error scales as ε=O(BΔ/τmin) _ eq=O(B _ eq/ _ ), so that greater risk aversion relaxes solver accuracy requirements. Our analysis provides the first regret guarantees for optimistic MARL with linear function approximation with risk-sensitivity and approximate equilibrium computation, rather than relying on a Nash equilibrium oracle. • Distributional robustness. We show that the RQRE are distributionally robust (Proposition 1), and generalize other robust notions of equilibrium. This connects the bounded rationality parameter to a formal notion of robustness against payoff misspecification. • Stability. We prove that the RQRE policy map is Lipschitz continuous in estimated payoffs (Corollary 2), a stability property that Nash equilibria provably lack (Example 3). This theoretically justifies the use of RQRE over Nash. Moreover, it allows us to conclude policy convergence under additional regularity (Proposition 3). • Empirical evaluation. We evaluate RQRE-OVI on popular multi-agent coordination benchmarks and demonstrate that it achieves competitive self-play performance while producing substantially more robust behavior under cross-play compared to Nash-based methods. An extended related work discussion is given in Appendix A. 2 Preliminaries In this section, we present the game-theoretic and multi-agent reinforcement learning preliminaries. We consider the framework of Markov games (also known as stochastic games), which generalizes the standard Markov decision process (MDP) to the multi-player setting (Shapley, 1953; Littman, 1994; Neyman et al., 2003). We define an episodic Markov game of the form ℳ=(,,H,,r)MG=(X,A,H,P,r) with state space X, joint action space =1×⋯×nA=A_1×·s×A_n, episode length H, and transition kernels =hh∈[H]P=\P_h\_h∈[H], where h(⋅∣x,a)P_h(· x,a) denotes the transition kernel at step h. Agent i’s reward is ri=ri,hh=1Hr_i=\r_i,h\_h=1^H with ri,h:×→[0,1]r_i,h:X×A→[0,1]. At step h, agent i selects action ai,h∈ia_i,h _i, and we write ah=(a1,h,…,an,h)∈a_h=(a_1,h,…,a_n,h) for the joint action. The agents’ action spaces are assumed finite; however, the state space can be arbitrarily large or continuous. We denote agent i’s policy by πi=πi,hh∈[H] _i=\ _i,h\_h∈[H] with πi,h:→Δ(i) _i,h:X→ (A_i), and by an abuse of notation write πh:→Δ() _h:X→ (A) for the joint policy. For agent i, define the value function V~hi(⋅;π):→ℝ V_h^i(·;π):X at step h as V~hi(x;π):=π[∑h′=hHri,h′(xh′,ah′)|xh=x] V_h^i(x;π):=E_π[ _h =h^Hr_i,h (x_h ,a_h )\, |\,x_h=x]. The most common solution concept for games is the Nash equilibrium (Nash, 1950). Definition 1 (Markov Nash Equilibrium). A joint policy π∗=(π1∗,…,πn∗)π^*=( _1^*,…, _n^*) is a Nash equilibrium if no player can improve their value by unilaterally deviating. That is, for all i∈[n]i∈[n], all alternative policies πi′ _i , and all initial states s0∈s_0 , the inequality V~1i(s0;π∗)≥V~1i(s0;π′) V_1^i(s_0;π^*)≥ V_1^i(s_0;π ) holds, where π′=(πi′,π−i∗)π =( _i , _-i^*) denotes the joint policy in which player i deviates to πi′ _i while all others play π−i∗ _-i^*. If V~1i(s0;π∗)≤ε+V~1i(s0;(πi,π−i∗)) V_1^i(s_0;π )≤ + V_1^i(s_0;( _i, _-i )) for all i and s0s_0, then π∗π is an ε -approximate Nash equilibrium. 2.1 Bounded Rationality and Quantal Response Equilibrium We now formalize the notion of bounded rationality central to risk quantal response equilibrium. Bounded rationality provides a principled mechanism for smoothing the equilibrium correspondence, ensuring uniqueness, and regularizing the learning problem, properties that are essential for stable multi-agent learning under function approximation. The quantal response framework of McKelvey and Palfrey (1995) captures this by modeling agents as stochastic optimizers who assign higher probability to higher-payoff actions while maintaining exploration over the full action space. With this in mind, we introduce the formalism for incorporating bounded rationality into the admissible policy class. Consider a finite normal-form game defined by the tuple =([n],ii∈[n],uii∈[n])G=([n],\A_i\_i∈[n],\u_i\_i∈[n]), where for each player i∈[n]i∈[n], ui:→ℝu_i:A is the utility function. We write a joint action as a=(ai,a−i)a=(a_i,a_-i), where a−ia_-i represents the actions of all players except i. For a fixed profile π−i _-i, let Ui(π−i)∈ℝ|i|U_i( _-i) ^|A_i| be the vector whose entry corresponding to action aia_i is ui(ai,π−i):=a−i∼π−i[ui(ai,a−i)]u_i(a_i, _-i):=E_a_-i _-i[u_i(a_i,a_-i)]. Definition 2 (Quantal Response Equilibrium (McKelvey and Palfrey, 1995)). A mixed-strategy profile π∗=(π1∗,…,πn∗)π^*=( _1^*,…, _n^*) is a Quantal Response Equilibrium (QRE) if, for every player i∈[n]i∈[n], the response is given by πi∗=σi(Ui(π−i∗)) _i^*= _i (U_i( _-i^*) ), where σi:ℝ|i|→Δ(i) _i:R^|A_i|→ (A_i) is a continuous quantal response function that is monotonic (i.e., for any x∈ℝ|i|x ^|A_i|, xa>xa′x_a>x_a implies σi(a∣x)>σi(a′∣x) _i(a x)> _i(a x)) and full support (i.e., σi(a∣x)>0 _i(a x)>0 for all a∈ia _i). It is well known that quantal responses may be introduced into games via regularization; indeed this is shown via constraining the player’s responses to quantal responses (see, e.g., Föllmer and Schied (2002); Hofbauer and Sandholm (2002)). This is straightforward via Fenchel duality. As an example consider the quantal response equilibrium induced by the logit map. Example 1 (Logit Quantal Response Equilibrium). For game G, a mixed-strategy profile π=(π1,…,πn)π=( _1,…, _n) is a logit-QRE with precision parameter ϵ>0ε>0 if for every player i and action ai∈ia_i _i, πi(ai)=eexp(ϵa−i∼π−i[ui(ai,a−i)])/(∑ai′∈iexp(ϵa−i∼π−i[ui(ai′,a−i)])). _i(a_i)=e (ε\, *E_a_-i _-i[u_i(a_i,a_-i)] )/ ( _a _i _i (ε\, *E_a_-i _-i[u_i(a _i,a_-i)] ) ). Equivalently, with the Shannon entropy Φ(μ)=−1ϵ∑aiμ(ai)logμ(ai) (μ)=- 1ε _a_iμ(a_i) μ(a_i), the policy πi _i solves the entropy-regularized problem πi∈argmaxμ∈Δ(i)ai∼μ,a−i∼π−i[ui(ai,a−i)]+1ϵΦ(μ). _i∈ *arg\,max_μ∈ (A_i) \ *E_a_i μ,a_-i _-i[u_i(a_i,a_-i)]+ 1ε (μ) \. Observe that as ϵ→∞ε→∞, the regularization term 1ϵΦ(μ)→0 1ε (μ)→ 0, thereby recovering the standard Nash equilibrium. Conversely, as ϵ→0ε→ 0, the entropy term dominates and the policy approaches the uniform distribution. πi∈argmaxμ∈Δ(i)ai∼μa−i∼π−i[ui(ai,a−i)]+1ϵΦ(μ). _i∈ *arg\,max_μ∈ (A_i) \ *E_ subarrayca_i μ\\ a_-i _-i subarray[u_i(a_i,a_-i)]+ 1ε (μ) \. 2.2 Risk-Sensitive Markov Games Having established the role of bounded rationality, we now incorporate risk aversion into the multi-agent framework. As discussed in Section 1, risk-sensitive objectives provide a principled mechanism for promoting safety, robustness to modeling error and strategic misspecification, and stability in settings with multiple equilibria or volatile dynamics. To formalize this, we equip each agent with a convex risk measure drawn from the class studied extensively in mathematical finance and operations research (Föllmer and Schied, 2002). Definition 3 (Convex Risk Measure). A risk functional ρ:L∞(Ω,ℱ,ℙ)→ℝρ:L^∞( ,F,P) is a convex risk measure if it satisfies the following properties: a. Convexity: For all x,y∈L∞(Ω,ℱ,ℙ)x,y∈ L^∞( ,F,P) and λ∈[0,1]λ∈[0,1], ρ(λx+(1−λ)y)≤λρ(x)+(1−λ)ρ(y)ρ(λ x+(1-λ)y)≤λρ(x)+(1-λ)ρ(y). b. Monotonicity: For all x,y∈L∞(Ω,ℱ,ℙ)x,y∈ L^∞( ,F,P) such that x≤yx≤ y, ρ(x)≥ρ(y)ρ(x)≥ρ(y). c. Translation Invariance: For all x∈L∞(Ω,ℱ,ℙ)x∈ L^∞( ,F,P) and c∈ℝc , ρ(x+c)=ρ(x)+cρ(x+c)=ρ(x)+c. A fundamental property of convex risk measures is that they admit a dual representation as worst-case expectations over adversarial perturbations (Föllmer and Schied, 2002), providing a principled framework for modeling uncertainty in both environment dynamics and opponent strategies. Theorem 1 (Dual Representation of Convex Risk Measures). A mapping ρ:→ℝρ:Z over a finite outcome space Ω is a convex risk measure if and only if there exists a convex, lower-semicontinuous penalty function φ:Δ(Ω)→(−∞,∞] : ( )→(-∞,∞] such that ρ(Z)=supp∈Δ(Ω)p[−Z]−φ(p)ρ(Z)= _p∈ ( ) \ *E_p[-Z]- (p) \. Assumption 1 (Lipschitz Penalty Functions). For each player i∈[n]i∈[n], the penalty function φi:Δ(Ω)→(−∞,∞] _i: ( )→(-∞,∞] in the dual representation (Theorem 1) is LφL_ -Lipschitz continuous with respect to the ℓ1 _1 norm. That is, for all p,q∈Δ(Ω)p,q∈ ( ), the bound holds: |φi(p)−φi(q)|≤Lφ‖p−q‖1| _i(p)- _i(q)|≤ L_ \|p-q\|_1. This assumption ensures that the risk measure ρ is Lipschitz continuous with respect to the underlying distribution of returns and hence with respect to the Q-functions we estimate. Risk-adjusted loss in matrix games. Consider an n-player matrix game with action sets ii=1n\A_i\_i=1^n and payoff functions ui:→ℝu_i:A . Each player i minimizes a risk-adjusted loss based on the negation of their utility. For a joint mixed-strategy profile π, the risk-adjusted loss is ℓi(πi,π−i):=ρi(−ui(a)) _i( _i, _-i):= _i(-u_i(a)), where the randomness is over the joint action a∼(πi,π−i)a ( _i, _-i). By Theorem 1 (dual representation), this loss is equivalently expressed as ℓi(πi,π−i)=suppi∈Δ(−i)a−i∼pi[−ui(πi,a−i)]−φi(pi,π−i). _i( _i, _-i)= _p_i∈ (A_-i) \ *E_a_-i p_i[-u_i( _i,a_-i)]- _i(p_i, _-i) \. (1) Here pip_i represents an adversarial distribution over the opponents’ joint actions, while φi(⋅,π−i) _i(·, _-i) is a convex penalty that constrains the adversary by penalizing deviations from the reference policy π−i _-i. A canonical choice is the entropic risk measure. Example 2 (Entropic Risk). The entropic risk measure is obtained by setting the penalty function φi _i to be the Kullback–Leibler divergence scaled by a temperature parameter. The risk-adjusted loss then admits the closed form ℓi(πi,π−i)=1τilog(a−i∼π−i[exp(−τiui(πi,a−i))]). _i( _i, _-i)= 1 _i ( *E_a_-i _-i [ (- _i\,u_i( _i,a_-i)) ] ). The parameter τi>0 _i>0 controls the degree of risk aversion: as τi→0 _i→ 0, the objective recovers the standard risk-neutral expected loss, whereas τi→∞ _i→∞ yields the worst-case (minimax) objective. Risk-Averse Quantal Response Equilibrium (RQE). To model agents that are both risk-averse and boundedly rational, we augment the risk-adjusted loss with a regularization term. For each player i, let νi:Δ(i)→ℝ _i: (A_i) be a strictly convex regularizer and ϵi>0 _i>0 a precision parameter controlling the degree of bounded rationality. The regularized risk-adjusted loss is li(πi,π−i):=ℓi(πi,π−i)+1ϵiνi(πi),l_i( _i, _-i):= _i( _i, _-i)+ 1 _i _i( _i), where ℓi _i is the risk-adjusted loss in (1). A common example of a convex regularizer is negative entropy νi(p)=∑kpklog(pk) _i(p)= _kp_k (p_k), for instance, if players are are constrained to logit response functions. Each player seeks to minimize this combined objective, balancing risk minimization against the entropy constraint imposed by bounded rationality. Definition 4 (Mazumdar et al. (2025)). Consider an n-player normal-form game. A joint strategy profile π⋆=(π1⋆,…,πn⋆)π =( _1 ,…, _n ) is a Risk-Averse Quantal Response Equilibrium (RQRE) if, for every player i∈[n]i∈[n], the policy in equilibrium is given by πi∗=argminπi∈Δ(i)ℓi(πi,π−i∗)+1ϵiνi(πi). _i^*= *arg\,min_ _i∈ (A_i)\ _i( _i, _-i^*)+ 1 _i _i( _i)\. Under sufficient risk aversion and bounded rationality, Mazumdar et al. (2025) show that RQRE is computationally tractable via no-regret learning by establishing an equivalence to the coarse correlated equilibrium of a lifted 2n2n-player game. Extension to Risk-Sensitive Markov games. Now we show the extension of the static RQRE concept to the finite-horizon Markov game setting, considering both the uncertainty of agents’ strategies and the environments (rewards and transitions). The key is applying the equilibrium condition stage-wise to the action-value functions. Let us formalize the connection between the policy-side and environment-side risk operators used in the risk-sensitive Markov game and a single abstract convex risk functional ρ. As demonstrated via Theorem 1, a large class of convex risk functionals admit the dual representation ρ(Z)=supp∈Δ(Ω)p[−Z]−φ(p).ρ(Z)= _p∈ ( ) \E_p[-Z]- (p) \. In risk-sensitive Markov games, risk operators arise from this dual form, but applied to different sources of randomness: (i) Environment risk: randomness in next state xh+1x_h+1; (i) Policy risk: randomness in opponents’ actions a−ia_-i. The penalty functions φ,i _ e,i and φ,i _ p,i determine the particular choice of convex risk functional ρ in each case. We remark that these two sources of risk are fundamentally different and thus must be separated. Policy risk represents a form of strategic risk-aversion and changes as the opponents’ strategies change over time. Environment risks are taken with respect to the randomness stemming from the random—but stationary—environment the agent is acting in. Now we express the environment risk as a conditional risk measure. Fixing (i,h,x,a)∈[n]×[H]×(i,h,x,a)∈[n]×[H]×X×A, the randomness in the environment arises from the next state xh+1∼h(⋅∣x,a)x_h+1 _h(· x,a). Given a continuation value function Vi,h+1(⋅;π)V_i,h+1(·;π), define the random variable Zi,h(x′):=Vi,h+1(x′;π)Z_i,h e(x ):=V_i,h+1(x ;π). We define the environment risk operator ℛi,h(ri,h,h,Vi,h+1;x,a):=ri,h(x,a)+ρi,h(Zi,h|h(⋅∣x,a)),R e_i,h (r_i,h,P_h,V_i,h+1;x,a ):=r_i,h(x,a)+ρ e_i,h (Z_i,h e\, |\,P_h(· x,a) ), (2) where the conditional risk functional is given in the dual form by ρi,h(Z|)=inf~∈()∫Z(x′)~(dx′)+φ,i(~∥).ρ e_i,h(Z|P)= _ P (X) \ Z(x )\, P(dx )+ _ e,i( P\,\|\,P) \. Thus, in this notation, we have action-value function Qhi(x,a;π)=ℛi,h(ri,h,h,Vi,h+1;x,a).Q_h^i(x,a;π)=R e_i,h (r_i,h,P_h,V_i,h+1;x,a ). The penalty function φ,i _ e,i determines the specific form of ρi,hρ e_i,h (e.g. entropic risk, distributionally robust risk). Now, let πh(⋅∣x) _h(· x) denote the joint mixed action. For each opponent action profile a−ia_-i, define the induced cost Zi,h(a−i):=∑ai∈iπi,h(ai∣x)Qhi(x,ai,a−i;π).Z_i,h p(a_-i):= _a_i _i _i,h(a_i x)\,Q_h^i(x,a_i,a_-i;π). The policy-side risk operator is ℛi,h(Qhi,πh;x):=ρi,h(Zi,h|π−i,h(⋅∣x)),R p_i,h (Q_h^i, _h;x ):=ρ p_i,h (Z_i,h p\, |\, _-i,h(· x) ), (3) where the dual representation is ρi,h(Z∣π−i)=suppi∈i−⟨Z,pi⟩−φ,i(pi,π−i).ρ p_i,h(Z _-i)= _p_i _i p\- Z,p_i - _ p,i(p_i, _-i)\. Hence, in this notation, the value function is Vhi(x;π)=ℛi,h(Qhi,πh;x).V_h^i(x;π)=R p_i,h (Q_h^i, _h;x ). With an additional strictly convex regularizer νi:Δ(i)→ℝ _i: (A_i) , the regularized value is Vi,hϵi(π;x)=ℛi,h(Qhi,πh;x)+1ϵiνi(πi,h(⋅∣x)).V_i,h _i(π;x)=R p_i,h (Q_h^i, _h;x )+ 1 _i _i( _i,h(· x)). (4) Thus the risk-regularized Bellman recursion is defined by Qhi=ℛi,h(ri,h,h,Vi,h+1),andVhi=ℛi,h(Qhi,πh).Q_h^i=R e_i,h (r_i,h,P_h,V_i,h+1 ), V_h^i=R p_i,h(Q_h^i, _h). Definition 5 (Risk Quantal Response Equilibrium for Markov Games). Consider a finite-horizon risk-sensitive Markov game ℳMG equipped with environment risk operators ℛi,hR e_i,h and policy risk operators ℛi,hR p_i,h, as defined in (2)–(3), for each player i∈[n]i∈[n]. A Markov policy profile π⋆=πh⋆h=1Hπ =\ _h \_h=1^H is called a Risk Quantal Response Equilibrium (RQRE) if for every stage h∈[H]h∈[H], every state x∈x , and every player i∈[n]i∈[n], the mixed action πi,h⋆(⋅∣x) _i,h (· x) satisfies the fixed-point condition πi,h⋆(⋅∣x)∈argminμi∈Δ(i)ℛi,h(Qhi(⋅;π⋆),(μi,π−i,h⋆);x)+1ϵiνi(μi), _i,h (· x)∈ _ _i∈ (A_i) \R p_i,h (Q_h^i(·;π ),( _i, _-i,h );x )+ 1 _i _i( _i) \, (5) where the continuation action-value functions satisfy the risk-sensitive Bellman recursion Qhi(x,a;π⋆)=ℛi,h(ri,h,h,Vi,h+1(⋅;π⋆);x,a)Q_h^i(x,a;π )=R e_i,h (r_i,h,P_h,V_i,h+1(·;π );x,a ), and Vi,hϵi(π⋆;x)=ℛi,h(Qhi,πh⋆;x)+1ϵiνi(πi,h⋆(⋅∣x))V_i,h _i(π ;x)=R p_i,h (Q_h^i, _h ;x )+ 1 _i _i( _i,h (· x)), with terminal condition Vi,H+1ϵi(⋅;π⋆)≡0V_i,H+1 _i(·;π )≡ 0. 3 Risk-Sensitive QRE Optimistic Value Iteration Algorithm 1 Risk QRE-Optimistic Value Iteration (RQRE-OVI) 1:Risk-sensitivity τi>0 _i>0, policy regularization (bounded rationality) ϵi>0 _i>0. 2:finite sets ^i P_i p (policy risk) and ^i P_i e (environment risk). Set Qhi,1≡HQ_h^i,1≡ H for all i,hi,h. 3:for k=1,2,…,Kk=1,2,…,K do ⊳ Episode k 4: for h=H,H−1,…,1h=H,H-1,…,1 do ⊳ Backward pass 5: Λhk←λId+∑t=1k−1ϕ(xht,aht,h)ϕ(xht,aht,h)⊤ _h^k←λ I_d+ _t=1^k-1φ(x_h^t,a_h^t,h)φ(x_h^t,a_h^t,h) 6: πh+1k(x)←RQREε(Qh+11,k(x,⋅),…,Qh+1n,k(x,⋅)) _h+1^k(x)← RQRE_ (Q_h+1^1,k(x,·),…,Q_h+1^n,k(x,·)) 7: for i=1,…,ni=1,…,n do 8: V^i,h+1ϵi(π;x):=maxpi∈^i−πi(⋅|x)⊤Qh+1i,k(x,:)pi−φ,i(pi,π−i)+1ϵiνi(πi). V_i,h+1 _i(π;x):= _p_i∈ P_i p\- _i(·|x) Q_h+1^i,k(x,:)\,p_i- _ p,i(p_i, _-i)\+ 1 _i _i( _i). 9: y^i,ht:=ri,h(xht,aht)+ρ^i,h,(V^i,h+1ϵi(πh+1k;xh+1)|xht,aht),t=1,…,k−1. y_i,h^t:=r_i,h(x_h^t,a_h^t)+ ρ_i,h e,k ( V_i,h+1 _i( _h+1^k;x_h+1)\ |\ x_h^t,a_h^t ), t=1,…,k-1. 10: whi,k←(Λhk)−1∑t=1k−1ϕ(xht,aht,h)y^i,htw_h^i,k←( _h^k)^-1 _t=1^k-1φ(x_h^t,a_h^t,h)\, y_i,h^t 11: Qhi,k(x,a)←min(whi,k)⊤ϕ(x,a,h)+βϕ(x,a,h)⊤(Λhk)−1ϕ(x,a,h),BQ_h^i,k(x,a)← \(w_h^i,k) φ(x,a,h)+β φ(x,a,h) ( _h^k)^-1φ(x,a,h),\;B \ 12: Execute episode k with πhk(x)←RQREε(Qh1,k(x,⋅),…,Qhn,k(x,⋅)) _h^k(x)← RQRE_ (Q_h^1,k(x,·),…,Q_h^n,k(x,·)). Consider an n-player episodic Markov game of the form ℳ=(,,H,,r)MG=(X,A,H,P,r) as defined in Section 2. To address large or continuous state spaces, we consider the setting of linear Markov games, in which the transition kernels and reward functions are assumed to be linear. This assumption implies that the action-value functions are linear, as we will show. As discussed in Jin et al. (2020), this is not an assumption on the policy class but rather a statistical modeling assumption on how the data are generated. Assumption 2. Consider a Markov game ℳ=(,,H,,r)MG=(X,A,H,P,r), and let π⋆π be an RQRE. a. The transition kernels and reward functions are linear. That is, there exists a feature map ϕ:×[H]→ℝdφ:X×A×[H] ^d such that for every h∈[H]h∈[H], there exist d unknown signed measures (μh1,…,μhd)( _h^1,…, _h^d) over X and an unknown vector θi,h∈ℝd _i,h ^d satisfying h(x′∣x,a)=⟨ϕ(x,a,h),μh(x′)⟩P_h(x x,a)= φ(x,a,h), _h(x ) , and ri,h(x,a)=⟨ϕ(x,a,h),θi,h⟩r_i,h(x,a)= φ(x,a,h), _i,h for all x,x′∈x,x , a∈a , and h∈[H]h∈[H]. Without loss of generality, we assume that ‖ϕ(x,a,h)‖≤1\|φ(x,a,h)\|≤ 1 for all (x,a,h)∈×[H](x,a,h) ×A×[H] and maxmaxx∈‖μh(x)‖,‖θi,h‖≤d \ _x \| _h(x)\|,\| _i,h\|\≤ d for all h∈[H]h∈[H]. b. Realizability. For each player i∈[n]i∈[n] and stage h∈[H]h∈[H], there exists a vector wi,h⋆∈ℝdw_i,h ^d such that for all (x,a)∈×(x,a) ×A, the action-value map Qhi(x,a;π⋆)=⟨ϕ(x,a,h),whi,⋆⟩Q_h^i(x,a;π )= φ(x,a,h),\,w_h^i, . Critically, this assumption implies that for any policy, the action-value functions are linear in the feature map ϕφ. Therefore, when designing multi-agent reinforcement learning algorithms, it suffices to focus on linear action-value functions. We refer the reader to Jin et al. (2020) for common examples of games encompassed by Assumption 2. Regret Notion. Let πi,hbr(⋅∣x)∈argmaxμi∈Δ(i)Vi,hϵi((μi,π−i,h(⋅∣x));x) _i,h br(· x)∈ _ _i∈ (A_i)V_i,h _i (( _i, _-i,h(· x));x ), is the smoothed best response such that future continuation uses πibr _i br recursively in Qi,h(πi′,π−i)(x,a) Q_i,h^( _i , _-i)(x,a) :=ri,h(x,a)+ρi,h(Vi,h+1ϵi((πi′,π−i);Xh+1)|x,a) :=r_i,h(x,a)+ _i,h e(V_i,h+1 _i(( _i , _-i);X_h+1)\ |\ x,a) Vi,hϵi((πi′,π−i);x) V_i,h _i(( _i , _-i);x) :=ℛi,h(Qi,h(πi′,π−i),(πi′,π−i)h;x)+1ϵiνi(πi′). :=R pol_i,h (Q_i,h^( _i , _-i),( _i , _-i)_h;x )+ 1 _i _i( _i ). with terminal condition Vi,H+1ϵi≡0V_i,H+1 _i≡ 0. Define the so-called exploitability regret by reg(K):=∑k=1Kmaxi∈[n](Vi,1ϵi(πibr(π−ik),π−ik;s0)−Vi,1ϵi(πk;s0)),reg(K):= _k=1^K _i∈[n] (V_i,1 _i (π br_i( _-i^k), _-i^k;\,s_0 )-V_i,1 _i (π^k;\,s_0 ) ), where the episode-wise regret term is zero precisely when the policy πk _k is an RQRE, which itself is commonly unique under sufficient regularity (Mazumdar et al., 2025). This regret is also analogous to the regret notion considered in prior works (Cisneros-Velarde and Koyejo, 2023). Bounding the exploitability reg(K)reg(K) implies that each πkπ^k is approximately unilaterally stable: no player can gain much by deviating in the risk-regularized sense. Indeed, it is algorithmically natural here as agents are computing πkπ^k via an approximate RQRE mapping from an optimistic QkQ^k. RQRE-OVI (Algorithm 1). The algorithm performs optimistic value iteration over episodes, solving an approximate RQRE at each stage game via the subroutine RQREε RQRE_ . This replaces the Nash oracle used in prior work (Cisneros-Velarde and Koyejo, 2023) with a unique, Lipschitz stable, and computationally tractable equilibrium computation, and risk measures for environmental, policy and opponent uncertainty. The environment-risk operator ρi,h _i,h e is estimated from samples, for instance via finite dual discretization or closed-form evaluation as in the entropic case (Example 2); concrete instantiations and error analysis are provided in Appendix C. Theorem 2 (Regret bound). Consider Algorithm 1, and let Assumption 2 holds. Suppose that there exists constant B>0B>0 such that 0≤Vi,hϵi(π;x)≤B0≤ V_i,h _i(π;x)≤ B for all (i,h,x,π)∈[n]×[H]×∈Π(i,h,x,π)∈[n]×[H]×X∈ , and suppose the following approximations are given: • Environment & Policy Risk. There exists ε≥0 _ env≥ 0 and ε _ pol such that for all bounded X, 0≤ρi,h(X)−ρ^i,hk(X)≤ε0≤ _i,h env(X)- ρ_i,h^\,k(X)≤ _ env, and for all (i,h,x,π)∈[n]×[H]×∈Π(i,h,x,π)∈[n]×[H]×X∈ , 0≤Vi,hϵi(π;x)−V^i,hϵi(π;x)≤ε.0≤ V_i,h _i(π;x)- V_i,h _i(π;x)≤ _ pol. • Stage RQRE Approximation. For each (h,x)∈[H]×(h,x)∈[H]×X and Q the computed stage equilibrium π~h(⋅|x;Q) π_h(·|x;Q) satisfies |Vi,hϵi(π~h;x,Q)−Vi,hϵi(πh⋆;x,Q)|≤ε|V_i,h _i ( π_h;x,Q )-V_i,h _i ( _h ;x,Q )|≤ _ eq for each i, where πh⋆ _h is the exact stage equilibrium. Then with probability at least 1−δ1-δ, the estimate holds: regret(K)≤~(LBKd3H3)+KH(ε+L(ε+ε)), *regret(K)\;≤\; O (L_ env\,B\, K\,d^3\,H^3 )\;+\;KH ( _ env+L_ env ( _ pol+ _ eq ) ), (6) where ~(⋅) O(·) hides logarithmic factors in (n,d,H,K,1/δ)(n,d,H,K,1/δ). This theorem builds on the analysis of optimistic value iteration with linear function approximation (Cisneros-Velarde and Koyejo, 2023; Zhou et al., 2021; Jin et al., 2020), sharing the same elliptical potential and statistical machinery, but requires several new ingredients to handle the approximation errors introduced by the risk estimation and approximate equilibrium computation. First, the covering number for the risk induced value class (Lemma 1) must be established for the RQRE smoothed best-response structure rather than for an exact Nash oracle. Unlike single-agent linear MDPs, the continuation values depend on the data-dependent mapping Q↦π~(Q)Q π(Q) and are subsequently transformed by nonlinear risk operators. As a result, the regression targets do not form a simple linear class, preventing a direct linear-bandit-style concentration argument. This requires controlling the complexity of the risk-induced value-function class via a covering argument. Second, the optimism guarantee (Lemma 2) must account for the combined effect of the confidence bonus at each episode and the approximate RQRE—rather than an exact Nash equilibrium—across all stages, translating the environment-risk, policy-risk, and equilibrium approximation errors into an additive optimism deficit. To the end, Lemma 3 relates the deviation gap at each stage to an optimistic Q-advantage plus the exploration bonus. Finally, a stage-wise performance difference recursion propagates these per-step errors through the risk-sensitive Bellman backup, where the Lipschitz constant L_ env of the environment risk operator governs how approximation errors compound across stages. We provide more detail on novelty in addition to the full proof in Appendix B. 3.1 Regret Bounds in terms of Rationality and Risk Preferences In Algorithm 1, we compute stage-wise ε _ eq–approximate RQRE. Here we give some sense in which this approximation depends on problem parameters. For example, a natural class of algorithms are no-regret; if agents run generic no-regret dynamics, then ε _ eq is εeq(T)=~(∑ilog(|i|)/T) _eq(T)= O( _i (|A_i|)/T) to a coarse correlated equilibrium (Cesa-Bianchi and Lugosi, 2006; Blum and Mansour, 2007). In the special case where the policy-space risk penalty is entropic (KL) and the player policy is entropy-regularized, there are number of methods one can employ including no-regret learning methods such as extra-gradient or mirror-prox, multiplicative weights, or iterative best response. In this case, we can obtain more explicit bounds which reveal how the risk sensitivity and bounded rationality parameters influence different performance criteria. To this end, fix a stage h and state x. For player i, let νi≡Φ _i≡ be an entropy regularizer, and let φ,i≡1τiKL _ p,i≡ 1 _iKL. Then policy-risk value functional admits the closed form Vi,hϵi,τi(π;x;Q)=−1τilog(∑a−iπ−i(a−i|x)exp(−τiuiπ(x,a−i;Q)))+1ϵiΦ(πi(⋅|x)),V_i,h _i, _i(π;x;Q)=- 1 _i ( _a_-i _-i(a_-i|x)\, (- _i\,u_i^π(x,a_-i;Q)) )+ 1 _i ( _i(·|x)), (7) where uiπ(x,a−i;Q):=∑aiπi(ai|x)Qi(x,ai,a−i)u_i^π(x,a_-i;Q):= _a_i _i(a_i|x)\,Q_i(x,a_i,a_-i). Here Qi(x,:)Q_i(x,:) denotes the tensor slice a↦Qi(x,a)a Q_i(x,a), and πi⊤Qipi _i Q_i\,p_i denotes ∑ai,a−iπi(ai|x)Qi(x,ai,a−i)pi(a−i) _a_i,a_-i _i(a_i|x)\,Q_i(x,a_i,a_-i)\,p_i(a_-i). The entropy regularization also impacts the range of values for value function. Indeed, assume stage rewards satisfy ri,h(x,a)∈[0,1]r_i,h(x,a)∈[0,1] and Vi,H+1ϵi,τi≡0V_i,H+1 _i, _i≡ 0. Then for any policy profile π and any (h,x)∈[H]×(h,x)∈[H]×X, the cumulative (undiscounted) reward-to-go is at most H. Moreover, the entropy satisfies 0≤Φ(πi(⋅|x))≤log|i|.0≤ ( _i(·|x))≤ |A_i|. Therefore the additive regularization term is bounded as 0≤Φ(πi(⋅|x))/ϵi≤log(|i|)/ϵi.0≤ ( _i(·|x))/ _i≤ (|A_i|)/ _i. Since the entropic risk term in (7) is a (KL-regularized) log-sum-exp aggregation of bounded Q-values, it preserves the same scale as the underlying payoff (up to the horizon factor). Consequently, when Q is clipped to [0,B][0,B] with B:=maxi∈[n]BiwhereBi:=H(1+log(|i|)/ϵi),B:= _i∈[n]B_i B_i:=H (1+ (|A_i|)/ _i ), we have 0≤Vi,hϵi,τi(π;x;Q)≤B0≤ V_i,h _i, _i(π;x;Q)≤ B for all (i,h,x)∈[n]×[H]×(i,h,x)∈[n]×[H]×X and policies π. Here the factor H matches the horizon scaling of cumulative costs, while log|i|/ϵi |A_i|/ _i captures the maximum magnitude of entropy regularization. Corollary 1 (Regret under entropic policy-risk and regularization). Under the assumptions of Theorem 2, specialize the policy-side risk/value operator to (7) and set the policy regularizer to νi(μi)=Φ(μi) _i( _i)= ( _i). Suppose the stage solver returns a policy with duality gap at most Δ _ eq uniformly over (h,x)∈[H]×(h,x)∈[H]×X and matrices Q so that ε≤cBΔ/τmin _ eq≤ c_ eq\,B _ eq/ _ where τmin:=mini∈[n]τi _ := _i∈[n] _i, and for an absolute constant c>0c_ eq>0 the dependence on τmin _ is explicit. With probability at least 1−δ1-δ, reg(K)≤~(LBKd3H3)+KH(ε+Lε+LcBΔ/τmin). (K)≤ O(L_ env\,B\, K\,d^3\,H^3)+KH ( _ env+L_ env _ pol+L_ env\,c_ eq\,B _ eq/ _ ). (8) For example, if agents run no-regret as mentioned above, then Δ≤O~(∑ilog(|i|)/T) _ eq≤ O( _i (|A_i|)/T) where the equilibrium solver RQREε RQRE_ is run for T steps. If the variational inequality is strongly monotone with modulus μ=μ(τ)μ=μ(τ) (cf. Corollary 2) and Lipschitz constant L=L(τ)L=L(τ), then an extragradient/Mirror-Prox solver run for T steps yields εeq(T)≤Cexp(−Tμ/L) _eq(T)≤ C (-Tμ/L). Plugging this into Theorem 2 replaces the additive equilibrium-solver term by KHLCexp(−Tμ/L)KHL_ envC (-Tμ/L). In Appendix B.2, we provide more precise examples of these approximations. Corollary 1 reveals the following parameter tradeoffs. Increasing ϵi _i (weaker entropy regularization) decreases B(ϵ)B(ε) and thus both the leading statistical term and the equilibrium-solver error. For fixed Δ _ eq, increasing τmin _ decreases the solver-error contribution as O(Δ/τmin)O( _ eq/ _ ). However, recovering risk neutrality (τ→0τ→ 0) requires scaling Δ=(τminε2/B2) _ eq=O( _ _ eq^2/B^2) to maintain a fixed ε _ eq. In Appendix B.4 we analyze the risk approximation errors as a function of ϵε and τ. 4 Distributional Robustness & Stability of RQRE Beyond the ability to capture phenomena of natural learners, a key motivation for RQRE over Nash is that the additional structure introduced by bounded rationality and risk sensitivity which yield both distributionally robustness and stability under approximation errors. 4.1 Distributional Robustness of RQRE In parallel to RQRE, several distributionally robust equilibrium concepts have been proposed, including strategically robust equilibrium via optimal transport (Lanzetti et al., 2025) and distributionally robust Nash equilibria (Alizadeh et al., 2025). The dual representation of the risk-adjusted loss (Section 2) reveals a direct connection between RQRE and distributionally robust optimization (DRO). In particular, the risk-adjusted loss (1) admits a natural interpretation as a penalized DRO objective: player i evaluates a strategy under an adversarial distribution over opponents’ actions while paying a convex penalty for deviating from the reference distribution π−i _-i. Consequently, RQRE corresponds to a fixed point of regularized best responses under penalized distributional robustness. Classical ambiguity-set DRO arises as a special case of (1). Proposition 1 (RQRE generalizes ambiguity-set robustness). Consider an n-player normal-form game with utilities ui:→ℝu_i:A . a. Any hard-DRO equilibrium is an RQRE. The risk-adjusted loss ℓi _i defined for each fixed π−i _-i by a proper convex and lower semi-continuous map pi↦φi(pi,π−i)p_i _i(p_i, _-i) reduces to the ambiguity-set DRO loss ℓi(πi,π−i)=suppi∈i(π−i)a−i∼pi[−ui(πi,a−i)]. _i( _i, _-i)= _p_i _i( _-i) *E_a_-i p_i [-u_i( _i,a_-i) ]. b. Convex-penalty RQRE strictly generalize indicator-penalty RQRE. There exist proper convex penalties φi(⋅,π−i) _i(·, _-i) for which the induced loss ℓi(⋅,π−i) _i(·, _-i) cannot be represented as a hard-DRO loss for any ambiguity set correspondence i(⋅)P_i(·). Proof Sketch. For any ambiguity set correspondence i(π−i)⊆Δ(−i)P_i( _-i) (A_-i), define the indicator penalty φi(pi,π−i):=ιi(π−i)(pi). _i(p_i, _-i):= _P_i( _-i)(p_i). The first claim holds by deriving the stated reduction using φi(⋅,π−i)=i(π−i) _i(·, _-i)= 1_P_i( _-i) and the convex measure duality (cf. Theorem 1). Indeed, given φi(⋅,π−i)=i(π−i) _i(·, _-i)= 1_P_i( _-i), for any function Z on −iA_-i, suppi∈Δ(−i)pi[Z]−i(π−i)(pi)=suppi∈i(π−i)pi[Z], _p_i∈ (A_-i)\E_p_i[Z]- 1_P_i( _-i)(p_i)\= _p_i _i( _-i)E_p_i[Z], which yields the stated reduction (with Z(a−i)=−ui(πi,a−i)Z(a_-i)=-u_i( _i,a_-i)). Taking fixed points of the best-response maps gives the equilibrium inclusion. To see that the second claim holds, consider the KL penalty φi(pi,π−i)=1τiKL(pi∥π−i) _i(p_i, _-i)= 1 _i *KL(p_i\| _-i) with τi>0 _i>0 which induces the entropic risk functional of Example 2—i.e., ℓi(πi,π−i)=1τiloga−i∼π−i[exp(τi(−ui(πi,a−i)))]. _i( _i, _-i)= 1 _i _a_-i _-i [ ( _i(-u_i( _i,a_-i))) ]. This is not representable as suppi∈i(π−i)pi[−ui(πi,a−i)] for any seti(π−i). _p_i _i( _-i) *E_p_i[-u_i( _i,a_-i)] for any set _i( _-i). Any hard-DRO mapping has the form Z↦supp∈p[Z]Z _p *E_p[Z] and is positively homogeneous: supp∈p[tZ]=tsupp∈p[Z] _p *E_p[tZ]=t _p *E_p[Z] for all t≥0t≥ 0. The entropic mapping Z↦(1/τ)logπ−i[exp(τZ)]Z (1/τ) *E_ _-i[ (τ Z)] is not positively homogeneous in general: e.g., take Z∈0,1Z∈\0,1\ with probability 1/21/2 each under π−i _-i, so that 1τlog((1+e2τ)/2)≠2τlog((1+eτ)/2) 1τ ((1+e^2τ)/2)≠ 2τ ((1+e^τ)/2). Hence no ambiguity set P can make these mappings coincide for all Z, proving strictness. ∎ In particular, part a shows that the strategically robust equilibrium concept based on ambiguity sets proposed by Lanzetti et al. (2025) arises as a special case of RQRE obtained by choosing i(π−i)P_i( _-i) to be an optimal-transport ball around π−i _-i. In fact, the following inclusions are generally true: RQRE ⊃Penalized DRO Equilibrium⊃Hard ambiguity-set DRO Equilibrium⊃Nash Equilibrium \;⊃\;Penalized DRO Equilibrium\;⊃\;Hard ambiguity-set DRO Equilibrium\;⊃\;Nash Equilibrium (9) Remark 1 (Existence versus expressivity). Indicator penalties 1_P are convex but not Lipschitz on Δ(−i) (A_-i). The Lipschitz assumption on φi _i is used to obtain existence (and stability) of RQRE. Proposition 1 is an expressivity statement: it shows that hard ambiguity-set robustness is contained in the RQRE class, even though such penalties lie outside the Lipschitz-penalty subclass for which our existence theory applies. Now for Markov games, we show that RQRE are distributionally robust (see Appendix E for details). Proposition 2 (RQRE in Markov Games are Distributionally Robust). Let π⋆π be an RQRE of the risk-sensitive Markov game ℳMG with penalty functions φ,i _ p,i, φ,i _ e,i as defined in the dual representation (Theorem 1) and satisfying Assumption 1. Then π⋆π is distributionally robust with respect to the agents policy, the opponents strategies, and the stochastic environment transitions where Lagrange multipliers that uniquely determine the size of the corresponding ambiguity sets. 4.2 RQRE Admit Stability Properties that Yield Performance Guarantees Another main advantage of RQRE over Nash equilibrium for value-iteration-based algorithms with function approximation is stability: small errors in the estimated Q-functions should produce small changes in the computed equilibrium policy. Since RQRE is unique by construction, the map from payoff tables to equilibrium policy is a well-defined function. In contrast, the Nash correspondence is set-valued in general-sum games, and any single-valued selection can be discontinuous (Fudenberg and Tirole, 1991; van Damme, 1987). This distinction is the source of the stability gap. Corollary 2 (Lipschitz Stability of RQRE). Suppose each player i∈[n]i∈[n] employs an αν _ν-strongly convex regularizer νi _i , and an α _ p-strongly convex policy-risk penalty φ,i(⋅,q) _ p,i(·,q) for any q. The regularized risk-adjusted objective is μ:=1ϵ+τα>0μ:= 1ε+τ _ p>0 strongly concave in πi _i, and there exists a constant c>0c>0 such that for any Q,Q~Q, Q, the estimate holds: ‖π(Q)−π(Q~)‖1≤cμ‖Q−Q~‖∞.\|π RQRE(Q)-π RQRE( Q)\|_1≤ cμ\|Q- Q\|_∞. In particular, for entropy regularization and policy risk, αν=1/ϵ _ν=1/ε and α=τ _ p=τ, so μ=1/ϵ+τ2μ=1/ε+τ^2. The Lipschitz constant c/μc/μ is controlled entirely by the bounded rationality and the risk-aversion parameters, both of which are design choices of RQRE-OVI. Stronger regularization (larger ϵε) or greater risk aversion (smaller τ) yields a smaller c/μc/μ, improving stability at the cost of regret performance. In contrast, Nash equilibria in general-sum games are not guaranteed to be unique, and any algorithm that must therefore perform stage-wise equilibrium selection suffers. The following example illustrates this phenomenon. Example 3 (Instability of Nash Equilibrium under Multiplicity). Consider the two-player symmetric coordination game with payoff matrix Q(α)=(100α)Q(α)= ( smallmatrix1&0\\ 0&α smallmatrix ) for any α>0α>0. This game has three Nash equilibria, including two pure-strategy equilibria (e1,e1)(e_1,e_1) and (e2,e2)(e_2,e_2). Standard equilibrium selection criteria (e.g., risk-dominance or payoff-dominance) select (e1,e1)(e_1,e_1) when α<1α<1 and (e2,e2)(e_2,e_2) when α>1α>1. Hence any Lipschitz constant L would have to satisfy L≥‖π(Q(1−ε))−π(Q(1+ε))‖1‖Q(1−ε)−Q(1+ε)‖∞=22ε=1ε,L≥ \|π NE(Q(1- ))-π NE(Q(1+ ))\|_1\|Q(1- )-Q(1+ )\|_∞= 22 = 1 , which diverges as ε→0 → 0. Thus no finite uniform Lipschitz constant exists. The instability is not due to a particular selection rule, but a consequence of equilibrium multiplicity itself. Under function approximation, estimated payoff tables are necessarily perturbed, and when the stage game admits multiple equilibria, arbitrarily small errors may cause a Nash oracle to return different policies across episodes (Cisneros-Velarde and Koyejo, 2023). RQRE-OVI avoids this failure mode: the regularization inherent in the formulation guarantees a unique equilibrium at every stage, and Corollary 2 ensures it varies smoothly with estimated payoffs. Such stability properties also translate to a form of policy convergence. Proposition 3 (Robustness of RQRE-OVI under Linear Function Approximation). Consider Algorithm 1 with parameter estimates w^h w_h satisfying maxi∈[n]‖w^hi−whi,⋆‖2≤δh _i∈[n]\| w_h^i-w_h^i, \|_2≤ _h for all h∈[H]h∈[H] where whi,⋆w^i, _h are the true parameters (Assumption 2). The induced RQRE policies satisfy ‖π^h−πh⋆‖1≤cμδh\| π_h- _h \|_1≤ cμ _h at each stage where π⋆=πh⋆h∈[H]π =\ _h \_h∈[H] is the RQRE of the Markov game and c>0c>0 is an absolute constant, and supx|V1π^(x)−V1π⋆(x)|=(Bδ¯μ∑t=0H−1Lt) _x|V_1 π(x)-V_1^π (x)|=O ( B δμ _t=0^H-1L_ env^t ) when δh≤δ¯ _h≤ δ for all h∈[H]h∈[H]. Moreover, if the environment risk operator is non-expansive in ∥⋅∥∞\|·\|_∞, i.e., L≤1L_ env≤ 1, then ∑t=0H−1Lt≤H _t=0^H-1L_ env^t≤ H, and hence supx|V1π^(x)−V1π⋆(x)|=(HBδ¯/μ) _x|V_1 π(x)-V_1^π (x)|=O(HB δ/μ). Observe that the 11-Lipschitz continuity property of the environment risk operator holds in a number of common settings including entropic risk and many coherent risk maps. The complete finite-horizon analysis is in Appendix D. 5 Numerical Experiments We evaluate RQRE-OVI on two multi-agent coordination benchmarks111Code is available at https://jakeagonzales.github.io/linear-rqe-website/.: a dynamic Stag Hunt environment modified from the Melting Pot suite (Agapiou et al., 2022), and Overcooked (Gessler et al., 2025), specifically using the implementation from JaxMARL (Rutherford et al., 2024). For each environment, we compare RQRE-OVI across a range of risk-aversion parameters against QRE-OVI (risk-neutral) and NQ-OVI (Cisneros-Velarde and Koyejo, 2023). We asses performance under three scenarios: Figure 1: Self-play team return during training. Moving average of team return over episodes for Stag-Hunt (left) and Overcooked (right). In Stag-Hunt, higher τ drives agents toward the payoff dominant (stag, stag) outcome, while lower τ yields the more robust risk-dominant (hare, hare) outcome. In Overcooked, all RQRE variants and QRE converge to comparable team returns, with Nash variants reaching similar or slightly lower levels. 1. Self-play, where agents train and evaluate with their own partner; 2. Cross-play with a perturbed partner, where an ego agent’s partner deviates to a random or fixed action with probability δ at test time; 3. Cross-play with an unseen partner, where agents trained under different algorithms are paired at test time. Across both environments, we find RQRE achieves competitive self-play performance while producing substantially more robust behavior in cross-play, with the risk-aversion parameter τ governing a tradeoff between peak self-play return and worst-case robustness. A detailed description of the environments, training procedures, and hyperparameters is in Appendix F. 5.1 Environment 1: Dynamic Stag-Hunt Game Stag Hunt is a classical coordination game in which two agents must choose between a safe, low-payoff action (hare) and a risky, high-payoff action (stag) that succeeds only under mutual coordination. We implement a dynamic, spatial variant of this game leveraging the Melting Pot framework (Agapiou et al., 2022). In our environment, agents navigate a 9×99× 9 grid to collect resources and interact to resolve payoffs. The payoff matrix follows the standard structure: mutual stag yields (4,4)(4,4), mutual hare (2,2)(2,2), and stag-hare mismatch gives (0,2)(0,2). Self-play reveals a risk-return tradeoff. Under self-play (Figure 1, left) the risk aversion parameter τ directly controls which equilibrium agents coordinate on. High τ agents (τ≥0.5τ≥ 0.5) converge to the payoff dominate outcome with team returns near 60, while low τ agents (τ≤0.05τ≤ 0.05) settle on the risk dominant outcome near 20. This is the tradeoff predicted by the theory—greater risk aversion biases agents toward strategies robust to coordination failure, at the cost of forgoing the higher-payoff but fragile stag equilibrium. QRE-OVI and NQ-OVI achieve intermediate returns converging to the payoff dominant strategy. Risk-averse agents degrade gracefully under partner perturbation. Under cross-play with a perturbed partner (Figure 2, left), more risk-averse agents (low τ) maintain high retention across all noise levels, as their convergence to the risk-dominant hare equilibrium renders them inherently insensitive to partner deviations. In contrast, less risk-averse agents coordinate on the fragile stag equilibrium and suffer sharp retention drops as δ increases. NQOVI and QRE exhibit similar fragility, having also converged to the payoff-dominant strategy. This is precisely the robustness–performance tradeoff predicted by the theory. Figure 2: Cross-play retention (R(δ)/R(0))(R(δ)/R(0)) as a function of perturbed partner noise (δ): Stag-Hunt (left) and Overcooked (right). At each evaluation step, the partner’s action is a fixed deterministic action (e.g., always move in one direction) with probability δ and otherwise follows its trained policy. This produces high-signal deviations to emphasize the robustness phenomena. Curves are normalized by the δ=0δ=0 baseline, so higher values indicate strong robustness and lower values indicate performance degradation. Results are averaged over 200 evaluation rollouts per noise level. 5.2 Environment 2: “Overcooked” Cooperative Dynamic Game The second environment on which we evaluate is Overcooked (Rutherford et al., 2024; Gessler et al., 2025): two agents cooperate in a small kitchen to prepare and deliver onion soup. The task requires a sequential chain of subtasks—picking onions, loading a pot, retrieving cooked soup with a plate, and delivering it—with a sparse team reward of 20 per delivery and shaped rewards for completing intermediate steps. The tight layout makes coordination essential, as agents must divide labor while avoiding blocking one another. RQRE and QRE outperform NQOVI in self-play. Under self-play (Figure 1, right), all RQRE-OVI variants and QRE-OVI converge to team returns in medium to high ranges while NQ-OVI converges more slowly and to notably lower returns. We attribute this gap to the equilibrium selection problem inherent to Nash computation. Overcooked requires consistent coordination across many time steps, as agents must implicitly agree on a division of labor and maintain this role assignment throughout the episode. Because Nash equilibria are non-unique in general-sum games, solving for Nash at each stage game introduces the possibility of inconsistent selections across stages and episodes, disrupting the sustained coordination the task demands. RQRE-OVI and QRE-OVI avoid this failure mode entirely because the RQRE ensures a unique equilibrium at every stage, producing consistent and coherent multi-step behavior. Among the RQRE variants, performance is relatively stable across risk levels indicating that moderate risk aversion does not substantially reduce self-play returns. Figure 3: Cross-play with unseen partners in Overcooked. Each point represents the reward of two agents trained under a different algorithm and paired at test time without ever seen each other before. The left panel shows RQRE-OVI agent’s reward (vertical axis) versus NQ-OVI agent’s reward (horizontal axis) for each pairing; the right panel reverses the roles. Points above the diagonal indicate that the agent on the vertical axis (in this case RQRE) achieves higher return than its partner. Labels denote the τ value of the corresponding RQRE-OVI agent, and the red diamond marks the QRE-OVI baseline score against NQ-OVI. Across all pairings, RQRE-OVI agents achieve equal or higher ego reward than their cross-play partner, with moderate τ values (e.g., τ=0.01τ=0.01) yielding the strongest advantage. RQRE retains performance under partner perturbation. Figure 2 shows that the moderate risk aversion retains 60−80%60-80\% of performance at δ=0.3δ=0.3, while NQOVI, QRE, and higher τ RQRE variants drop below 40%40\%. Combined with the cross play with unseen partners results that follow, this suggests that risk aversion produces policies that are fundamentally more adaptive to partner deviation, rather than overfitting to the specific partner encountered during training. RQRE dominates cross-play with unseen partners. Figure 3 shows rewards when agents trained under different algorithms are paired at test time without ever seeing each other before. Across nearly all pairings, RQRE agents achieve equal or higher ego reward than their partner, with points consistently above the diagonal. The advantage is most pronounced at moderate risk levels, where the RQRE agent achieves around 2−3×2-3× the reward of the NQ-OVI partner. Notably, these results hold across both pairing directions, indicating that the robustness advantage reflects a genuinely more adaptive policy rather than an artifact of which agent is designated as ego. Moreover, the QRE agent performs comparably to NQ-OVI in cross-play, suggesting bounded rationality alone does not account for improved robustness and risk aversion is the key driver of cross-play advantage. 6 Conclusion In this paper, we study the problem of learning robust equilibria in general-sum Markov games with linear function approximation. We provide the first finite-sample regret guarantees for Risk-Sensitive Quantal Response Equilibria that explicitly characterize how the rationality and risk-sensitivity parameters govern sample complexity, establish that RQRE strictly generalizes existing distributionally robust equilibrium concepts, and prove Lipschitz stability of the equilibrium map under payoff perturbation—a property we leverage to obtain policy convergence guarantees under approximation error. The theoretical and empirical results suggest that robust and behaviorally grounded solution concepts offer a promising path for scalable multi-agent reinforcement learning beyond Nash equilibrium. Natural future directions include decentralizing the bonus term, which may be feasible under the monotonicity conditions established for RQRE in the infinite-horizon setting (Zhang and Mazumdar, 2025), and a more fine-grained understanding of the role of risk sensitivity, including risk-seeking agents and asymmetric risk profiles across players. Acknowledgments LJR is supported in part by NSF award 2312775. JG is supported by an NSF Graduate Research Fellowship under Grant No. DGE-2140004. References J. P. Agapiou, A. S. Vezhnevets, E. A. Duéñez-Guzmán, J. Matyas, Y. Mao, P. Sunehag, R. Köster, U. Madhushani, K. Kopparapu, R. Comanescu, D. Strouse, M. B. Johanson, S. Singh, J. Haas, I. Mordatch, D. Mobbs, and J. Z. Leibo (2022) Melting pot 2.0. arXiv preprint arXiv:2211.13746. Cited by: §F.1, §5.1, §5. Z. Alizadeh, A. Farsi, and A. Jalilzadeh (2025) Distributionally robust nash equilibria via variational inequalities. OPT2025 Workshop on Optimization for ML (arXiv preprint arXiv:2510.17024). Cited by: §4.1. P. Artzner, F. Delbaen, J. Eber, and D. Heath (1999) Coherent measures of risk. Mathematical Finance 9 (3), p. 203–228. External Links: Document, Link, https://onlinelibrary.wiley.com/doi/pdf/10.1111/1467-9965.00068 Cited by: Remark 4. R. J. Aumann (1974) Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics 1 (1), p. 67–96. External Links: ISSN 0304-4068, Document, Link Cited by: Appendix A. A. Blum and Y. Mansour (2007) From external to internal regret.. Journal of Machine Learning Research 8 (6). Cited by: §3.1. N. Cesa-Bianchi and G. Lugosi (2006) Prediction, learning, and games. Cambridge university press. Cited by: §B.4, §3.1. Z. Chen, D. Zhou, and Q. Gu (2022) Almost optimal algorithms for two-player zero-sum linear mixture markov games. External Links: 2102.07404, Link Cited by: Appendix A. P. Cisneros-Velarde and S. Koyejo (2023) Finite-sample guarantees for Nash Q-learning with linear function approximation. In Uncertainty in Artificial Intelligence, p. 424–432. External Links: Link Cited by: Appendix A, Appendix A, §B.1, §B.1, §B.1, §B.5, §B.5, §1, §3, §3, §3, §4.2, §5. Q. Cui, K. Zhang, and S. Du (2023) Breaking the curse of multiagents in a large state space: rl in markov games with independent linear function approximation. In Proceedings of Thirty Sixth Conference on Learning Theory, G. Neu and L. Rosasco (Eds.), Proceedings of Machine Learning Research, Vol. 195, p. 2651–2652. External Links: Link Cited by: Appendix A. M. F. Cusumano-Towner, D. Hafner, A. Hertzberg, B. Huval, A. Petrenko, E. Vinitsky, E. Wijmans, T. W. Killian, S. Bowers, O. Sener, P. Kraehenbuehl, and V. Koltun (2025) Robust autonomy emerges from self-play. In Forty-second International Conference on Machine Learning, External Links: Link Cited by: §1. Y. Dai, Q. Cui, and S. S. Du (2024) Refined sample complexity for markov games with independent linear function approximation (extended abstract). In Proceedings of Thirty Seventh Conference on Learning Theory, S. Agrawal and A. Roth (Eds.), Proceedings of Machine Learning Research, Vol. 247, p. 1260–1261. External Links: Link Cited by: Appendix A. C. Daskalakis (2013) On the complexity of approximating a nash equilibrium. ACM Trans. Algorithms 9 (3). External Links: ISSN 1549-6325, Link, Document Cited by: Appendix A. E. Eaton, M. Hussing, M. Kearns, A. Roth, S. B. Sengupta, and J. Sorrell (2025) Replicable reinforcement learning with linear function approximation. External Links: 2509.08660, Link Cited by: Appendix A. I. Erev and A. E. Roth (1998) Predicting how people play games: reinforcement learning in experimental games with unique, mixed strategy equilibria. American Economic Review 88 (4), p. 848–881. External Links: Document, Link Cited by: Appendix A, §1. H. Föllmer and A. Schied (2002) Convex measures of risk and trading constraints. Finance and stochastics 6 (4), p. 429–447. Cited by: Appendix E, §2.1, §2.2, §2.2. D. Fudenberg and J. Tirole (1991) Game theory. MIT Press, Cambridge, MA. Cited by: §4.2. T. Gessler, T. Dizdarevic, A. Calinescu, B. Ellis, A. Lupu, and J. N. Foerster (2025) OvercookedV2: rethinking overcooked for zero-shot coordination. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: §F.2, §5.2, §5. J. K. Goeree and C. A. Holt (1999) Stochastic game theory: for playing games, not just for doing theory. Proceedings of the National Academy of Sciences 96 (19), p. 10564–10567. External Links: Document, Link, https://w.pnas.org/doi/pdf/10.1073/pnas.96.19.10564 Cited by: Appendix A, §1. S. Gu, J. Grudzien Kuba, Y. Chen, Y. Du, L. Yang, A. Knoll, and Y. Yang (2023) Safe multi-agent reinforcement learning for multi-robot control. Artif. Intell. 319 (C). External Links: ISSN 0004-3702, Link, Document Cited by: §1. T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine (2018) Soft actor-critic: off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proceedings of the 35th International Conference on Machine Learning, J. Dy and A. Krause (Eds.), Proceedings of Machine Learning Research, Vol. 80, p. 1861–1870. External Links: Link Cited by: Appendix A. M. Heger (1994) Consideration of risk in reinforcement learning. In Machine Learning Proceedings 1994, W. W. Cohen and H. Hirsh (Eds.), p. 105–111. External Links: ISBN 978-1-55860-335-6, Document, Link Cited by: Appendix A. D. Hernández-Hernández and S. I. Marcus (1996) Risk sensitive control of markov processes in countable state space. Syst. Control Lett. 29 (3), p. 147–155. External Links: ISSN 0167-6911, Link, Document Cited by: Appendix A. J. Hofbauer and W. H. Sandholm (2002) On the global convergence of stochastic fictitious play. Econometrica 70 (6), p. 2265–2294. Cited by: §2.1. R. A. Howard and J. E. Matheson (1972) Risk-sensitive markov decision processes. Management Science 18 (7), p. 356–369. External Links: ISSN 00251909, 15265501, Link Cited by: Appendix A. J. Hu and M. P. Wellman (2003) Nash q-learning for general-sum stochastic games. Journal of machine learning research 4 (Nov), p. 1039–1069. Cited by: Appendix A, Appendix A, §1. C. Jin, Z. Yang, Z. Wang, and M. I. Jordan (2020) Provably efficient reinforcement learning with linear function approximation. In Proceedings of Thirty Third Conference on Learning Theory, J. Abernethy and S. Agarwal (Eds.), Proceedings of Machine Learning Research, Vol. 125, p. 2137–2143. External Links: Link Cited by: Appendix A, §B.1, §3, §3, §3. J. Lacotte, Y. Chow, M. Ghavamzadeh, and M. Pavone (2018) Risk-sensitive generative adversarial imitation learning. CoRR abs/1808.04468. External Links: Link, 1808.04468 Cited by: Appendix A. N. Lanzetti, S. Fricker, S. Bolognani, F. Dörfler, and D. Paccagnan (2025) Strategically robust game theory via optimal transport. External Links: 2507.15325, Link Cited by: Appendix A, Appendix A, §1, §4.1, §4.1. M. L. Littman (1994) Markov games as a framework for multi-agent reinforcement learning. In Proceedings of the Eleventh International Conference on International Conference on Machine Learning, ICML’94, San Francisco, CA, USA, p. 157–163. External Links: ISBN 1558603352 Cited by: §2. Q. Liu, T. Yu, Y. Bai, and C. Jin (2021) A sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning, p. 7001–7010. External Links: Link Cited by: Appendix A, §1. E. Mazumdar, K. Panaganti, and L. Shi (2025) Tractable multi-agent reinforcement learning through behavioral economics. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: Appendix A, Appendix A, Appendix A, §B.2, §B.2, §1, §2.2, §3, Definition 4. E. Mazumdar, L. J. Ratliff, T. Fiez, and S. S. Sastry (2017) Gradient-based inverse risk-sensitive reinforcement learning. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), p. 5796–5801. Cited by: Appendix A. R. D. McKelvey and T. R. Palfrey (1995) Quantal response equilibria for normal form games. Games and Economic Behavior 10 (1), p. 6–38. External Links: ISSN 0899-8256, Document, Link Cited by: Appendix A, §B.5, §1, §2.1, Definition 2. J. McMahan, G. Artiglio, and Q. Xie (2024) Roping in uncertainty: robustness and regularization in markov games. In Forty-first International Conference on Machine Learning, External Links: Link Cited by: Appendix A. P. Mertikopoulos and W. H. Sandholm (2016) Learning in games via reinforcement and regularization. Mathematics of Operations Research 41 (4), p. 1297–1324. External Links: ISSN 0364765X, 15265471, Link Cited by: Appendix A. V. Mohl, S. Frey, R. Leyland, K. Li, G. Nigmatulin, M. Cucuringu, S. Zohren, J. Foerster, and A. Calinescu (2025) JaxMARL-hft: gpu-accelerated large-scale multi-agent reinforcement learning for high-frequency trading. External Links: 2511.02136, Link Cited by: §1. H. Moulin and J. Vial (1978) Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory 7 (3–4), p. 201–221. External Links: ISSN 1432-1270, Document, Link Cited by: Appendix A. R. Munos and C. Szepesvári (2008) Finite-time bounds for fitted value iteration. Journal of Machine Learning Research 9 (27), p. 815–857. External Links: Link Cited by: Appendix A. R. Munos, M. Valko, D. Calandriello, M. Gheshlaghi Azar, M. Rowland, Z. D. Guo, Y. Tang, M. Geist, T. Mesnard, C. Fiegel, A. Michi, M. Selvi, S. Girgin, N. Momchev, O. Bachem, D. J. Mankowitz, D. Precup, and B. Piot (2024) Nash learning from human feedback. In Proceedings of the 41st International Conference on Machine Learning, R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp (Eds.), Proceedings of Machine Learning Research, Vol. 235, p. 36743–36768. External Links: Link Cited by: §1. J. F. Nash (1950) Equilibrium points in ¡i¿n¡/i¿-person games. Proceedings of the National Academy of Sciences 36 (1), p. 48–49. External Links: Document, Link, https://w.pnas.org/doi/pdf/10.1073/pnas.36.1.48 Cited by: Appendix A, §2. Abraham. Neyman, S. Sorin, and N. A. T. Organization. S. A. Division. (2003) Stochastic games and applications. 1st ed. 2003. edition, Nato Science Series C:, Mathematical and Physical Sciences ; 570, Springer Netherlands, NATO Advanced Study Institute on Stochastic Games and Applications (1999 : Stony Brook, N.Y.), Dordrecht (eng). External Links: ISBN 94-010-0189-8 Cited by: §2. S. Qiu, J. Ye, Z. Wang, and Z. Yang (2022) On reward-free rl with kernel and neural function approximations: single-agent mdp and markov game. External Links: 2110.09771, Link Cited by: Appendix A. W. Qiu, X. Wang, R. Yu, X. He, R. Wang, B. An, S. Obraztsova, and Z. Rabinovich (2021) RMIX: learning risk-sensitive policies for cooperative reinforcement learning agents. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21, Red Hook, NY, USA. External Links: ISBN 9781713845393 Cited by: Appendix A. L. J. Ratliff and E. Mazumdar (2019) Inverse risk-sensitive reinforcement learning. IEEE Transactions on Automatic Control 65 (3), p. 1256–1263. Cited by: Appendix A. A. Ruszczyński (2010) Risk-averse dynamic programming for markov decision processes. Math. Program. 125 (2), p. 235–261. External Links: ISSN 0025-5610 Cited by: Appendix A. A. Rutherford, B. Ellis, M. Gallici, J. Cook, A. Lupu, G. Ingvarsson, T. Willi, R. Hammond, A. Khan, C. S. de Witt, A. Souly, S. Bandyopadhyay, M. Samvelyan, M. Jiang, R. T. Lange, S. Whiteson, B. Lacerda, N. Hawes, T. Rocktäschel, C. Lu, and J. N. Foerster (2024) JaxMARL: multi-agent rl environments and algorithms in jax. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track, Cited by: §F.2, §5.2, §5. L. S. Shapley (1953) Stochastic games*. Proceedings of the National Academy of Sciences 39 (10), p. 1095–1100. External Links: Document, Link, https://w.pnas.org/doi/pdf/10.1073/pnas.39.10.1095 Cited by: §2. S. Shen, C. Ma, C. Li, W. Liu, Y. Fu, S. Mei, X. Liu, and C. Wang (2023) RiskQ: risk-sensitive multi-agent reinforcement learning value factorization. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Red Hook, NY, USA. Cited by: Appendix A. Y. Shen, M. J. Tobia, T. Sommer, and K. Obermayer (2014) Risk-sensitive reinforcement learning. Neural Computation 26 (7), p. 1298–1328. External Links: ISSN 0899-7667, Document, Link, https://direct.mit.edu/neco/article-pdf/26/7/1298/923875/neco_a_00600.pdf Cited by: Appendix A. L. Shi, E. Mazumdar, Y. Chi, and A. Wierman (2024) Sample-efficient robust multi-agent reinforcement learning in the face of environmental uncertainty. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. Cited by: Appendix A. S. Singh, J. Lacotte, A. Majumdar, and M. Pavone (2018) Risk-sensitive inverse reinforcement learning via semi- and non-parametric methods. Int. J. Rob. Res. 37 (13–14), p. 1713–1740. External Links: ISSN 0278-3649, Link, Document Cited by: Appendix A. O. Slumbers, D. H. Mguni, S. B. Blumberg, S. McAleer, Y. Yang, and J. Wang (2023) A game-theoretic framework for managing risk in multi-agent systems. In Proceedings of the 40th International Conference on Machine Learning, ICML’23. Cited by: Appendix A. S. Sokota, R. D’Orazio, J. Z. Kolter, N. Loizou, M. Lanctot, I. Mitliagkas, N. Brown, and C. Kroer (2023) A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. In The Eleventh International Conference on Learning Representations, External Links: Link Cited by: Appendix A. J. Tsitsiklis and B. Van Roy (1996) Analysis of temporal-diffference learning with function approximation. In Advances in Neural Information Processing Systems, M.C. Mozer, M. Jordan, and T. Petsche (Eds.), Vol. 9, p. . External Links: Link Cited by: Appendix A. E. van Damme (1987) Stability and perfection of nash equilibria. Springer-Verlag, Berlin. Cited by: §4.2. B. Wang, Y. Yan, and J. Fan (2021) Sample-efficient reinforcement learning for linearly-parameterized MDPs with a generative model. In Advances in Neural Information Processing Systems, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan (Eds.), External Links: Link Cited by: Appendix A. Y. Wang, Q. Liu, Y. Bai, and C. Jin (2023) Breaking the curse of multiagency: provably efficient decentralized multi-agent rl with function approximation. In Proceedings of Thirty Sixth Conference on Learning Theory, G. Neu and L. Rosasco (Eds.), Proceedings of Machine Learning Research, Vol. 195, p. 2793–2848. External Links: Link Cited by: Appendix A. Z. Wang, Y. Shen, M. M. Zavlanos, and K. H. Johansson (2024) Learning of nash equilibria in risk-averse games. In 2024 American Control Conference (ACC), Vol. , p. 3270–3275. External Links: Document Cited by: Appendix A. L. Yang and M. Wang (2019) Sample-optimal parametric q-learning using linearly additive features. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, K. Chaudhuri and R. Salakhutdinov (Eds.), Proceedings of Machine Learning Research, Vol. 97, p. 6995–7004. External Links: Link Cited by: Appendix A. A. Yekkehkhany, T. Murray, and R. Nagi (2020) Risk-averse equilibrium for games. External Links: 2002.08414, Link Cited by: Appendix A. A. Zanette, D. Brandfonbrener, E. Brunskill, M. Pirotta, and A. Lazaric (2020) Frequentist regret bounds for randomized least-squares value iteration. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, S. Chiappa and R. Calandra (Eds.), Proceedings of Machine Learning Research, Vol. 108, p. 1954–1964. External Links: Link Cited by: Appendix A. K. Zhang, T. SUN, Y. Tao, S. Genc, S. Mallya, and T. Basar (2020) Robust multi-agent reinforcement learning with model uncertainty. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.), Vol. 33, p. 10571–10583. External Links: Link Cited by: Appendix A. K. Zhang, Z. Yang, and T. Başar (2021) Multi-agent reinforcement learning: a selective overview of theories and algorithms. In Handbook of Reinforcement Learning and Control, K. G. Vamvoudakis, Y. Wan, F. L. Lewis, and D. Cansever (Eds.), p. 321–384. External Links: ISBN 978-3-030-60990-0, Document, Link Cited by: §1. Y. Zhang and E. Mazumdar (2025) Convergent q-learning for infinite-horizon general-sum markov games through behavioral economics. External Links: 2508.08669, Link Cited by: Appendix A, §6. D. Zhou, Q. Gu, and C. Szepesvari (2021) Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes. In Proceedings of Thirty Fourth Conference on Learning Theory, M. Belkin and S. Kpotufe (Eds.), Proceedings of Machine Learning Research, Vol. 134, p. 4532–4576. External Links: Link Cited by: Appendix A, §3. Appendix A Extended Discussion & Related Work In this section we provide a detailed discussion of related literature. Our work studies the Risk Sensitive Quantal Response Equilibrium (RQRE) introduced by Mazumdar et al. (2025), which combines risk aversion with bounded rationality to yield a class of equilibria that is computationally tractable via no-regret learning in all finite-action, finite-horizon Markov games, provided agents exhibit a sufficient degree of risk aversion and bounded rationality. Zhang and Mazumdar (2025) extended these results to discounted infinite-horizon Markov games, proving contraction of the risk-averse quantal response Bellman operator and convergence of a Q-learning algorithm under monotonicity conditions. In this work we build on this foundation by providing the first finite-sample regret guarantees for learning RQRE with linear function approximation, enabling scalability to large or continuous state spaces. Beyond this extension to function approximation, our analysis reveals an explicit dependence of the regret on the rationality and risk-sensitivity parameters, establishes that RQRE strictly generalizes existing distributionally robust equilibrium concepts, and proves Lipschitz stability of the RQRE policy map—a property that Nash equilibria provably lack—which we leverage to obtain policy convergence guarantees under approximation error. Nash equilibrium methods in Markov games. The standard solution concept when studying multi-agent interactions from a game-theoretic perspective is the Nash equilibrium (Nash, 1950): a joint policy from which no agent can improve their outcome by unilaterally deviating. In a seminal work, Hu and Wellman (2003) introduced Nash Q-learning, the first extension of single-agent Q-learning to general-sum stochastic games. The core mechanism involves agents maintaining Q-functions over joint actions and performing updates based on the assumption that all participants will adopt Nash equilibrium behavior in the stage games. However, this original formulation provides only asymptotic guarantees. Building on this, Liu et al. (2021) provided the first finite-sample guarantees by incorporating optimism into the online learning process, an exploration bonus term that allows agents to efficiently learn an accurate model of the environment from a limited number of interactions. Despite these advancements, both works are restricted to the tabular setting, whose computational and memory costs scale prohibitively with the size of the state space. Moreover, computing Nash equilibria in general-sum games is computationally intractable in general (Daskalakis, 2013). This intractability has motivated alternative solution concepts such as correlated equilibria (Aumann, 1974) and coarse correlated equilibria (Moulin and Vial, 1978), but these rely on a shared correlation device and lack individual rationalizability, meaning each agent’s learned policy carries no meaningful optimality guarantees unless all agents jointly follow the correlated recommendation. To address the scalability issues of tabular methods, Cisneros-Velarde and Koyejo (2023) proposed Nash Q-learning with Optimistic Value Iteration (NQOVI), extending the framework of Hu and Wellman (2003) to the linear function approximation regime and providing finite-sample regret bounds that scale with feature dimension rather than the size of the state space. As discussed in Section 1 & 4, a fundamental bottleneck persists: the algorithm requires solving for a Nash equilibrium at every stage game and every episode, inheriting both computational intractability and the instability of the Nash correspondence under payoff perturbations (Example 3). In the function approximation setting, where Q-values are necessarily estimated with error, this brittleness is especially problematic. Bounded Rationality and Risk Aversion. Bounded rationality has a long history in behavioral game theory, where it was introduced to better predict the strategic behavior of human decision-makers known to be imperfect optimizers (McKelvey and Palfrey, 1995; Erev and Roth, 1998; Goeree and Holt, 1999). The standard formalization replaces exact best responses with quantal responses—stochastic policies that assign higher probability to higher payoff actions. In the context of multi-agent reinforcement learning, this modeling choice offers several important benefits. First, it provides a principled equilibrium selection since entropy-regularized response functions yield a unique, smooth equilibrium for any finite game, resolving the multiplicity and discontinuity issues inherent to Nash equilibrium (McKelvey and Palfrey, 1995). Second, bounded rationality reduces sensitivity to the approximation errors and non-stationarity unavoidable in learning settings, producing policies that trade off optimality against stability. Third, this formulation aligns naturally with modern reinforcement learning, where entropy-regularized objectives are widely employed as components of coherent decision-theoretic frameworks (Haarnoja et al., 2018; Sokota et al., 2023; Mertikopoulos and Sandholm, 2016). Incorporating risk aversion addresses fundamental limitations of purely expected utility maximizing agents. Risk-sensitive objectives provide a principled mechanism for promoting safety and reliability by discouraging policies that achieve high average performance at the cost of rare but catastrophic outcomes, a failure mode that is especially pronounced in strategic, non-stationary environments. In game-theoretic settings, risk aversion acts as a form of robustification: by penalizing outcome variability, agents become less sensitive to modeling error, finite-sample noise, and strategic misspecification of opponents (Mazumdar et al., 2025; Lanzetti et al., 2025). This can further stabilize learning by biasing agents towards equilibria with lower variance and more predictable joint behavior, ultimately improving generalization across opponents and environments. We refer the reader to Mazumdar et al. (2025) who provide a thorough exposition and history of these concepts, and their use in Markov games. Risk sensitive multi-agent reinforcement learning. Our work leverages risk-aversion, where policies prefer actions with more certain outcomes in exchange for potentially lower expected return. Risk sensitivity in decision-making has its origins in Markov decision processes (Howard and Matheson, 1972), dynamic programming (Ruszczyński, 2010), and optimal control (Hernández-Hernández and Marcus, 1996), with a subsequent line of work integrating risk sensitivity into reinforcement learning (Shen et al., 2014; Heger, 1994; Mazumdar et al., 2017; Ratliff and Mazumdar, 2019; Singh et al., 2018; Lacotte et al., 2018). This work focuses on risk in multi-agent reinforcement learning. From a theoretical point of view, most existing works differ in the source of risk they address and make varying structural assumptions. Wang et al. (2024) considers risk-aversion to randomness in the stochastic payoffs via the conditional value at risk and requires strong monotonicity of the risk-averse game to guarantee convergence to a unique Nash equilibrium. Yekkehkhany et al. (2020) studies risk-aversion to the randomness induced by a population of mixed strategies of other agents in stochastic games, proving existence of equilibria in all finite games. Slumbers et al. (2023) considers risk-aversion to opponents’ strategies by regularizing each agent’s utility with the variance induced by the other agents’ actions, and proves existence of their equilibrium concept, but the resulting formulation lacks tractability for general games. Lanzetti et al. (2025) takes a complementary approach, proposing a strategically robust equilibrium in which each agent optimizes against the worst-case opponent behavior within an ambiguity set, defined using optimal transport, and shows that such equilibria exist under the same assumptions as Nash equilibria and interpolate between Nash and maximin strategies. While these works focus on theoretical guarantees, recent empirical studies suggest risk-sensitive techniques extend to function approximators such as neural networks (Qiu et al., 2021; Shen et al., 2023). A related but distinct line of work is robust multi-agent reinforcement learning (Shi et al., 2024; Zhang et al., 2020; McMahan et al., 2024), which primarily addresses environmental uncertainty and worst-case parameters. Linear function approximation in RL and Markov games. Foundational work by Tsitsiklis and Van Roy (1996) established asymptotic convergence guarantees in reinforcement learning algorithms with linear function approximation. Early results in providing finite-sample guarantees with linear function approximation was provided by Munos and Szepesvári (2008) studying fitted-value iteration under the assumption of access to a generative model of the environment. More recently, Jin et al. (2020) provided a provably sample efficient algorithm for linear MDPs in an online setting using optimism. Zhou et al. (2021) further refined these results, obtaining nearly minimax-optimal guarantees. Subsequently, linear function approximation has been extensively studied in the single-agent setting (Yang and Wang, 2019; Wang et al., 2021; Eaton et al., 2025; Zanette et al., 2020). Although less explored, extending these approaches to Markov games has attracted growing attention. The first line of works accomplished this in the two-player zero-sum setting (Chen et al., 2022; Qiu et al., 2022). Most recently, concurrent works Wang et al. (2023) and Cui et al. (2023) introduced independent linear function approximation to simultaneously address large state spaces while breaking the curse of multi-agents, achieving sample complexities polynomial in the number of agents rather than exponential. Dai et al. (2024) further refined these results with improved convergence rates. Most relevant to our work, Cisneros-Velarde and Koyejo (2023) extended Nash Q-learning (Hu and Wellman, 2003) to the linear function approximation regime, providing finite-sample regret bounds that scale with the feature dimension rather than the size of the state space. However, their algorithm requires solving for a Nash equilibrium at every stage game, inheriting both the computational intractability of Nash in general-sum games and its brittleness under payoff perturbations (as we show in Example 3). Moreover, Nash equilibria are not guaranteed to be unique in general-sum games, introducing an equilibrium selection problem that is particularly problematic under function approximation, where Q-values are necessarily estimated with error. In contrast, RQRE yields a unique, smooth equilibrium that is Lipschitz continuous in estimated payoffs (Corollary 2), and is individually rationalizable in the sense that each agent’s learned Q-function carries meaningful optimality guarantees independent of whether other agents follow the equilibrium. Beyond the choice of equilibrium concept, our analysis introduces new technical challenges not present in Cisneros-Velarde and Koyejo (2023): we must bound the equilibrium approximation error incurred by computing an approximate RQRE at each stage in terms of the risk-aversion and bounded rationality parameters, and account for the additional approximation error introduced by the risk operators. Appendix B RQRE-OVI Regret Bounds In this appendix section, we prove the main regret results (Theorem 2, Corollary 1). B.1 Proof Roadmap & Comparison to Prior Art This section provides a high-level overview of the proof of Theorem 2 and highlights the key differences relative to prior analyses of optimistic value iteration in single-agent reinforcement learning and Nash Q-learning in Markov games (Cisneros-Velarde and Koyejo, 2023). Regret definition. Recall that the regret is defined via the episode-wise exploitability gap: Δk=maxi∈[n](Vi,1(sBRi(π−ik),π−ik;s0)−Vi,1(πk;s0)),regret(K)=∑k=1KΔk. _k= _i∈[n] (V_i,1(sBR_i( _-i^k), _-i^k;s_0)-V_i,1(π^k;s_0) ), *regret(K)= _k=1^K _k. (10) Proof Sketch in Four Steps. The proof proceeds through four main steps. Step 1: Optimistic Value Estimation under Risk Operators. The algorithm maintains a linear approximation of the action-value functions Qi,hk(x,a)=min⟨wi,hk,ϕ(x,a,h)⟩+βϕ(x,a,h)⊤(Λhk)−1ϕ(x,a,h),B,Q_i,h^k(x,a)= \ w_i,h^k,φ(x,a,h) +β φ(x,a,h) ( _h^k)^-1φ(x,a,h),\,B \, (11) where the second term is the exploration bonus and Λhk _h^k is the ridge regression covariance matrix. The first key technical step establishes an optimism property. Lemma 2 shows that with high probability Qi,hk(x,a)≥ri,h(x,a)+ρi,h(Vi,h+1(πh+1k;⋅))−(ε+L(ε+ε)).Q_i,h^k(x,a)≥ r_i,h(x,a)+ _i,h env (V_i,h+1( _h+1^k;·) )- ( _ env+L_ env( _ pol+ _ eq) ). (12) Compared to the standard optimistic Bellman inequality used in risk-neutral RL, this bound includes additional approximation terms arising from (i)(i) estimation error ε _ env in the environment risk operator, (ii)(i) approximation error ε _ pol in policy-risk evaluation, (iii)(i) error in the stage equilibrium solver ε _ eq. These errors propagate through the environment risk operator via its Lipschitz constant L_ env. Step 2: Uniform Concentration via Covering Numbers. The second step controls the statistical complexity of the induced value-function class. This is formalized in Lemma 1. In single-agent linear MDP analyses, concentration bounds often rely on self-normalized martingale inequalities that lead to a linear-bandit style argument. In contrast, the present setting requires controlling a much richer class of value functions. Specifically, the regression targets depend on the composition Q↦π~h(⋅∣x;Q)↦Vi,h+1(⋅;π~)↦ρi,h(Vi,h+1),Q\; \; π_h(· x;Q)\; \;V_i,h+1(·; π)\; \; _i,h e(V_i,h+1), (13) where π~h π_h is the approximate RQRE policy computed from Q. Since the equilibrium policy depends on the current estimate Q, the induced value functions form a data-dependent function class. Controlling concentration therefore requires a uniform bound over this class. To accomplish this, the proof constructs an ε -cover of the induced value-function class i,hkV_i,h^k and bounds its covering number (⋅)N(·). Indeed, since the equilibrium policy depends on the current estimate Q, the resulting value functions form a data-dependent class. Lemma 1 bounds the covering number of this class, yielding log(ϵ,i,hk,∥⋅∥∞)=~(d2) (ε,V_i,h^k,\|·\|_∞)= O(d^2) (14) reflecting the need to simultaneously control (i)(i) the linear predictor w, (ii)(i) the bonus term involving (Λhk)−1( _h^k)^-1, and (iii)(i) the equilibrium mapping Q↦π~Q π. This bound determines the confidence radius β used in the optimistic value estimates. This larger covering number leads to a larger confidence radius β, which ultimately yields a regret bound with higher dependence on the feature dimension d than in the single-agent linear MDP case. Step 3: Incorporating Equilibrium Approximation. The third ingredient shows how the stage-game equilibrium solver error enters the regret bound. Lemma 3 proves that the value accuracy guarantee of the approximate RQRE solver translates into an additive error term in the exploitability gap. Combining this lemma with the optimism property yields a bound on the per-episode exploitability gap in terms of the cumulative exploration bonuses along the trajectory plus an additive approximation budget. Step 4: Performance Difference Decomposition & Sum of Bonuses. Fix episode k and let i⋆∈argmaxi(Vi,1(sBRi(π−ik),π−ik;s0)−Vi,1(πk;s0)).i ∈ _i (V_i,1(sBR_i( _-i^k), _-i^k;s_0)-V_i,1(π^k;s_0) ). (15) Define the deviation policy πk,br=(sBRi⋆(π−i⋆k),π−i⋆k)π^k,br=(sBR_i ( _-i ^k), _-i ^k). For each stage h, define Δk,h(x)=Vi⋆,h(πk,br;x)−Vi⋆,h(πk;x) _k,h(x)=V_i ,h(π^k,br;x)-V_i ,h(π^k;x). A stage-wise recursion shows Δk,h(x)≤(advantage term)+[Δk,h+1(xh+1)]. _k,h(x)≤(advantage term)+E[ _k,h+1(x_h+1)]. (16) Using the optimism property and the approximate equilibrium guarantee, the advantage term can be bounded by βϕ(xhk,ahk,h)⊤(Λhk)−1ϕ(xhk,ahk,h)+ε.β φ(x_h^k,a_h^k,h) ( _h^k)^-1φ(x_h^k,a_h^k,h)+ _ eq. (17) This yields a bound on the exploitability gap in terms of the cumulative bonuses along the trajectory. Next, we bound the sum of bonuses. Indeed, summing the recursion over h=1,…,Hh=1,…,H yields Δk≲∑h=1Hβϕ(xhk,ahk,h)⊤(Λhk)−1ϕ(xhk,ahk,h)+H(ε+L(ε+ε)). _k _h=1^Hβ φ(x_h^k,a_h^k,h) ( _h^k)^-1φ(x_h^k,a_h^k,h)+H ( _ env+L_ env( _ pol+ _ eq) ). (18) Summing over episodes and applying the elliptical potential lemma gives ∑k,hϕ(xhk,ahk,h)⊤(Λhk)−1ϕ(xhk,ahk,h)=~(KdH). _k,h φ(x_h^k,a_h^k,h) ( _h^k)^-1φ(x_h^k,a_h^k,h)= O( KdH). (19) Final Bound Construction. The remaining step of the proof bounds the cumulative exploration bonuses along the trajectory. This is done using the standard elliptical potential argument commonly used in analyses of optimistic value iteration (Jin et al., 2020; Cisneros-Velarde and Koyejo, 2023). Indeed, combining this with the covering-number bound on β yields the final regret bound regret(K)≤~(LBKd3H3)+KH(ε+L(ε+ε)). *regret(K)≤ O (L_ envB Kd^3H^3 )+KH ( _ env+L_ env( _ pol+ _ eq) ). (20) Comparison to Nash Q-Learning. The closest related analysis is that of Cisneros-Velarde and Koyejo (2023), which studies optimistic value iteration for risk-neutral Markov games with linear function approximation. Three key differences distinguish the present analysis: 1. Explicit equilibrium approximation. Their algorithm assumes access to a Nash equilibrium oracle for each stage game. In contrast, our algorithm computes an approximate RQRE which are known to be efficiently computable via no-regret algorithms, introducing an additional error term ε _ eq that must be propagated through the dynamic programming recursion. 2. Risk-sensitive Bellman operators. The Bellman operators involve nonlinear risk operators acting on the continuation values, as opposed to risk-neutral expectations. As a result, the analysis must control the propagation of estimation and equilibrium errors through these operators, leading to the Lipschitz amplification factor L_ env and additional approximation terms in the regret bound. 3. Data-Dependent Risk-Induced Value Function Class. Since the equilibrium policy is computed from the current value estimates, the continuation values depend on the data-dependent mapping Q↦π~(Q)Q π(Q), which then are transformed via the risk measure ρ e. This requires constructing the appropriate vale function class that is induced by the risk operators. Controlling the resulting function class requires a covering-number argument for the induced value functions. Together these features lead to a regret analysis that differs from the Nash-Q case (and single agent case) while yielding guarantees for an algorithm that is computationally realizable in practice. Comparison to Single-Agent Linear MDP Analyses. In single-agent linear MDP analyses, the Bellman target depends only on a linear expectation of the next-stage value function. This structure enables sharper self-normalized concentration arguments and typically leads to regret bounds with smaller dimension dependence. In contrast, the regression targets in the present setting involve the composition Q↦π~h(⋅∣x;Q)↦Vi,h+1(⋅;π~)↦ρi,h(Vi,h+1),Q\; \; π_h(· x;Q)\; \;V_i,h+1(·; π)\; \; _i,h env(V_i,h+1), (21) where π~h π_h is the approximate RQRE policy computed from Q. Controlling concentration uniformly over this induced value class requires a covering-number argument, which leads to a larger confidence radius and the higher d-dependence appearing in the regret bound. B.2 Technical Lemmas In this section, we have all the technical lemmas for the main regret results (Theorem 2). Covering Number Bounds for the Value Functions. The first technical lemma we prove is the covering number bound that accounts for both the risk measures and the data-dependent risk-induced value functions. Lemma 1 (Covering number of the induced value class). Fix (i,h)(i,h) and an episode index k. Let Λhk⪰λId _h^k λ I_d be the (random but fixed conditional on ℱk,h−1F_k,h-1) design matrix used by Algorithm 1 at stage h in episode k. Define the optimistic Q-class at stage h as follows: i,hk:=(x,a)↦min⟨w,ϕ(x,a,h)⟩+βϕ(x,a,h)⊤(Λhk)−1ϕ(x,a,h),B:‖w‖2≤B.Q_i,h^k:= \(x,a) \ w,φ(x,a,h) +β φ(x,a,h) ( _h^k)^-1φ(x,a,h),\;B \:\; w _2≤ B \. Additionally, define the induced policy-evaluated value class as follows: i,hk:=x↦V^i,hϵi(π;x;Q):Q∈i,hk,π(⋅|x)∈Δ().V_i,h^k:= \x V_i,h _i(π;x;Q):\;Q _i,h^k,\ π(·|x)∈ (A) \. Then for any ε∈(0,B] ∈(0,B], under the metric dist∞(V,V′):=supx|V(x)−V′(x)|dist_∞(V,V ):= _x|V(x)-V (x)|, log(ε,i,hk,dist∞)≤dlog(1+4Bε)+d2log(1+8dβ2λε2). ( ,V_i,h^k,dist_∞ )≤ d (1+ 4B )+d^2 (1+ 8 d\,β^2λ\, ^2 ). (22) Proof. We proceed in four steps. Step 1: Lipschitz composition reduces the problem to covering i,hkQ_i,h^k. Fix any Q,Q′∈i,hkQ,Q _i,h^k and any Markov π. First observe that for each fixed (i,h)∈[n]×[H](i,h)∈[n]×[H] and any Markov π, the map Q↦V^i,hϵi(π;⋅;Q)Q V_i,h _i(π;·;Q) is 1-Lipschitz in sup-norm: supx∈|V^i,hϵi(π;x;Q)−V^i,hϵi(π;x;Q′)|≤‖Q−Q′‖∞. _x | V_i,h _i(π;x;Q)- V_i,h _i(π;x;Q ) |≤ Q-Q _∞. For the dual-representation-based V V, this holds because it is a supremum of expectations of Q over a set of distributions plus an additive regularizer. By this 1-Lipschitz property, we have the bound dist∞(V^i,hϵi,τi(π;⋅;Q),V^i,hϵi,τi(π;⋅;Q′))≤‖Q−Q′‖∞.dist_∞ ( V_i,h _i, _i(π;·;Q),\ V_i,h _i, _i(π;·;Q ) )≤ Q-Q _∞. Therefore, any ε -cover of i,hkQ_i,h^k in ∥⋅∥∞\|·\|_∞ pushes forward to an ε -cover of i,hkV_i,h^k in dist∞(⋅,⋅)dist_∞(·,·), and hence (ε,i,hk,dist∞(⋅,⋅))≤(ε,i,hk,∥⋅∥∞).N( ,V_i,h^k,dist_∞(·,·)) ( ,Q_i,h^k,\|·\|_∞). So it suffices to bound the covering number of i,hkQ_i,h^k. Step 2: Separate the parametric linear part and the bonus part. For each w define the unclipped function fw(x,a):=⟨w,ϕ(x,a,h)⟩+bhk(x,a),bhk(x,a):=βϕ(x,a,h)⊤(Λhk)−1ϕ(x,a,h).f_w(x,a):= w,φ(x,a,h) +b_h^k(x,a), b_h^k(x,a):=β φ(x,a,h) ( _h^k)^-1φ(x,a,h). Let T(u):=minu,BT(u):= \u,B\ be the clipping operator. Then Qw:=T∘fw∈i,hkQ_w:=T f_w _i,h^k. Since T is 1-Lipschitz on ℝR, we have that ‖Qw−Qw′‖∞=‖T∘fw−T∘fw′‖∞≤‖fw−fw′‖∞. Q_w-Q_w _∞= T f_w-T f_w _∞≤ f_w-f_w _∞. Also, since bhkb_h^k does not depend on w, we deduce that ‖fw−fw′‖∞=supx,a|⟨w−w′,ϕ(x,a,h)⟩|≤‖w−w′‖2⋅supx,a‖ϕ(x,a,h)‖2≤‖w−w′‖2, f_w-f_w _∞= _x,a | w-w ,φ(x,a,h) |≤ w-w _2· _x,a φ(x,a,h) _2≤ w-w _2, using ‖ϕ‖≤1 φ ≤ 1. Thus, if we cover the Euclidean ball w:‖w‖2≤B\w: w _2≤ B\ in ℓ2 _2 to radius ε , we automatically get an ε -cover of i,hkQ_i,h^k in ∥⋅∥∞\|·\|_∞ provided the bonus term is fixed. However, because the proof must hold uniformly over all possible random matrices Λhk _h^k that can arise adaptively along the algorithm’s trajectory, we incorporate a standard operator-covering argument: we bound the number of distinguishable bonus shapes ϕ⊤(Λhk)−1ϕφ ( _h^k)^-1φ over all Λ in the admissible set. Step 3: Cover the linear predictors (the dlog(1+4B/ε)d (1+4B/ ) term). Let :=w∈ℝd:‖w‖2≤BW:=\w ^d: w _2≤ B\. A standard volumetric bound for Euclidean balls gives an ε -net ε⊂W_ of size at most |ε|≤(1+2Bε)d≤(1+4Bε)d,|W_ |≤ (1+ 2B )^d≤ (1+ 4B )^d, since ε≤B ≤ B For any w∈w , pick w~∈ε w _ with ‖w−w~‖2≤ε w- w _2≤ . Then for all (x,a)∈×(x,a) ×A, we have that |⟨w,ϕ⟩−⟨w~,ϕ⟩|=|⟨w−w~,ϕ⟩|≤‖w−w~‖2‖ϕ‖2≤ε. | w,φ - w,φ |= | w- w,φ |≤ w- w _2 φ _2≤ . Thus, if the bonus term were fixed, this would already provide an ε -cover. Step 4: Cover the bonus shapes over admissible Λ . Define the normalized feature vectors u(x,a):=ϕ(x,a,h)∈ℝd,such that ‖u(x,a)‖2≤1.u(x,a):=φ(x,a,h) ^d, that u(x,a) _2≤ 1. For any positive semi-definite matrix M⪰0M 0, define the quadratic form qM(u):=u⊤Mu.q_M(u):=u Mu. Here M=(Λhk)−1M=( _h^k)^-1 and Λhk⪰λId _h^k λ I_d implies 0⪯M⪯λ−1Id,and‖M‖2≤λ−1.0 M λ^-1I_d, M _2≤λ^-1. We need a finite set ℳηM_η such that for every admissible M there exists M~∈ℳη M _η with sup‖u‖≤1|u⊤Mu−u⊤M~u|≤η. _ u ≤ 1 |u Mu-u Mu |≤η. Note that for symmetric M−M~M- M, the bound holds: sup‖u‖≤1|u⊤(M−M~)u|=‖M−M~‖2. _ u ≤ 1|u (M- M)u|= M- M _2. Thus it suffices to build an η-net in operator norm for the set M:0⪯M⪯λ−1I\M:0 M λ^-1I\. A standard covering bound for bounded subsets of ℝd×dR^d× d gives an η-net in Frobenius norm of size at most (1+2Rη)d2,R:=sup‖M‖F≤dλ−1. (1+ 2Rη )^d^2, R:= M _F≤ d\,λ^-1. Since ‖A‖2≤‖A‖F A _2≤ A _F, an η-net in Frobenius norm is also an η-net in operator norm. Therefore there exists ℳηM_η with |ℳη|≤(1+2dλ−1η)d2.|M_η|≤ (1+ 2 d\,λ^-1η )^d^2. Next we connect η to the bonus scale. First, the bonus uses u⊤Mu u Mu. For any nonnegative scalars s,ts,t, we have that |s−t|≤|s−t|. | s- t |≤ |s-t|. Hence, if sup‖u‖≤1|u⊤Mu−u⊤M~u|≤η _ u ≤ 1|u Mu-u Mu|≤η, then sup‖u‖≤1|u⊤Mu−u⊤M~u|≤η. _ u ≤ 1 | u Mu- u Mu |≤ η. Multiplying by β gives a bonus error at most βηβ η. To make this bonus error at most ε , choose η=(ε/β)2η=( /β)^2. Then log|ℳη|≤d2log(1+2dλ−1(ε/β)2)=d2log(1+2dβ2λε2). |M_η|≤ d^2 (1+ 2 d\,λ^-1( /β)^2 )=d^2 (1+ 2 d\,β^2λ\, ^2 ). Adjusting constants—replacing 22 by 88—to absorb the earlier ε -splitting and the clipping/Lipschitz steps gives log|ℳη|≤d2log(1+8dβ2λε2). |M_η|≤ d^2 (1+ 8 d\,β^2λ\, ^2 ). Combine nets. Take the Cartesian product net ε×ℳ(ε/β)2W_ ×M_( /β)^2. For any admissible (w,M)(w,M), choose (w~,M~)( w, M) from the nets. Then the linear part incurs at most ε error in ∥⋅∥∞\|·\|_∞, and the bonus part incurs at most ε error in ∥⋅∥∞\|·\|_∞. By triangle inequality, the unclipped f differs by at most 2ε2 , and clipping is 1-Lipschitz so the clipped Q differs by at most 2ε2 . Replacing ε by ε/2 /2 yields the stated bound (22). ∎ Optimism via bonus term and approximations. Next we construct a technical lemma on bounding the bonus term and approximation errors that arise from the risk measures and equilibrium computation. Fix (i,h)∈[n]×[H](i,h)∈[n]×[H]. Let (xht,aht)(x_h^t,a_h^t) be the sequence of state-action pairs observed at stage h up to the current episode index k−1k-1 (across episodes), and define Λhk:=λId+∑t<kϕ(xht,aht,h)ϕ(xht,aht,h)⊤. _h^k:=λ I_d+ _t<kφ(x_h^t,a_h^t,h)φ(x_h^t,a_h^t,h) . Define the empirical targets as in Algorithm 1—namely, yi,ht:=ri,h(xht,aht)+ρ^i,ht(V^i,h+1ϵi,τi(πh+1t;⋅)).y_i,h^t:=r_i,h(x_h^t,a_h^t)+ ρ_i,h^\,t ( V_i,h+1 _i, _i(π^t_h+1;·) ). Let wi,hkw_i,h^k be the ridge regression estimate wi,hk:=(Λhk)−1∑t<kϕ(xht,aht,h)yi,ht.w_i,h^k:=( _h^k)^-1 _t<kφ(x_h^t,a_h^t,h)\,y_i,h^t. Let the optimistic estimate be Qi,hk(x,a):=min⟨wi,hk,ϕ(x,a,h)⟩+βϕ(x,a,h)⊤(Λhk)−1ϕ(x,a,h),B.Q_i,h^k(x,a):= \ w_i,h^k,φ(x,a,h) +β φ(x,a,h) ( _h^k)^-1φ(x,a,h),\;B \. Lemma 2 (Uniform self-normalized confidence and optimism). For β=cBd2Hιβ=cB d^2H\, as in Theorem 2, with probability at least 1−δ1-δ simultaneously for all (i,h,k,x,a)∈[n]×[H]×[K]×(i,h,k,x,a)∈[n]×[H]×[K]×X×A, the lower bound holds: Qi,hk(x,a)≥ri,h(x,a)+ρi,h(Vi,h+1ϵi(πh+1k;⋅))−(ε+L(ε+ε)).Q_i,h^k(x,a)≥ r_i,h(x,a)+ _i,h env (V_i,h+1 _i(π^k_h+1;·) )- ( _ env+L_ env( _ pol+ _ eq) ). (23) Proof. The proof has three parts: (1) express the true Bellman target in the linear form, (2) establish a uniform self-normalized confidence bound using Lemma 1, (3) translate the approximation errors and risk-Lipschitz errors into the additive term. Throughout, fix (i,h)∈[n]×[H](i,h)∈[n]×[H] and condition on the filtration up to the start of stage h in episode k so that Λhk _h^k is fixed. Part 1: linear Bellman target under realizability. By Assumption (a), for any bounded measurable function g:→ℝg:X , x′∼h(⋅|x,a)[g(x′)]=∫g(x′)h(dx′|x,a)=⟨ϕ(x,a,h),∫g(x′)μh(x′)x′⟩. *E_x _h(·|x,a)[g(x )]= g(x )P_h(dx |x,a)= φ(x,a,h),\; g(x ) _h(x )dx . Define the vector ζh(g):=∫g(x′)μh(x′)x′∈ℝd. _h(g):= g(x ) _h(x )\,dx ^d. Then the expected one-step (non-risk) backup is linear in ϕφ: ri,h(x,a)+[g(x′)|x,a]=⟨ϕ(x,a,h),θi,h+ζh(g)⟩.r_i,h(x,a)+ *E[g(x )|x,a]= φ(x,a,h), _i,h+ _h(g) . Now the environment risk operator ρi,h _i,h e is applied to the random next-state value g(xh+1)g(x_h+1) (or an equivalent lifted representation). We do not need ρi,h _i,h e itself to be linear; we only need concentration for the scalar targets and Lipschitzness to control errors, which we do below. Part 2: self-normalized confidence uniformly over the induced value class. Define the (ideal) target at time t: y¯i,ht:=ri,h(xht,aht)+ρi,h(Vi,h+1ϵi,τi(πh+1t;⋅)). y_i,h^t:=r_i,h(x_h^t,a_h^t)+ _i,h e (V_i,h+1 _i, _i(π^t_h+1;·) ). Define the target noise: ηt:=yi,ht−y¯i,ht. _t:=y_i,h^t- y_i,h^t. We will show ηt _t is uniformly bounded and forms a martingale difference sequence, then apply the self-normalized inequality with a union bound over a cover. First, by assumption, the rewards lie in [0,1][0,1] and all value functions are in [0,B][0,B]. The monotonicity plus Lipschitz continuity assumption imply ρi,h(X) _i,h e(X) is bounded whenever X is bounded; in particular, there is a constant—absorbed into B by clipping—such that |ρi,h(V)|≤B| _i,h e(V)|≤ B when 0≤V≤B0≤ V≤ B. Similarly, by assumption, we have that ρ^i,ht(V)≤ρi,h(V) ρ_i,h^\,t(V)≤ _i,h e(V). Thus both y¯i,ht y_i,h^t and yi,hty_i,h^t lie in an interval of length (B)O(B), hence |ηt|≤B| _t|≤ B (up to an absolute constant factor absorbed into c). Second, ηt _t is measurable with respect to the randomness at episode/stage t and satisfies the standard conditional mean-zero property needed for the self-normalized bound once we condition on the sigma-field generated by all past data: the only randomness in ηt _t is through the empirical dual approximation and policy approximation, both of which are treated as bounded perturbations; hence we can apply a bounded-differences martingale concentration. Concretely, we use the standard self-normalized bound stated as: for any fixed δ′∈(0,1)δ ∈(0,1), with probability at least 1−δ′1-δ , ∀x,a:|⟨whi,k−whi,⋆,ϕ(x,a,h)⟩|≤βϕ(x,a,h)⊤(Λhk)−1ϕ(x,a,h),∀\;x,a: | w_h^i,k-w_h^i, ,φ(x,a,h) |≤β φ(x,a,h) ( _h^k)^-1φ(x,a,h), (24) where whi,⋆w_h^i, is the (unknown) linear parameter corresponding to the ideal targets y¯i,ht y_i,h^t and β scales as Bdlog(⋅)B d (·). To make (24) hold uniformly over all time indices and the induced value class (because the targets depend on V V which depends on past data), we apply a union bound over an ε -net of the induced value class. Lemma 1 gives the required finite cover size, which yields the logarithmic term ι=log(nHKδ)+dlog(1+Kλ) = ( nHKδ )+d (1+ Kλ ) appearing in the theorem statement. Choosing β=cBd2Hιβ=cB d^2H\, (absorbing all absolute constants) ensures (24) holds simultaneously for all (i,h,k,x,a)∈[n]×[H]×[K]×(i,h,k,x,a)∈[n]×[H]×[K]×X×A with probability at least 1−δ1-δ. Part 3: translate approximation errors and derive optimism. By construction, we have that Qhi,k(x,a)≥⟨whi,k,ϕ(x,a,h)⟩Q_h^i,k(x,a)≥ w_h^i,k,φ(x,a,h) and Qhi,k(x,a)≥⟨whi,k,ϕ(x,a,h)⟩+βϕ⊤(Λhk)−1ϕ−(U(x,a)−B)+,Q_h^i,k(x,a)≥ w_h^i,k,φ(x,a,h) +β φ ( _h^k)^-1φ-(U(x,a)-B)_+, where U(x,a):=⟨whi,k,ϕ(x,a,h)⟩+βϕ⊤(Λhk)−1ϕU(x,a):= w_h^i,k,φ(x,a,h) +β φ ( _h^k)^-1φ and (z)+:=minz,0(z)_+:= \z,0\ as usual. Since clipping only decreases values above B and all true quantities are within [0,B][0,B] by assumption, clipping does not harm the lower bound we are establishing. Using (24), we have that ⟨whi,k,ϕ(x,a,h)⟩+βϕ⊤(Λhk)−1ϕ≥⟨whi,⋆,ϕ(x,a,h)⟩. w_h^i,k,φ(x,a,h) +β φ ( _h^k)^-1φ≥ w_h^i, ,φ(x,a,h) . But ⟨whi,⋆,ϕ(x,a,h)⟩ w_h^i, ,φ(x,a,h) is the linear prediction of the ideal target y¯ y at (x,a)(x,a), i.e. ⟨whi,⋆,ϕ(x,a,h)⟩=ri,h(x,a)+ρi,h(Vi,h+1ϵi,τi(πh+1k;⋅)), w_h^i, ,φ(x,a,h) =r_i,h(x,a)+ _i,h e (V_i,h+1 _i, _i(π^k_h+1;·) ), by definition of whi,⋆w_h^i, for the ideal target. It remains to incorporate the approximation errors (d,e,f) to relate the algorithm’s implemented target to the ideal target. The assumption on the risk measure gives us that for any bounded X, the bound holds: 0≤ρi,h(X)−ρ^i,hk(X)≤ε.0≤ _i,h e(X)- ρ_i,h^\,k(X)≤ _ e. Hence, we deduce that ρi,h(X)≥ρ^i,hk(X). _i,h e(X)≥ ρ_i,h^\,k(X). The bounds on the value function imply that 0≤Vi,h+1ϵi(π;x)−V^i,h+1ϵi(π;x)≤ε,0≤ V_i,h+1 _i(π;x)- V_i,h+1 _i(π;x)≤ _ pol, so by L_ env-Lipschitzness of ρi,h _i,h e, we have the bound |ρi,h(Vi,h+1ϵi(π;⋅))−ρi,h(V^i,h+1ϵi(π;⋅))|≤Lε. | _i,h e(V_i,h+1 _i(π;·))- _i,h e( V_i,h+1 _i(π;·)) |≤ L_ env _ pol. Finally, by assumption we have that the stage equilibrium computation error changes the policy-evaluated value by at most ε _ eq; again, when this error is propagated through the environment operator, it contributes at most LεL_ env _ eq. Collecting these additive losses yields exactly (23). ∎ Technical Lemmas on Equilibrium Approximation. Fix an episode k, stage h, and the realized state x:=xhkx:=x_h^k. Let QhkQ_h^k denote the optimistic stage Q-table at (h,x)(h,x) for all players. Let π~h(⋅∣x) π_h(· x) be the policy returned by the stage solver, and let πh⋆(⋅∣x) _h (· x) denote the exact stage equilibrium policy for the same stage game induced by QhkQ_h^k. Lemma 3 (Stage-solver accuracy). Assume the stage solver satisfies the value-accuracy condition from Theorem 2: for every player i∈[n]i∈[n], the estimate holds: |Vi,hϵi(π~h;x,Qhk)−Vi,hϵi(πh⋆;x,Qhk)|≤ε. |V_i,h _i ( π_h;x,Q_h^k )-V_i,h _i ( _h ;x,Q_h^k ) |\;≤\; _ eq. (25) Further assume the policy-risk value functional Vi,hϵi(⋅;x,Q)V_i,h _i(·;x,Q) is 1-Lipschitz in the payoff table in the following sense: for any two payoff tables Q,Q′Q,Q on (h,x)(h,x) and any fixed policy profile π, |Vi,hϵi(π;x,Q)−Vi,hϵi(π;x,Q′)|≤supa∈|Qi(x,a)−Qi′(x,a)|. |V_i,h _i (π;x,Q )-V_i,h _i (π;x,Q ) |≤ _a \, |Q_i(x,a)-Q _i(x,a) |. (26) Let ahk∼π~h(⋅∣x)a_h^k π_h(· x) be the action actually played by the algorithm at (h,x)(h,x), and let ahk,bra_h^k,br denote a (possibly randomized) stage-wise best-response action for the distinguished player i⋆i against π~−i⋆,h(⋅∣x) π_-i ,h(· x) with respect to the true stage payoff table Q¯hk Q_h^k (defined below). Suppose the optimistic table admits the usual decomposition: Qi,hk(x,a)=Q¯i,hk(x,a)+bhk(x,a),bhk(x,a):=βϕ(x,a,h)⊤(Λhk)−1ϕ(x,a,h),Q_i,h^k(x,a)= Q_i,h^k(x,a)+b_h^k(x,a), b_h^k(x,a):=β φ(x,a,h) ( _h^k)^-1φ(x,a,h), (27) with bhk(x,a)≥0b_h^k(x,a)≥ 0 for all a. Then the following bound holds: [Qi⋆,hk(x,ahk,br)−Qi⋆,hk(x,ahk)]≤[bhk(x,ahk)]+ε, *E [Q_i ,h^k(x,a_h^k,br)-Q_i ,h^k(x,a_h^k) ]\;≤\; *E [b_h^k(x,a_h^k) ]+ _ eq, (28) where the expectation is over the randomness in the stage solver (if any) and the action sampling. Proof. The proof proceeds in two parts: (part 1) we first show the best-response improvement is controlled by the stage equilibrium error, and then (part 2) we relate the deviation gap to an optimistic Q-advantage plus a bonus term. Part 1: Best-response improvement is controlled by the stage equilibrium error. By definition of πh⋆(⋅∣x) _h (· x) as an exact stage equilibrium for the game induced by QhkQ_h^k and the value functional Vi,hϵi(⋅;x,Qhk)V_i,h _i(·;x,Q_h^k), player i⋆i cannot improve its (policy-risk) value by a unilateral deviation at (h,x)(h,x): Vi⋆,hϵi⋆((σi⋆,π−i⋆,h⋆);x,Qhk)−Vi⋆,hϵi⋆(πh⋆;x,Qhk)≤ 0,∀σi⋆∈Δ(i⋆).V_i ,h _i (( _i , _-i ,h );x,Q_h^k )-V_i ,h _i ( _h ;x,Q_h^k )\;≤\;0, ∀ _i ∈ (A_i ). (29) Now evaluate the deviation σi⋆ _i that achieves the best response against π~−i⋆,h(⋅∣x) π_-i ,h(· x)—i.e., the deviation that generates ahk,bra_h^k,br. Add and subtract Vi⋆,hϵi⋆(π~h;x,Qhk)V_i ,h _i ( π_h;x,Q_h^k) and Vi⋆,hϵi⋆(πh⋆;x,Qhk)V_i ,h _i ( _h ;x,Q_h^k) to get that Vi⋆,hϵi⋆((σi⋆,π~−i⋆,h);x,Qhk)−Vi⋆,hϵi⋆(π~h;x,Qhk) V_i ,h _i (( _i , π_-i ,h);x,Q_h^k )-V_i ,h _i ( π_h;x,Q_h^k ) =(Vi⋆,hϵi⋆((σi⋆,π~−i⋆,h);x,Qhk)−Vi⋆,hϵi⋆((σi⋆,π−i⋆,h⋆);x,Qhk)) = (V_i ,h _i (( _i , π_-i ,h);x,Q_h^k )-V_i ,h _i (( _i , _-i ,h );x,Q_h^k ) ) (30) +(Vi⋆,hϵi⋆((σi⋆,π−i⋆,h⋆);x,Qhk)−Vi⋆,hϵi⋆(πh⋆;x,Qhk)) + (V_i ,h _i (( _i , _-i ,h );x,Q_h^k )-V_i ,h _i ( _h ;x,Q_h^k ) ) (31) +(Vi⋆,hϵi⋆(πh⋆;x,Qhk)−Vi⋆,hϵi⋆(π~h;x,Qhk)). +\; (V_i ,h _i ( _h ;x,Q_h^k )-V_i ,h _i ( π_h;x,Q_h^k ) ). (32) Observe that (31) is less than or equal to zero by (29), and (32) is less than or equal to ε _ eq by (25). Thus, we deduce that Vi⋆,hϵi⋆((σi⋆,π~−i⋆,h);x,Qhk)−Vi⋆,hϵi⋆(π~h;x,Qhk) V_i ,h _i (( _i , π_-i ,h);x,Q_h^k )-V_i ,h _i ( π_h;x,Q_h^k ) (33) ≤Vi⋆,hϵi⋆((σi⋆,π~−i⋆,h);x,Qhk)−Vi⋆,hϵi⋆((σi⋆,π−i⋆,h⋆);x,Qhk)+ε. ≤ V_i ,h _i (( _i , π_-i ,h);x,Q_h^k )-V_i ,h _i (( _i , _-i ,h );x,Q_h^k )+ _ eq. Step 2: Relating the deviation gap to an optimistic Q-advantage plus bonus. The regret proof uses the standard “optimism” relation that the optimistic table QhkQ_h^k can be written as the (model-based / fitted) estimate Q¯hk Q_h^k plus the confidence bonus bhkb_h^k, as in (27). Since Vi,hϵi(⋅;x,Q)V_i,h _i(·;x,Q) is 1-Lipschitz in Q (cf. (26)), swapping Q¯hk Q_h^k for QhkQ_h^k changes any value by at most supabhk(x,a) _ab_h^k(x,a), and in particular for the realized action ahka_h^k we obtain the pointwise bound Vi⋆,hϵi⋆((σi⋆,π~−i⋆,h);x,Qhk)−Vi⋆,hϵi⋆(π~h;x,Qhk)≥[Q¯hi⋆,k(x,ahk,br)−Q¯hi⋆,k(x,ahk)]−[bhk(x,ahk)], V_i ,h _i (( _i , π_-i ,h);x,Q_h^k )-V_i ,h _i ( π_h;x,Q_h^k )≥ *E [ Q_h^i ,k(x,a_h^k,br)- Q_h^i ,k(x,a_h^k) ]- *E [b_h^k(x,a_h^k) ], (34) where the expectation is with respect to the sampling of ahk∼π~h(⋅∣x)a_h^k π_h(· x) and ahk,bra_h^k,br induced by σi⋆ _i and π~−i⋆,h(⋅∣x) π_-i ,h(· x). Now we combine (33) and (34), and use Qhk=Q¯hk+bhkQ_h^k= Q_h^k+b_h^k from (27) to convert back to QhkQ_h^k as follows: [Qhi⋆,k(x,ahk,br)−Qhi⋆,k(x,ahk)] *E [Q_h^i ,k(x,a_h^k,br)-Q_h^i ,k(x,a_h^k) ] =[Q¯hi⋆,k(x,ahk,br)−Q¯i⋆,hk(x,ahk)]+[bhk(x,ahk,br)−bhk(x,ahk)] = *E [ Q_h^i ,k(x,a_h^k,br)- Q_i ,h^k(x,a_h^k) ]+ *E [b_h^k(x,a_h^k,br)-b_h^k(x,a_h^k) ] ≤[Q¯hi⋆,k(x,ahk,br)−Q¯hi⋆,k(x,ahk)]+[bhk(x,ahk,br)] ≤ *E [ Q_h^i ,k(x,a_h^k,br)- Q_h^i ,k(x,a_h^k) ]+ *E [b_h^k(x,a_h^k,br) ] ≤(Vi⋆,hϵi⋆((σi⋆,π~−i⋆,h);x,Qhk)−Vi⋆,hϵi⋆(π~h;x,Qhk))+[bhk(x,ahk)] ≤ (V_i ,h _i (( _i , π_-i ,h);x,Q_h^k )-V_i ,h _i ( π_h;x,Q_h^k ) )+ *E [b_h^k(x,a_h^k) ] ≤[bhk(x,ahk)]+ε, ≤ *E [b_h^k(x,a_h^k) ]+ _ eq, where the last inequality uses (33) and drops the term corresponding to (30), which is non-positive when σi⋆ _i is chosen as the stage-wise best response induced by the equilibrium operator, and the stage game is evaluated at the same optimistic table QhkQ_h^k; this is precisely the sense in which the solver returns an approximate stage equilibrium for the optimistic table. This yields (28). ∎ Remark 2 (How ε _ eq scales under common stage solvers). The theorem assumes a value-accuracy guarantee of the form (25). How ε _ eq depends on the number of inner iterations T depends on the solver and on structural properties of the stage game. (i) Strongly monotone VI (Mirror-Prox / extragradient). Suppose the stage equilibrium (RQRE) can be written as the unique solution of a variational inequality VI(F,Π)VI(F, ) over the product simplex Π:=∏iΔ(i) := _i (A_i), and that the operator F is μ-strongly monotone and L-Lipschitz (in a fixed norm). Then standard results for Mirror-Prox/extragradient yield a geometric decay of the VI gap (and hence of the value residual): ε(T)≤C0exp(−TμL), _ eq(T)≤ C_0 (- TμL ), for a constant C0C_0 depending on initialization. In entropy-regularized settings, μ typically scales with the regularization level (e.g., μ≍1/ϵmaxμ 1/ _ under the common “1ϵΦ 1ε ” convention which we adopt), while L depends on the smoothness of the payoff map and, in entropic-risk models, on τ through the curvature of the log-sum-exp operator. Consequently, the condition number κ:=L/μκ:=L/μ, and thus the required T, inherits explicit τ-dependence. Indeed, let us specialize to see the dependence. Specialize to the entropic policy-risk value (7) and entropy regularization νi(πi)=Φ(πi) _i( _i)= ( _i). Fix a stage (h,x)(h,x) and write, for each player i∈[n]i∈[n], uiπ(a−i):=∑aiπi(ai)Qi(x,ai,a−i),gi(π):=−1τilog(∑a−iπ−i(a−i)e−τiuiπ(a−i))+1ϵiΦ(πi).u_i^π(a_-i)\;:=\; _a_i _i(a_i)\,Q_i(x,a_i,a_-i),\;\;g_i(π)\;:=\;- 1 _i ( _a_-i _-i(a_-i)e^- _iu_i^π(a_-i) )+ 1 _i ( _i). Let the stage RQRE be characterized as the unique solution of the (regularized) VI over Π:=∏iΔ(i) := _i (A_i) associated with the first-order optimality conditions of minπigi(π)i=1n\ _ _ig_i(π)\_i=1^n (equivalently, a strongly monotone operator F on Π ). Assume Qi(x,a)∈[0,B]Q_i(x,a)∈[0,B] for all (i,a)∈[n]×(i,a)∈[n]×A. a. Strong monotonicity. The entropy regularizer contributes strong convexity, yielding strong monotonicity modulus μ≥1ϵmax,ϵmax:=maxi∈[n]ϵi,μ≥ 1 _ , _ := _i∈[n] _i, with respect to the ℓ1 _1 geometry on each simplex.222More precisely, −Φ(⋅)- (·) is 11-strongly convex with respect to ∥⋅∥1\|·\|_1, so the term (1/ϵi)Φ(πi)(1/ _i) ( _i) induces modulus 1/ϵi1/ _i; taking the worst case gives 1/ϵmax1/ _ . b. Lipschitzness. The entropic-risk term is a log-sum-exp smoothing of a linear map πi↦uiπ(⋅) _i u_i^π(·). Its gradient with respect to πi _i is a convex combination of payoff vectors and therefore satisfies the uniform ℓ∞ _∞ bound ‖∇πigi(π)‖∞≤B,\| _ _ig_i(π)\|_∞\;≤\;B, and, moreover, its Jacobian with respect to (πi,π−i)( _i, _-i) is Lipschitz with constant scaling as L≤cL(Bτmax+Bτmin),τmin:=miniτi,τmax:=maxiτi,L≤ c_L (B\, _ \;+\; B _ ), _ := _i _i, _ := _i _i, for an absolute constant cL>0c_L>0. The 1τmin 1 _ term comes from the curvature of the log-sum-exp map and dominates as τmin→0 _ → 0.333One convenient way to see the τ-dependence is to use that the Hessian of τ−1log∑jeτzjτ^-1 _je^τ z_j has operator norm ≤τ≤τ (with respect to ℓ∞/ℓ1 _∞/ _1), while the induced sensitivity of the soft minimization weights with respect to π−i _-i contributes a τ−1τ^-1 factor when π−i _-i enters inside the log. Consequently, the condition number κ:=L/μκ:=L/μ satisfies κ≤cLϵmax(Bτmax+Bτmin),κ≤ c_L\, _ (B\, _ + B _ ), and Mirror-Prox/extragradient yields the geometric solver error bound ε(T)≤C0exp(−Tκ)≤C0exp(−TcLϵmax(Bτmax+B/τmin)). _ eq(T)≤ C_0 (- Tκ )≤ C_0 (- Tc_L\, _ (B _ +B/ _ ) ). In particular, holding all else fixed, achieving a target ε _ eq requires T≳ϵmax(Bτmax+Bτmin)log(C0ε),T\; \; _ (B _ + B _ ) ( C_0 _ eq ), so the number of inner iterations grows on the order of 1/τmin1/ _ as τmin→0 _ → 0. (i) Vanilla No-Regret. Fix a stage (h,x)∈[H]×(h,x)∈[H]×X and a bounded action–value function Q. Define the induced finite stage payoff ui(π):=Vi,hϵi(π;x,Q),i∈[n].u_i(π)\;:=\;V_i,h _i(π;x,Q), i∈[n]. Assume that for all i∈[n]i∈[n] and all policies π∈Δ()π∈ (A), the utility is bounded as 0≤ui(π)≤U0≤ u_i(π)≤ U for some constant U>0U>0. Consider the associated lifted 2n2n-player game ~(h,x,Q) G(h,x,Q) as in Mazumdar et al. (2025). Suppose each player in the lifted game runs an external-regret algorithm for T rounds, producing joint play (πt,pt)(π^t,p^t) for t=1,…,Tt=1,…,T, and let σT:=1T∑t=1Tδ(πt,pt) _T\;:=\; 1T _t=1^T _(π^t,p^t) denote the empirical distribution. Then σT _T is an εCCE(T) _ CCE(T)-coarse correlated equilibrium of the lifted game, where εCCE(T)≤1T∑j=12nregj(T). _ CCE(T)≤ 1T _j=1^2nreg_j(T). In particular, if each player uses Hedge (or any algorithm with regret bound regj(T)≤U2Tlog|j|reg_j(T)≤ U 2T |A_j|), then εCCE(T)≤U∑j=12n2log|j|T. _ CCE(T)≤ U _j=1^2n 2 |A_j|T. Under the equilibrium-collapse result of Mazumdar et al. (2025), the induced policy π~h(⋅∣x;Q) π_h(· x;Q) obtained from σT _T is an εCCE(T) _ CCE(T)-approximate stage RQRE of the original game. Consequently, for every i∈[n]i∈[n], the bound holds: |Vi,hϵi(π~h;x,Q)−Vi,hϵi(πh⋆;x,Q)|≤ε, |V_i,h _i ( π_h;x,Q )-V_i,h _i ( _h ;x,Q ) |\;≤\; _ eq, with the specialization ε:=εCCE(T) _ eq\;:=\; _ CCE(T). In particular, to ensure ε≤ε _ eq≤ , it suffices to take T≳U2ε2(∑j=12nlog|j|)2,T\; \; U^2 ^2 ( _j=1^2n |A_j| )^2, up to universal constants. B.3 Proof of Theorem 2 Now with the main technical lemmas in place, we prove the regret bound. Proof of Theorem 2. Fix the high-probability event ℰE on which Lemma 2 holds simultaneously for all (i,h,k,x,a)∈[n]×[H]×[K]×(i,h,k,x,a)∈[n]×[H]×[K]×X×A; by Lemma 2, Pr(ℰ)≥1−δ (E)≥ 1-δ. For each episode k, define the episode exploitability gap by Δk:=maxi∈[n](Vi,1ϵi,τi(sBRi(π−ik),π−ik;s0)−Vi,1ϵi,τi(πk;s0)),regret(K)=∑k=1KΔk. _k:= _i∈[n] (V_i,1 _i, _i (sBR_i( _-i^k), _-i^k;\,s_0 )-V_i,1 _i, _i (π^k;\,s_0 ) ), *regret(K)= _k=1^K _k. Fix an episode k and let i⋆i attain the max above. A stage-wise performance-difference recursion. Let xhkx_h^k be the state at stage h of episode k and let ahka_h^k be the joint action sampled from πhk(⋅|xhk) _h^k(·|x_h^k). Fix a player i⋆∈[n]i ∈[n], and define the one-step best response to π−i⋆kπ^k_-i as sBRi⋆(π−i⋆k)∈argmaxσi⋆Vi⋆,1ϵi⋆((σi⋆,π−i⋆k);s0).sBR_i (π^k_-i )∈ _ _i V_i ,1 _i (( _i ,π^k_-i );s_0 ). Define the deviating profile πk,br:=(sBRi⋆(π−i⋆k),π−i⋆k).π^k,br:=(sBR_i ( _-i ^k),\, _-i ^k). For any stage h∈[H]h∈[H] and state x∈x , define the value gap Δk,h(x):=Vi⋆,hϵi⋆(πk,br;x)−Vi⋆,hϵi⋆(πk;x). _k,h(x):=V_i ,h _i (π^k,br;x)-V_i ,h _i (π^k;x). In particular, Δk=Δk,1(s0) _k= _k,1(s_0). We now bound Δk,h(x) _k,h(x) by a one-step advantage term plus the next-stage gap. By the definition of the true environment backup and policy evaluation, the stage-h value depends on the stage-h Q table and the policy-risk operator. Indeed, by the risk-sensitive Bellman backup definition, we have that Vi⋆,hϵi⋆(π;x) V_i ,h _i (π;x) =ρi⋆,h(a∼πh(⋅|x)[ri⋆,h(x,a)+Vi⋆,h+1ϵi⋆(π;x′)]). = _i ,h e ( *E_a _h(·|x) [r_i ,h(x,a)+V_i ,h+1 _i (π;x ) ] ). (35) Apply this to both policies to get that Δk,h(x) _k,h(x) =ρi⋆,h(Zbr)−ρi⋆,h(Zk), = _i ,h e(Z^br)- _i ,h e(Z^k), (36) where we have defined the random variables Zbr Z^br :=[ri⋆,h(x,ahk,br)+Vi⋆,h+1ϵi⋆(πk,br;x′)], := *E [r_i ,h(x,a_h^k,br)+V_i ,h+1 _i (π^k,br;x ) ], Zk Z^k :=[ri⋆,h(x,ahk)+Vi⋆,h+1ϵi⋆(πk;x′)]. := *E [r_i ,h(x,a_h^k)+V_i ,h+1 _i (π^k;x ) ]. Now since ρi,h _i,h e is L_ env Lipschitz continuous, we have that Δk,h(x)≤L(Zbr−Zk) _k,h(x)≤ L_ env\,(Z^br-Z^k). Expanding the difference of random variables, we have that Zbr−Zk Z^br-Z^k =[r(x,ahk,br)−r(x,ahk)]+[Vh+1(πk,br;x′)−Vh+1(πk;x′)]. = *E [r(x,a_h^k,br)-r(x,a_h^k) ]+ *E [V_h+1(π^k,br;x )-V_h+1(π^k;x ) ]. The second expectation is exactly [Δk,h+1(x′)∣x] *E [ _k,h+1(x ) x ]. Now define the true stage h Q-function as follows: Qhi⋆(x,a):=ri⋆,h(x,a)+ρi⋆,h(Vi⋆,h+1ϵi⋆(πk;⋅)).Q_h^i (x,a):=r_i ,h(x,a)+ _i ,h e (V_i ,h+1 _i (π^k;·) ). Then using our little friend ”add and subtract” to introduce the next-stage term under πkπ^k. Indeed, adding and subtracting Vh+1(πk;x′)V_h+1(π^k;x ) inside the first expectation, we get that Zbr−Zk Z^br-Z^k =[r(x,ak,br)+Vh+1(πk;x′)+(Vh+1(πk,br;x′)−Vh+1(πk;x′))]−[r(x,ak)+Vh+1(πk;x′)]. =E [r(x,a^k,br)+V_h+1(π^k;x )+ (V_h+1(π^k,br;x )-V_h+1(π^k;x ) ) ]-E [r(x,a^k)+V_h+1(π^k;x ) ]. =[r(x,ak,br)+Vh+1(πk;x′)]−[r(x,ak)+Vh+1(πk;x′)]+[Vh+1(πk,br;x′)−Vh+1(πk;x′)]. =E [r(x,a^k,br)+V_h+1(π^k;x ) ]-E [r(x,a^k)+V_h+1(π^k;x ) ]+E [V_h+1(π^k,br;x )-V_h+1(π^k;x ) ]. The second expectation is exactly [Δk,h+1(x′)∣x]E [ _k,h+1(x ) x ]. The first line, on the other hand, corresponds to [Qhi⋆(x,ak,br)−Qhi⋆(x,ak)∣x].E [Q_h^i (x,a^k,br)-Q_h^i (x,a^k) x ]. where we define the true Q-function evaluated using the continuation under πkπ^k as Qhi⋆(x,a):=ri⋆,h(x,a)+ρi⋆,h(Vi⋆,h+1ϵi⋆(πk;⋅)).Q_h^i (x,a):=r_i ,h(x,a)+ _i ,h e (V_i ,h+1 _i (π^k;·) ). Combining these we have Δk,h(x)≤L([Qhi⋆(x,ak,br)−Qhi⋆(x,ak)∣x]+[Δk,h+1(x′)∣x]). _k,h(x)≤ L_ env (E [Q_h^i (x,a^k,br)-Q_h^i (x,a^k) x ]+E [ _k,h+1(x ) x ] ). Now observe that the algorithm uses an approximate policy evaluation (due to the estimation of the associated risk measure) with error ε _ pol and an approximate stage equilibrium with error ε _ eq. Hence we have that [Qhi⋆(x,ahk,br)−Qhi⋆(x,ahk)∣x]≤[Qhi⋆,k(x,ahk,br)−Qhi⋆,k(x,ahk)∣x]+(ε+ε). *E [Q_h^i (x,a_h^k,br)-Q_h^i (x,a_h^k) x ]≤ *E [Q_h^i ,k(x,a_h^k,br)-Q_h^i ,k(x,a_h^k) x ]+( _ pol+ _ eq). Therefore using monotonicity of ρi⋆,h _i ,h env and the stage-wise best-response definition, and applying the standard telescoping argument as above, we have that Δk,h(xhk) _k,h(x_h^k) ≤L[Qhi⋆,k(xhk,ahk,br)−Qhi⋆,k(xhk,ahk)|xhk] ≤ L_ env\, *E [Q_h^i ,k(x_h^k,a_h^k,br)-Q_h^i ,k(x_h^k,a_h^k)\ |\ x_h^k ] (37) +L[Δk,h+1(xh+1k)∣xhk]+L(ε+ε), +L_ env\, *E [ _k,h+1(x_h+1^k) x_h^k ]+L_ env( _ pol+ _ eq), where ahk,br∼πhk,br(⋅|xhk)a_h^k,br _h^k,br(·|x_h^k) and ahk∼πhk(⋅|xhk)a_h^k _h^k(·|x_h^k). Why the factor L_ env appears here: the one-step difference in value-to-go is a difference of the form ρi⋆,h(X)−ρi⋆,h(Y) _i ,h e(X)- _i ,h e(Y), where X,YX,Y are next-state value random variables induced by different action mixtures. By the environment risk Lipschitz continuity assumption, we have that |ρi⋆,h(X)−ρi⋆,h(Y)|≤L‖X−Y‖∞,| _i ,h e(X)- _i ,h e(Y)|≤ L_ env\|X-Y\|_∞, so that every time we convert a value-function deviation into a risk-to-go deviation, we incur the factor L_ env. Unrolling (37) from h=1h=1 to H and using Δk,H+1≡0 _k,H+1≡ 0 gives Δk≤L∑h=1H[Qi⋆,hk(xhk,ahk,br)−Qi⋆,hk(xhk,ahk)]+HL(ε+ε). _k≤ L_ env _h=1^H *E [Q_i ,h^k(x_h^k,a_h^k,br)-Q_i ,h^k(x_h^k,a_h^k) ]+H\,L_ env( _ pol+ _ eq). (38) Replace Qhi⋆,kQ_h^i ,k by the optimistic estimates and use optimism. On the event ℰE, Lemma 2 gives, for all (x,a)∈×(x,a) ×A, us that Qhi⋆,k(x,a)≤Qhi⋆,k(x,a)Q_h^i ,k(x,a)≤ Q_h^i ,k(x,a) and Qhi⋆,k(x,a)Q_h^i ,k(x,a) is optimistic for the true backup up to ε+L(ε+ε) _ env+L_ env( _ pol+ _ eq). More concretely, rearranging (23) yields ri⋆,h(x,a)+ρi⋆,h(Vh+1i⋆,ϵ(πh+1k))≤Qhi⋆,k(x,a)+ε+L(ε+ε).r_i ,h(x,a)+ _i ,h e(V_h+1^i ,ε( _h+1^k))≤ Q_h^i ,k(x,a)+ _ env+L_ env( _ pol+ _ eq). This implies that the true advantage of ahk,bra_h^k,br over ahka_h^k is controlled by the optimistic advantage plus the additive approximation error; plugging into (38) yields Δk≤L∑h=1H[Qhi⋆,k(xhk,ahk,br)−Qhi⋆,k(xhk,ahk)]+H(ε+L(ε+ε)). _k≤ L_ env _h=1^H *E [Q_h^i ,k(x_h^k,a_h^k,br)-Q_h^i ,k(x_h^k,a_h^k) ]+H ( _ env+L_ env( _ pol+ _ eq) ). (39) Use that πhk _h^k is an approximate stage equilibrium for the optimistic Q table. By the assumption on the equilibrium approximation, at each h∈[H]h∈[H] and encounter state xhk∈x_h^k , the policy πhk(⋅|xhk) _h^k(·|x_h^k) is an ε _ eq-equilibrium for the stage game defined by the optimistic Q table. In particular, as shown in Lemma 3, the improvement obtained by any alternative (including the stage-wise best response) is bounded by ε _ eq in the policy-risk value, and thus the expected optimistic advantage satisfies [Qhi⋆,k(xhk,ahk,br)−Qhi⋆,k(xhk,ahk)]≤[βϕ(xhk,ahk,h)⊤(Λhk)−1ϕ(xhk,ahk,h)]+ε. *E [Q_h^i ,k(x_h^k,a_h^k,br)-Q_h^i ,k(x_h^k,a_h^k) ]≤ *E [β φ(x_h^k,a_h^k,h) ( _h^k)^-1φ(x_h^k,a_h^k,h) ]+ _ eq. Substituting this bound into (39) gives us that Δk≤Lβ∑h=1H[ϕ(xhk,ahk,h)⊤(Λhk)−1ϕ(xhk,ahk,h)]+H(ε+L(ε+ε)). _k≤ L_ envβ _h=1^H *E [ φ(x_h^k,a_h^k,h) ( _h^k)^-1φ(x_h^k,a_h^k,h) ]+H ( _ env+L_ env( _ pol+ _ eq) ). Sum over episodes and apply the elliptical potential lemma. Summing over k=1,…,Kk=1,…,K and applying Cauchy–Schwarz, we have that ∑k=1K∑h=1Hϕk,h⊤(Λhk)−1ϕk,h≤KH∑k=1K∑h=1Hϕk,h⊤(Λhk)−1ϕk,h, _k=1^K _h=1^H _k,h ( _h^k)^-1 _k,h≤ KH\; _k=1^K _h=1^H _k,h ( _h^k)^-1 _k,h, where ϕk,h:=ϕ(xhk,ahk,h) _k,h:=φ(x_h^k,a_h^k,h). For each fixed h∈[H]h∈[H], the standard elliptical potential argument yields ∑k=1Kϕk,h⊤(Λhk)−1ϕk,h≤2logdet(ΛhK+1)det(λI)≤2dlog(1+Kλ). _k=1^K _k,h ( _h^k)^-1 _k,h≤ 2 ( _h^K+1) (λ I)≤ 2d (1+ Kλ ). Summing over h=1,…,Hh=1,…,H gives us the bound ∑k=1K∑h=1Hϕk,h⊤(Λhk)−1ϕk,h≤2Hdlog(1+Kλ). _k=1^K _h=1^H _k,h ( _h^k)^-1 _k,h≤ 2Hd (1+ Kλ ). Therefore, we have that ∑k=1K∑h=1Hϕk,h⊤(Λhk)−1ϕk,h≤KH2Hdlog(1+Kλ)=~(HKd). _k=1^K _h=1^H _k,h ( _h^k)^-1 _k,h≤ KH\; 2Hd (1+ Kλ )= O (H Kd ). Putting everything together, we deduce that reg(K)=∑k=1KΔk≤~(LβHKd)+KH(ε+L(ε+ε)).reg(K)= _k=1^K _k≤ O (L_ envβ\;H Kd )+KH ( _ env+L_ env( _ pol+ _ eq) ). Final regret bound via plugging in β=cBd2Hιβ=cB d^2H\, . Using β=~(Bd2H)β= O(B d^2H), we have that LβHKd=O~(LBd2H⋅HKd)=~(LBKd3H3),L_ envβ\;H Kd= O (L_ envB d^2H· H Kd )= O (L_ envB Kd^3H^3 ), which yields exactly (6) conditioned on the event ℰE. Since Pr(ℰ)≥1−δ (E)≥ 1-δ, the theorem holds with probability at least 1−δ1-δ. ∎ B.4 Regret with Explicit Error Dependence: Entropic Risks & Regularizers In Section 3.1 we specialize to the case where the risk measures and regularizers are entropic. That is, in the special case where the policy-space risk penalty is entropic (KL) and the player policy is entropy-regularized, there are number of methods one can employ including no-regret learning methods such as extra-gradient or mirror-prox, multiplicative weights, or iterative best response. In this case, we can obtain more explicit bounds which reveal how the risk sensitivity and bounded rationality parameters influence different performance criteria. Set constants Amax:=maxi∈[n]|i|,ϵmin:=mini∈[n]ϵi,τmin:=mini∈[n]τi.A_ := _i∈[n]|A_i|, _ := _i∈[n] _i, _ := _i∈[n] _i. Assume stage rewards satisfy ri,h(x,a)∈[0,1]r_i,h(x,a)∈[0,1] and Vi,H+1ϵi,τi≡0V_i,H+1 _i, _i≡ 0. Then the cumulative reward-to-go is bounded by H. Moreover the entropy regularization satisfies 0≤Φ(πi(⋅|x))≤log|i|.0≤ ( _i(·|x))≤ |A_i|. Hence the additive regularization term satisfies 0≤Φ(πi(⋅|x))/ϵi≤log(|i|)/ϵi.0≤ ( _i(·|x))/ _i≤ (|A_i|)/ _i. Since the entropic policy-value operator (7) is a log-sum-exp aggregation of bounded Q values, it preserves the same scale as the underlying payoffs. Consequently, clipping Q to [0,B][0,B] as in Algorithm 1 with Bi:=H(1+log|i|ϵi),B:=maxi∈[n]Bi,B_i:=H (1+ |A_i| _i ), B:= _i∈[n]B_i, ensures 0≤Vi,hϵi,τi(π;x;Q)≤B0≤ V_i,h _i, _i(π;x;Q)≤ B for all (i,h,x,π)∈[n]×[H]×Δ()(i,h,x,π)∈[n]×[H]×X× (A). Using AmaxA_ and ϵmin _ we obtain the simpler bound B≤H(1+logAmaxϵmin).B≤ H (1+ A_ _ ). (40) Substituting this value range into Theorem 2 and expanding the logarithmic factors yields the following explicit regret bound. Corollary 3 (Explicit regret bound with (n,|i|)(n,|A_i|) dependence). Under the assumptions of Theorem 2 with entropic policy regularization νi(μi)=Φ(μi) _i( _i)= ( _i), let Amax=maxi|i|A_ = _i|A_i| and ϵmin=miniϵi _ = _i _i. Then for an absolute constant C1>0C_1>0, with probability at least 1−δ1-δ, the bound holds: reg(K) (K) ≤C1LH(1+logAmaxϵmin)Kd3H3log(nH/δ)+KH(ε+Lε+LcBΔ/τmin). ≤ C_1L_ envH (1+ A_ _ ) Kd^3H^3 (nH/δ )+KH ( _ env+L_ env _ pol+L_ env\,c_ eq\,B _ eq/ _ ). (41) If the stage solver runs a no-regret algorithm for T iterations, then the duality gap satisfies Δ≲∑i=1nlog|i|T. _ eq\; \; _i=1^n |A_i|T. Alternatively, if the equilibrium variational inequality is strongly monotone with modulus μ(τ)μ(τ) and Lipschitz constant L(τ)L(τ), then an extragradient or Mirror-Prox solver (cf. Cesa-Bianchi and Lugosi (2006), e.g.) yields ε(T)≤Cexp(−Tμ/L). _ eq(T)≤ C (-Tμ/L). Suppose the environment risk operator is the entropic risk measure—namely, ρτ(Z)=1τlog[exp(τZ)]. _τ(Z)= 1τ *E[ (τ Z)]. Then the operator is 11-Lipschitz in the sup norm—i.e., |ρτ(Z)−ρτ(Z′)|≤‖Z−Z′‖∞,| _τ(Z)- _τ(Z )|≤\|Z-Z \|_∞, so we may take L=1L_ env=1. For the environment risk estimation error, let Z∈[0,B]Z∈[0,B] denote the continuation value. Given m samples Z1,…,ZmZ_1,…,Z_m, define the estimator ρ^τ=1τlog(1m∑j=1mexp(τZj)). ρ_τ= 1τ ( 1m _j=1^m (τ Z_j) ). Applying a union bound over all players i∈[n]i∈[n] and stages h∈[H]h∈[H] and setting the per-event failure probability to δ/(nH)δ/(nH) yields ε≲1τminexp(τmaxB)log(nH/δ)m. _ env\; \; 1 _ ( _ B) (nH/δ)m. (42) The exponential factor arises because the entropic risk depends on the moment generating function [eτZ] *E[e^τ Z], and without additional distributional assumptions the range bound Z∈[0,B]Z∈[0,B] implies eτZ∈[1,eτB]e^τ Z∈[1,e^τ B], which necessarily introduces exp(τB) (τ B). If the policy-side entropic operator (7) is evaluated exactly (finite action spaces), then ε=0 _ pol=0. If it is approximated via sampling m actions, a typical bound is ε≲1τminexp(τmaxB)log(nH/δ)m. _ pol\; \; 1 _ ( _ B) (nH/δ)m. Substituting these expressions yields the regret bound reg(K) (K) ≤~(H(1+logAmaxϵmin)Kd3H3)+KH(1τminexp(τmaxB)log(nH/δ)m+cBΔ/τmin). ≤ O (H (1+ A_ _ ) Kd^3H^3 )+KH ( 1 _ ( _ B) (nH/δ)m+c_ eqB _ eq/ _ ). Making the (τ,ϵ)(τ,ε) interaction explicit. Under entropic policy regularization with rewards in [0,1][0,1] and horizon H, clipping ensures the continuation values satisfy Z∈[0,B]Z∈[0,B] with B=maxi∈[n]Bi,Bi:=H(1+log|i|ϵi)≤H(1+logAmaxϵmin),B= _i∈[n]B_i, B_i:=H (1+ |A_i| _i )\;≤\;H (1+ A_ _ ), where Amax=maxi|i|A_ = _i|A_i| and ϵmin=miniϵi _ = _i _i. Plugging this into (42) gives ε≲1τminexp(τmaxH(1+logAmaxϵmin))log(nH/δ)m. _ env\; \; 1 _ ( _ H (1+ A_ _ ) ) (nH/δ)m. (43) Note that in the dual representation the ambiguity penalty scales as 1τKL(⋅∥⋅) 1τKL(·\|·), so increasing τ reduces the penalty weight and therefore moves the objective toward the risk-neutral limit. In this sense, larger τ corresponds to less robustness, while smaller τ enforces stronger regularization. Consequently, the statistical error bound (43) worsens with τmax _ through the factor exp(τmaxB) ( _ B) even though the underlying objective becomes closer to risk-neutral as τ increases. Risk-sensitivity regimes. The generic estimation bound ε≲1τminexp(τmaxB)log(nH/δ)m _ env\; \; 1 _ ( _ B) (nH/δ)m exhibits two opposing effects: increasing τ decreases the prefactor 1/τmin1/ _ but increases the exponential exp(τmaxB) ( _ B). One can interpret the bound in terms of the “effective scale” g(τ):=1τexp(τB),g(τ):= 1τ (τ B), which is minimized at τ⋆=1/Bτ =1/B (treating B as fixed). Consequently, the estimate is most favorable when τmaxB _ B is (1)O(1), and becomes large both when τ is too small (large 1/τ1/τ) and when τ is too large (large exp(τB) (τ B)). In particular, for τmaxB≲1 _ B 1 we may expand exp(τmaxB)=1+τmaxB+((τmaxB)2) ( _ B)=1+ _ B+O(( _ B)^2) to obtain ε≲1τminlog(nH/δ)m+τmaxτminBlog(nH/δ)m+(τmax2B2τminlog(nH/δ)m). _ env\; \; 1 _ (nH/δ)m\;+\; _ _ \,B\, (nH/δ)m\;+\;O ( _ ^2B^2 _ (nH/δ)m ). (44) If τmax≍τmin=τ _ _ =τ and τB≪1τ B 1, this simplifies to ε≲(1+B+(τB2))log(nH/δ)m, _ env\; \;(1+B+O(τ B^2)) (nH/δ)m, up to constants, recovering the familiar bounded-value estimation rate. Thus, in the strongly robust regime the leading dependence is typically ε≍1τlog(nH/δ)/m _ env 1τ (nH/δ)/m (up to lower-order additive terms involving B). When τ is large, the exponential factor dominates and the bound behaves as ε≍Blog(nH/δ)/m _ env B (nH/δ)/m. Decreasing ϵmin _ increases ε _ env through the value range B, while decreasing τmin _ increases ε _ env through the prefactor 1/τmin1/ _ . In addition, τmax _ and ϵmin _ interact multiplicatively in the exponent exp(τmaxB) ( _ B) via B. B.5 QRE-OVI: Quantal Response Optimistic Value Iteration The risk-neutral, boundedly rational setting—in which agents employ quantal responses—is a special case of our framework. Specifically, QRE-OVI is obtained from Algorithm 1 by setting the environment and policy risk operators to their risk-neutral limits, i.e., replacing ρi,h _i,h e with the standard expectation x′∼h(⋅|x,a)[⋅] *E_x _h(·|x,a)[·] and removing the policy-risk adversary by setting φ,i≡0 _ p,i≡ 0. The resulting algorithm retains the entropy regularization (1/ϵi)νi(πi)(1/ _i) _i( _i) that defines the quantal response, and at each stage game computes a QRE rather than a Nash equilibrium or an RQRE. This yields a direct replacement of the Nash oracle in NQ-OVI (Cisneros-Velarde and Koyejo, 2023): the only modification is that the stage-game solver Nash is replaced by QREε QRE_ , while the optimistic value iteration structure, linear function approximation, and confidence bonus construction remain unchanged. The advantage of this substitution is that QRE is unique for any finite game and any ϵi>0 _i>0 (McKelvey and Palfrey, 1995), eliminating the equilibrium selection problem inherent to Nash. Corollary 4 (Regret bound for QRE-OVI). Consider Algorithm 1 in the risk-neutral specialization described above, so that L=1L_ env=1, ε=0 _ env=0, and ε=0 _ pol=0. Under Assumption 2 with B=maxi∈[n]H(1+log|i|/ϵi)B= _i∈[n]H(1+ |A_i|/ _i), with probability at least 1−δ1-δ, the estimate holds: reg(K)≤~(BKd3H3)+KHε,reg(K)≤ O (B K\,d^3\,H^3 )+KH\, _ eq, where ε _ eq is the stage-game QRE approximation error. Proof. Set L=1L_ env=1, ε=0 _ env=0, and ε=0 _ pol=0 in Theorem 2. The bound follows immediately from (6). ∎ Compared to the NQ-OVI regret bound of Cisneros-Velarde and Koyejo (2023), the leading statistical term acquires the factor B(ϵ)=H(1+log||/ϵ)B(ε)=H(1+ |A|/ε) in place of H, reflecting the enlarged value range due to entropy regularization. This is the price of uniqueness and Lipschitz stability (Corollary 2): as ϵ→∞ε→∞, B→HB→ H and the bound approaches that of NQ-OVI, while the equilibrium computation becomes increasingly ill-conditioned. Conversely, moderate ϵε yields a modest increase in the regret bound while guaranteeing a unique, stable equilibrium at every stage game. Appendix C Risk Estimation In Algorithm 1, the true risk operator ρi _i cannot be computed exactly because the transition kernel hP_h is unknown to the agents. Only samples (xht,aht,xh+1t)(x_h^t,a_h^t,x_h+1^t) are observed, so the true distribution of the continuation value Z:=Vh+1i(Xh+1)Z:=V^i_h+1(X_h+1), where Xh+1∼h(⋅∣x,a)X_h+1 _h(· x,a), is unavailable. In this section, we formalize the distinction between ρ and its computable proxy ρ ρ, quantify the resulting approximation error, and provide concrete instantiations for common risk measures. C.1 Empirical Environment Risk Operator Recall from (2) that the true environment risk operator at stage h takes the form ρi,h(Z∣h(⋅∣x,a))=inf~∈Δ()∫Z(x′)~(dx′)+φ,i(~∥h(⋅∣x,a)).ρ e_i,h(Z _h(· x,a))= _ P∈ (X) \ Z(x )\, P(dx )+ _ e,i( P\|P_h(· x,a)) \. Since hP_h is unknown, Algorithm 1 replaces this with an empirical approximation. Two strategies are available depending on the structure of the penalty φ,i _ e,i. Finite dual discretization for general penalties. For a general convex penalty φ,i _ e,i, we approximate the infimum over Δ() (X) by restricting to a finite set of candidate transition kernels ^i,h(x,a)=P~h(1)(⋅∣x,a),…,P~h(M)(⋅∣x,a) Q_i,h(x,a)=\ P_h^(1)(· x,a),…, P_h^(M)(· x,a)\, yielding ρ^i,h,k(Z∣x,a):=minm∈[M]^x′∼P~h(m)(⋅∣x,a)[Z(x′)]+φ,i(P~h(m)(⋅∣x,a)∥P^hk(⋅∣x,a)), ρ_i,h e,k(Z x,a):= _m∈[M] \ *E_x P_h^(m)(· x,a)[Z(x )]+ _ e,i ( P_h^(m)(· x,a)\, \|\, P_h^k(· x,a) ) \, where P^hk P_h^k is the empirical estimate of hP_h constructed from the first k−1k-1 episodes. The expectations under each candidate kernel may themselves be approximated via Monte Carlo sampling: ∫Z(x′)P~h(m)(dx′)≈1N∑j=1NZ(x′(j)),x′(j)∼P~h(m)(⋅∣x,a). Z(x )\, P_h^(m)(dx )≈ 1N _j=1^NZ(x (j)), x (j) P_h^(m)(· x,a). The approximation error ε _ env then depends on both the covering quality of ^i,h Q_i,h and the Monte Carlo sample size N. Closed-form evaluation under entropic penalties. When the penalty is the scaled KL divergence φ,i(~∥h)=1τiKL(~∥h) _ e,i( P\|P_h)= 1 _i *KL( P\|P_h), the environment risk operator admits the closed form ρi,h(Z∣h)=1τilogx′∼h(⋅∣x,a)[exp(τiZ(x′))].ρ e_i,h(Z _h)= 1 _i *E_x _h(· x,a) [ ( _i\,Z(x )) ]. In this case, no finite dual discretization is needed; the operator is approximated by replacing hP_h with the empirical transition estimate P^hk P_h^k and evaluating the resulting log-sum-exp expression from samples. Given N independent next-state samples x′(1),…,x′(N)∼P^hk(⋅∣x,a)x (1),…,x (N) P_h^k(· x,a), the empirical estimator is ρ^i,h,k(Z∣x,a)=1τilog(1N∑j=1Nexp(τiZ(x′(j)))). ρ_i,h e,k(Z x,a)= 1 _i ( 1N _j=1^N ( _i\,Z(x (j))) ). C.2 True versus empirical risk operators For a fixed policy profile π, the true risk-adjusted Q-function is defined via the Bellman recursion Qhi,⋆(x,a):=ri,h(x,a)+ρi(Vh+1i,⋆(Xh+1)),Xh+1∼h(⋅∣x,a),Q_h^i, (x,a)\;:=\;r_i,h(x,a)+ _i (V_h+1^i, (X_h+1) ), X_h+1 _h(· x,a), where ρi _i is applied to the distribution of the random continuation value induced by the true transition kernel. Since ρi _i integrates out all randomness, Qhi,⋆Q_h^i, is a deterministic function of (x,a)(x,a). The learning algorithm replaces ρi _i with a computable proxy ρ^i ρ_i, as appears in the regression targets of Algorithm 1. Two sources of approximation arise. First, if ρi _i admits a dual representation (Theorem 1), ρi(Z)=supp∈ip[Z]−Di(p), _i(Z)\;=\; _p _i \E_p[Z]-D_i(p) \, the algorithm may use a finite subset ^i=p(1),…,p(M)⊂i P_i=\p^(1),…,p^(M)\ _i, yielding the finite-dual approximation ρ^i(Z):=maxj∈[M]p(j)[Z]−Di(p(j)). ρ_i(Z)\;:=\; _j∈[M] \E_p^(j)[Z]-D_i (p^(j) ) \. Second, the expectations under each p(j)p^(j) may themselves be estimated from samples. We define the worst-case approximation error as ε:=maxi∈[n]supZ:‖Z‖∞≤H|ρi(Z)−ρ^i(Z)|. _P\;:=\; _i∈[n]\; _Z:\,\|Z\|_∞≤ H | _i(Z)- ρ_i(Z) |. (45) This quantity enters the regret bounds as an additive bias of ε _P per Bellman backup, accumulating to O(KHε)O(KH _P) over K episodes. When ^i=i P_i=P_i and expectations are computed exactly, ε=0 _P=0 and the bound in Theorem 2 applies without modification. C.3 Examples We instantiate the approximation error for three common risk measures. Example 4 (Entropic risk). For parameter τi>0 _i>0, the entropic risk measure is ρi(Z):=1τilog([eτiZ]). _i(Z)\;:=\; 1 _i\, (E [e _iZ ] ). Given m independent samples Z1,…,ZmZ_1,…,Z_m from the distribution of Z, the empirical entropic risk is ρ^i(Z):=1τilog(1m∑ℓ=1meτiZℓ). ρ_i(Z)\;:=\; 1 _i\, ( 1m _ =1^me _iZ_ ). Under sub-Gaussian assumptions on Z, the approximation error satisfies |ρ^i(Z)−ρi(Z)|=Oℙ(log(1/δ)/m)| ρ_i(Z)- _i(Z)|=O_P ( (1/δ)/m ). Example 5 (Conditional Value-at-Risk). For confidence level α∈(0,1)α∈(0,1), the CVaR of Z is ρi(Z):=CVaRα(Z)=11−α∫α1FZ−1(u)u, _i(Z)\;:=\;CVaR_α(Z)\;=\; 11-α _α^1F_Z^-1(u)\,du, where FZ−1F_Z^-1 is the quantile function. Given samples Z1,…,ZmZ_1,…,Z_m with order statistics Z(1)≤⋯≤Z(m)Z_(1)≤·s≤ Z_(m), the empirical CVaR is ρ^i(Z):=1(1−α)m∑ℓ=⌈αm⌉mZ(ℓ). ρ_i(Z)\;:=\; 1(1-α)m _ = α m ^mZ_( ). Standard results give |ρ^i(Z)−CVaRα(Z)|=Oℙ(1/m)| ρ_i(Z)-CVaR_α(Z)|=O_P ( 1/m ). Example 6 (Coherent risk with finite dual set). Let iP_i be a convex set of distributions over the support of Z and Di:i→ℝ+D_i:P_i _+ a convex penalty. The coherent risk measure ρi(Z):=supp∈ip[Z]−Di(p) _i(Z)\;:=\; _p _i \E_p[Z]-D_i(p) \ is approximated using a finite subset ^i=p(1),…,p(M) P_i=\p^(1),…,p^(M)\ via ρ^i(Z):=maxj∈[M]p(j)[Z]−Di(p(j)) ρ_i(Z):= _j∈[M]\E_p^(j)[Z]-D_i(p^(j))\. The approximation error ε=supZ|ρi(Z)−ρ^i(Z)| _P= _Z| _i(Z)- ρ_i(Z)| depends on the covering quality of ^i P_i and enters the regret bound as an additive term. Appendix D Stability of Stage Games to Finite-Horizon Value Robustness In this section, we provide the complete stability analysis for RQRE under linear function approximation. We first establish stagewise robustness (Section D.1), then lift these bounds to finite-horizon value functions via backward induction (Section D.2). D.1 Stagewise Robustness under Linear Function Approximation Consider the finite-horizon Markov game with players i∈[n]i∈[n], state space X, joint action space =∏i=1niA= _i=1^nA_i, and stages h∈[H]h∈[H]. Rewards are bounded i.e., |ri,h(x,a)|≤Rmax|r_i,h(x,a)|≤ R_ . Under linear function approximation (Assumption 2), each player’s Q-function takes the form Qhi(x,a;whi)=ϕ(x,a,h)⊤whi,‖ϕ(x,a,h)‖2≤1∀(x,a,h).Q_h^i(x,a;w_h^i)=φ(x,a,h) w_h^i, \|φ(x,a,h)\|_2≤ 1 ∀(x,a,h). For fixed (x,h)(x,h), define the induced stage-game payoff table for player i as Uhi(x)a:=Qhi(x,a;whi).U_h^i(x)_a:=Q_h^i(x,a;w_h^i). Let Uh(x):=(Uh1(x),…,Uhn(x))U_h(x):=(U_h^1(x),…,U_h^n(x)) denote the collection of payoff tables. Assumption 3 (RQRE Lipschitz Continuity). At each (x,h)(x,h), the stage-game RQRE is defined by a μ-strongly concave objective with μ:=1ϵ+τ⋅αR>0μ:= 1ε+τ· _R>0, yielding a unique equilibrium profile πh(x;Uh(x))∈∏i=1nΔ(i) _h RQRE(x;U_h(x))∈ _i=1^n (A_i). A consequence of this assumption is that the equilibrium map is Lipschitz in payoff tables: ‖πh(x;U)−πh(x;U~)‖1≤L‖U−U~‖∞,L≤cμ, \| _h RQRE(x;U)- _h RQRE(x; U) \|_1≤ L_ RQRE\|U- U\|_∞, L_ RQRE≤ cμ, (46) where c>0c>0 is a universal constant. Theorem 3 (Stagewise Robustness under Linear Function Approximation). Fix state x and stage h. Let wh:=whii∈[n]w_h:=\w_h^i\_i∈[n] and w~h:=w~hii∈[n] w_h:=\ w_h^i\_i∈[n] be two parameter collections inducing payoff tables Uh(x)U_h(x) and U~h(x) U_h(x). Then ‖Uh(x)−U~h(x)‖∞≤maxi∈[n]‖whi−w~hi‖2\|U_h(x)- U_h(x)\|_∞≤ _i∈[n]\|w_h^i- w_h^i\|_2 so that the RQRE policies satisfy ‖πh(x;wh)−πh(x;w~h)‖1≤cμmaxi∈[n]‖whi−w~hi‖2. \| _h RQRE(x;w_h)- _h RQRE(x; w_h) \|_1≤ cμ _i∈[n]\|w_h^i- w_h^i\|_2. (47) Proof. For any player i and joint action a∈a , we have that |Uhi(x)a−U~hi(x)a|=|ϕ(x,a,h)⊤(whi−w~hi)|≤‖ϕ(x,a,h)‖2‖whi−w~hi‖2≤‖whi−w~hi‖2.|U_h^i(x)_a- U_h^i(x)_a|=|φ(x,a,h) (w_h^i- w_h^i)|≤\|φ(x,a,h)\|_2\|w_h^i- w_h^i\|_2≤\|w_h^i- w_h^i\|_2. Taking the maximum over i and a yields the payoff bound. The policy bound follows from Assumption 3. ∎ Remark 3. Theorem 3 is agnostic to how the parameter estimates are obtained. It applies to any estimation procedure (OVI, least-squares regression, etc.) that provides parameter-error bounds. D.2 Finite-Horizon Value Robustness via Backward Induction We now lift stagewise policy perturbations to value function perturbations over the full horizon. For a Markov policy profile π=πhh=1Hπ=\ _h\_h=1^H, recall the recursive definition of the risk-adjusted value function: Qhi,π(x,a) Q_h^i,π(x,a) :=ℛi,h(ri,h,h,Vh+1i,π;x,a), :=R e_i,h (r_i,h,P_h,V_h+1^i,π;x,a ), Vhi,π(x) V_h^i,π(x) :=ℛi,h(Qhi,π,πh;x)+1ϵiνi(πi,h(⋅∣x)). :=R p_i,h(Q_h^i,π, _h;x)+ 1 _i _i( _i,h(· x)). For two joint-action distributions πh(⋅∣x) _h(· x) and π~h(⋅∣x) π_h(· x), define the pointwise deviation Δh(x):=∥πh(⋅∣x)−π~h(⋅∣x)∥1. _h(x):=\| _h(· x)- π_h(· x)\|_1. Lemma 4 (One-Step Value Sensitivity). Let f:→ℝf:A satisfy ‖f‖∞≤M\|f\|_∞≤ M. For any distributions p,q∈Δ()p,q∈ (A), |a∼p[f(a)]−a∼q[f(a)]|≤M‖p−q‖1. |E_a p[f(a)]-E_a q[f(a)] |≤ M\|p-q\|_1. Theorem 4 (Risk-Sensitive Value Perturbation). Let π=πhh=1Hπ=\ _h\_h=1^H and π~=π~hh=1H π=\ π_h\_h=1^H be two Markov policy profiles. Let L_ env be the Lipschitz constant of the environment risk operator as in Theorem 2. Assume Qmax,hQ_ ,h is an upper bound incorporating both the payoff and regularization ranges, i.e., Qmax,h≥‖Qhi,π‖∞+Lν/ϵiQ_ ,h≥\|Q_h^i,π\|_∞+L_ν/ _i for all h,i,πh,i,π, where LνL_ν is the Lipschitz constant of νi _i. Then for all h∈[H]h∈[H] and x∈x , |Vhi,π(x)−Vhi,π~(x)|≤∑t=hH(L)t−hQmax,t⋅π~[Δt(Xt)∣Xh=x]. |V_h^i,π(x)-V_h^i, π(x) |≤ _t=h^H(L_ env)^t-hQ_ ,t·E_ π [ _t(X_t) X_h=x ]. (48) Taking the supremum over the state space, we have that supx∈|Vhi,π(x)−Vhi,π~(x)|≤∑t=hH(L)t−hQmax,t⋅supx′∈Δt(x′). _x |V_h^i,π(x)-V_h^i, π(x) |≤ _t=h^H(L_ env)^t-hQ_ ,t· _x _t(x ). (49) Proof. We proceed by backward induction on h. Base case (h=Hh=H): At the terminal stage there is no continuation value, so the policy-risk operator reduces to evaluation of the immediate payoff: VHi,π(x)=ℛi,H(ri,H,πH;x)+1ϵiνi(πi,H(⋅∣x)),V_H^i,π(x)=R p_i,H(r_i,H, _H;x)+ 1 _i _i( _i,H(· x)), which has sensitivity to πH _H bounded by Qmax,HQ_ ,H since ri,h(x,a)∈[0,1]r_i,h(x,a)∈[0,1] and Qmax,HQ_ ,H incorporates the regularization range. By Lemma 4, |VHi,π(x)−VHi,π~(x)|≤Qmax,H∥πH(⋅|x)−π~H(⋅|x)∥1=(L)0Qmax,HΔH(x). |V_H^i,π(x)-V_H^i, π(x) |≤ Q_ ,H\| _H(·|x)- π_H(·|x)\|_1=(L_ env)^0Q_ ,H _H(x). This satisfies (48) for t=Ht=H. Inductive step : Assume (48) holds for stage h+1h+1. Consider stage h. We decompose the value difference into two terms: deviation due to the policy change (Term I) and deviation due to the continuation value propagation (Term I) as follows: |Vhi,π(x)−Vhi,π~(x)| |V_h^i,π(x)-V_h^i, π(x) | ≤|ℛi,h(Qhi,π,πh;x)−ℛi,h(Qhi,π,π~h;x)|+1ϵi|νi(πi,h(⋅∣x))−νi(π~i,h(⋅∣x))|⏟(I) Policy Error ≤ |R p_i,h(Q_h^i,π, _h;x)-R p_i,h(Q_h^i,π, π_h;x) |+ 1 _i | _i( _i,h(· x))- _i( π_i,h(· x)) |_(I) Policy Error +|ℛi,h(Qhi,π,π~h;x)−ℛi,h(Qhi,π~,π~h;x)|⏟(I) Value Propagation. + |R p_i,h(Q_h^i,π, π_h;x)-R p_i,h(Q_h^i, π, π_h;x) |_(I) Value Propagation. • Bounding (I): By Lemma 4, the policy-risk operator term satisfies |ℛi,h(Qhi,π,πh;x)−ℛi,h(Qhi,π,π~h;x)|≤‖Qhi,π‖∞Δh(x)|R p_i,h(Q_h^i,π, _h;x)-R p_i,h(Q_h^i,π, π_h;x)|≤\|Q_h^i,π\|_∞ _h(x), and the Lipschitz continuity of νi _i gives 1ϵi|νi(πi,h(⋅|x))−νi(π~i,h(⋅|x))|≤(Lν/ϵi)Δh(x) 1 _i| _i( _i,h(·|x))- _i( π_i,h(·|x))|≤(L_ν/ _i) _h(x). Since Qmax,h≥‖Qhi,π‖∞+Lν/ϵiQ_ ,h≥\|Q_h^i,π\|_∞+L_ν/ _i by assumption, we obtain (I)≤Qmax,hΔh(x).(I)≤ Q_ ,h\, _h(x). • Bounding (I): Since ℛi,hR p_i,h is 1-Lipschitz in the Q-argument and Qhi,πQ_h^i,π depends on Vh+1i,πV_h+1^i,π through ℛi,hR e_i,h, which is L_ env-Lipschitz in the continuation value, we obtain (I)≤Lπ~[|Vh+1i,π(Xh+1)−Vh+1i,π~(Xh+1)||Xh=x].(I)≤ L_ env\,E_ π [ |V_h+1^i,π(X_h+1)-V_h+1^i, π(X_h+1) |\; |\;X_h=x ]. Combining the bounds on (I) and (I): Applying the inductive hypothesis for the term inside the expectation, we have that (I) (I) ≤Lπ~[∑t=h+1H(L)t−(h+1)Qmax,tπ~[Δt(Xt)∣Xh+1]|Xh=x] ≤ L_ envE_ π [ _t=h+1^H(L_ env)^t-(h+1)Q_ ,tE_ π[ _t(X_t) X_h+1]\; |\;X_h=x ] =∑t=h+1H(L)t−hQmax,tπ~[Δt(Xt)∣Xh=x]. = _t=h+1^H(L_ env)^t-hQ_ ,tE_ π[ _t(X_t) X_h=x]. Adding Term (I) (Qmax,hΔh(x)Q_ ,h _h(x)) to Term (I) completes the sum from t=ht=h to H, proving the theorem. ∎ Corollary 5 (End-to-End Value Robustness for RQRE-OVI). Suppose Algorithm 1 produces parameter estimates w^h w_h satisfying supx∈maxi∈[n]‖w^hi−whi,⋆‖2≤δh∀h∈[H]. _x _i∈[n]\| w_h^i-w_h^i, \|_2≤ _h ∀ h∈[H]. Let πh(x):=πh(x;w^h) _h(x):= _h RQRE(x; w_h) and πh⋆(x):=πh(x;wh⋆) _h (x):= _h RQRE(x;w_h ), where both are exact stage-game RQRE solutions for the respective payoff tables. By Theorem 3, the policy deviation is bounded by supxΔh(x)≤cμδh _x _h(x)≤ cμ _h. When the stage solver is approximate with error ε _ eq, the policy deviation bound becomes supxΔh(x)≤cμδh+ε _x _h(x)≤ cμ _h+ _ eq, and the value bound (50) acquires an additional additive term of HεH\, _ eq. Consequently, by Theorem 4, the value error bound holds: supx∈|V1i,π(x)−V1i,π⋆(x)|≤cμ∑t=1H(L)t−1Qmax,tδt. _x |V_1^i,π(x)-V_1^i,π (x) |≤ cμ _t=1^H(L_ env)^t-1Q_ ,t _t. (50) If δt≤δ¯ _t≤ δ and Qmax,t≤HQ_ ,t≤ H for all t, then the following bound also holds: supx∈|V1i,π(x)−V1i,π⋆(x)|≤cHδ¯μ(∑t=0H−1(L)t). _x |V_1^i,π(x)-V_1^i,π (x) |≤ cH δμ ( _t=0^H-1(L_ env)^t ). (51) Remark 4 (Risk Sensitivity and Comparison with Nash). The bound in (51) highlights the stability benefits of RQRE. When the risk measure is coherent or risk-neutral we have L=1L_ env=1 (Artzner et al., 1999), and recover a polynomial dependence O(H2δ¯/μ)O(H^2 δ/μ). For general convex risk measures where L>1L_ env>1, the error bound scales exponentially with the horizon, reflecting the inherent difficulty of risk-sensitive planning. However, crucially, this error remains Lipschitz continuous with respect to the estimation error δ¯ δ. Example 3 shows that Nash equilibria can exhibit O(1)O(1) policy jumps from arbitrarily small payoff perturbations at even a single stage, making the analogous bound for Nash-based algorithms potentially unbounded. Appendix E Proofs for Distributional Robustness of RQRE We begin by showing a result which demonstrates the equivalence of the penalty and constraint formulations of the convex risk measure. What follows is a simplified version of results in (Föllmer and Schied, 2002). Proposition 4 (Penalty–Constraint Duality for Convex Risk Measures). Let ρ:→ℝρ:Z be a convex risk measure with dual representation ρ(Z)=supp∈Δ(Ω)p[−Z]−φ(p)ρ(Z)= _p∈ ( )\ *E_p[-Z]- (p)\ as in Theorem 1, where φ:Δ(Ω)→(−∞,∞] : ( )→(-∞,∞] is a convex, lower-semicontinuous penalty function. Then for any bounded random variable Z, the penalized problem is equivalent to the constrained problem supp∈Δ(Ω)p[−Z]−φ(p)=supp∈Δ(Ω)p[−Z]s.t.φ(p)≤δ _p∈ ( ) \ *E_p[-Z]- (p) \\;=\; _p∈ ( ) \ *E_p[-Z]\;s.t.\; (p)≤δ \ for a radius δ=δ(ρ,Z)δ=δ(ρ,Z) uniquely determined by the optimality conditions, and always larger than the minimum value of φ . The risk parameter governing ρ acts as the Lagrange multiplier of the constraint. Proof. The equivalence follows by Lagrangian duality. Introduce the multiplier λ≥0λ≥ 0 for the constraint constraint φ(p)≤δ (p)≤δ and write supp∈Δ(Ω)p[−Z]s.t.φ(p)≤δ _p∈ ( ) \ *E_p[-Z]\;s.t.\; (p)≤δ \ =supp∈Δ(Ω)p[−Z]+minλ≥0λ(δ−φ(p)) = _p∈ ( ) \ *E_p[-Z]+ _λ≥ 0λ(δ- (p)) \ =minλ≥0supp∈Δ(Ω)p[−Z]−λφ(p)+λδ = _λ≥ 0 _p∈ ( ) \ *E_p[-Z]-λ (p) \+λδ =minλ≥0ϕ(λ)+λδ, = _λ≥ 0φ(λ)+λδ, where the second equality is due to strong duality, which holds by Slater’s condition as the minimum value of φ is always a feasible point. Note that the above implies that for any fixed δ, we can recover the equivalent λ by minimizing ϕ(λ)+λδφ(λ)+λδ. Thus the penalized version of the problem is equivalent to the hard constraint φ(p)≤δ (p)≤δ. ∎ We now prove Proposition 2 by showing how each component of the RQRE objective corresponds to a distributional robustness guarantee, using Proposition 4 as the key tool. Bounded rationality as policy robustness. The bounded rationality component of the RQRE objective assigns each player a regularized best response of the form πi∈argmaxμi∈Δ(i)a∼(μi,π−i)[ui(a)]+1ϵiνi(μi). _i∈ *arg\,max_ _i∈ (A_i) \ *E_a ( _i, _-i)[u_i(a)]+ 1 _i _i( _i) \. Applying Proposition 4 with φ=νi = _i and λ=1/ϵiλ=1/ _i, this is equivalent to πi∈argmaxμi∈Δ(i)a∼(μi,π−i)[ui(a)]s.t.νi(μi)≤δ, _i∈ *arg\,max_ _i∈ (A_i) \ *E_a ( _i, _-i)[u_i(a)]\;\;s.t.\;\; _i( _i)≤ _ pol \, where the radius δ=δ(ϵi) _ pol= _ pol( _i) is uniquely determined by the optimality conditions, with 1/ϵi1/ _i severing as the Lagrange multiplier of the constraint. Thus bounded rationality corresponds to distributionally robust policy selection where each agent maximizes expected payoff over all policies with a νi _i-ball of radius δ _ pol. As ϵi→∞ _i→∞, the multiplier vanishes, the constraint tightens, and the Nash best response is recovered. Conversely, as ϵi→0 _i→ 0, the ball expands and the policy approaches the maximizer of νi _i (e.g., the uniform distribution when νi _i is the negative entropy). Strategic robustness from risk aversion. In risk averse Markov games, the policy risk operator can be written as ℛi,hpol(Qhi,πh;x):=ρi,h(Zi,h|π−i,h(⋅∣x)),R^pol_i,h (Q_h^i, _h;x ):=ρ p_i,h (Z_i,h p\, |\, _-i,h(· x) ), where ρi,h(Z∣π−i)=suppi∈i−⟨Z,pi⟩−φ,i(pi,π−i),ρ p_i,h(Z _-i)= _p_i _i p\- Z,p_i - _ p,i(p_i, _-i)\, is the risk measure given in dual form. Applying Proposition 4 to this penalized problem yields the constrained formulation ρi,h(Z∣π−i)=suppi∈i−⟨Z,pi⟩∣φ,i(pi,π−i)≤δ.ρ p_i,h(Z _-i)= _p_i _i p\- Z,p_i \;\; \;\; _ p,i(p_i, _-i)≤ _ opp\. Environment robustness from risk aversion. Similarly, we write the environment risk operator in terms of the environment risk measure ρi,h(Z|)=inf~∈()∫Z(x′)~(dx′)+φ,i(~∥)ρ e_i,h(Z|P)= _ P (X) \ Z(x )\, P(dx )+ _ e,i( P\,\|\,P) \ which, due to Proposition 4, has the constrained formulation ρi,h(Z|)=inf~∈()∫Z(x′)~(dx′)∣φ,i(~∥)<δ.ρ e_i,h(Z|P)= _ P (X) \ Z(x )\, P(dx )\;\; \;\; _ e,i( P\,\|\,P)< _ env \. Here, we replace the sup with inf and flip the sign on the penalty function. In both these settings, the radii δ,δ _ opp, _ env is determined by by the optimality conditions of the penalized-constrained duality, with the Lagrange multiplier governed by the structure of φ,i _ p,i and φ,i _ e,i. The first, δ _ opp, can be viewed as defining a radius of opponent actions we are risk averse to. Similarly, δ _ env can be viewed as defining a radius of environment transitions. We usually set φ to be scaled by a risk aversion parameter 1/τ1/τ, and thus as τ→∞τ→∞ the radius δ will grow to cover the entire space of measures (either over the opponents actions or the environment transition). As τ→0τ→ 0 we recover the risk neutral Markov game setting, where risk averse utilities become utilities and risk averse value functions become value functions. Appendix F Additional Experimental Details In this section we provide further details on our experiments. Figure 4: Dynamic Stag Hunt (left) and Overcooked (right) environments used in experiments. F.1 Dynamic Stag Hunt Environment 1: Dynamic Stag Hunt. We evaluate on a Dynamic Stag Hunt environment based on the Melting Pot suite (Agapiou et al., 2022) implemented as a 9×99× 9 grid-world with episodes of 7575 timesteps. At each step, agents choose from six actions: four cardinal movements, stay, and interact. The grid contains four stag resources placed in the corners and four hare resources adjacent to the spawn points; agents pick up a resource by walking over it and may swap by stepping onto a different type. An interaction resolves when at least one agent chooses the interact action while both agents are adjacent and carrying a resource. The resulting payoffs follow the classic Stag Hunt matrix: mutual stag yields (4,4)(4,4), mutual hare yields (2,2)(2,2), and stag-hare mismatch gives (0,2)(0,2) with 0 to the stag-holder and 22 to the hare-holder. Upon interaction, both agents are respawned randomly at one of the spawn points with empty inventories, allowing multiple interactions per episode. The spatial structure introduces a coordination challenge beyond the matrix game: hare resources are close to spawn, providing a safe default, while stag resources require navigating to the corners, demanding both spatial and strategic coordination. Figure 5: Stag Hunt outcome distributions during training. Each panel shows the fraction of stag–stag, hare–hare, and mixed interaction outcomes (rolling average) for a given algorithm and risk-aversion level. NQOVI, QRE, and low risk averse RQRE agents converge to payoff dominant stag–stag outcomes, while highly risk averse agents to risk dominant hare–hare, confirming the expected equilibrium selection. Each state is represented by a 15-dimensional observation vector capturing both players’ normalized grid positions, Manhattan distances to the nearest stag and hare resources, inventory indicators (one-hot encoding of whether each agent carries a stag, hare, or nothing), normalized inter-agent distance, a timing feature (fraction of episode elapsed), and bias term. The joint state-action feature vector ϕ(x,a1,a2)∈ℝ200φ(x,a_1,a_2) ^200 is constructed by concatenating the observation, one-hot action encoding for both players, observation-action cross products for each player, and an action-action cross products. F.1.1 Dynamic Stag Hunt Training details We train all agents for K=5000K=5000 episodes using optimistic value iteration with ridge regression (λ=1.0λ=1.0) and exploration bonus coefficient β=0.1β=0.1. The experience buffer stores the most recent 10001000 transitions and parameters are updated every 2020 episodes via batch least-squares regression over the buffered data. The reward scale is set to 4.04.0, matching the maximum single-interaction payoff. For QRE and RQRE agents, the stage-game equilibrium solver runs for up to T=100T=100 fixed-point iterations with early stopping at tolerance 10−610^-6, using bounded rationality ϵ=0.05ε=0.05 for both players. RQRE agents use symmetric risk-aversion parameters τ1=τ2=τ _1= _2=τ, swept over 0.005,0.01,0.05,0.1,0.5,1.0\0.005,0.01,0.05,0.1,0.5,1.0\. All experiments use a single seed with results averaged over 200200 evaluation rollouts for cross-play and perturbation experiments. F.2 Overcooked Figure 6: Self play performance for each algorithm in Overcooked over 200 evaluation rollouts. Environment 2: Overcooked. We also evaluate on the Overcooked environment (Gessler et al., 2025); specifically, we use the version introduced in JaxMARL (Rutherford et al., 2024) with custom visualizations. Two agents operate in a small kitchen and must cooperate to prepare and deliver onion soups: pick up onions from piles, place them in a pot (which requires three onions to begin cooking), retrieve the finished soup with a plate, and deliver it to a serving location for a sparse reward of 20. Each agent chooses from six actions (four cardinal movements, stay, and interact) over a horizon of 100 timesteps. The environment provides both sparse delivery rewards and shaped rewards for intermediate subtask completion (e.g., placing an onion in the pot, picking up a plate when soup is cooking). The tight layout and sequential subtask structure make coordination essential, as agents must avoid blocking each other while efficiently dividing labor. The observation is a 49-dimensional vector encoding both agents’ positions, orientations, and inventory states, pot status (number of onions, cooking progress, readiness), per-agent proximity features to key locations (pot, onion pile, plate pile, serving goal), a time fraction, and hand-crafted goal-potential features that capture task-relevant interactions. The joint state-action feature vector ϕ(x,a1,a2)∈ℝ685φ(x,a_1,a_2) ^685 concatenates the observation, one-hot action encodings, and cross products between a selected subset of a core observation features and each agents’ action. Figure 7: Cross-play with a perturbed partner. Ego agent reward as a function of the partner noise for Stag Hunt (left) and Overcooked (right). At each evaluation step, the perturbed partner’s action is replaced with a fixed deterministic action (e.g., always move in a single direction) with probability δ, and the trained policy is executed otherwise. This deterministic perturbation ensures that deviations are high-signal rather than averaging out under uniform noise. The results are averaged over 200 evaluation rollouts at each noise level. F.2.1 Overcooked Training details Agents are trained for K=5000K=5000 episodes with ridge parameter λ=5.0λ=5.0 (larger than Stag Hunt due to the higher feature dimension d=685d=685) and exploration bonus β=0.1β=0.1. The buffer stores 500500 transitions and updates occur every 1010 episodes. Training rewards combine sparse delivery rewards and shaped intermediate rewards with equal weighting (both coefficients set to 1.01.0), and the reward scale is set to 20.020.0 to match the delivery reward. The QRE solver runs for up to T=100T=100 iterations with early stopping at tolerance 10−610^-6, with ϵ1=ϵ2=0.1 _1= _2=0.1. RQRE agents use symmetric τ1=τ2=τ _1= _2=τ swept over 0.005,0.01,0.05,1.0\0.005,0.01,0.05,1.0\. The environment runs in cooperative mode, where both agents receive identical sparse rewards upon delivery. F.3 Hyperparameters We provide the hyperparamters used in each experiment below. Table 1: Hyperparameters for Stag Hunt experiments Category Hyperparameter Value Setup Episodes (K) 5000 Feature dimension (d) 200 Ridge parameter (λ) 1.0 Exploration bonus (β) 0.1 Buffer size 1000 Update frequency 10 Seed 42 Environment Horizon (H) 75 Actions per agent 6 Grid size 9×99× 9 Rewards Stag–Stag payoff (4,4)(4,4) Hare–Hare payoff (2,2)(2,2) Stag–Hare payoff (0,2)(0,2) Step cost 0 RQRE Bounded rationality (ϵε) 0.1 Risk aversion (τ) 0.005,0.01,0.05,1.0\0.005,0.01,0.05,1.0\ Solver tolerance 10−610^-6 Max solver iterations (T) 100 Table 2: Hyperparameters for Overcooked experiments Category Hyperparameter Value Setup Episodes (K) 5000 Feature dimension (d) 685 Ridge parameter (λ) 5.0 Exploration bonus (β) 0.1 Buffer size 500 Update frequency 10 Seed 42 Environment Horizon (H) 100 Actions per agent 6 Layout Cramped Room Rewards Placement in pot 3 Plate pickup 4 Soup pickup 8 Delivery completion 6 Soup drop penalty −1-1 RQRE Bounded rationality (ϵε) 0.1 Risk aversion (τ) 0.005,0.01,0.05,1.0\0.005,0.01,0.05,1.0\ Solver tolerance 10−610^-6 Max solver iterations (T) 100