Paper deep dive
Training with (Swap) Regret Loss in a Single-Layer Self-Attention Model: A Case Study on the Probability Simplex
Chanwoo Park, Asuman Ozdaglar
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We revisit the regret loss framework introduced in Park et al. (2025), which uses decision-theoretic regret as a direct loss function for training models to make better decisions, through the lens of probability-simplex policies. Our first result shows that a single-layer self-attention model trained with regret loss admits a stationary point whose forward-pass exactly matches smoothed fictitious play with the appropriate stepsize that ensures no-regret behavior-i.e., for any given policy input, the model outputs the same update that smoothed fictitious play would produce. In parallel, we also newly introduce a swap-regret loss function, which extends the regret-loss framework beyond external regret and enables models to directly optimize for swap-deviation robustness. We further show that this swap-regret loss admits a stationary point whose forward pass implements the corresponding swap-regret update induced by classical Blum-Mansour no-pass implementation algorithm, with each head implementing an external-regret update via smoothed fictitious play. Together, these results show that regret-trained attention can realize differentiable mechanisms whose deployment induces equilibrium behavior in games: external-regret dynamics lead to coarse correlated equilibrium, while swap-regret dynamics lead to correlated equilibrium. Thus, regret-based objectives steer minimal attention architectures toward online-learning dynamics with game-theoretic guarantees, without supervised traces of those algorithms.
Tags
Links
- Source: https://arxiv.org/abs/2607.23333v1
- Canonical: https://arxiv.org/abs/2607.23333v1
Trouble viewing inline? Open PDF directly →
Full Text
158,254 characters extracted from source content.
Expand or collapse full text
Training with (Swap) Regret Loss in a Single-Layer Self-Attention Model: A Case Study on the Probability Simplex Chanwoo Park MIT EECS Asuman Ozdaglar MIT EECS Abstract We revisit the regret loss framework introduced in Park et al. (2025b), which uses decision-theoretic regret as a direct loss function for training models to make better decisions, through the lens of probability-simplex policies. Our first result shows that a single-layer self-attention model trained with regret loss admits a stationary point whose forward-pass exactly matches smoothed fictitious play with the appropriate stepsize that ensures no-regret behavior—i.e., for any given policy input, the model outputs the same update that smoothed fictitious play would produce. In parallel, we also newly introduce a swap-regret loss function, which extends the regret-loss framework beyond external regret and enables models to directly optimize for swap-deviation robustness. We further show that this swap-regret loss admits a stationary point whose forward pass implements the corresponding swap-regret update induced by classical Blum–Mansour no-swap-regret algorithm, with each head implementing an external-regret update via smoothed fictitious play. Together, these results show that regret-trained attention can realize differentiable mechanisms whose deployment induces equilibrium behavior in games: external-regret dynamics lead to coarse correlated equilibrium, while swap-regret dynamics lead to correlated equilibrium. Thus, regret-based objectives steer minimal attention architectures toward online-learning dynamics with game-theoretic guarantees, without supervised traces of those algorithms. 1 Introduction As large language models (LLMs) become increasingly integrated into everyday life, their usage is evolving from single-turn, task-specific applications to multi-agent, sequential decision-making scenarios (Yao et al., 2023; Hao et al., 2023; Shinn et al., 2024; Wang et al., 2023b; Significant Gravitas, 2023; Ahn et al., 2022; Wang et al., 2023a; Li et al., 2024). Rather than merely seeking one-off answers—such as solving a math problem (Guo et al., 2025) —users now engage with LLMs in ways that influence long-term planning and cumulative outcomes. As more individuals turn to LLMs to augment their decision-making, the setting naturally sometimes becomes multi-agent: each user constitutes an independent agent with unique goals, interacting with a shared or personalized model in pursuit of improved long-term outcomes and multi-agent sequential decision-making is regret, which quantifies the difference between the cumulative reward achieved by an agent and that of the best possible strategy in hindsight (Shalev-Shwartz, 2012). While minimizing regret is not the only objective in these settings, it provides a rigorous measure of an agent’s adaptability and learning efficiency over time. Recent work shows that off-the-shelf LLMs—those used without fine-tuning or explicit inference-time control—still struggle on even simple, canonical online decision-making tasks. Empirical evaluations consistently find that such models fail to explore effectively without external scaffolding (Krishnamurthy et al., 2024), incur linear regret in non-stochastic environments (Park et al., 2025b), exhibit unstable exploitation behavior (Xia et al., 2024), and underperform in non-stationary settings (Zhang et al., 2025). Taken together, these results indicate that fundamental decision-making abilities—regret minimization, exploration, and adaptation—remain unsolved for current LLMs. This highlights the need for principled methods that explicitly strengthen these foundations before deploying LLMs as autonomous agents at scale. To address this gap, Park et al. (2025b) proposed a novel training loss function named regret loss, which explicitly optimizes models to minimize regret across sequences of interactions. While their preliminary results—focused primarily on online learning tasks—demonstrated both empirical gains and theoretical guarantees, the broader applicability of regret-based training remains underexplored. Follow-up paper (Park et al., 2025a) found that post-training with regret-based signals can enable successful adaptation in single-agent environments, suggesting that regret supervision can play a critical role in improving sequential learning performance. Moreover, given that LLMs are fundamentally built on self-attention architectures, it is essential to understand how such regret-minimization dynamics manifest in even the simplest form of these models. However, a detailed characterization of regret-based training for single-layer self-attention is still incomplete even in the canonical probability-simplex setting. Park et al. (2025b) analyzed continuous ℓ2 _2-constrained policies and proved that regret loss recovers Follow-the-Regularized-Leader updates, yet it remains unclear how the same loss behaves when the policy must lie on the simplex—precisely the regime relevant to external and swap regret in online learning and games. Table 1 summarizes this gap. In this paper, we revisit the regret loss framework with a singular focus on probability-simplex policies. Our first contribution shows that, for the standard loss sequences used to evaluate external regret, a stationary point of a single-layer self-attention model trained with regret loss coincides with smoothed fictitious play with a ~(1/T) (1/ T) stepsize. Our second contribution targets swap regret. We introduce a new swap-regret loss that operationalizes swap regret as a differentiable training objective. Using this loss, we construct a multi-head linear self-attention network whose stationary point mirrors the classical Blum–Mansour no-swap-regret algorithm (Blum and Mansour, 2007). Each head implements a smoothed fictitious play external-regret update with a ~(1/T) (1/ T) stepsize, so the entire block behaves like a collection of parallel external-regret minimizers stitched together through multi-head self-attention. We prove that optimizing the swap-regret loss recovers this structure end-to-end, showing that differentiable multi-head attention can faithfully instantiate swap-regret dynamics. Together, these results highlight how external- and swap-regret objectives can be realized directly within minimal Transformer architectures. This provides a mechanistic route from regret-based post-training objectives for LLM agents to equilibrium guarantees in multi-agent environments. Regret-trained attention is not merely imitating an online-learning algorithm; at the stationary points we identify, it implements a differentiable mechanism whose repeated deployment induces the corresponding game-theoretic behavior. Single-head softmax attention implements external-regret dynamics, so multi-agent deployment leads to coarse correlated equilibrium. Multi-head fixed-point attention implements swap-regret dynamics, so deployment leads to correlated equilibrium. The choice of regret surrogate is therefore not only an optimization detail: external-regret loss induces coarse-deviation robustness, while swap-regret loss induces action-contingent deviation robustness. Notation We write d 1_d and d 0_d for the d-dimensional all-ones and all-zeros vectors, d×d O_d× d for the d×d× d zero matrix, and Id×dI_d× d for the d×d× d identity, let () (A) be the probability simplex over the action set A, use [d]:=1,…,d[d]:=\1,…,d\ for the first d integers, and write ⋅ 1\·\ for indicator functions. For asymptotics as T→∞T→∞ we use (f(T)) (f(T)) to denote quantities bounded above and below by constant multiples of f(T)f(T), O(f(T))O(f(T)) for upper bounds, o(f(T))o(f(T)) for terms that vanish relative to f(T)f(T), and O~(f(T)) O(f(T)) (or ~(f(T)) (f(T))) when bounds hold up to polylogarithmic factors. For a set and norm ∥⋅∥\|·\|, we denote by Proj,∥⋅∥(x):=argminy∈‖x−y‖Proj_ ,\|·\|(x):= argmin_y∈ \|x-y\| the projection of x onto ; when the norm is Euclidean we write Proj(x)Proj(x) for brevity. For any vector v, P⟂vP_ v denotes the orthogonal projector onto the subspace orthogonal to v. For a Markov matrix P, we write Fixed−Point(P)Fixed-Point(P) for any stationary distribution satisfying π=Pπ=Pπ; when the stationary distribution is unique we identify Fixed−Point(P)Fixed-Point(P) with that π. 2 Preliminaries 2.1 Linear Self-Attention We consider a single-layer linear attention model equipped with an output operator that maps the resulting representation into a decision policy. This architecture represents one of the simplest forms of Transformer-based models and has been used in prior work to analyze the inductive properties of attention mechanisms (Ahn et al., 2023; Mahankali et al., 2023; Park et al., 2025b). The output of the model is given by: g((ℓ1,…,ℓt,d);V,K,Q,vc,kc,qc)=Operator(∑i=1t(Vℓi+vc)((Kℓi+kc)⊺(Qd+qc))), g(( _1,…, _t, 1_d);V,K,Q,v_c,k_c,q_c)= Operator ( _i=1^t(V _i+v_c) ((K _i+k_c) (Q 1_d+q_c) ) ), (1) where V,K,Q∈ℝd×dV,K,Q ^d× d are the value, key, and query matrices, and vc,kc,qc∈ℝdv_c,k_c,q_c ^d are their corresponding bias vectors. We denote the full set of model parameters as ϕ=(V,K,Q,vc,kc,qc)φ=(V,K,Q,v_c,k_c,q_c). The model takes as input a sequence of loss vectors (ℓ1,…,ℓt)⊂ℝd( _1,…, _t) ^d, along with a placeholder vector d∈ℝd 1_d ^d, and produces a prediction for the next policy πt+1 _t+1. The inner product term computes attention scores over the sequence (ℓ1,…,ℓt)( _1,…, _t), and the resulting aggregated vector is transformed by a final mapping, denoted as Operator, to produce a valid policy. The specific choice of Operator depends on the policy space . For example, if =() = (A), the probability simplex induced by a finite action set (as in the Experts Problem), Operator is the standard SoftmaxSoftmax function. In the most basic case, Operator can be the identity map, Operator(x)=x Operator(x)=x, recovering the original form of linear self-attention (Ahn et al., 2023; Zhang et al., 2023; Schlag et al., 2021). This formulation provides a minimal yet expressive setting for studying how attention-based models can learn adaptive policies in sequential decision-making environments. In this paper, as Equation 1 has the equivalent formulation with g((ℓ1,…,ℓt,d);V,a,vc)=Operator(∑i=1t(Vℓiℓi⊺a+(V+vca⊺)ℓi+vc)), g(( _1,…, _t, 1_d);V,a,v_c)= Operator ( _i=1^t(V _i _i a+(V+v_ca ) _i+v_c) ), (2) where V∈ℝd×dV ^d× d and vc,a∈ℝdv_c,a ^d. Equation 2 is a reduced form of Equation 1 but having the same representation power with Equation 1. 2.2 Learning Environment 2.2.1 Online Learning We consider the online learning framework in which an agent interacts with an environment over T rounds, making sequential decisions and receiving feedback. At each round t∈[T]t∈[T], the agent selects a decision policy πt∈ _t∈ , where is a bounded decision space. After committing to πt _t, the environment reveals a loss function ft:→[−B,B]f_t: →[-B,B] for some constant B>0B>0, which may be chosen adversarially. The agent then incurs loss ft(πt)f_t( _t) and updates her policy based on this feedback. A fundamental special case is when the action space A is finite and the decision set is the probability simplex over A, i.e., =() = (A). This is known as the Experts Problem (Cover, 1966; Vovk, 1990; Littlestone and Warmuth, 1994; Hazan, 2016). In this case, each loss function can be expressed as a linear form ft(πt)=⟨ℓt,πt⟩f_t( _t)= _t, _t , where ℓt∈ℝd _t ^d is a loss vector (with d:=||d:=|A|). Whenever we refer to the policy space as the simplex below, we implicitly mean this finite-action setting. The agent will receive the entire loss vector ℓt _t in the full-information setting. 2.2.2 Repeated Static Games The online learning framework extends naturally to multi-agent interactions through the lens of repeated static games. Let =⟨N,nn∈[N],rnn∈[N]⟩G= N,\A_n\_n∈[N],\r_n\_n∈[N] denote a normal-form game with players n∈[N]n∈[N], where each nA_n is the action set of player n, and rn::=1×⋯×N→[−B,B]r_n:A:=A_1×…×A_N→[-B,B] is her reward (or negative loss) function. At each round t, every player outputs a policy πn,t∈(n) _n,t∈ (A_n). We use the term action only for the realized play induced by the policy: in finite (simplex) domains, an action an,ta_n,t is sampled as an,t∼πn,ta_n,t _n,t. From the perspective of player n, the realized joint play induces an individual online learning problem over (n) (A_n) with per-round loss ℓn,t:=−a−n,t∼π−n,t[rn(⋅,a−n,t)]:=−rn(⋅,π−n,t). _n,t:=-E_a_-n,t _-n,t [r_n(·,a_-n,t) ]:=-r_n(·, _-n,t). 2.3 Performance Metrics: External and Swap Regret 2.3.1 External Regret We begin by defining external regret (usually just denoted as regret), a central performance measure in online learning and repeated games. Let A denote an algorithm that selects a sequence of policies (π,t)t∈[T]( _ A,t)_t∈[T] over a decision space . Given a sequence of loss functions (ft)t∈[T](f_t)_t∈[T], the external regret of A is defined as Regret((ft)t∈[T]):=∑t=1Tft(π,t)−infπ∈∑t=1Tft(π). _ A((f_t)_t∈[T]):= _t=1^Tf_t( _ A,t)- _π∈ _t=1^Tf_t(π). (3) This quantity compares the cumulative loss of the learner to that of the best fixed decision in hindsight. In the Experts Problem, this specializes to Regret((ℓt)t∈[T]):=∑t=1T⟨ℓt,π,t⟩−infπ∈∑t=1T⟨ℓt,π⟩, _ A(( _t)_t∈[T]):= _t=1^T _t, _ A,t - _π∈ _t=1^T _t,π , (4) where each ℓt∈ℝd _t ^d is a loss vector and =() = (A) is the simplex over the finite action set A. An algorithm A is said to be no-(external-)regret if sup(ft)Regret((ft)t∈[T])=o(T), _(f_t)Regret_ A((f_t)_t∈[T])=o(T), i.e., the worst-case regret grows sublinearly in T. 2.3.2 Swap Regret While external regret compares the learner’s performance to the best fixed decision in hindsight, swap regret allows each action to be reassigned to another action in hindsight. Formally, a swap deviation is encoded by a mapping σ:[d]→[d]σ:[d]→[d] (or equivalently by a row-stochastic matrix PσP_σ). The swap regret of algorithm A in the Experts setting is Swap-Regret((ℓt)t∈[T]):=maxσ:[d]→[d]∑t=1T⟨π,t,ℓt−Pσ⊺ℓt⟩=maxP∈ℳ∑t=1T⟨π,t,ℓt−P⊺ℓt⟩, -Regret_ A(( _t)_t∈[T]):= _σ:[d]→[d] _t=1^T _ A,t,\, _t-P_σ _t = _P _t=1^T _ A,t,\, _t-P _t , (5) where Pσ∈0,1d×dP_σ∈\0,1\^d× d is defined by (Pσ)ij=σ(i)=j(P_σ)_ij= 1\σ(i)=j\ and ℳ:=P∈ℝd×d:Pd=d,P≥0M:=\P ^d× d:P 1_d= 1_d,\,P≥ 0\ denotes the set of row-stochastic (Markov) matrices. The equality follows since the objective is linear in each row of P, and thus its maximum over ℳM is attained at an extreme point PσP_σ. Intuitively, swap regret measures how much the learner could have improved by systematically substituting each played action i with another action σ(i)σ(i) across all rounds. An algorithm is said to be no-swap-regret if the above quantity is o(T)o(T). In this paper, if A is clear from the context, we will drop the subscript and write Regret and Swap-Regret for external and swap regret, respectively. 2.4 Equilibrium Concepts in Repeated Games Repeated interactions among learning agents often lead to stable long-run behaviors that correspond to equilibrium concepts. Writing everything in terms of policies allows us to reason directly about simplex-valued play. Coarse Correlated Equilibrium (CCE). A distribution μ∈()μ∈ (A) is a CCE if, for every player n and every fixed (policy-level) deviation πn′∈(n) _n ∈ (A_n), π∼μ[rn(π)]≥π∼μ[rn(πn′,π−n)].E_π μ\! [r_n(π) ]\;≥\;E_π μ\! [r_n( _n ,\, _-n) ]. Thus, no player can gain by unconditionally switching to a single alternative policy prior to receiving any recommendation. Correlated Equilibrium (CE). A distribution μ∈()μ∈ (A) over joint actions is a correlated equilibrium if, for every player n and every action-dependent deviation represented by a row-stochastic Markov matrix Mn∈ℳM_n , π∼μ[rn(π)]≥π∼μ[rn(Mn(πn),π−n)],E_π μ\! [r_n(π) ]\;≥\;E_π μ\! [r_n\! (M_n( _n),\, _-n ) ], where Mn(πn)M_n( _n) denotes the (possibly mixed) action drawn from the row of MnM_n corresponding to the recommended action πn _n. Thus, no player can gain by conditionally deviating from the recommendation using any action-dependent strategy. If every player achieves no external regret, the empirical average play converges to a CCE, and if every player achieves no swap regret, the empirical average play converges to a CE (Cesa-Bianchi and Lugosi, 2006). 2.5 Concepts of Regret Loss Training We now define a training objective that explicitly minimizes regret across sampled decision-making environments. Let the model be parameterized by ϕφ, and let modelϕmodel_φ denote a policy generator (e.g., a single-layer attention model as in Equation 1). The regret loss function is defined as ℒ(ϕ,):=[h(Regretmodelϕ((ft)t∈[T]))], (φ,D):=E_D [h (Regret_model_φ ((f_t)_t∈[T] ) ) ], (6) where h:ℝ→ℝh:R is a convex surrogate function (e.g., identity, squared loss, or a smooth approximation of max ), and the expectation is taken over decision-making instances sampled from D. Throughout the paper we instantiate Regret as either external regret or swap regret. We will describe the precise form of the model input shortly. The distribution D captures the randomness in the environment. Each round’s loss function is ft(π)=⟨ℓt,π⟩f_t(π)= _t,π , where ℓt∼d _t _d is a sampled loss vector. For each decision round t, the model receives the interaction history and produces the next policy πt+1 _t+1. Especially, the model input is the full history of loss vectors, i.e., (ℓ1,…,ℓt)( _1,…, _t). Previous theoretical work on regret-loss training (Park et al., 2025b, a) primarily analyzed continuous ℓ2 _2-constrained policies. In this paper we restrict attention to the probability simplex—the setting relevant to external and swap regret—and study how regret loss shapes the induced dynamics. Table 1 summarizes the most relevant comparisons. No Regret (test) Operator Post Operation FTRL Equivalence FTRL stepsize Park et al. (2025b) Theorem 5.2 Online Learning (=B(d,R,∥⋅∥2) =B( 0_d,R, \|· \|_2)) Identity ProjB(d,R,∥⋅∥2)Proj_B( 0_d,R, \|· \|_2) ✓ (1Td) ( 1 Td ) Park et al. (2025b) Conjecture 3 Online Learning (=() = (A)) Static Game SoftmaxSoftmax × [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0× ? ?? Theorem 1 Online Learning (=() = (A), no external regret) Static Game SoftmaxSoftmax × [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0× ✓ (Stationary Point) (1T) ( 1 T ) Theorem 2 Online Learning (=() = (A), no swap regret) Static Game Row-wise SoftmaxSoftmax, Fixed−PointFixed-Point × [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0× ✓ (Stationary Point) Each head implements an external-regret FTRL update (1T) ( 1 T ) Table 1: The top rows report known results from Park et al. (2025b); the bottom rows highlight our new stationary-point characterizations showing that regret-loss objectives on attention models recover smoothed fictitious play (external regret) and Blum–Mansour dynamics (swap regret). 3 Emergence of Smoothed Fictitious Play as a Stationary Point of Single-layer Linear Self-Attention We begin by revisiting the observation of Park et al. (2025b) that single-layer linear self-attention trained with the regret-loss objective recovers FTRL updates with L2L_2 regularization when the operator is the identity. Their result, however, depends crucially on applying a projection Proj,∥⋅∥Proj_ ,\|·\| to the model output only at inference time: the training objective never sees the projection, so the match to FTRL is achieved post hoc. This leaves open whether the post operation can be integrated directly into the optimization so that the learned representation is already the desired policy without any additional post operation steps. Throughout this section we adopt an end-to-end viewpoint: the same nonlinearity used at inference—namely the SoftmaxSoftmax mapping—is embedded directly in the loss. Consequently, the model must optimize through the SoftmaxSoftmax transformation itself, jointly learning the attention weights while satisfying the policy-domain constraints. We show that even under this stricter objective, the stationary points remain fully interpretable: they coincide with smoothed fictitious play on the simplex. Moreover, we characterize the associated theoretical stepsize of these stationary points, which in turn yields a no-regret guarantee. This is also conjectured by Park et al. (2025b) that the stationary point of the regret-loss function is the smoothed fictitious play. Theorem 1. The configuration of a single-layer linear attention model as defined in Equation 2, with Operator = SoftmaxSoftmax, and parameters V=−kId×dV=-kI_d× d, a=da= 0_d, and vc=vdv_c=v 1_d, is a stationary point of the regret-loss function Equation 6 if k=~(1/T)k= (1/ T), with h(x)=x2h(x)=x^2, ft(π)=⟨ℓt,π⟩f_t(π)= _t,π , where ℓt∼(d,Id×d) _t ( 0_d,I_d× d) i.i.d. Proof structure for Theorem 1. At V=−kId×dV=-kI_d× d, a=da= 0_d, and vc=vdv_c=v 1_d, the round-t logits and policy satisfy zt=−k∑s<tℓs+(t−1)vd,πt=Softmax(−k∑s<tℓs),z_t=-k _s<t _s+(t-1)v 1_d, _t=Softmax\! (-k _s<t _s ), where the second identity uses shift-invariance. Thus the forward pass is entropy-regularized FTRL, equivalently smoothed fictitious play, with learning rate k; the substantive issue is to prove that the full regret-loss gradient vanishes at a nonzero k of the claimed scale. Let RT(k)R_T(k) be the external regret induced by the above policy and L(k)=[RT(k)2]L(k)=E[R_T(k)^2]. The first-order conditions are then verified block by block: the vcv_c-block is annihilated pointwise by shift-invariance and Jsm(z)⊺d=dJ_sm(z) 1_d= 0_d; the a-block requires Gaussian permutation symmetry, which makes the expected gradient a multiple of d 1_d, while the softmax Jacobian maps into the zero-sum subspace. For the V-block, permutation equivariance and the same row-sum constraint force ∇Vℒ(−kI,,v)=α(k)(Id×d−1ddd⊺). _VL(-kI, 0,v 1)=α(k) (I_d× d- 1d 1_d 1_d ). Consequently the matrix condition reduces to the scalar derivative along the ray V=−kIV=-kI. It remains to locate a zero of L′(k)L (k). The appendix derives L′(k)=−2(k)1+2(k)2,L (k)=-2_1(k)+2_2(k), where 1 is the learner-response term and 2 is the best-fixed-action comparator term. Expanding πt(k)=u−kJ0St−1+O(k2‖St−1‖∞2) _t(k)=u-kJ_0S_t-1+O(k^2\|S_t-1\|_∞^2) and Jt(k)=J0+O(k‖St−1‖∞)J_t(k)=J_0+O(k\|S_t-1\|_∞), with u=d/du= 1_d/d and J0=Diag(u)−uu⊺J_0=Diag(u)-u , separates the signs of these terms: the comparator contribution dominates for very small k, giving L′(k)<0L (k)<0, while at the inverse-T T scale the learner-response term dominates after Gaussian maximum, MGF, and softmax-Jacobian remainder bounds, giving L′(k)>0L (k)>0. Continuity yields a root k⋆=~(1/T)k = (1/ T), at which every parameter block is first-order stationary. The proof, deferred to Appendix A, pins down the precise scale of the attention weight k. Earlier analyses of in-context learning only established that FTRL-like outputs could be recovered at stationary points if they have a SoftmaxSoftmax layer (Cheng et al., 2023) or convergence of the training dynamics (Chen et al., 2024); in contrast, Theorem 1 identifies the first-order stationary point and shows that the resulting update is precisely smoothed fictitious play with learning rate ~(1/T) (1/ T). Empirically, we observe a unique k⋆(d,T)k (d,T) consistent with this scaling, further supporting the theoretical prediction (Figure 1). Figure 1: Estimated stationary stepsize k⋆k on the probability simplex as a function of (d,T)(d,T) for the single-head softmax model (left) and the swap-regret architecture (right). Each marker aggregates 5050 independent runs with 800800 Monte Carlo samples per run; shaded bands indicate ±1± 1 standard deviation. The above characterizations lift immediately to multi-agent learning dynamics. Corollary 1. Consider a repeated game where each player deploys the trained single-layer architecture from Theorem 1 with Operator = SoftmaxSoftmax. Then the time-averaged joint play converges to a coarse correlated equilibrium (CCE) in finite action games. Thus, enforcing the simplex-respecting nonlinearity inside the loss not only yields interpretable single-agent updates but also preserves standard equilibrium guarantees when the model is embedded in multi-agent environments. Mechanistically, the learned attention layer implements an external-regret dynamic, and external regret is precisely the deviation notion underlying CCE: no player can improve by replacing their realized sequence of actions with a single fixed action in hindsight. This connects the stationary-point characterization of regret-trained attention directly to coarse-deviation robustness in games. 3.1 Local minimality within the smoothed-fictitious-play family Proposition 1 (Restricted local minimality). Let L(k):=[RT(k)2],πt(k)=Softmax(−k∑s<tℓs).L(k):=E[R_T(k)^2], _t(k)=Softmax\! (-k _s<t _s ). Under the setting of Theorem 1, there exists k⋆=~(1/T)k = (1/ T) that is a local minimizer of L(k)L(k). Consequently, V=−k⋆Id×d,a=d,vc=vdV=-k I_d× d, a= 0_d, v_c=v 1_d is a local minimizer of the population regret loss when optimization is restricted to this Softmax–smoothed-fictitious-play scalar family. Proof. The sign estimates in the proof of Theorem 1 provide k−<k+k_-<k_+, both at the stated scale up to the displayed dimension and polylogarithmic factors, such that L′(k−)<0L (k_-)<0 and L′(k+)>0L (k_+)>0. The continuous function L attains a minimum on [k−,k+][k_-,k_+]. The strict derivative signs exclude both endpoints, so at least one minimizer k⋆k lies in the interior. It is therefore a local minimizer of L, and L′(k⋆)=0L (k )=0. The full-gradient symmetry reduction in the proof of Theorem 1 then also gives first-order stationarity in the unrestricted parameterization. ∎ This proposition is deliberately restricted to the scalar FTRL family. It does not establish local minimality over the full parameter space or global convergence of gradient descent. We separately test whether training from random initialization reaches the identified behavior. 3.2 Empirical FTRL matching We test whether unrestricted random-initialization training reaches the entropy-FTRL behavior identified by Theorem 1. We train the reduced one-layer model with squared regret loss at d=3,T=20d=3,T=20 for three independent seeds, without FTRL trajectories, FTRL parameters, or a constraint V=−kIV=-kI. For each learned checkpoint, we fit a scalar η∈[0,5]η∈[0,5] on 4,0964,096 held-out Gaussian sequences by minimizing the mean policy MSE between the model output and πtFTRL(η)=Softmax(−η∑s<tℓs). _t^FTRL(η)=Softmax\! (-η _s<t _s ). Figure 2 (left) shows that the learned policies are close to entropy-FTRL: on average, only 2.71%2.71\% of probability mass must be moved to match the fitted FTRL policy. This is finite-horizon evidence that the theoretically identified family is empirically reachable; it is not a claim of global convergence from arbitrary initialization. 3.3 Regret training in deeper Softmax Transformers We next train two- and four-layer causal Softmax Transformers under the same Gaussian regret objective. These models use four attention heads per layer; we do not fit their outputs to FTRL or claim an FTRL identification theorem. We evaluate on held-out biased-Gaussian sequences ℓt=m+ϵt _t=m+ _t, where the sequence-specific mean m creates a best action that must be learned from history. Writing RtR_t for cumulative regret through time t, both depths maintain substantially smaller Rt/tR_t/t than the non-adaptive uniform policy. At T=20T=20, the two- and four-layer models attain respectively R20=4.380±0.046R_20=4.380± 0.046 and 4.322±0.0174.322± 0.017, or normalized regret 0.2190.219 and 0.2160.216, compared with R20=7.021±0.052R_20=7.021± 0.052 and R20/20=0.351R_20/20=0.351 for uniform play (Figure 2, right). (a) One-layer FTRL matching Quantity Mean ± SD Fitted η η 0.4456±.00460.4456±.0046 Policy MSE 0.000739±.0001760.000739±.000176 Mean L1L_1 0.0542±.00710.0542±.0071 TV (% mass) 0.0271±.00360.0271±.0036 (2.71%2.71\%) Error/action 0.0181±.00240.0181±.0024 (1.811.81 p) (b) Regret over time Figure 2: Random-initialization regret-loss training at d=3,T=20d=3,T=20. Left: entropy-FTRL fit to one-layer policies; “p” denotes percentage points. Right: normalized regret for deeper Transformers on biased-Gaussian sequences. The table reports mean ± sample standard deviation and curves show means with ±1± 1 standard-error bands across three seeds. 3.4 Coarse-correlated-equilibrium evaluation We evaluate the learned policies in a 3×33× 3 weighted zero-sum rock–paper–scissors game whose equilibrium marginal is (3,2,1)/6(3,2,1)/6. With expected full-information loss feedback, we form the time-averaged joint mixed play μ¯T=T−1∑t=1Tπ1,t⊗π2,t μ_T=T^-1 _t=1^T _1,t _2,t and measure its maximum CCE-deviation gap. At T=20T=20, the one-, two-, and four-layer models obtain respectively 0.0832±0.00280.0832± 0.0028, 0.0467±0.00950.0467± 0.0095, and 0.0653±0.00540.0653± 0.0054, compared with 0.11110.1111 for uniform play. Figure 4 (left) reports the complete curves. This directly measures the equilibrium quantity controlled by average external regret. 4 Swap-Regret Loss Minimization on the Probability Simplex We now recall the classical reduction of Blum and Mansour, which turns any external-regret minimizer on the simplex into a swap-regret minimizer. Let the action set be =1,…,dA=\1,…,d\ and write () (A) for the corresponding probability simplex. A swap transformation is represented by a column-stochastic matrix ≔P=(p1∣…∣pd)∈ℝd×d:pi∈()for all i, \; \; \P=(p_1 … p_d) ^d× d:p_i∈ (A)\;for all i \, which acts on π∈()π∈ (A) by π↦Pπ=∑i=1dπipiπ Pπ= _i=1^d _ip_i. At round t, the adversary reveals a loss vector ℓt∈ℝd _t ^d so that the learner incurs the linear loss ⟨ℓt,πt⟩ _t, _t . Blum–Mansour construction. Fix d copies of an external-regret minimizer for () (A), denoted ℛ1,…,ℛdR_1,…,R_d. At each round t∈[T]t∈[T] the swap-regret algorithm performs: 1. Next strategy. For each i∈[d]i∈[d], query ℛiR_i for pi,t∈()p_i,t∈ (A). Assemble the matrix Pt=(p1,t∣…∣pd,t)∈.P_t\;=\; (p_1,t … p_d,t )∈ . Compute a fixed point πt=Fixed−Point(Pt)∈() _t=Fixed-Point(P_t)∈ (A) and play πt _t. 2. Loss feedback. After observing the loss vector ℓt _t, each external-regret copy ℛiR_i receives the scaled linear loss xi,t=πt,iℓtx_i,t\;=\; _t,i\, _t, i.e., it runs on the loss vector xi,tx_i,t. Thus each ℛiR_i runs on the same action space () (A), but with losses rescaled by the i-th coordinate of the fixed point πt _t. Fact 1 (Blum–Mansour). Let RegretiRegret_i denote the external regret of ℛiR_i after T rounds when fed the losses (xi,t)t∈[T](x_i,t)_t∈[T], that is Regreti((xi,t)t∈[T])≔maxp~i∈()∑t=1T(⟨xi,t,pi,t⟩−⟨xi,t,p~i⟩).Regret_i((x_i,t)_t∈[T])\; \; _ p_i∈ (A) _t=1^T ( x_i,t,p_i,t - x_i,t, p_i ). (7) Then the cumulative swap regret admits the exact column-wise decomposition Swap-Regret((ℓt)t∈[T])=−minP^=(p^1∣…∣p^d)∈∑t=1T∑i=1d⟨xi,t,p^i−pi,t⟩,Swap-Regret(( _t)_t∈[T])=- _ P=( p_1 … p_d)∈ _t=1^T _i=1^d x_i,t, p_i-p_i,t , (8) and therefore satisfies Swap-Regret((ℓt)t∈[T])≤∑i=1dRegreti((xi,t)t∈[T]).Swap-Regret(( _t)_t∈[T])\;≤\; _i=1^dRegret_i((x_i,t)_t∈[T]). In particular, if each ℛiR_i has sublinear external regret, then the Blum–Mansour construction has sublinear swap regret. The proof is deferred to Appendix C. Inspired by the classical Blum–Mansour construction, we introduce a new neural architecture for swap-regret minimization. Our design uses a d-head linear self-attention module to parameterize the transition matrix. After the multi-head attention step, each head applies a SoftmaxSoftmax to produce one strictly positive column of the transition matrix, thereby obtaining a valid column-stochastic Markov matrix. The final policy is then computed via a Fixed−PointFixed-Point procedure, which can be efficiently implemented using power iteration. This yields a differentiable, end-to-end model that mirrors the theoretical structure of the Blum–Mansour minimizer while allowing scalable learning. Mathematically, the architecture is given by: πt+1 _t+1 =Fixed-Point((p1,t+1∣⋯∣pd,t+1)), = Fixed-Point\! ( (p_1,t+1\, \,·s \,p_d,t+1 ) ), (9) pj,t+1 p_j,t+1 =Softmax(∑i=1t(V(j)XiXi⊺a(j)+(V(j)+vc(j)a(j)⊺)Xi+vc(j))),j∈[d]. =Softmax\! ( _i=1^t (V^(j)X_iX_i a^(j)+(V^(j)+v_c^(j)a^(j) )X_i+v_c^(j) ) ), j∈[d]. where V(j)∈ℝd×d2,a(j)∈ℝd2,vc(j)∈ℝdV^(j) ^d× d^2,a^(j) ^d^2,v_c^(j) ^d are the parameters for the j-th head of the linear self-attention module, and Xi:=ℓi⊗πi=(xi,t)t=1⊺∈ℝd2X_i:= _i _i=(x_i,t)_t=1 ^d^2, which consider every possible combination of ℓi _i and πi _i. The Fixed−PointFixed-Point operation is implemented using power iteration. Remark 1 (Differentiability of the fixed-point layer). Because every column pj,t+1p_j,t+1 is produced by a SoftmaxSoftmax, the matrix Pt+1=(p1,t+1∣⋯∣pd,t+1)P_t+1=(p_1,t+1 ·s p_d,t+1) has strictly positive entries and is column-stochastic. By Perron–Frobenius theory, Pt+1P_t+1 is primitive and has a unique stationary distribution in the relative interior of the simplex. Moreover, the eigenvalue 11 is simple, so the fixed-point map P↦Fixed−Point(P)P -Point(P) is smooth on the open set of strictly positive column-stochastic matrices; equivalently, differentiability follows from the implicit function theorem after restricting to the simplex tangent space u:d⊺u=0\u: 1_d u=0\. In implementation, gradients can be obtained by backpropagating through the finite power-iteration procedure, or by implicit differentiation of the stationary equation π=Pπ=Pπ. Figure 3: Multi-head linear self-attention architecture for swap-regret minimization. Each head processes the block features Xt=ℓt⊗πtX_t= _t _t and outputs one simplex vector pj,t+1p_j,t+1 through a SoftmaxSoftmax layer; these vectors form a transition matrix, and the final policy πt+1 _t+1 is obtained as its fixed point, matching the Blum–Mansour reduction from external regret to swap regret. Now, we provide a theoretical analysis of the new architecture. Theorem 2. The configuration of the multi-head linear self-attention architecture defined in Equation 9 is a stationary point of the swap-regret loss ℒ((V(j),a(j),vc(j))j∈[d]) ((V^(j),a^(j),v_c^(j))_j∈[d]) =X∼(0,Id2T)[(minP^∈(([d]))d∑t=1T∑i=1d⟨xi,t,P^i−pi,t⟩)2], =E_X (0,I_d^2T) [ ( _ P∈( ([d]))^d _t=1^T _i=1^d x_i,t, P_i-p_i,t )^2 ], (10) where xi,t:=Xd(i−1)+1:di,t∈ℝd,x_i,t:=X_d(i-1)+1:di,\;t ^d, and the parameters satisfy V(j)=(V1(j),…,Vd(j)),Vr(j)=−kId×d,r=j,d×d,rj,a(j)=d2,vc(j)=vd,V^(j)=(V^(j)_1,…,V^(j)_d), V^(j)_r= cases-kI_d× d,&r=j,\\[3.0pt] O_d× d,&r≠ j, cases a^(j)= 0_d^2, v_c^(j)=v 1_d, for some k=(1/T)k= (1/ T). Proof structure for Theorem 2. At the proposed configuration, head j ignores all blocks of XtX_t except the block xj,tx_j,t, and its logits become zj,t=−k∑s<txj,s+(t−1)vd.z_j,t=-k _s<tx_j,s+(t-1)v 1_d. Thus every head is a single-head smoothed fictitious-play learner, while the swap objective couples the heads through the fixed-point policy and the Blum–Mansour decomposition in 1. The gradient calculation separates this coupling carefully: shift invariance eliminates the vc(j)v_c^(j) and a(j)a^(j) directions, block independence eliminates off-diagonal Vr(j)V^(j)_r terms for rjr≠ j, and permutation equivariance reduces the diagonal block Vj(j)V^(j)_j to the projector direction I−d−1dd⊺I-d^-1 1_d 1_d . The remaining directional derivative along Vj(j)=−kIV^(j)_j=-kI is exactly d times the scalar derivative of the single-head external-regret objective, so the same k⋆k scale from Theorem 1 yields stationarity. Here, Equation 10 is the square of the swap-regret decomposition in Equation 8. Therefore, Theorem 2 shows that for the multi-head linear self-attention with Fixed−PointFixed-Point operation, minimizing the swap regret loss provides a no-swap-regret guarantee, and the stationary point is equivalent to the Blum–Mansour swap-regret minimizer – input and output are the same as the Blum–Mansour construction. Moreover, for each head, the configuration is equivalent to the external-regret smoothed fictitious play with appropriate stepsize. The proof is deferred to Appendix D. We also provide an empirical k⋆(d,T)k (d,T) consistent with this scaling, further supporting the theoretical prediction (Figure 1, right). Remark 2 (Fixed−PointFixed-Point iteration for the swap-regret minimizer). A natural question is why the architecture requires a Fixed−PointFixed-Point operation. The rationale is twofold. First, the computational complexity of fixed-point iteration is the same as that of classical no-swap-regret minimization (Hazan and Kale, 2007), making it algorithmically consistent with known constructions. Second, most swap-regret and -regret algorithms explicitly rely on a fixed-point computation (Greenwald and Jafari, 2003): a common approach is to minimize external regret in the -space and then recover the final policy via a fixed point of the induced transition operator. While alternative methods exist—such as the Markov-chain-tree–theorem–based approach of Anagnostides et al. (2023), which replaces the fixed point with a linear map—that method requires d−1d^\,d-1 parameters and is therefore exponentially large and unsuitable for transformer-based architectures. For these reasons, using a Fixed−PointFixed-Point operation offers both theoretical alignment and practical scalability. Finally, we provide a corollary that the stationary point of the new architecture is a CE in finite action games. Corollary 2. Consider a repeated game where each player deploys the trained multi-head single-layer linear attention from Theorem 2 with Operator = SoftmaxSoftmax. Then the time-averaged joint play converges to a CE in finite action games. The distinction from the single-head result is the strength of the allowed deviations. External-regret dynamics rule out fixed-action deviations and therefore imply CCE, whereas swap-regret dynamics rule out action-contingent deviations and therefore imply CE. The fixed-point layer is the mechanism that converts the parallel external-regret heads into a single policy with swap-regret guarantees, so changing the regret surrogate changes the equilibrium concept approached by interacting agents. 4.1 Correlated-equilibrium evaluation We train all attention parameters of the d-head architecture jointly from random initialization under the Gaussian block-input objective in Equation 10, then evaluate the learned heads through the recurrent fixed-point layer. Because the training objective uses full-scale head blocks whereas the fixed-point recurrence supplies xi,t=πt,iℓtx_i,t= _t,i _t, we apply the predetermined dimension-only calibration khead=dktraink_head=d\,k_train. For each run, we compute the standard maximum pairwise CE-deviation gap directly from μ¯T μ_T. At T=20T=20, the learned fixed-point architecture obtains 0.0627±0.00180.0627± 0.0018, a 43.6%43.6\% reduction from uniform play (0.11110.1111) and nearly the value of the classical Blum–Mansour entropy-FTRL algorithm (0.06170.0617). Its stronger full-swap gap is 0.0956±0.00680.0956± 0.0068. Without the dimension calibration, the pairwise and full-swap gaps are 0.0968±0.00490.0968± 0.0049 and 0.1627±0.01100.1627± 0.0110, respectively. Thus the finite-horizon empirical distribution is an approximate, not exact, CE. Figure 4: Equilibrium gaps of time-averaged joint mixed play in weighted rock–paper–scissors. Left: external-regret-trained architectures and the maximum CCE gap. Right: the learned fixed-point architecture, classical Blum–Mansour entropy-FTRL, and uniform play, evaluated by the maximum pairwise CE gap. Curves are means with ±1± 1 standard-error bands over the nine ordered pairs of three learned row and column checkpoints; algorithmic baselines are deterministic. 5 Conclusion We revisited regret-based training of linear attention with policy space () (A) and showed that even minimal architectures admit interpretable stationary points once the non-linearity used at inference time is included in the training objective. For single-head models on the simplex, the regret loss recovers smoothed fictitious play with stepsize ~(1/T) (1/ T). Extending the loss to swap regret and lifting the architecture to a multi-head configuration leads to a differentiable realization of the Blum–Mansour procedure in which each head implements an entropy-regularized FTRL learner and a Fixed−PointFixed-Point layer aggregates the resulting transition matrix. Our characterization highlights that regret supervision can endow attention models with provably no-regret behavior without auxiliary projections or post-processing. Our analysis identifies interpretable stationary points rather than proving global optimality or convergence of training dynamics. The proof also relies on full-information Gaussian training losses, simplex-valued policies, one-layer linear attention, the SoftmaxSoftmax operator, and horizon-dependent scaling of the learned stepsize. The resulting forward pass, however, coincides with classical no-regret algorithms whose regret guarantees extend to bounded adversarial losses. Several avenues remain open. First, understanding whether deeper or non-linear attention layers share the same stationary geometry would bridge the gap to practical Transformers. Second, translating these insights to LLMs, for example by pairing regret-based objectives with post-training pipelines as in Park et al. (2025a), would test whether the same mechanism appears at realistic scale. Third, extending the stationary-point characterization to bounded non-Gaussian training distributions, horizon-free rates, and richer feedback models such as delayed or bandit observations would clarify how robust the structure is beyond the full-information Gaussian setting. References K. Ahn, X. Cheng, H. Daneshmand, and S. Sra (2023) Transformers learn to implement preconditioned gradient descent for in-context learning. Advanced in Neural Information Processing Systems. Cited by: §E.1, §2.1, §2.1. M. Ahn, A. Brohan, N. Brown, Y. Chebotar, O. Cortes, B. David, C. Finn, C. Fu, K. Gopalakrishnan, K. Hausman, et al. (2022) Do as i can, not as i say: grounding language in robotic affordances. arXiv preprint arXiv:2204.01691. Cited by: §1. I. Anagnostides, G. Farina, and T. Sandholm (2023) Near-optimal phi-regret learning in extensive-form games. In Proceedings of the 40th International Conference on Machine Learning, A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett (Eds.), Proceedings of Machine Learning Research, Vol. 202, p. 814–839. External Links: Link Cited by: Remark 2. A. Blum and Y. Mansour (2007) From external to internal regret. Journal of Machine Learning Research 8 (6). Cited by: §1. T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. (2020) Language models are few-shot learners. Advances in neural information processing systems 33, p. 1877–1901. Cited by: §E.1. N. Cesa-Bianchi and G. Lugosi (2006) Prediction, learning, and games. Cambridge University Press. Cited by: §E.2, §2.4. S. Chen, H. Sheen, T. Wang, and Z. Yang (2024) Training dynamics of multi-head softmax attention for in-context learning: emergence, convergence, and optimality. External Links: 2402.19442, Link Cited by: §E.1, §3. X. Cheng, Y. Chen, and S. Sra (2023) Transformers implement functional gradient descent to learn non-linear functions in context. arXiv preprint arXiv:2312.06528. Cited by: §3. X. Cheng, Y. Chen, and S. Sra (2024) Transformers implement functional gradient descent to learn non-linear functions in context. External Links: 2312.06528, Link Cited by: §E.1. T. M. Cover (1966) Behavior of sequential predictors of binary sequences. Stanford University, Stanford Electronics Laboratories, Systems Theory …. Cited by: §2.2.1. S. Garg, D. Tsipras, P. S. Liang, and G. Valiant (2022) What can transformers learn in-context? a case study of simple function classes. Advances in Neural Information Processing Systems 35, p. 30583–30598. Cited by: §E.1. R. D. Gordon (1941) Values of mills’ ratio of area to bounding ordinate and of the normal probability integral for large values of the argument. The Annals of Mathematical Statistics 12 (3), p. 364–366. Cited by: Appendix B. A. Greenwald and A. Jafari (2003) A general class of no-regret learning algorithms and game-theoretic equilibria. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, p. 2–12. Cited by: Remark 2. D. Guo, D. Yang, H. Zhang, J. Song, R. Zhang, R. Xu, Q. Zhu, S. Ma, P. Wang, X. Bi, et al. (2025) Deepseek-r1: incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948. Cited by: §1. S. Hao, Y. Gu, H. Ma, J. Hong, Z. Wang, D. Wang, and Z. Hu (2023) Reasoning with language model is planning with world model. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, H. Bouamor, J. Pino, and K. Bali (Eds.), Singapore, p. 8154–8173. External Links: Link, Document Cited by: §1. E. Hazan and S. Kale (2007) Computational equivalence of fixed points and no regret algorithms, and convergence to equilibria. Advances in Neural Information Processing Systems 20. Cited by: Remark 2. E. Hazan (2016) Introduction to online convex optimization. Foundations and Trends® in Optimization 2 (3-4), p. 157–325. Cited by: §2.2.1. A. Krishnamurthy, K. Harris, D. J. Foster, C. Zhang, and A. Slivkins (2024) Can large language models explore in-context?. Advances in Neural Information Processing Systems 37, p. 120124–120158. Cited by: §1. M. Laskin, L. Wang, J. Oh, E. Parisotto, S. Spencer, R. Steigerwald, D. Strouse, S. Hansen, A. Filos, E. Brooks, et al. (2023) In-context reinforcement learning with algorithm distillation. International Conference on Learning Representations. Cited by: §E.1. J. N. Lee, A. Xie, A. Pacchiano, Y. Chandak, C. Finn, O. Nachum, and E. Brunskill (2023) Supervised pretraining can learn in-context reinforcement learning. Neural Information Processing Systems. Cited by: §E.1. C. Li, R. Yang, T. Li, M. Bafarassat, K. Sharifi, D. Bergemann, and Z. Yang (2024) Stride: a tool-assisted llm agent framework for strategic and interactive decision-making. arXiv preprint arXiv:2405.16376. Cited by: §1. L. Lin, Y. Bai, and S. Mei (2024) Transformers as decision makers: provable in-context reinforcement learning via supervised pretraining. International Conference on Learning Representations. Cited by: §E.1. N. Littlestone and M. K. Warmuth (1994) The weighted majority algorithm. Information and computation 108 (2), p. 212–261. Cited by: §2.2.1. A. Mahankali, T. B. Hashimoto, and T. Ma (2023) One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention. International Conference on Learning Representations. Cited by: §E.1, §2.1. S. Min, X. Lyu, A. Holtzman, M. Artetxe, M. Lewis, H. Hajishirzi, and L. Zettlemoyer (2022) Rethinking the role of demonstrations: what makes in-context learning work?. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, Y. Goldberg, Z. Kozareva, and Y. Zhang (Eds.), Abu Dhabi, United Arab Emirates, p. 11048–11064. External Links: Link, Document Cited by: §E.1. C. Park, Z. Chen, A. Ozdaglar, and K. Zhang (2025a) Post-training llms as better decision-making agents: a regret-minimization approach. arXiv preprint arXiv:2511.04393. Cited by: §1, §2.5, §5. C. Park, X. Liu, A. Ozdaglar, and K. Zhang (2025b) Do llm agents have regret? a case study in online learning and games. In International Conference on Learning Representations, Cited by: §1, §1, §1, §2.1, §2.5, Table 1, Table 1, Table 1, Table 1, §3. I. Schlag, K. Irie, and J. Schmidhuber (2021) Linear transformers are secretly fast weight programmers. In International conference on machine learning, p. 9355–9366. Cited by: §2.1. S. Shalev-Shwartz (2012) Online learning and online convex optimization. Foundations and Trends® in Machine Learning 4 (2), p. 107–194. Cited by: §1. N. Shinn, F. Cassano, A. Gopinath, K. Narasimhan, and S. Yao (2024) Reflexion: language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems 36. Cited by: §1. Significant Gravitas (2023) AutoGPT. External Links: Link Cited by: §1. C. M. Stein (1981) Estimation of the mean of a multivariate normal distribution. The annals of Statistics, p. 1135–1151. Cited by: Lemma 13. A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin (2017) Attention is all you need. Advances in neural information processing systems 30. Cited by: §E.1. V. G. Vovk (1990) Aggregating strategies. In Proceedings of the third Annual Workshop on Computational Learning Theory, p. 371–386. Cited by: §2.2.1. G. Wang, Y. Xie, Y. Jiang, A. Mandlekar, C. Xiao, Y. Zhu, L. Fan, and A. Anandkumar (2023a) Voyager: an open-ended embodied agent with large language models. arXiv preprint arXiv:2305.16291. Cited by: §1. Z. Wang, S. Cai, A. Liu, X. Ma, and Y. Liang (2023b) Describe, explain, plan and select: interactive planning with large language models enables open-world multi-task agents. Advances in neural information processing systems. Cited by: §1. F. Xia, H. Liu, Y. Yue, and T. Li (2024) Beyond numeric awards: in-context dueling bandits with LLM agents. arXiv preprint arXiv:2407.01887. Cited by: §1. S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao (2023) React: synergizing reasoning and acting in language models. International Conference on Learning Representations. Cited by: §1. R. Zhang, S. Frei, and P. L. Bartlett (2023) Trained transformers learn linear models in-context. arXiv preprint arXiv:2306.09927. Cited by: §E.1, §2.1. Z. Zhang, D. Wang, N. Chen, R. Mansur, and V. Sarhangian (2025) Comparing exploration-exploitation strategies of llms and humans: insights from standard multi-armed bandit tasks. arXiv preprint arXiv:2505.09901. Cited by: §1. Appendix A Proof of Theorem 1 See 1 The proof will be divided into two parts. First, we prove the existence of the stationary point with V=−kId×d,a=d,vc=vdV=-kI_d× d,a= 0_d,v_c=v 1_d. Second, we show that k will have a scale of (1/T) (1/ T). Proof for the existence of the stationary point with V=−kId×d,a=0d,vc=v1dV=-kI_d× d,a= 0_d,v_c=v 1_d. Fix d≥2d≥ 2 and horizon T. For t∈[T]t∈[T] write St:=∑i=1tℓi∈ℝd,zt(V,a,vc):=∑i=1t(Vℓiℓi⊺a+(V+vca⊺)ℓi+vc)∈ℝd,S_t:= _i=1^t _i ^d, z_t(V,a,v_c)\ :=\ _i=1^t (V\, _i _i a+(V+v_ca ) _i+v_c ) ^d, and πt=Softmax(zt) _t= Softmax(z_t). With V=−kId×dV=-kI_d× d and a=da= 0_d we have zt(−kId×d,0,vc)=−kSt+tvc.z_t(-kI_d× d,0,v_c)\ =\ -k\,S_t+t\,v_c. Regret can be written as: Regret((ℓt)t≤T):=∑t=1T⟨ℓt,πt⟩−infπ∈d⟨∑t=1Tℓt,π⟩=∑t=1T⟨ℓt,πt⟩−minj∈[d](ST)j.Regret(( _t)_t≤ T)\ :=\ _t=1^T _t, _t - _π∈^d\, _t=1^T _t,\ π \ =\ _t=1^T _t, _t - _j∈[d](S_T)_j. For a fixed realization (ℓt)t≤T( _t)_t≤ T, write R:=Regret((ℓt)t≤T)R:=Regret(( _t)_t≤ T), and ℒ=[h(R)]L\ =\ E[h(R)], where h(x)=x2h(x)=x^2. First, compute the derivative w.r.t. πt _t. We have: ∂R∂πt=ℓt, ∂ R∂ _t= _t, since only the term ⟨ℓt,πt⟩ _t, _t depends on πt _t and the comparator minj(ST)j _j(S_T)_j is constant with respect to the parameters. Let Jsm(zt)∈ℝd×dJ_sm(z_t) ^d× d denote the Jacobian of SoftmaxSoftmax at ztz_t, i.e. Jsm(zt)=∂Softmax(zt)∂zt=Diag(πt)−πtπt⊺,πt=Softmax(zt).J_sm(z_t)\ =\ ∂\, Softmax(z_t)∂ z_t\ =\ Diag( _t)- _t _t , _t= Softmax(z_t). Then ∂R∂zt=Jsm(zt)⊺∂R∂πt=Jsm(zt)⊺ℓt. ∂ R∂ z_t=J_sm(z_t) \, ∂ R∂ _t=J_sm(z_t) _t. By the chain rule for h(R)h(R), ∂zth(R)=h′(R)∂R∂zt=2RJsm(zt)⊺ℓt. ∂ z_th(R)\ =\ h (R)\, ∂ R∂ z_t=2R\,J_sm(z_t) _t. We define the (random) vector :=t∂zth(R)= 2Regret((ℓs)s≤T)Jsm(zt)⊺ℓt∈ℝd._t\ :=\ ∂ z_th(R)\ =\ 2\,Regret(( _s)_s≤ T)\;J_sm(z_t) _t\ ∈\ R^d. The mapping (z1,…,zT)↦h(R)(z_1,…,z_T) h(R) is C1C^1, and by dominated convergence (SoftmaxSoftmax and h are smooth, Gaussian tails), we may exchange gradient and expectation, so for any perturbation (δzt)t≤T(δ z_t)_t≤ T: δℒ=[∑t=1T⟨,tδzt⟩]. \ =\ E [ _t=1^T _t,\ δ z_t ]. For arbitrary perturbations δV,δa,δvδ V,δ a,δ v (with δvc=δv 1dδ v_c=δ v\, 1_d), δztδ z_t is given by δzt δ z_t =∑i=1t(δVℓiℓi⊺a+Vℓiℓi⊺δa)+∑i=1t(δVℓi+vc⟨δa,ℓi⟩+δvca⊺ℓi)+∑i=1tδvc = _i=1^t (δ V\, _i _i a+V\, _i _i δ a )+ _i=1^t (δ V\, _i+v_c\, δ a, _i +δ v_c\,a _i )+ _i=1^tδ v_c =∑i=1t(δVℓiℓi⊺a+δVℓi)⏟(∗V)+∑i=1t(Vℓiℓi⊺δa+vcℓi⊺δa)⏟(∗a)+∑i=1t(δvca⊺ℓi+δvc)⏟(∗v). = _i=1^t (δ V\, _i _i a+δ V\, _i )_( _V)\ +\ _i=1^t (V\, _i _i δ a+v_c\, _i δ a )_( _a)\ +\ _i=1^t (δ v_c\,a _i+δ v_c )_( _v). We now instantiate at (V,a,vc)=(−kId×d,0,vd)(V,a,v_c)=(-kI_d× d,0,v 1_d), so that St=∑i=1tℓiS_t= _i=1^t _i and (∗V)=δVSt,(∗a)=(−k∑i=1tℓiℓi⊺+v 1dSt⊺)δa,(∗v)=tδv 1d.( _V)=δ V\,S_t, ( _a)= (-k _i=1^t _i _i +v\, 1_dS_t )δ a, ( _v)=t\,δ v\, 1_d. Thus at (V,a,vc)=(−kId×d,0,vd)(V,a,v_c)=(-kI_d× d,0,v 1_d) we may write δℒ=[∑t=1T⟨,tδzt⟩],δzt=δVSt+(−k∑i=1tℓiℓi⊺+v 1dSt⊺)δa+tδv 1d, \ =\ E [ _t=1^T _t,\ δ z_t ], δ z_t\ =\ δ V\,S_t\ +\ (-k _i=1^t _i _i +v\, 1_dS_t )δ a\ +\ t\,δ v\, 1_d, (11) with =t 2Regret((ℓs)s≤T)(Diag(πt)−πtπt⊺)⊺ℓt,πt=Softmax(zt)._t\ =\ 2\,Regret(( _s)_s≤ T)\; (Diag( _t)- _t _t ) _t, _t= Softmax(z_t). (i) The v-direction. Using δzt(v)=tδv 1dδ z_t^(v)=t\,δ v\, 1_d in (11) we obtain δℒ(v)=δv∑t=1Tt[⟨,td⟩]. ^(v)=δ v\, _t=1^Tt\,E [ _t, 1_d ]. Now =t2R(Diag(πt)−πtπt⊺)ℓt,πt=Softmax(zt),_t=2R (Diag( _t)- _t _t ) _t, _t= Softmax(z_t), and hence ⟨,td⟩ _t, 1_d =2R 1d⊺(Diag(πt)−πtπt⊺)ℓt =2R\, 1_d (Diag( _t)- _t _t ) _t =2R(d⊺Diag(πt)⏟=d⊺πt=1−d⊺πtπt⊺⏟=1⋅πt⊺)ℓt=2R(1−1)πt⊺ℓt=0. =2R\, ( 1_d Diag( _t)_= 1_d _t=1- 1_d _t _t _=1· _t ) _t=2R\,(1-1)\, _t _t=0. Thus each term in the sum vanishes pointwise, so δℒ(v)=0 ^(v)=0 for all δvδ v, i.e. ∂ℒ∂v=0, ∂ v=0, which matches (and refines) the earlier shift-invariance argument. (i) The a-direction at a=da= 0_d. At (V,a,vc)=(−kId×d,0,vd)(V,a,v_c)=(-kI_d× d,0,v 1_d), (11) gives δℒ(a) ^(a) =[∑t=1T⟨,t(−k∑i=1tℓiℓi⊺+v 1dSt⊺)δa⟩] =E [ _t=1^T _t,\ (-k _i=1^t _i _i +v\, 1_dS_t )δ a ] =−k[∑t=1T⟨,t∑i=1tℓiℓi⊺δa⟩]+v[∑t=1T⟨,tdSt⊺δa⟩]. =-k\,E [ _t=1^T _t,\ _i=1^t _i _i δ a ]\ +\ v\,E [ _t=1^T _t, 1_dS_t δ a ]. The second term vanishes because d⊺=t0 1_d _t=0: ⟨,tdSt⊺δa⟩=(d⊺)t⟨St,δa⟩=0. _t, 1_dS_t δ a =( 1_d _t)\, S_t,δ a =0. Hence δℒ(a)=−k⟨[∑t=1T∑i=1tℓiℓi⊺]t,δa⟩. ^(a)=-k\, [ _t=1^T _i=1^t _i _i _t ],\ δ a . We may write ∇aℒ|(V,a,vc)=(−kId×d,0,vd)=−k[∑t=1T∑i=1tℓiℓi⊺]t∈ℝd. _aL |_(V,a,v_c)=(-kI_d× d,0,v 1_d)=-k\,E [ _t=1^T _i=1^t _i _i _t ]\ ∈\ R^d. Set H:=[∑t=1T∑i=1tℓiℓi⊺]t∈ℝd,H:=E [ _t=1^T _i=1^t _i _i _t ] ^d, so that ∇aℒ=−kH _aL=-kH. We claim H=dH= 0_d. To see this, use the permutation invariance of the law of (ℓt)t≤T( _t)_t≤ T (it is spherically symmetric since ℓt∼(0,Id×d) _t (0,I_d× d) i.i.d.) and the permutation equivariance of SoftmaxSoftmax: for any permutation matrix P, PSoftmax(x)=Softmax(Px)P\, Softmax(x)= Softmax(Px). Under (ℓt)↦(Pℓt)( _t) (P _t) we have St↦PStS_t PS_t and hence zt↦−kPStz_t -k\,PS_t, so πt↦Pπt _t P _t and ↦tPt_t P_t. Therefore H=[∑t,i(Pℓi)(Pℓi)⊺(P)t]=P[∑t,iℓiℓi⊺]t=PHfor all permutations P.H\ =\ E [ _t,i(P _i)(P _i) (P_t) ]\ =\ P\,E [ _t,i _i _i _t ]\ =\ P\,H all permutations P. The only vectors fixed by all coordinate permutations are multiples of d 1_d. On the other hand, d⊺H=[∑t,i⟨d,ℓiℓi⊺⟩t]=[∑t,i⟨ℓi,⟩t⋅⟨d,ℓi⟩]. 1_d H=E [ _t,i 1_d,\ _i _i _t ]=E [ _t,i _i,_t · 1_d, _i ]. By symmetry the joint law is invariant under ℓi↦−ℓi _i - _i while t changes sign exactly as ℓt _t does through the SoftmaxSoftmax Jacobian (the mapping is odd along each coordinate in expectation); thus d⊺H=0 1_d H=0. Hence the only permutation-fixed vector orthogonal to d 1_d is d 0_d, so H=dH= 0_d and therefore ∇aℒ|a==d. . _aL |_a= 0= 0_d. (i) The V-direction at V=−kId×dV=-kI_d× d. From (∗V)( _V), at a=0a=0 we have δzt=δVStδ z_t=δ V\,S_t. Using (11) and writing the Frobenius product, δℒ =[∑t=1T⟨,tδVSt⟩]=[∑t=1T⟨St⊺t,δV⟩F] =E [ _t=1^T _t,\ δ VS_t ]=E [ _t=1^T _tS_t ,\ δ V _F ] =⟨[∑t=1TSt⊺t]⏟=:G(V),δV⟩F, = E [ _t=1^T_tS_t ]_=:G(V),\ δ V _F, so ∇Vℒ=G(V) _VL=G(V). Evaluate at V=−kId×dV=-kI_d× d. For every permutation matrix P, the Gaussian law is invariant under (ℓt)↦(Pℓt)( _t) (P _t), and SoftmaxSoftmax is permutation-equivariant. Thus (St,)t=d(PSt,P)t(S_t,_t) d=(PS_t,P_t) and G(−kId×d)=[∑t=1TSt⊺t]=[∑t=1T(P)t(PSt)⊺]=PG(−kId×d)P⊺G(-kI_d× d)\ =\ E [ _t=1^T_tS_t ]\ =\ E [ _t=1^T(P_t)(PS_t) ]\ =\ P\,G(-kI_d× d)\,P for all permutation matrices P. By Lemma 1, there are scalars α(k),β(k)α(k),β(k) such that G(−kId×d)=α(k)Id×d+β(k)dd⊺.G(-kI_d× d)=α(k)I_d× d+β(k) 1_d 1_d . Moreover, d⊺=t0 1_d _t=0 for every t because Jsm(zt)⊺d=dJ_sm(z_t) 1_d= 0_d, and hence d⊺G(−kId×d)=d⊺ 1_d G(-kI_d× d)= 0_d . Therefore ∇Vℒ(−kId×d,0,vd)=α(k),0:=0Id×d−1d⊺. _VL(-kI_d× d,0,v 1_d)=α(k)_0, _0:=I_d× d- 1d 1_d 1_d . Let k⋆k be any stationary point of the one-dimensional function ϕ(k):=ℒ(V=−kId×d,a=0,vc=vd),φ(k):=L(V=-kI_d× d,a=0,v_c=v 1_d), which exists by smoothness and standard compactification/continuity arguments; at a local minimizer we certainly have ϕ′(k⋆)=0φ (k )=0. Then 0=ϕ′(k⋆)=⟨∇Vℒ(−k⋆I,0,vd),∂(−kId×d)∂k⟩F=⟨α(k⋆),0−I⟩F=−(d−1)α(k⋆),0\ =\ φ (k )\ =\ _VL(-k I,0,v 1_d),\ ∂(-kI_d× d)∂ k _F\ =\ α(k )_0,\ -I _F\ =\ -(d-1)α(k ), so α(k⋆)=0α(k )=0 and hence ∇Vℒ(−k⋆I,0,vd)= _VL(-k I,0,v 1_d)= 0. Conclusion. At the parameter triple (V,a,vc)=(−k⋆Id×d, 0d,v 1d)(V,a,v_c)=(-k I_d× d,\ 0_d,\ v\, 1_d) we have ∇Vℒ=d×d,∇aℒ=d,∇vcℒ=d. _VL= O_d× d, _aL= 0_d, _v_cL= 0_d. Thus the configuration is a first-order stationary point of ℒL. ∎ Remark 3. The argument uses only: (1) SoftmaxSoftmax shift-invariance and its Jacobian Jsm(z)=Diag(π)−ππ⊺J_sm(z)=Diag(π)-π ; (2) permutation invariance of the Gaussian hierarchical model ℓt∼(0,Id×d) _t (0,I_d× d) i.i.d.; and (3) the zero-sum range of the SoftmaxSoftmax Jacobian. Now we show that k will have a scale of (1/T) (1/ T). Proof for the scale of k. Fix integers d≥2d≥ 2 and T≥1T≥ 1. Let (ℓt)t=1⊺( _t)_t=1 be i.i.d. (0,Id×d)N(0,I_d× d), and define partial sums St:=∑i=1tℓiS_t:= _i=1^t _i with S0:=0S_0:=0, exactly as in the previous part of the proof. For k∈ℝk , the SoftmaxSoftmax policy induced by V=−kId×dV=-kI_d× d, a=da= 0_d, vc=vdv_c=v 1_d reads πt(k):=Softmax(−kSt−1)∈,dJt(k):=Jsm(−kSt−1)=Diag(πt(k))−πt(k)πt(k)⊺, _t(k):= Softmax(-kS_t-1)∈_d, J_t(k):=J_sm(-kS_t-1)=Diag( _t(k))- _t(k) _t(k) , where we re-use the Jacobian notation JsmJ_sm from the first part. Let the regret against the best fixed coordinate be RT(k):=∑t=1T⟨ℓt,πt(k)⟩−minj∈[d]ST,j,R_T(k):= _t=1^T _t, _t(k) - _j∈[d]S_T,j, and the objective ℒ(k):=[RT(k)2]L(k):=E[R_T(k)^2]. Let J⋆:=argminj∈[d]ST,jJ := _j∈[d]S_T,j (unique a.s.). Write u:=1ddu:= 1d 1_d and J0:=Diag(u)−uu⊺=1dP⟂dJ_0:=Diag(u)-u = 1dP_ 1_d. We will use the following two elementary facts. Fact 2. For each t≤Tt≤ T, [St−1∣ST]=t−1TSTE[S_t-1 S_T]= t-1TS_T and St−1−t−1TST⟂STS_t-1- t-1TS_T \!\!\! S_T. Hence [St−1,J⋆]=t−1T[min1≤j≤dST,j].E [S_t-1,J ]= t-1T\,E\! [ _1≤ j≤ dS_T,j ]. Fact 3 (Exact derivative identity). For every k∈ℝk , ℒ′(k)=−2∑t=1T[⟨Jt(k)St−1,πt(k)−u⟩]⏟=:1+ 2∑t=1T[⟨Jt(k)St−1,eJ⋆⟩]⏟=:2.L (k)=-2 _t=1^TE\! [ J_t(k)S_t-1,\, _t(k)-u ]_=:_1\;+\;2 _t=1^TE\! [ J_t(k)S_t-1,\,e_J ]_=:_2. (12) Proof. Since the comparator minjST,j _jS_T,j is k-independent, dk∑t=1T⟨ℓt,πt(k)⟩=−∑t=1T⟨ℓt,Jt(k)St−1⟩. ddk _t=1^T _t, _t(k) =- _t=1^T _t,J_t(k)S_t-1 . Thus ℒ′(k)=2[RT(k)⋅dk∑t⟨ℓt,πt(k)⟩]=−2∑t[RT(k)⟨ℓt,Jt(k)St−1⟩]L (k)=2\,E\! [R_T(k)· ddk _t _t, _t(k) ]=-2 _tE\! [R_T(k) _t,J_t(k)S_t-1 ]. Fix t and condition on ℱt−1=σ(ℓ1,…,ℓt−1)F_t-1=σ( _1,…, _t-1). Stein’s lemma (Lemma 13) for ℓt∼(0,Id×d) _t (0,I_d× d) yields [⟨ℓt,v⟩RT(k)∣ℱt−1]=[⟨v,∇ℓtRT(k)⟩∣ℱt−1],v=Jt(k)St−1.E\! [ _t,v R_T(k) _t-1 ]=E\! [ v, _ _tR_T(k) _t-1 ], v=J_t(k)S_t-1. Because ∂ℓt⟨ℓt,πt(k)⟩=πt(k) _ _t _t, _t(k) = _t(k), for s>ts>t one has ∂ℓt⟨ℓs,πs(k)⟩=−kJs(k)ℓs _ _t _s, _s(k) =-k\,J_s(k) _s, and ∂ℓtminjST,j=eJ⋆ _ _t _jS_T,j=e_J almost surely; hence ∇ℓtRT(k)=πt(k)−eJ⋆−k∑s>tJs(k)ℓs. _ _tR_T(k)= _t(k)-e_J -k _s>tJ_s(k) _s. Therefore [RT(k)⟨ℓt,v⟩]=[⟨v,πt(k)−eJ⋆⟩]−k∑s>t[⟨v,Js(k)ℓs⟩].E\! [R_T(k) _t,v ]=E[ v, _t(k)-e_J ]-k _s>tE[ v,J_s(k) _s ]. Conditioning on ℱs−1F_s-1, the second term is 0 because [ℓs∣ℱs−1]=0E[ _s _s-1]=0. Summing in t gives the claim. Here, we also used that Js(k)d=dJ_s(k) 1_d= 0_d for all s and k by definition of Js(k)J_s(k). ∎ Now, we provide a first-order expansion of the policy with bounds on the remainder term. Proposition 2 (First–order expansion of the policy). The following equation and inequalities hold: πt(k)−u=−J0kSt−1+rt,‖rt‖2≤34k2‖St−1‖22,‖rt‖∞≤k2‖St−1‖∞2. _t(k)-u\;=\;-\,J_0\,k\,S_t-1\;+\;r_t, \|r_t\|_2≤ 34\,k^2\,\|S_t-1\|_2^2, \|r_t\|_∞≤ k^2\,\|S_t-1\|_∞^2. (13) Proof. Use the fundamental theorem of calculus on the ray θ↦θztθ θ z_t: πt(k)−u=Softmax(−kSt−1)−Softmax(0)=∫01Jsm(θ(−kSt−1))(−kSt−1)θ. _t(k)-u\;=\; Softmax(-kS_t-1)- Softmax(0)\;=\; _0^1J_sm(θ(-kS_t-1))\,(-kS_t-1)\,dθ. Add and subtract −J0kSt−1-J_0kS_t-1 and define rt:=∫01(Jsm(θ(−kSt−1))−J0)(−kSt−1)θ,r_t:= _0^1 (J_sm(θ(-kS_t-1))-J_0 )\,(-kS_t-1)\,dθ, Then by Lemma 2-(d), ‖rt‖2≤∫01‖Jsm(θ(−kSt−1))−J0‖op‖(−kSt−1)‖2θ≤∫0132θ‖kSt−1‖22θ=34‖kSt−1‖22.\|r_t\|_2\;≤\; _0^1 \|J_sm(θ(-kS_t-1))-J_0 \|_op\,\|(-kS_t-1)\|_2\,dθ\;≤\; _0^1 32θ\|kS_t-1\|_2^2\,dθ= 34\|kS_t-1\|_2^2. Thus (13) holds with C1:=34C_1:= 34. Moreover, using Lemma 2-(e) with h=−kSt−1h=-kS_t-1, ‖Jsm(θ(−kSt−1))−J0‖∞→∞≤2θ|k|‖St−1‖∞. \|J_sm(θ(-kS_t-1))-J_0 \|_∞→∞≤ 2θ\,|k|\,\|S_t-1\|_∞. Therefore, the following inequality holds: ‖rt‖∞≤∫01‖Jsm(−θkSt−1)−J0‖∞→∞‖kSt−1‖∞θ≤∫012θ|k|‖St−1‖∞|k|‖St−1‖∞θ=k2‖St−1‖∞2.\|r_t\|_∞≤ _0^1 \|J_sm(-θ kS_t-1)-J_0 \|_∞→∞\,\|kS_t-1\|_∞\,dθ≤ _0^12θ\,|k|\,\|S_t-1\|_∞\,|k|\,\|S_t-1\|_∞\,dθ=k^2\|S_t-1\|_∞^2. ∎ Proposition 3 (First–order expansion of the Jacobian). There exists an absolute L>0L>0 such that Jt(k)=J0+Rt,‖Rt‖op≤Lk‖St−1‖2‖Rt‖∞→∞≤2k‖St−1‖∞.J_t(k)\;=\;J_0\;+\;R_t, \|R_t\|_op\;≤\;L\,k\,\|S_t-1\|_2 \|R_t \|_∞→∞≤ 2k\|S_t-1\|_∞. (14) Proposition 3 is a re-instantitation of Lemma 2-(e). We now establish two auxiliary lemmas specific to this proof. Theorem 3 (Negativity for k≤c/Tdk≤ c/ Td). There exists an absolute constant c∗>0c_ >0 such that if k=~(1/Td)k= O(1/ Td), then ℒ′(k)<0L (k)<0. Proof. First, we provide an upper bound on −21-2_1. Fix t and abbreviate S:=St−1S:=S_t-1, π:=πt(k)π:= _t(k), Jt:=Jt(k)J_t:=J_t(k). From Proposition 2 and Proposition 3, we have π−u=−kJ0S+rt,Jt=J0+Rt.π-u=-kJ_0S+r_t, J_t=J_0+R_t. By plugging in formula for 1, we have ⟨JtS,π−u⟩ J_tS,π-u =⟨(J0+Rt)S,−kJ0S+rt⟩ = (J_0+R_t)S,-kJ_0S+r_t =−k‖J0S‖22+⟨J0S,rt⟩⏟E1,t−k⟨RtS,J0S⟩⏟E2,t+⟨RtS,rt⟩⏟E3,t. =-k\|J_0S\|_2^2\;+\; J_0S,r_t _E_1,t\;-\; k R_tS,J_0S _E_2,t\;+\; R_tS,r_t _E_3,t. (15) Therefore, we have −2≤1 2k∑t=1T∥J0St−1∥22+2∑t|E1,t|+2k∑t|E2,t|+2∑t|E3,t|.-2_1\;≤\;2k _t=1^TE\|J_0S_t-1\|_2^2+2 _tE|E_1,t|+2k _tE|E_2,t|+2 _tE|E_3,t|. (16) Main term. Because St−1∼(d,(t−1)Id×d)S_t-1 ( 0_d,(t-1)I_d× d) and J0J_0 is a projection (scaled by 1/d1/d) onto an (d−1)(d-1)-dimensional subspace, ‖J0St−1‖22=d−1d2(t−1),E\|J_0S_t-1\|_2^2= d-1d^2(t-1), and thus 2k∑t=1T‖J0St−1‖22=kd−1d2T(T−1).2k _t=1^TE\|J_0S_t-1\|_2^2=k d-1d^2T(T-1). (17) Bound on E1,t=⟨J0S,rt⟩E_1,t= J_0S,r_t . By Hölder inequality in (1,∞)(1,∞), Proposition 2, and ‖St−1‖∞≤‖St−1‖∞\|S_t-1\|_∞≤\|S_t-1\|_∞, |E1,t|≤‖J0S‖1‖rt‖∞≤‖J0‖1→1‖S‖1⋅k2‖S‖∞2≤2dk2‖S‖1‖S‖∞2≤2k2‖S‖∞3.|E_1,t|≤\|J_0S\|_1\|r_t\|_∞≤\|J_0\|_1→ 1\|S\|_1· k^2\|S\|_∞^2≤ 2dk^2\|S\|_1\|S\|_∞^2≤ 2k^2\|S\|_∞^3. Taking expectations and summing over t with Lemma 8, for some absolute constant C1>0C_1>0, ∑t=1T|E1,t|≤2k2∑t=1T‖St−1‖∞3≤C1k2T5/2(log(ed))3/2. _t=1^TE|E_1,t|≤ 2k^2 _t=1^TE\|S_t-1\|_∞^3≤ C_1k^2T^5/2( (ed))^3/2. (18) Bound on E2,t=k⟨RtS,J0S⟩E_2,t=k R_tS,J_0S . We will prove there exists an absolute constant C>0C>0 such that for all t≤Tt≤ T, |[E2,t]|≤Cd3/2k2(t−1)3/2(log(ed))3/2e4k2(t−1). |E[E_2,t] |\;≤\; Cd^3/2\,k^2\,(t-1)^3/2 ( (ed) )^3/2\,e^4k^2(t-1). (19) and consequently, ∑t=1T|[E2,t]|≤Cd3/2k2T5/2(log(ed))3/2e4k2T. _t=1^T |E[E_2,t] |\;≤\; Cd^3/2\,k^2\,T^5/2 ( (ed) )^3/2\,e^4k^2T. (20) By Lemma 4, (Jt(k)−J0)S=(Jt(k)−J0)J0S(J_t(k)-J_0)S=(J_t(k)-J_0)J_0S, so E2,t=k⟨(Jsm(−kS)−J0)J0S,J0S⟩.E_2,t=k (J_sm(-kS)-J_0)J_0S,\ J_0S . Let J(z):=Jsm(z)J(z):=J_sm(z). Along the ray θ↦−θkSθ -θ kS we have J(−kS)−J0=∫01DJ(−θkS)[−kS]θ.J(-kS)-J_0\;=\; _0^1DJ(-θ kS)[-kS]\,dθ. Therefore E2,t=k∫01⟨DJ(−θkS)[−kS]J0S,J0S⟩θ.E_2,t=k _0^1 DJ(-θ kS)[-kS]\,J_0S,\ J_0S \,dθ. (21) Expand DJ(−θkS)DJ(-θ kS) around 0: DJ(−θkS)[−kS]=DJ(0)[−kS]+∫0θD2J(−τkS)[−kS,−kS]τ.DJ(-θ kS)[-kS]=DJ(0)[-kS]\;+\; _0^θD^2J(-τ kS)[-kS,-kS]\,dτ. Plugging this into (21), we obtain E2,t=Hlin(S)+Hrem(S),E_2,t=H_lin(S)+H_rem(S), where Hlin(S) H_lin(S) :=k⟨DJ(0)[−kS]J0S,J0S⟩, :=k DJ(0)[-kS]\,J_0S,\ J_0S , Hrem(S) H_rem(S) :=k∫01∫0θ⟨D2J(−τkS)[−kS,−kS]J0S,J0S⟩τθ. :=k _0^1\! _0^θ D^2J(-τ kS)[-kS,-kS]\,J_0S,\ J_0S \,dτ\,dθ. Consider the transformation S↦−S -S. Since J0J_0 is linear, J0(−S)=−J0SJ_0(-S)=-J_0S. Furthermore, DJ(0)[h]DJ(0)[h] is linear in h, so DJ(0)[−k(−S)]=DJ(0)[kS]=−DJ(0)[−kS]DJ(0)[-k(-S)]=DJ(0)[kS]=-DJ(0)[-kS]. A direct sign check yields Hlin(−S)=k⟨DJ(0)[−k(−S)]J0(−S),J0(−S)⟩=−Hlin(S).H_lin(-S)=k DJ(0)[-k(-S)]\,J_0(-S),\ J_0(-S) =-H_lin(S). Since S is symmetric in law, ℒ(S)=ℒ(−S)L(S)=L(-S), we obtain [Hlin(S)]=0E[H_lin(S)]=0 and therefore [E2,t]=[Hrem(S)].E[E_2,t]=E[H_rem(S)]. Let Mτ(S):=D2J(−τkS)[−kS,−kS].M_τ(S):=D^2J(-τ kS)[-kS,-kS]. By Hölder in (∞,1)(∞,1), |⟨Mτ(S)J0S,J0S⟩|≤‖Mτ(S)‖∞→∞‖J0S‖∞‖J0S‖1. | M_τ(S)J_0S,\ J_0S |≤\|M_τ(S)\|_∞→∞\,\|J_0S\|_∞\,\|J_0S\|_1. By Lemma 2 (f), ‖Mτ(S)‖∞→∞≤16de2τkqk2q2,q:=‖S‖∞.\|M_τ(S)\|_∞→∞≤ 16d\,e^2τ kq\,k^2q^2, q:=\|S\|_∞. By Lemma 6, ‖J0S‖∞≤2dq,‖J0S‖1≤2q.\|J_0S\|_∞≤ 2d\,q, \|J_0S\|_1≤ 2\,q. Hence |⟨Mτ(S)J0S,J0S⟩|≤64d2k2q4e2τkq. | M_τ(S)J_0S,\ J_0S |≤ 64d^2\,k^2q^4e^2τ kq. Therefore, |Hrem(S)| |H_rem(S)| ≤k∫01∫0θ|⟨Mτ(S)J0S,J0S⟩|τθ ≤ k _0^1\! _0^θ | M_τ(S)J_0S,\ J_0S |\,dτ\,dθ ≤64d2k3q4∫01∫0θe2τkqτθ. ≤ 64d^2\,k^3q^4 _0^1\! _0^θe^2τ kq\,dτ\,dθ. Using ∫01∫0θe2τkqτθ=∫01(1−τ)e2τkqτ≤∫01e2τkqτ=e2kq−12kq≤12kqe2kq, _0^1\! _0^θe^2τ kq\,dτ\,dθ= _0^1(1-τ)e^2τ kq\,dτ≤ _0^1e^2τ kq\,dτ= e^2kq-12kq≤ 12kqe^2kq, we obtain |Hrem(S)|≤32d2k2q3e2kq.|H_rem(S)|≤ 32d^2\,k^2q^3e^2kq. Taking expectations, |[E2,t]|=|[Hrem(S)]|≤32d2k2[q3e2kq]. |E[E_2,t] |= |E[H_rem(S)] |≤ 32d^2\,k^2\,E [q^3e^2kq ]. Apply Cauchy–Schwarz: [q3e2kq]≤([q6])1/2([e4kq])1/2.E [q^3e^2kq ]≤ (E[q^6] )^1/2 (E[e^4kq] )^1/2. By Lemma 8 with q=6q=6, [q6]≲(t−1)3(log(ed))3.E[q^6] (t-1)^3 ( (ed) )^3. By the MGF bound for the sup (Lemma 12), [e4kq]≲dexp(8k2(t−1)).E[e^4kq] d\, (8k^2(t-1) ). Thus [q3e2kq]≲(t−1)3/2(log(ed))3/2d1/2e4k2(t−1).E [q^3e^2kq ] (t-1)^3/2 ( (ed) )^3/2\,d^1/2e^4k^2(t-1). Combining this with the prefactor 32/d232/d^2 gives |[E2,t]|≤Cd3/2k2(t−1)3/2(log(ed))3/2e4k2(t−1) |E[E_2,t] |\;≤\; Cd^3/2\,k^2\,(t-1)^3/2 ( (ed) )^3/2e^4k^2(t-1) for some absolute constant C>0C>0, proving (19). Summing over t and using ∑t=1T(t−1)3/2≲T5/2 _t=1^T(t-1)^3/2 T^5/2 yields (20). Bound on E3,t=⟨RtS,rt⟩E_3,t= R_tS,r_t . We use the integral representation of rtr_t. For θ∈[0,1]θ∈[0,1] set Aθ:=Jsm(θ(−kS))−J0A_θ:=J_sm(θ(-kS))-J_0 so that Rt=A1R_t=A_1 and rt=∫01Aθ(−kS)θ=−k∫01AθSθ.r_t= _0^1A_θ(-kS)\,dθ=-k _0^1A_θS\,dθ. By Lemma 4, AθS=AθJ0SA_θS=A_θJ_0S and RtS=RtJ0SR_tS=R_tJ_0S. Therefore E3,t=⟨RtS,rt⟩=−k∫01⟨Rt(J0S),Aθ(J0S)⟩θ.E_3,t= R_tS,\,r_t =-k _0^1 R_t(J_0S),\,A_θ(J_0S) \,dθ. Taking absolute values and using Hölder in (∞,1)(∞,1), |E3,t|≤k∫01‖Rt(J0S)‖∞‖Aθ(J0S)‖1θ≤k∫01‖Rt‖∞→∞‖J0S‖∞⋅‖Aθ‖1→1‖J0S‖1θ.|E_3,t|≤ k _0^1\|R_t(J_0S)\|_∞\,\|A_θ(J_0S)\|_1\,dθ≤ k _0^1\|R_t\|_∞→∞\,\|J_0S\|_∞·\|A_θ\|_1→ 1\,\|J_0S\|_1\,dθ. By Lemma 2-(e) with h=−kSh=-kS, ‖Rt‖∞→∞≤2k‖S‖∞\|R_t\|_∞→∞≤ 2k\|S\|_∞ and ‖Aθ‖1→1=‖Jsm(θ(−kS))−J0‖1→1≤2θk‖S‖∞.\|A_θ\|_1→ 1=\|J_sm(θ(-kS))-J_0\|_1→ 1≤ 2θ k\|S\|_∞. By the definition of J0J_0, ‖J0S‖∞≤2d‖S‖∞\|J_0S\|_∞≤ 2d\|S\|_∞ and ‖J0S‖1≤2d‖S‖1≤2‖S‖∞\|J_0S\|_1≤ 2d\|S\|_1≤ 2\|S\|_∞ (the last inequality uses ‖S‖1≤d‖S‖∞\|S\|_1≤ d\|S\|_∞). Plugging these four bounds, |E3,t|≤k∫01(2k‖S‖∞)(2d‖S‖∞)(2θk‖S‖∞)(2‖S‖∞)θ=8dk3‖S‖∞4.|E_3,t|≤ k _0^1 (2k\|S\|_∞ ) ( 2d\|S\|_∞ ) (2θ k\|S\|_∞ ) (2\|S\|_∞ )\,dθ= 8d\,k^3\,\|S\|_∞^4. Taking expectations, using Lemma 8 with q=4q=4, and summing over t, ∑t=1T|E3,t|≤8dk3∑t=1T‖St−1‖∞4≤Cdk3∑t=1T(t−1)2log(ed)≤Cdk3T3(log(ed))2. _t=1^TE|E_3,t|≤ 8d\,k^3 _t=1^TE\|S_t-1\|_∞^4≤ Cd\,k^3 _t=1^T(t-1)^2 (ed)≤ Cd\,k^3\,T^3\, ( (ed) )^2. (22) Combining (16), (17), (18), (20), and (22), we obtain −2≤1kdT2+C1k2T5/2(log(ed))3/2+C2k2d3/2T5/2(log(ed))3/2e4k2T+C3k3dT3(log(ed))2.-2_1\;≤\; kdT^2+C_1k^2T^5/2( (ed))^3/2+C_2 k^2d^3/2T^5/2( (ed))^3/2\,e^4k^2T+C_3 k^3dT^3( (ed))^2. (23) If k=~(1/Td)k= O(1/ Td) for some absolute constant c∗>0c_ >0, then −2≤1~(T3/2d3/2+T3/2d+T3/2d5/2+T3/2d7/2).-2_1\;≤\; O ( T^3/2d^3/2+ T^3/2d+ T^3/2d^5/2+ T^3/2d^7/2 ). Next, we provide an upper bound on 222_2. We split 2 into two parts: =2+2,0,2,pert:=2,0∑t=1T[⟨J0St−1,eJ⋆⟩],:=2,pert∑t=1T[⟨(Jt(k)−J0)St−1,eJ⋆⟩]._2=_2,0+_2,pert, _2,0:= _t=1^TE [ J_0S_t-1,e_J ], _2,pert:= _t=1^TE [ (J_t(k)-J_0)S_t-1,e_J ]. Baseline negative term. (2,0) By 2 and Lemma 10, 2≤2,0−c0T(T−1)logd.2_2,0\;≤\;-\,c_0\, T\,(T-1)\, dd. (24) 2=2,0−(T3/2logd).2_2,0\;=\;-\, (\, T^3/2\, dd ). (25) Perturbative term 2,pert. By Lemma 4, ⟨(Jt(k)−J0)S,eJ⋆⟩=⟨RtJ0S,eJ⋆⟩,Rt:=Jt(k)−J0. (J_t(k)-J_0)S,\,e_J \;=\; R_tJ_0S,\,e_J , R_t:=J_t(k)-J_0. Hence, using Hölder in (∞,1)(∞,1) and ‖eJ⋆‖1=1\|e_J \|_1=1, |⟨(Jt(k)−J0)S,eJ⋆⟩|≤‖RtJ0S‖∞≤‖Rt‖∞→∞‖J0S‖∞. | (J_t(k)-J_0)S,\,e_J |≤\|R_tJ_0S\|_∞≤\|R_t\|_∞→∞\,\|J_0S\|_∞. By Lemma 2 (e) with h=−kSh=-kS, ‖Rt‖∞→∞=‖Jsm(−kS)−J0‖∞→∞≤2k‖S‖∞.\|R_t\|_∞→∞=\|J_sm(-kS)-J_0\|_∞→∞≤ 2k\|S\|_∞. By the definition of J0J_0, ‖J0S‖∞≤2d‖S‖∞\|J_0S\|_∞≤ 2d\|S\|_∞. Therefore |⟨(Jt(k)−J0)S,eJ⋆⟩|≤4dk‖S‖∞2. | (J_t(k)-J_0)S,\,e_J |≤ 4d\,k\,\|S\|_∞^2. Taking expectations and summing over t, and using Lemma 8 with q=2q=2, ||2,pert≤4dk∑t=1T∥St−1∥∞2≤Cdk∑t=1T(t−1)log(ed)≤CdkT2log(ed).|_2,pert|≤ 4d\,k _t=1^TE\|S_t-1\|_∞^2≤ Cd\,k _t=1^T(t-1) (ed)≤ Cd\,k\,T^2 (ed). Together, we have 2≤2−c0T(T−1)logd+CdkT2log(ed).2_2≤-c_0 T\,(T-1)\, dd+ Cd\,k\,T^2 (ed). If k=~(1/Td)k= O(1/ Td) for some absolute constant c∗>0c_ >0, then 2≤2−c0T(T−1)logd+~(T3/2d3/2).2_2≤-c_0 T\,(T-1)\, dd+ O ( T^3/2d^3/2 ). Therefore, ℒ′(k)<0L (k)<0 for k=~(1/Td)k= O(1/ Td) as desired. ∎ Theorem 4 (Positivity for k=C/Tpolylog(d)k=C/ Tpolylog(d)). There exists an absolute constant C>0C>0 such that for all T,d≥2T,d≥ 2, if k=~(1/T)k= (1/ T), then ℒ′(k)>0L (k)>0. Proof. First, we use 3 and analyze 1 and 2 separately. First, we restate Equation 15 as ⟨JtS,π−u⟩ J_tS,π-u =⟨(J0+Rt)S,π−u⟩ = (J_0+R_t)S,π-u =⟨J0S,π⟩⏟N1,t−⟨RtS,π−u⟩⏟N2,t. = J_0S,π _N_1,t\;-\; R_tS,π-u _N_2,t. (26) First, we will bound N2,tN_2,t. Claim 1. There exist absolute constants c0,C0>0c_0,C_0>0 such that the following holds. For every k with 0<k≤c0/T0<k≤ c_0/ T, |⟨(Jt(k)−Jt(0))St−1,πt(k)−π0⟩|≤C0Tkd−3/2log(ed). |E (J_t(k)-J_t(0) )S_t-1,\ _t(k)- _0 |\ ≤\ C_0\,T\,k\,d^-3/2\, (ed). (27) Proof. Again, we abbreviate S:=St−1S:=S_t-1, and write πt(k)=sm(−kS) _t(k)=sm(-kS) and Jt(k)=Jsm(−kS)J_t(k)=J_sm(-kS). We wish to bound the following term: Qt(k):=⟨(Jt(k)−Jt(0))St−1,πt(k)−π0⟩=⟨RS,πk−π0⟩.Q_t(k):=E (J_t(k)-J_t(0))S_t-1,\ _t(k)- _0 =E RS,\ _k- _0 . (28) By Lemma 4, for every z∈ℝdz ^d we have (Jsm(z)−J0)d=d. (J_sm(z)-J_0 ) 1_d= 0_d. Then S decomposes into a multiple of d 1_d plus S⟂∈range(J0)S_ (J_0), and Lemma 4 implies RS=RS⟂.RS=RS_ . (29) Moreover, πk _k and π0 _0 are probability vectors, so ‖πk−π0‖1≤2\| _k- _0\|_1≤ 2. Thus, by Hölder’s inequality in (∞,1)(∞,1), |⟨RS,πk−π0⟩|=|⟨RS⟂,πk−π0⟩|≤‖RS⟂‖∞‖πk−π0‖1≤2‖RS⟂‖∞.| RS, _k- _0 |=| RS_ , _k- _0 |≤\|RS_ \|_∞\,\| _k- _0\|_1≤ 2\,\|RS_ \|_∞. (30) Taking expectations in (30) and using (28), |Qt(k)|≤ 2‖RS⟂‖∞.|Q_t(k)|\ ≤\ 2\,E\|RS_ \|_∞. (31) It remains to bound ‖RS⟂‖∞E\|RS_ \|_∞. Along the ray θ↦−θkSθ -θ kS we have the second-order expansion R=Jsm(−kS)−Jsm(0)=DJsm(0)[−kS]+∫01(1−θ)D2Jsm(−θkS)[−kS,−kS]θ.R=J_sm(-kS)-J_sm(0)=DJ_sm(0)[-kS]+ _0^1(1-θ)\,D^2J_sm(-θ kS)[-kS,-kS]\,dθ. (32) Set L:=DJsm(0)[−kS],ℛ:=∫01(1−θ)D2Jsm(−θkS)[−kS,−kS]θ,L:=DJ_sm(0)[-kS], := _0^1(1-θ)\,D^2J_sm(-θ kS)[-kS,-kS]\,dθ, so that R=L+ℛR=L+R. Then ‖RS⟂‖∞≤‖LS⟂‖∞+‖ℛS⟂‖∞.\|RS_ \|_∞≤\|LS_ \|_∞+\|RS_ \|_∞. (33) We bound the expectations of the two terms in (33) separately. By Lemma 9, ‖DJ(0)[h]‖∞→∞≤6d‖h‖∞∀h∈ℝd.\|DJ(0)[h]\|_∞→∞≤ 6d\,\|h\|_∞ ∀ h ^d. With h=−kSh=-kS we obtain ‖L‖∞→∞=‖DJ(0)[−kS]‖∞→∞≤6dk‖S‖∞.\|L\|_∞→∞=\|DJ(0)[-kS]\|_∞→∞≤ 6d\,k\|S\|_∞. By Lemma 6, ‖S⟂‖∞=‖J0S‖∞≤2d‖S‖∞.\|S_ \|_∞=\|J_0S\|_∞≤ 2d\,\|S\|_∞. Hence ‖LS⟂‖∞≤‖L‖∞→∞‖S⟂‖∞≤12d2k‖S‖∞2.\|LS_ \|_∞≤\|L\|_∞→∞\,\|S_ \|_∞≤ 12d^2\,k\|S\|_∞^2. (34) Recall that S=St−1∼(0,(t−1)Id×d)S=S_t-1 (0,(t-1)I_d× d). By Lemma 8 with q=2q=2, ‖S‖∞2≤C(t−1)log(ed)E\|S\|_∞^2≤ C\,(t-1)\, (ed) (35) for some absolute constant C>0C>0. Taking expectations in (34) and using (35) yields ‖LS⟂‖∞≤C1kd2(t−1)log(ed)E\|LS_ \|_∞\ ≤\ C_1\, kd^2\,(t-1)\, (ed) (36) for an absolute constant C1>0C_1>0. From Lemma 2 (f), for each θ∈[0,1]θ∈[0,1] and all S, ‖D2J(−θkS)[−kS,−kS]‖∞→∞≤16de2θk‖S‖∞k2‖S‖∞2. \|D^2J(-θ kS)[-kS,-kS] \|_∞→∞≤ 16d\,e^2θ k\|S\|_∞\,k^2\|S\|_∞^2. (37) Therefore, ‖ℛS⟂‖∞ \|RS_ \|_∞ ≤∫01(1−θ)‖D2J(−θkS)[−kS,−kS]‖∞→∞‖S⟂‖∞θ ≤ _0^1(1-θ)\, \|D^2J(-θ kS)[-kS,-kS] \|_∞→∞\,\|S_ \|_∞\,dθ ≤∫01(1−θ)16de2θk‖S‖∞k2‖S‖∞2⋅2d‖S‖∞θ ≤ _0^1(1-θ)\, 16de^2θ k\|S\|_∞k^2\|S\|_∞^2· 2d\|S\|_∞\,dθ =32d2k2‖S‖∞3∫01(1−θ)e2θk‖S‖∞θ. = 32d^2k^2\|S\|_∞^3 _0^1(1-θ)e^2θ k\|S\|_∞\,dθ. (38) For q>0q>0, a direct computation gives ∫01(1−θ)e2θkqθ≤12kqe2kq. _0^1(1-θ)e^2θ kq\,dθ≤ 12kq\,e^2kq. Applying this in (38) with q=‖S‖∞q=\|S\|_∞ yields ‖ℛS⟂‖∞≤16d2k‖S‖∞2e2k‖S‖∞.\|RS_ \|_∞≤ 16d^2k\,\|S\|_∞^2e^2k\|S\|_∞. (39) Now take expectations. By Cauchy–Schwarz, [‖S‖∞2e2k‖S‖∞]≤(‖S‖∞4)1/2(e4k‖S‖∞)1/2.E [\|S\|_∞^2e^2k\|S\|_∞ ]≤ (E\|S\|_∞^4 )^1/2 (Ee^4k\|S\|_∞ )^1/2. (40) By Lemma 8 with q=4q=4, ‖S‖∞4≤C(t−1)2(log(ed))2.E\|S\|_∞^4≤ C\,(t-1)^2( (ed))^2. (41) By the MGF bound for the sup (Lemma 12), e4k‖S‖∞≤C′dexp(C′k2(t−1))Ee^4k\|S\|_∞≤ C \,d\, (C \,k^2(t-1) ) (42) for absolute constants C′,C′>0C ,C >0. Plugging (41) and (42) into (40), we obtain [‖S‖∞2e2k‖S‖∞]≤C2(t−1)log(ed)dexp(C3k2(t−1))E [\|S\|_∞^2e^2k\|S\|_∞ ]≤ C_2\,(t-1)\, (ed)\, d\, (C_3k^2(t-1) ) (43) for some absolute constants C2,C3>0C_2,C_3>0. Combining (39) and (43) gives ‖ℛS⟂‖∞≤C2kd2(t−1)log(ed)dexp(C3k2(t−1))=C2kd3/2(t−1)log(ed)eC3k2(t−1).E\|RS_ \|_∞≤ C_2\, kd^2\,(t-1) (ed)\, d\, (C_3k^2(t-1) )=C_2\, kd^3/2\,(t-1) (ed)\,e^C_3k^2(t-1). (44) From (33), (36), and (44), ‖RS⟂‖∞≤C1kd2(t−1)log(ed)+C2kd3/2(t−1)log(ed)eC3k2(t−1).E\|RS_ \|_∞≤ C_1\, kd^2\,(t-1) (ed)+C_2\, kd^3/2\,(t-1) (ed)\,e^C_3k^2(t-1). (45) Recalling (31), we obtain |Qt(k)|≤2‖RS⟂‖∞≤Ck(t−1)log(ed)(1d2+1d3/2eC3k2(t−1))|Q_t(k)|≤ 2\,E\|RS_ \|_∞≤ C\,k\,(t-1) (ed) ( 1d^2+ 1d^3/2e^C_3k^2(t-1) ) (46) for some absolute C>0C>0. Now assume 0<k≤c0/T0<k≤ c_0/ T for a sufficiently small absolute constant c0>0c_0>0. Then, for all t≤Tt≤ T, k2(t−1)≤k2T≤c02,⇒eC3k2(t−1)≤eC3c02=:C∗,k^2(t-1)≤ k^2T≤ c_0^2, e^C_3k^2(t-1)≤ e^C_3c_0^2=:C_ , where C∗C_ is an absolute constant. Moreover t−1≤Tt-1≤ T, and, for all d≥2d≥ 2, 1d2≤1d3/2. 1d^2≤ 1d^3/2. Thus, absorbing C∗C_ and the factor 22 into a new constant C0C_0, (46) yields |Qt(k)|≤C0kTd3/2log(ed),|Q_t(k)|≤ C_0\, kTd^3/2\, (ed), uniformly over all t∈[T]t∈[T], all d≥2d≥ 2, and all k∈(0,c0/T]k∈(0,c_0/ T]. This is exactly (27), which completes the proof. ∎ Now, we focus on calculating N1,tN_1,t. By Lemma 14, we have N1,t=~(T2kd)N_1,t= ( T^2kd). more specifically, N1,t≤−C2T2kdN_1,t≤-C_2 T^2kd. Therefore, we have −2≥12C2T2kd−C0kT2d3/2log(ed) -2_1≥ 2C_2 T^2kd-C_0 kT^2d^3/2\, (ed) (47) Now, we focus on calculating 2. For 2,0, by 2 and Lemma 11, we have =2,0~(T1/2(T−1)logd)_2,0= ( T^1/2(T-1) dd). more specifically, ≥2,0−C4T1/2(T−1)logd_2,0≥-C_4 T^1/2(T-1) dd for some C4>0C_4>0. Proposition 4. There exist absolute constants C1,C2>0C_1,C_2>0 such that ||2,pert≤C1d2kT2log(ed)+C3d3/2kT5/2log(ed)e4k2T.|_2,pert|≤ C_1d^2\,k\,T^2 (ed)+ C_3d^3/2\,k\,T^5/2 (ed)e^4k^2T. (48) In particular, with k=1/Tk=1/ T, ||2,pert≤Cd−7/4T3/2polylog(d).|_2,pert|≤ C\,d^-7/4\,T^3/2\,polylog(d). Proof. Fix t and write S:=St−1S:=S_t-1. By Lemma 4 and Hölder in (∞,1)(∞,1), |⟨RtS,eJ⋆⟩|≤‖RtJ0S‖∞.| R_tS,e_J |≤\|R_tJ_0S\|_∞. where Rt=Jt(k)−J0R_t=J_t(k)-J_0 defined in Proposition 3 Decompose RtR_t into its linear and quadratic parts along the ray: Rt=DJ()[−kS]⏟=:Lt+∫01(1−θ)D2J(−θkS)[−kS,−kS]θ⏟=:ℛt.R_t= DJ( 0)[-kS]_=:L_t+ _0^1(1-θ)\,D^2J(-θ kS)[-kS,-kS]\,dθ_=:R_t. Thus ‖RtJ0S‖∞≤‖LtJ0S‖∞+‖ℛtJ0S‖∞.\|R_tJ_0S\|_∞\;≤\;\|L_tJ_0S\|_∞\;+\;\|R_tJ_0S\|_∞. (i) Linear piece. By Lemma 9 and Lemma 6, ‖LtJ0S‖∞≤‖DJ()[−kS]‖∞→∞‖J0S‖∞≤6dk‖S‖∞⋅2d‖S‖∞=12d2k‖S‖∞2.\|L_tJ_0S\|_∞≤\|DJ( 0)[-kS]\|_∞→∞\,\|J_0S\|_∞≤ 6dk\|S\|_∞· 2d\|S\|_∞= 12d^2k\,\|S\|_∞^2. Taking expectations and summing (using Lemma 8 with q=2q=2), ∑t=1T‖LtJ0St−1‖∞≤C1d2kT2log(ed). _t=1^TE\|L_tJ_0S_t-1\|_∞\;≤\; C_1d^2\,k\,T^2 (ed). (49) (i) Quadratic remainder, via Cauchy–Schwarz and MGF. For a fixed t, ‖ℛtJ0S‖∞ \|R_tJ_0S\|_∞ ≤∫01(1−θ)‖D2J(−θkS)[−kS,−kS]J0S‖∞θ ≤ _0^1(1-θ)\, \|D^2J(-θ kS)[-kS,-kS]\,J_0S \|_∞\,dθ ≤∫01(1−θ)‖D2J(−θkS)[−kS,−kS]‖∞→∞‖J0S‖∞θ ≤ _0^1(1-θ)\,\|D^2J(-θ kS)[-kS,-kS]\|_∞→∞\,\|J_0S\|_∞\,dθ ≤(i)∫01(1−θ)16de2θk‖S‖∞k2‖S‖∞2‖J0S‖∞θ (i)≤ _0^1(1-θ)\, 16d\,e^2θ k\|S\|_∞k^2\|S\|_∞^2\|J_0S\|_∞dθ ≤(ii)∫01(1−θ)32d2e2θk‖S‖∞k2‖S‖∞3θ (i)≤ _0^1(1-θ)\, 32d^2\,e^2θ k\|S\|_∞k^2\|S\|_∞^3dθ ≤∫0132d2e2θk‖S‖∞k2‖S‖∞3θ=32d2k2‖S‖∞312k‖S‖∞(e2k‖S‖∞−1)≤16d2k‖S‖∞2e2k‖S‖∞. ≤ _0^1 32d^2\,e^2θ k\|S\|_∞k^2\|S\|_∞^3dθ= 32d^2\,k^2\|S\|_∞^3 12k\|S\|_∞(e^2k\|S\|_∞-1)≤ 16d^2\,k\|S\|_∞^2e^2k\|S\|_∞. where (i) is due to Lemma 2-(f) and (i) is due to Lemma 6. Therefore, we have ∑t=1T‖ℛtJ0St−1‖∞ _t=1^TE\|R_tJ_0S_t-1\|_∞ ≤16d2k∑t=1T[‖St−1‖∞2e2k‖St−1‖∞] ≤ 16d^2\,k _t=1^TE[\|S_t-1\|_∞^2e^2k\|S_t-1\|_∞] ≤16d2k∑t=1T[‖St−1‖∞4][e4k‖St−1‖∞] ≤ 16d^2\,k _t=1^T E[\|S_t-1\|_∞^4]E[e^4k\|S_t-1\|_∞] ≤(iii)C1d2k∑t=1T[‖St−1‖∞4]dexp(8k2(t−1)) (i)≤ C_1d^2\,k _t=1^T E[\|S_t-1\|_∞^4]d (8k^2(t-1) ) ≤(iv)C2d2k∑t=1T(t−1)2log(ed)2dexp(8k2(t−1))≤C3d3/2kT2log(ed)e4k2T (iv)≤ C_2d^2\,k _t=1^T (t-1)^2 (ed)^2d (8k^2(t-1) )≤ C_3d^3/2kT^2 (ed)e^4k^2T where (i) is due to Lemma 12 and (iv) is due to Lemma 8 with q=4q=4. Therefore, we have ||2,pert≤C1d2kT2log(ed)+C3d3/2kT5/2log(ed)e4k2T. |_2,pert|≤ C_1d^2\,k\,T^2 (ed)+ C_3d^3/2\,k\,T^5/2 (ed)e^4k^2T. ∎ Therefore, we have 2≥2−C4T1/2(T−1)logd−C5d2kT2log(ed)−C6d3/2kT5/2log(ed)e4k2T 2_2≥-C_4 T^1/2(T-1) dd- C_5d^2\,k\,T^2 (ed)- C_6d^3/2\,k\,T^5/2 (ed)e^4k^2T (50) and combining (47) and (50) with k=(1/Tpolylog(d))k= (1/ Tpolylog(d)), we have ℒ′(k)>0L (k)>0. ∎ By Theorem 3 and Theorem 4, we have ℒ′(k)<0L (k)<0 for k=~(1/Td)k= O(1/ Td) and ℒ′(k)>0L (k)>0 for k=(1/Tpolylog(d))k= (1/ Tpolylog(d)). Therefore, there exists k⋆k in the interval (~(1/Td),~(1/T))( (1/ Td), (1/ T)) such that ℒ′(k⋆)=0L (k )=0. ∎ Appendix B Deferred Lemmas We provide the proofs of lemmas related to Gaussian distributions and the SoftmaxSoftmax function that are used in the main text for the sake of completeness. Lemma 1 (Permutation commutant). Let A∈ℝd×dA ^d× d satisfy PAP⊺=Afor every permutation matrix P.PAP \;=\;A every permutation matrix P. Then there exist scalars α,β∈ℝα,β such that A=αId×d+βdd⊺.A=α I_d× d+β 1_d 1_d . If, in addition, d⊺A=d⊺ 1_d A= 0_d or Ad=dA 1_d= 0_d, then A=α(Id×d−1ddd⊺).A=α (I_d× d- 1d 1_d 1_d ). Consequently, ⟨A,−Id×d⟩F=−α(d−1) A,-I_d× d _F=-α(d-1) in this zero-sum case. Proof. Fix A satisfying PAP⊺=APAP =A for all permutation matrices P. For any two coordinates i,ji,j, a transposition exchanging them shows Aii=AjjA_i=A_j, so all diagonal entries are equal. For any two ordered pairs (i,j)(i,j) and (r,s)(r,s) with iji≠ j and rsr≠ s, there is a permutation sending i to r and j to s, so Aij=ArsA_ij=A_rs. Thus all off-diagonal entries are equal, which is equivalent to A=αId×d+βdd⊺A=α I_d× d+β 1_d 1_d after reparameterizing the common diagonal and off-diagonal values. If d⊺A=d⊺ 1_d A= 0_d , then d⊺A=(α+dβ)d⊺ 1_d A=(α+dβ) 1_d , so β=−α/dβ=-α/d. The same conclusion follows from Ad=dA 1_d= 0_d. Finally, ⟨Id×d−d−1dd⊺,Id×d⟩F=d−1 I_d× d-d^-1 1_d 1_d ,I_d× d _F=d-1, giving the displayed Frobenius identity. ∎ Lemma 2 (SoftmaxSoftmax Jacobian: spectral, ∞, and 11 bounds). For z∈ℝdz ^d, let p=Softmax(z),Jsm(z)=Diag(p)−pp⊺.p=Softmax(z), J_sm(z)=Diag(p)-p . Then: (a) Jsm(z)J_sm(z) is symmetric positive semidefinite and Jsm(z)d=0J_sm(z) 1_d=0. (b) Operator, ∞→∞→∞, and 1→11→ 1 bounds: ‖Jsm(z)‖op=‖Jsm(z)‖∞→∞=‖Jsm(z)‖1→1≤12.\|J_sm(z)\|_op=\|J_sm(z)\|_∞→∞=\|J_sm(z)\|_1→ 1≤ 12. (c) ℓ2 _2–Lipschitz continuity of SoftmaxSoftmax: ‖Softmax(z)−Softmax(z′)‖2≤12‖z−z′‖2.\|Softmax(z)-Softmax(z )\|_2\;≤\; 12\|z-z \|_2. (d) ℓ2 _2–Lipschitz continuity of the Jacobian: ‖Jsm(z)−Jsm(z′)‖op≤32‖z−z′‖2.\|J_sm(z)-J_sm(z )\|_op\;≤\; 32\,\|z-z \|_2. (e) Derivative bounds in induced norms: ‖DJsm(z)[h]‖∞→∞≤2‖h‖∞,‖DJsm(z)[h]‖1→1≤2‖h‖∞,\|DJ_sm(z)[h]\|_∞→∞≤ 2\,\|h\|_∞, \|DJ_sm(z)[h]\|_1→ 1≤ 2\|h\|_∞, and therefore ‖Jsm(θz)−Jsm(d)‖∞→∞≤2θ‖z‖∞ \|J_sm(θ z)-J_sm( 0_d) \|_∞→∞≤ 2θ \|z \|_∞. (f) ∞→∞→∞ bound of the second derivative of JsmJ_sm: ‖D2Jsm(z)[h,h]‖∞→∞≤16de2‖z‖∞‖h‖∞2\|D^2J_sm(z)[h,h]\|_∞→∞\;≤\; 16d\,e^2\|z\|_∞\|h\|_∞^2 (51) for some absolute constant C>0C>0. Proof. (a) PSD and nullspace property. For any x∈ℝdx ^d, x⊺Jsm(z)x=∑ipixi2−(∑ipixi)2=Varp(x)≥0.x J_sm(z)x= _ip_ix_i^2- ( _ip_ix_i )^2=Var_p(x)≥ 0. Also, Jsm(z)d=Diag(p)d−p(p⊺d)=p−p(1)=0.J_sm(z) 1_d=Diag(p) 1_d-p(p 1_d)=p-p(1)=0. (b) Spectral-norm bound. Since Jsm(z)J_sm(z) is symmetric, ‖Jsm(z)‖op=sup‖x‖2=1Varp(x).\|J_sm(z)\|_op= _\|x\|_2=1Var_p(x). For any x with ‖x‖2=1\|x\|_2=1 and m=minxim= x_i, M=maxxiM= x_i, Varp(x)≤(M−m)24.Var_p(x)≤ (M-m)^24. But (M−m)2=(xi−xj)2≤2(xi2+xj2)≤2‖x‖22=2.(M-m)^2=(x_i-x_j)^2≤ 2(x_i^2+x_j^2)≤ 2\|x\|_2^2=2. Thus Varp(x)≤12.Var_p(x)≤ 12. Moreover, for each row i, ∑j|(Jsm(z))ij|=pi(1−pi)+pi∑jipj=2pi(1−pi)≤12, _j|(J_sm(z))_ij|=p_i(1-p_i)+p_i _j≠ ip_j=2p_i(1-p_i)≤ 12, since x(1−x)≤1/4x(1-x)≤ 1/4; the same bound holds for each column by symmetry. Thus the ∞→∞→∞ and 1→11→ 1 operator norms also equal ‖Jsm(z)‖op\|J_sm(z)\|_op. (c) SoftmaxSoftmax is 1/21/2–Lipschitz in ℓ2 _2. For γ(θ)=(1−θ)z+θz′γ(θ)=(1-θ)z+θ z , Softmax(z′)−Softmax(z)=∫01Jsm(γ(θ))(z′−z)θ.Softmax(z )-Softmax(z)= _0^1J_sm(γ(θ))(z -z)\,dθ. Take norms and use (b): ‖Softmax(z′)−Softmax(z)‖2≤12‖z′−z‖2.\|Softmax(z )-Softmax(z)\|_2≤ 12\|z -z\|_2. (d) Jacobian Lipschitz bound. Differentiate Jsm(z)=Diag(p(z))−p(z)p(z)⊺.J_sm(z)=Diag(p(z))-p(z)p(z) . For q:=Dp(z)[h]=Jsm(z)hq:=Dp(z)[h]=J_sm(z)h, DJsm(z)[h]=Diag(q)−(qp⊺+pq⊺).DJ_sm(z)[h]=Diag(q)-(qp +pq ). Operator norms satisfy ‖Diag(q)‖op≤‖q‖∞≤‖q‖2,‖qp⊺‖op=‖q‖2‖p‖2≤‖q‖2,\|Diag(q)\|_op≤\|q\|_∞≤\|q\|_2, \|qp \|_op=\|q\|_2\|p\|_2≤\|q\|_2, and likewise for pq⊺pq . Hence ‖DJsm(z)[h]‖op≤3‖q‖2.\|DJ_sm(z)[h]\|_op≤ 3\|q\|_2. Using ‖q‖2=‖Jsm(z)h‖2≤12‖h‖2\|q\|_2=\|J_sm(z)h\|_2≤ 12\|h\|_2 from (b), ‖DJsm(z)[h]‖op≤32‖h‖2.\|DJ_sm(z)[h]\|_op≤ 32\|h\|_2. Integrate along the segment from z to z′z to conclude ‖Jsm(z)−Jsm(z′)‖op≤32‖z−z′‖2.\|J_sm(z)-J_sm(z )\|_op≤ 32\|z-z \|_2. (e) Bounds for DJsm(z)[h]DJ_sm(z)[h] in ∞– and 11–norms. From above, DJsm(z)[h]=Diag(q)−(qp⊺+pq⊺).DJ_sm(z)[h]=Diag(q)-(qp +pq ). (52) Step 1: generic bound. Using induced–norm identities, ‖DJsm(z)[h]‖α→α≤2‖q‖∞+‖q‖1,α∈1,∞.\|DJ_sm(z)[h]\|_α→α≤ 2\|q\|_∞+\|q\|_1, α∈\1,∞\. Step 2: bounds on q. From (b): ‖q‖∞=‖Jsm(z)h‖∞≤12‖h‖∞\|q\|_∞=\|J_sm(z)h\|_∞≤ 12\|h\|_∞ We also need the dimension-free inequality ‖q‖1=∑ipi|hi−⟨p,h⟩|≤‖h‖∞.\|q\|_1= _ip_i|h_i- p,h |≤\|h\|_∞. This follows by thinking p as a probability distribution and define X as a discrete random variable with taking hih_i with probability pip_i, then [|X−[X]|]≤[|X−[X]|2]=Var(X)≤‖h‖∞E[|X-E[X]|]≤ E[|X-E[X]|^2]= Var(X)≤ \|h \|_∞. Step 3: final estimates. For the ∞→∞→∞ norm: ‖DJsm(z)[h]‖∞→∞≤2⋅12‖h‖∞+‖h‖∞=2‖h‖∞.\|DJ_sm(z)[h]\|_∞→∞≤ 2· 12\|h\|_∞+\|h\|_∞=2\|h\|_∞. For the 1→11→ 1 norm: ‖DJsm(z)[h]‖1→1≤2‖h‖∞.\|DJ_sm(z)[h]\|_1→ 1≤ 2\|h\|_∞. This completes the proof. (f) ∞→∞→∞ bound of the second derivative of JsmJ_sm. First, we differentiate (52) in direction h. Recall that for p(z)=Softmax(z)p(z)=Softmax(z), Jsm(z)=Diag(p)−pp⊺,J_sm(z)\;=\;Diag(p)-p , and for a fixed direction h we write q:=Dp(z)[h]=Jsm(z)h,a:=D2p(z)[h,h].q:=Dp(z)[h]=J_sm(z)h, a:=D^2p(z)[h,h]. From (52) we have DJsm(z)[h]=Diag(q)−qp⊺−pq⊺.DJ_sm(z)[h]=Diag(q)-qp -pq . Differentiating once more in the direction h gives D2Jsm(z)[h,h] D^2J_sm(z)[h,h] =D(Diag(q))[h]−D(qp⊺)[h]−D(pq⊺)[h] =D(Diag(q))[h]-D(qp )[h]-D(pq )[h] =Diag(Dq[h])−((Dq[h])p⊺+q(Dp[h])⊺)−(p(Dq[h])⊺+(Dp[h])q⊺). =Diag(Dq[h])- ((Dq[h])p +q(Dp[h]) )- (p(Dq[h]) +(Dp[h])q ). Since Dp[h]=qDp[h]=q and Dq[h]=D2p(z)[h,h]=aDq[h]=D^2p(z)[h,h]=a, this becomes D2Jsm(z)[h,h] D^2J_sm(z)[h,h] =Diag(a)−(ap⊺+qq⊺)−(pa⊺+qq⊺) =Diag(a)- (ap +q )- (pa +q ) =Diag(a)−ap⊺−pa⊺−2qq⊺. =Diag(a)-ap -pa -2q . Thus D2Jsm(z)[h,h]=Diag(a)−ap⊺−pa⊺−2qq⊺,p:=p(z),q:=Jsm(z)h,a:=D2p(z)[h,h].D^2J_sm(z)[h,h]=Diag(a)-ap -pa -2q , p:=p(z), q:=J_sm(z)h, a:=D^2p(z)[h,h]. By standard calculation, we can derive that ai=pi(z)((hi−μ)2−σ2)a_i=p_i(z)((h_i-μ)^2-σ^2), where μ=∑j=1dpj(z)hjμ= _j=1^dp_j(z)h_j and σ2=∑j=1dpj(z)(hj−μ)2σ^2= _j=1^dp_j(z)(h_j-μ)^2. Due to the definition of ‖h‖∞ \|h \|_∞, we have |hi−μ|≤2‖h‖∞|h_i-μ|≤ 2 \|h \|_∞ and |σ2|≤4‖h‖∞2|σ^2|≤ 4 \|h \|_∞^2. Thus |ai|≤pi(z)(4‖h‖∞2+4‖h‖∞2)=8pi(z)‖h‖∞2.|a_i|≤ p_i(z)(4 \|h \|_∞^2+4 \|h \|_∞^2)=8p_i(z) \|h \|_∞^2. Therefore, ‖Diag(a)‖∞→∞≤8‖p‖∞‖h‖∞2.\|Diag(a)\|_∞→∞≤ 8\|p\|_∞ \|h \|_∞^2. Similarly, we have ‖ap⊺‖∞→∞≤8‖p‖∞‖h‖∞2\|ap \|_∞→∞≤ 8\|p\|_∞ \|h \|_∞^2 and ‖pa⊺‖∞→∞≤8‖p‖∞‖h‖∞2\|pa \|_∞→∞≤ 8\|p\|_∞ \|h \|_∞^2. Now, we bound ‖qq⊺‖∞→∞\|q \|_∞→∞ by bounding ‖q‖∞\|q\|_∞ and ‖q‖1\|q\|_1, since ‖qq⊺‖∞→∞≤‖q‖∞‖q‖1\|q \|_∞→∞≤\|q\|_∞\|q\|_1. We bound ‖q‖∞\|q\|_∞ by using the definition of q: q=Jsm(z)h=Diag(p(z))h−p(z)(p(z)⊺h)q=J_sm(z)h=Diag(p(z))h-p(z)(p(z) h) Therefore we have the followings: |qi| |q_i| ≤pi(z)|hi|+pi(z)∑j=1dpj(z)|hj|≤pi(z)‖h‖∞+pi(z)‖h‖∞≤2‖p(z)‖∞‖h‖∞ ≤ p_i(z)|h_i|+p_i(z) _j=1^dp_j(z)|h_j|≤ p_i(z) \|h \|_∞+p_i(z) \|h \|_∞≤ 2 \|p(z) \|_∞ \|h \|_∞ ‖q‖1 \|q \|_1 ≤‖Diag(p(z))h‖1+‖p(z)(p(z)⊺h)‖1≤‖h‖∞+‖h‖∞≤2‖h‖∞ ≤ \|Diag(p(z))h \|_1+ \|p(z)(p(z) h) \|_1≤ \|h \|_∞+ \|h \|_∞≤ 2 \|h \|_∞ Thus, we have ‖q‖∞≤2‖p(z)‖∞‖h‖∞\|q\|_∞≤ 2 \|p(z) \|_∞ \|h \|_∞ and ‖q‖1≤2‖h‖∞\|q\|_1≤ 2 \|h \|_∞, therefore ‖qq⊺‖∞→∞≤4‖p(z)‖∞‖h‖∞2\|q \|_∞→∞≤ 4 \|p(z) \|_∞ \|h \|_∞^2. Collecting all the bounds, we have ‖D2Jsm(z)[h,h]‖∞→∞≤32‖p(z)‖∞‖h‖∞2.\|D^2J_sm(z)[h,h]\|_∞→∞≤ 32\|p(z)\|_∞ \|h \|_∞^2. Now, we have pi(z)=pi(z−z¯)=ezi−z¯∑j=1dezj−z¯ p_i(z)=p_i(z- z)= e^z_i- z _j=1^de^z_j- z where z¯=1d∑j=1dzj z= 1d _j=1^dz_j. We know that 1d∑j=1dezj−z¯≥1 1d _j=1^de^z_j- z≥ 1 due to Jensen’s inequality, therefore ‖p(z)‖∞≤1de2‖z‖∞\|p(z)\|_∞≤ 1de^2\|z\|_∞, which concludes the proof. ∎ Lemma 3. Define J0=Diag(u)−uu⊺J_0=Diag(u)-u with u=1ddu= 1d 1_d. For every x∈ℝdx ^d, ‖J0x‖∞≤1d(‖x‖∞+|d⊺x|)\|J_0x\|_∞\;≤\; 1d (\|x\|_∞+| 1_d x| ) Proof. Since J0=1dId×d−1d2dd⊺J_0= 1dI_d× d- 1d^2 1_d 1_d , we have (J0x)i=1d(xi−(d⊺x)/d).(J_0x)_i= 1d (x_i-( 1_d x)/d ). Hence ‖J0x‖∞=1dmaxi|xi−x¯|≤1d(‖x‖∞+|x¯|).\|J_0x\|_∞= 1d _i|x_i- x|≤ 1d (\|x\|_∞+| x| ). ∎ Lemma 4 (Null-direction reduction). For every z∈ℝdz ^d and every x∈ℝdx ^d, (Jsm(z)−J0)x=(Jsm(z)−J0)J0x. (J_sm(z)-J_0 )\,x\;=\; (J_sm(z)-J_0 )\,J_0x. Equivalently, with Rt:=Jt(k)−J0R_t:=J_t(k)-J_0 and Aθ:=Jsm(θz)−J0A_θ:=J_sm(θ z)-J_0 (for any z), Rtx=RtJ0x,Aθx=AθJ0x.R_tx\;=\;R_tJ_0x, A_θx\;=\;A_θJ_0x. Proof. By Lemma 2-(a), Jsm(z)d=0J_sm(z) 1_d=0 for all z, and also J0d=0J_0 1_d=0. Hence (Jsm(z)−J0)d=0. (J_sm(z)-J_0 ) 1_d=0. Write x=J0x+αdx=J_0x+α 1_d, where α:=1dd⊺xα:= 1d 1_d x. Then (Jsm(z)−J0)x=(Jsm(z)−J0)J0x+α(Jsm(z)−J0)d=(Jsm(z)−J0)J0x.∎ (J_sm(z)-J_0 )\,x= (J_sm(z)-J_0 )\,J_0x+α\, (J_sm(z)-J_0 ) 1_d= (J_sm(z)-J_0 )\,J_0x. Lemma 5. Let x∈ℝdx ^d and α≥0α≥ 0. Set π:=Softmax(−αx)π:= Softmax(-α x) and p:=diag(π)−ππ⊺p:= diag(π)-π . Then ⟨px,π⟩≤0 px,π ≤ 0. Proof. Sort indices so that x1≤x2≤⋯≤xdx_1≤ x_2≤·s≤ x_d. Then π1≥π2≥⋯≥πd _1≥ _2≥·s≥ _d because πi∝e−αxi _i e^-α x_i. Write μπ:=∑iπixi _π:= _i _ix_i and note ⟨px,π⟩=∑i=1dπi2(xi−μπ)=(∑i=1dπi2)(∑iπi2xi∑iπi2⏟=:μπ2−μπ). px,π = _i=1^d _i^2(x_i- _π)= ( _i=1^d _i^2 ) ( _i _i^2x_i _i _i^2_=:~ _π^2- _π ). Let q:=π2/∑jπj2q:=π^2/ _j _j^2 be π squared and renormalized; then q is more concentrated than π, i.e. π≻qπ q in the majorization order (Hardy–Littlewood–Pólya). Since (xi)(x_i) is increasing, majorization implies μπ=∑iπixi≥∑iqixi=μπ2⟹μπ2−μπ≤ 0, _π= _i _ix_i\ ≥\ _iq_ix_i\ =\ _π^2 _π^2- _π\ ≤\ 0, hence ⟨px,π⟩≤0 px,π ≤ 0. ∎ Lemma 6. Let J0=Diag(u)−uu⊺J_0=Diag(u)-u with u=1ddu= 1d 1_d. Then ‖J0‖∞→∞=‖J0‖1→1=2(d−1)d2≤2d,‖J0‖op=1d\|J_0\|_∞→∞=\|J_0\|_1→ 1\;=\; 2(d-1)d^2\;≤\; 2d, \|J_0 \|_op= 1d Proof. The iith row of J0J_0 has diagonal entry (d−1)/d2(d-1)/d^2 and off-diagonal entries −1/d2-1/d^2. Thus row i has ℓ1 _1-norm d−1d2+(d−1)1d2=2(d−1)d2. d-1d^2+(d-1) 1d^2= 2(d-1)d^2. The same holds for column sums, yielding the claim. Lastly, the operator norm is the largest singular value, which is the largest eigenvalue of J0J0⊺=1d2dd⊺J_0J_0 = 1d^2 1_d 1_d , so ‖J0‖op=1d \|J_0 \|_op= 1d. ∎ Lemma 7. For all h, ‖DJsm()[h]‖∞→∞≤6d‖h‖∞\|DJ_sm( 0)[h]\|_∞→∞≤ 6d\|h\|_∞. Proof. For all h, DJsm()[h]=Diag(J0h)−(J0h)u⊺−u(J0h)⊺,u=1dd,DJ_sm( 0)[h]=Diag(J_0h)-(J_0h)u -u(J_0h) , u= 1d 1_d, Using Lemma 6, we have ‖J0h‖∞≤2d‖h‖∞\|J_0h\|_∞≤ 2d\|h\|_∞, so ‖DJsm()[h]‖∞→∞≤6d‖h‖∞.\|DJ_sm( 0)[h]\|_∞→∞≤ 6d\|h\|_∞. ∎ Lemma 8 (Gaussian supremum moments). Let Z∼(d,Id×d)Z ( 0_d,I_d× d) and q≥1q≥ 1. There exists Cq>0C_q>0, independent of d, such that ‖Z‖∞q≤Cq(log(ed))q/2.E\|Z\|_∞^q\;≤\;C_q\,( (ed))^q/2. Proof. By a union bound, ℙ(‖Z‖∞≥t)≤2de−t2/2P(\|Z\|_∞≥ t)≤ 2d\,e^-t^2/2. Integrating by parts gives ‖Z‖∞q≤Cq(log(ed))q/2E\|Z\|_∞^q≤ C_q( (ed))^q/2 for some CqC_q. ∎ Lemma 9. For all h, ‖DJsm()[h]‖∞→∞≤6d‖h‖∞\|DJ_sm( 0)[h]\|_∞→∞≤ 6d\|h\|_∞. Proof. For all h, DJsm()[h]=Diag(J0h)−(J0h)u⊺−u(J0h)⊺,u=1dd,DJ_sm( 0)[h]=Diag(J_0h)-(J_0h)u -u(J_0h) , u= 1d 1_d, Using Lemma 6, we have ‖J0h‖∞≤2d‖h‖∞\|J_0h\|_∞≤ 2d\|h\|_∞, so ‖DJsm()[h]‖∞→∞≤6d‖h‖∞.\|DJ_sm( 0)[h]\|_∞→∞≤ 6d\|h\|_∞. ∎ Lemma 10. There exists an absolute constant cev∈(0,1)c_ev∈(0,1) such that [min1≤j≤dGj]≤−cevlogd,d≥2,E\! [ _1≤ j≤ dG_j ]\;≤\;-\,c_ev d, d≥ 2, for i.i.d. Gj∼(0,1)G_j (0,1). Proof. We define Md:=max1≤j≤dGjM_d:= _1≤ j≤ dG_j and Xd:=min1≤j≤dGjX_d:= _1≤ j≤ dG_j. Since the GjG_j are i.i.d. standard normals, ℙ(Md≤a)=(a)dP(M_d≤ a)= (a)^d, where denotes the standard normal cdf. We use the classical Mills ratio inequality (Gordon, 1941): for all x>0x>0, 1−(x)≥x1+x2φ(x),1- (x)\;≥\; x1+x^2\, (x), (52) where φ(x)=12πe−x2/2 (x)= 1 2πe^-x^2/2 is the standard normal density. Set a:=logda:= d. Then φ(a)=12πd−1/2,a1+a2=logd 1+logd≥c0logd (a)= 1 2πd^-1/2, a1+a^2= d\,1+ d\,\;≥\; c_0 d for some universal constant c0>0c_0>0 and all d≥2d≥ 2. Using (52), 1−(a)≥c0d−1/2logd.1- (a)\;≥\;c_0\, d^-1/2 d. Thus ℙ(Md≤a)=(a)d=(1−(1−(a)))d≤(1−c0d−1/2logd)d≤exp(−c0d1/2logd).P(M_d≤ a)= (a)^d= (1-(1- (a)) )^d≤ (1-c_0\, d^-1/2 d )^d≤ \! (-c_0\, d^1/2 d ). Therefore, ℙ(Xd≤−a)=1−ℙ(Md≤a)≥1−exp(−c0d1/2logd).P\! (X_d≤-a )=1-P(M_d≤ a)≥ 1- \! (-c_0\, d^1/2 d ). For all sufficiently large d, the right-hand side is at least 1/21/2, so for such d, [Xd]≤−aℙ(Xd≤−a)≤−12logd.E[X_d]\;≤\;-a\,P(X_d≤-a)\;≤\;- 12 d. Since [Xd]≤0E[X_d]≤ 0 for each fixed d and the ratio −[Xd]/logd-E[X_d]/ d is bounded away from 0 on the finite range 2≤d≤d02≤ d≤ d_0, we obtain a universal constant cev∈(0,1)c_ev∈(0,1) such that [Xd]≤−cevlogdfor all d≥2.E[X_d]≤-c_ev d all d≥ 2. ∎ Lemma 11. There exists an absolute constant Cev>0C_ev>0 such that [min1≤j≤dGj]≥−Cevlogd,d≥2,E\! [ _1≤ j≤ dG_j ]\;≥\;-\,C_ev d, d≥ 2, for i.i.d. Gj∼(0,1)G_j (0,1). Proof. It suffices to upper bound [Md]E[M_d] by ClogdC d for some absolute constant C>0C>0. For any t>0t>0, ℙ(Md≥t)=ℙ(⋃j=1dGj≥t)≤∑j=1dℙ(Gj≥t)=dℙ(G1≥t)≤de−t2/2.P(M_d≥ t)=P ( _j=1^d\G_j≥ t\ )\;≤\; _j=1^dP(G_j≥ t)=d\,P(G_1≥ t)≤ de^-t^2/2. Next, decompose MdM_d into its positive and negative parts: Md+:=maxMd,0,Md−:=max−Md,0,M_d^+:= \M_d,0\, M_d^-:= \-M_d,0\, so that Md=Md+−Md−M_d=M_d^+-M_d^- and hence [Md]=[Md+]−[Md−]≤[Md+].E[M_d]=E[M_d^+]-E[M_d^-]\;≤\;E[M_d^+]. Since Md+≥0M_d^+≥ 0, we can use the standard tail integral representation for nonnegative random variables: [Md+]=∫0∞ℙ(Md+≥t)t=∫0∞ℙ(Md≥t)t.E[M_d^+]= _0^∞P(M_d^+≥ t)\,dt= _0^∞P(M_d≥ t)\,dt. Therefore, [Md]≤[Md+]=∫0∞ℙ(Md≥t)t.E[M_d]\;≤\;E[M_d^+]= _0^∞P(M_d≥ t)\,dt. Fix x:=2logdx:= 2 d and split the integral: [Md]≤∫0x1t+∫x∞ℙ(Md≥t)t≤x+d∫x∞e−t2/2t.E[M_d]≤ _0^x1\,dt\;+\; _x^∞P(M_d≥ t)\,dt\;≤\;x\;+\;d _x^∞e^-t^2/2\,dt. We bound the Gaussian tail using ∫x∞e−t2/2t≤1xe−x2/2,x>0, _x^∞e^-t^2/2\,dt\;≤\; 1xe^-x^2/2, x>0, which follows from integrating by parts or from a standard inequality for Gaussian tails. Plugging x=2logdx= 2 d, we get d∫x∞e−t2/2t≤d⋅1xe−x2/2=d⋅12logd⋅e−logd=12logd≤ 1,d _x^∞e^-t^2/2\,dt\;≤\;d· 1xe^-x^2/2=d· 1 2 d· e^- d= 1 2 d\;≤\;1, for all d≥2d≥ 2. Therefore, [Md]≤x+1=2logd+1≤(2+1)logd≤ 3logd,d≥2.E[M_d]\;≤\;x+1\;=\; 2 d+1\;≤\;( 2+1) d\;≤\;3 d, d≥ 2. ∎ Lemma 12 (MGF for Gaussian suprema). Let G∼(d,tId×d)G ( 0_d,tI_d× d). For any a≥0a≥ 0, exp(a‖G‖∞)≤ 2dexp(a2t2).E \! (a\|G\|_∞ )\;≤\;2d\, \! ( a^2t2 ). Proof. By the union bound, exp(a‖G‖∞)=maxiexp(a|Gi|)≤∑iexp(a|Gi|) (a\|G\|_∞)= _i (a|G_i|)≤ _i (a|G_i|), so ea‖G‖∞≤dea|G1|Ee^a\|G\|_∞≤ d\,Ee^a|G_1|. For Gi∼(0,t)G_i (0,t), ea|Gi|=2∫0∞eax12πte−x2/(2t)x≤2ea2t/2Ee^a|G_i|=2 _0^∞e^ax 1 2π te^-x^2/(2t)dx≤ 2e^a^2t/2. ∎ Lemma 13 (Stein’s lemma for Gaussian vectors). (Stein, 1981) Let X∼(d,Id×d)X ( 0_d,I_d× d) and let f:ℝd→ℝf:R^d be differentiable with ‖∇f(X)‖2<∞E\|∇ f(X)\|_2<∞ and |Xif(X)|<∞E|X_if(X)|<∞ for all i. Then for every v∈ℝdv ^d, [⟨X,v⟩f(X)]=[⟨v,∇f(X)⟩].E\! [\, X,v \,f(X)\, ]\;=\;E\! [\, v,∇ f(X) \, ]. Equivalently, coordinatewise: [Xif(X)]=[∂if(X)],i=1,…,d.E[\,X_if(X)\,]=E[\, _if(X)\,], i=1,…,d. Proof. We give the proof in one dimension; the multivariate case follows by linearity. Let Z∼(0,1)Z (0,1) with density φ(z)=12πe−z2/2 (z)= 1 2πe^-z^2/2. Assume |Zf(Z)|<∞E|Zf(Z)|<∞ and |f′(Z)|<∞E|f (Z)|<∞. Then [Zf(Z)]=∫−∞zf(z)φ(z)z.E[Zf(Z)]= _-∞^∞zf(z)\, (z)\,dz. Since φ′(z)=−zφ(z) (z)=-z (z), we may write zφ(z)=−φ′(z),z (z)=- (z), so that [Zf(Z)]=−∫f(z)φ′(z)z.E[Zf(Z)]=- f(z)\, (z)\,dz. Integrating by parts, −∫f(z)φ′(z)z=−[f(z)φ(z)]−∞+∫f′(z)φ(z)z.- f(z)\, (z)\,dz=- [f(z) (z) ]_-∞^∞+ f (z) (z)\,dz. Because f(z)φ(z)→0f(z) (z)→ 0 as |z|→∞|z|→∞ (Gaussian density dominates any polynomially growing f), the boundary term vanishes, and we obtain [Zf(Z)]=∫f′(z)φ(z)z=[f′(Z)].E[Zf(Z)]= f (z) (z)\,dz=E[f (Z)]. For the d-dimensional case, apply the one-dimensional identity to each coordinate, conditioning on the remaining coordinates. Linearity of expectation and ⟨X,v⟩=∑iviXi X,v = _iv_iX_i then give [⟨X,v⟩f(X)]=∑i=1dvi[Xif(X)]=∑i=1dvi[∂if(X)]=[⟨v,∇f(X)⟩].E[ X,v f(X)]= _i=1^dv_i\,E[X_if(X)]= _i=1^dv_i\,E[ _if(X)]=E[ v,∇ f(X) ]. ∎ Lemma 14. Let a>0,d≥2a>0,d≥ 2 and X∼(0,aId×d)X (0,aI_d× d), and π(k)=Softmax(−kX)π(k)=Softmax(-kX). Define Fd(a,k)≔⟨J0X,π(k)⟩.F_d(a,k)\ \ E\, J_0X,\,π(k) . If k=~(1/a)k= O (1/ a ), Fd(a,k)=−(ak/d).F_d(a,k)\;=\;-\, \! (ak/d ). Proof. First, by the definition of J0J_0 and Lemma 13, Fd(a,k) F_d(a,k) =1d⟨X,π(k)⟩=1d∑i∈[d][Xiπi(k)] = 1dE X,π(k) = 1d _i∈[d]E[X_i _i(k)] =1d∑i∈[d][∂Xiπi(k)]=−akd∑i∈[d][πi(k)(1−πi(k))]=−akd[1−‖π(k)‖22] = 1d _i∈[d]E [ ∂ X_i _i(k) ]=- akd _i∈[d]E[ _i(k)(1- _i(k))]=- akdE[1-\|π(k)\|_2^2] From the calculation above, Fd(a,k)=−akd[ 1−‖π(k)‖22],π(k)=Softmax(−kX).F_d(a,k)\;=\;-\, akd\;E\! [\,1-\|π(k)\|_2^2\, ], π(k)=Softmax(-kX). (53) Write X=aZX= a\,Z with Z∼(d,Id×d)Z ( 0_d,I_d× d) and set κ:=kaκ:=k a. Then πi(k)=e−κZi∑j=1de−κZj,‖π(k)‖22=∑i=1de−2κZi(∑j=1de−κZj)2. _i(k)\;=\; e^-κ Z_i _j=1^de^-κ Z_j, \|π(k)\|_2^2\;=\; _i=1^de^-2κ Z_i ( _j=1^de^-κ Z_j )^2. Let Yi:=e−κZiY_i:=e^-κ Z_i so that Yi>0Y_i>0 are i.i.d. sub-exponential with μ1:=Yi=eκ2/2 _1:=EY_i=e^κ^2/2 and μ2:=Yi2=e2κ2 _2:=EY_i^2=e^2κ^2. Define S1=∑j=1dYjS_1= _j=1^dY_j and S2=∑i=1dYi2S_2= _i=1^dY_i^2. By Bernstein/Chernoff bounds for sub-exponential sums, there exist absolute constants c0,C0>0c_0,C_0>0 (depending only on an a priori bound κ≤κ⋆κ≤ _ ) such that with probability at least 1−2e−c0d1-2e^-c_0d, 12dμ1≤S1≤ 2dμ1and12dμ2≤S2≤ 2dμ2. 12d _1\;≤\;S_1\;≤\;2d _1 12d _2\;≤\;S_2\;≤\;2d _2. On this event, 18⋅μ2μ12⋅1d≤S2S12=‖π(k)‖22≤ 8⋅μ2μ12⋅1d= 8eκ2d. 18· _2 _1^2· 1d\;≤\; S_2S_1^2\;=\;\|π(k)\|_2^2\;≤\;8· _2 _1^2· 1d\;=\;8\, e^κ^2d. Taking expectations and absorbing the exponentially small tail yields constants 0<c1≤C1<∞0<c_1≤ C_1<∞ (depending only on κ⋆ _ ) for which c1d≤‖π(k)‖22≤C1dfor all d large enough. c_1d\;≤\;E\|π(k)\|_2^2\;≤\; C_1d all d large enough. (54) Combining (54) with (53), we obtain −akd(1−c1d)≤Fd(a,k)≤−akd(1−C1d).-\; akd (1- c_1d )\;≤\;F_d(a,k)\;≤\;-\; akd (1- C_1d ). In particular, for all d≥2C1d≥ 2C_1, −akd≤Fd(a,k)≤−12akd.-\; akd\;≤\;F_d(a,k)\;≤\;-\; 12\, akd. Renaming absolute constants completes the proof. ∎ Appendix C Proof of 1 Proof. By definition of external regret for ℛiR_i, we have (7) for each i∈[d]i∈[d]. Fix any P^=(p^1∣…∣p^d)∈ P=( p_1 … p_d)∈ . The cumulative swap regret with respect to this transformation is ∑t=1T(⟨ℓt,πt⟩−⟨ℓt,P^πt⟩) _t=1^T ( _t, _t - _t, P _t ) =(i)∑t=1T(⟨ℓt,Ptπt⟩−⟨ℓt,P^πt⟩)=∑t=1T[∑i=1dπt,i⟨ℓt,pi,t⟩−∑i=1dπt,i⟨ℓt,p^i⟩] (i)= _t=1^T ( _t,P_t _t - _t, P _t )= _t=1^T [ _i=1^d _t,i _t,p_i,t - _i=1^d _t,i _t, p_i ] =∑t=1T∑i=1d(⟨xi,t,pi,t⟩−⟨xi,t,p^i⟩)=∑i=1d∑t=1T(⟨xi,t,pi,t⟩−⟨xi,t,p^i⟩) = _t=1^T _i=1^d ( x_i,t,p_i,t - x_i,t, p_i )= _i=1^d _t=1^T ( x_i,t,p_i,t - x_i,t, p_i ) (55) ≤(ii)∑i=1dRegreti((xi,t)t∈[T]). (i)≤ _i=1^dRegret_i((x_i,t)_t∈[T]). Here (i) follows from the definition of πt _t and the fact that πt=Ptπt _t=P_t _t, and (i) follows from the definition of RegretiRegret_i. Since the identity holds for every P^∈ P∈ , taking the maximum over P P gives (8), and then Swap-Regret((ℓt)t∈[T])≤∑i=1dRegreti((xi,t)t∈[T]),Swap-Regret(( _t)_t∈[T])≤ _i=1^dRegret_i((x_i,t)_t∈[T]), which completes the proof. ∎ Appendix D Proof of Theorem 2 See 2 We define partial sums Si,t:=∑s=1txi,s∈ℝdS_i,t:= _s=1^tx_i,s ^d with Si,0:=dS_i,0:= 0_d for each head i∈[d]i∈[d] and time t∈[T]t∈[T]. For each head j∈[d]j∈[d] and time t∈[T]t∈[T] we write zj,tz_j,t for the pre-SoftmaxSoftmax logits and pj,t=Softmax(zj,t)∈([d])p_j,t= Softmax(z_j,t)∈ ([d]) for the corresponding mixed action (the j-th column of the transition matrix at time t). Throughout we reuse the SoftmaxSoftmax Jacobian notation from Appendix A: for π=Softmax(z)π= Softmax(z), Jsm(z):=∂Softmax(z)/∂z=Diag(π)−ππ⊺∈ℝd×dJ_sm(z):=∂\, Softmax(z)/∂ z=Diag(π)-π ^d× d, so Jsm(z)⊺d=dJ_sm(z) 1_d= 0_d and d⊺Jsm(z)=d⊺ 1_d J_sm(z)= 0_d . Proof of the existence of the stationary point.. We now impose the special parameter configuration from the statement: for each j∈[d]j∈[d] we write V(j)=(V1(j),…,Vd(j)),Vr(j)∈ℝd×d,V^(j)=(V^(j)_1,…,V^(j)_d), V^(j)_r ^d× d, and assume Vr(j)=−kId×d,r=j,d×d,rj,a(j)=d2,vc(j)=vd,V^(j)_r= cases-kI_d× d,&r=j,\\[2.0pt] O_d× d,&r≠ j, cases a^(j)= 0_d^2, v_c^(j)=v 1_d, for some k>0k>0. We also split XsX_s into d blocks of length d: Xs=(x1,s⊺,…,xd,s⊺)⊺,xi,s∈ℝd.X_s= (x_1,s ,…,x_d,s ) , x_i,s ^d. At this configuration the quadratic term XsXs⊺a(j)X_sX_s a^(j) vanishes and a(j)⊺Xs=0a^(j) X_s=0, so zj,t+1=∑s=1t(V(j)Xs+vd)=∑s=1t(∑r=1dVr(j)xr,s+vd).z_j,t+1= _s=1^t (V^(j)X_s+v 1_d )= _s=1^t ( _r=1^dV^(j)_rx_r,s+v 1_d ). Using the special form of V(j)V^(j), zj,t+1=∑s=1t(−kxj,s+vd)=−kSj,t+tvd.z_j,t+1= _s=1^t (-kx_j,s+v 1_d )=-kS_j,t+t\,v 1_d. Re-indexing time so that policies at round t use the sum up to t−1t-1 (as in Theorem 1), we obtain the simpler representation pj,t=Softmax(−kSj,t−1+(t−1)vd),j∈[d],t∈[T].p_j,t= Softmax (-kS_j,t-1+(t-1)v 1_d ), j∈[d],\ t∈[T]. (56) Thus, for each fixed j, the mapping (xj,1,…,xj,T)↦(pj,t)t≤T(x_j,1,…,x_j,T) (p_j,t)_t≤ T is exactly the single-layer linear attention model from Theorem 1, with ℓt _t there replaced by xj,tx_j,t here. For a fixed realization of (xi,t)(x_i,t) the per-head regret RiR_i satisfies Ri=∑t=1T⟨xi,t,pi,t⟩−minq∈([d])⟨∑t=1Txi,t,q⟩=∑t=1T⟨xi,t,pi,t⟩−minj∈[d]Si,T,j.R_i= _t=1^T x_i,t,p_i,t - _q∈ ([d]) _t=1^Tx_i,t,q = _t=1^T x_i,t,p_i,t - _j∈[d]S_i,T,j. By (56), each RiR_i has the same law as the single-head regret RT(k)R_T(k) from Theorem 1 (with ℓt _t replaced by xi,tx_i,t). The inner minimum in ℒL decouples across columns: minP^∈(([d]))d∑t=1T∑i=1d⟨xi,t,P^i−pi,t⟩ _ P∈( ([d]))^d _t=1^T _i=1^d x_i,t, P_i-p_i,t =∑i=1dminp^i∈([d])∑t=1T⟨xi,t,p^i−pi,t⟩ = _i=1^d _ p_i∈ ([d]) _t=1^T x_i,t, p_i-p_i,t =∑i=1d(minp^i∑t=1T⟨xi,t,p^i⟩−∑t=1T⟨xi,t,pi,t⟩) = _i=1^d ( _ p_i _t=1^T x_i,t, p_i - _t=1^T x_i,t,p_i,t ) =∑i=1d(minq∈([d])⟨Si,T,q⟩−∑t=1T⟨xi,t,pi,t⟩) = _i=1^d ( _q∈ ([d]) S_i,T,q - _t=1^T x_i,t,p_i,t ) =−∑i=1dRi. =- _i=1^dR_i. Hence we may write Rtot:=Swap-Regret((xi,t)i∈[d],t∈[T])=∑i=1dRi,ℒ((V(j),a(j),vc(j))j∈[d])=[Rtot2].R_tot:=Swap-Regret((x_i,t)_i∈[d],t∈[T])= _i=1^dR_i, ((V^(j),a^(j),v_c^(j))_j∈[d])=E[R_tot^2]. The d random variables R1,…,RdR_1,…,R_d are independent and have the same distribution as RT(k)R_T(k). We now compute the gradient of Rtot2R_tot^2 with respect to the logits zj,tz_j,t. For each fixed j the per-head regret RiR_i with iji≠ j does not depend on pj,⋅p_j,·, hence ∂Rtot∂pj,t=∂Rj∂pj,t=xj,t. ∂ R_tot∂ p_j,t= ∂ R_j∂ p_j,t=x_j,t. Using pj,t=Softmax(zj,t)p_j,t=Softmax(z_j,t) and the chain rule, ∂Rtot∂zj,t=Jsm(zj,t)⊺xj,t,∂Rtot2∂zj,t=2RtotJsm(zj,t)⊺xj,t. ∂ R_tot∂ z_j,t=J_sm(z_j,t) x_j,t, ∂ R_tot^2∂ z_j,t=2R_tot\,J_sm(z_j,t) x_j,t. We abbreviate :=j,t∂Rtot2∂zj,t=2RtotJsm(zj,t)⊺xj,t∈ℝd._j,t:= ∂ R_tot^2∂ z_j,t=2R_tot\,J_sm(z_j,t) x_j,t ^d. By dominated convergence (SoftmaxSoftmax is smooth and all Gaussian moments are finite), we may exchange gradient and expectation. Thus for any perturbations (δzj,t)j∈[d],t∈[T](δ z_j,t)_j∈[d],t∈[T], δℒ=[∑j=1d∑t=1T⟨,j,tδzj,t⟩]. =E [ _j=1^d _t=1^T _j,t,δ z_j,t ]. (57) We now express δzj,tδ z_j,t in terms of perturbations of the parameters of head j. For notational brevity we suppress the superscript (j)(j) in this step and write (V,a,vc)(V,a,v_c) for (V(j),a(j),vc(j))(V^(j),a^(j),v_c^(j)). From the definition of zj,t+1z_j,t+1 we obtain, for arbitrary perturbations (δV,δa,δvc)(δ V,δ a,δ v_c), δzt+1 δ z_t+1 =∑s=1t(δVXsXs⊺a+VXsXs⊺δa)+∑s=1t(δVXs+vcδa⊺Xs+δvca⊺Xs)+∑s=1tδvc. = _s=1^t (δ VX_sX_s a+VX_sX_s δ a )+ _s=1^t (δ VX_s+v_c\,δ a X_s+δ v_c\,a X_s )+ _s=1^tδ v_c. At the special configuration a=d2a= 0_d^2 this reduces to δzt+1=∑s=1tδVXs+∑s=1tvcδa⊺Xs+tδvc.δ z_t+1= _s=1^tδ VX_s+ _s=1^tv_c\,δ a X_s+t\,δ v_c. Restoring the head index j and re-indexing time so that t runs from 11 to T (i.e., replacing t+1t+1 by t), we have δzj,t=∑s=1t−1δV(j)Xs⏟(∗V)+∑s=1t−1vc(j)δa(j)⊺Xs⏟(∗a)+(t−1)δvc(j)⏟(∗v).δ z_j,t= _s=1^t-1δ V^(j)X_s_( _V)+ _s=1^t-1v_c^(j)\,δ a^(j) X_s_( _a)+ (t-1)δ v_c^(j)_( _v). (58) We now treat separately the three types of perturbations δvc(j)δ v_c^(j), δa(j)δ a^(j), and δV(j)δ V^(j). (i) The vc(j)v_c^(j)-direction (shift invariance). Using (∗v)( _v) in (58), δzj,t(v)=(t−1)δvc(j),δ z_j,t^(v)=(t-1)δ v_c^(j), so (57) gives δℒ(v)=∑j=1d∑t=1T(t−1)[⟨,j,tδvc(j)⟩]. ^(v)= _j=1^d _t=1^T(t-1)\,E [ _j,t,δ v_c^(j) ]. Write δvc(j)=δv(j)dδ v_c^(j)=δ v^(j) 1_d. Since d⊺Jsm(zj,t)⊺=d⊺ 1_d J_sm(z_j,t) = 0_d for all zj,tz_j,t, we have d⊺=j,t2F 1d⊺Jsm(zj,t)⊺xj,t=0 1_d _j,t=2F\, 1_d J_sm(z_j,t) x_j,t=0 pointwise, and therefore each term in the sum vanishes. Hence δℒ(v)=0 ^(v)=0 for all perturbations (δv(j))j∈[d](δ v^(j))_j∈[d], and ∇vc(j)ℒ|conf.=d,j∈[d]. _v_c^(j)L |_conf.= 0_d, j∈[d]. (i) The a(j)a^(j)-direction at a(j)=0a^(j)=0. From (∗a)( _a) in (58), δzj,t(a)=∑s=1t−1vc(j)δa(j)⊺Xs=v 1d∑s=1t−1⟨Xs,δa(j)⟩.δ z_j,t^(a)= _s=1^t-1v_c^(j)\,δ a^(j) X_s=v\, 1_d _s=1^t-1 X_s,δ a^(j) . Plugging into (57), δℒ(a) ^(a) =∑j=1d[∑t=1T⟨,j,tv 1d∑s=1t−1⟨Xs,δa(j)⟩] = _j=1^dE [ _t=1^T _j,t,v\, 1_d _s=1^t-1 X_s,δ a^(j) ] =v∑j=1d[∑t=1T(d⊺)j,t∑s=1t−1⟨Xs,δa(j)⟩]. =v _j=1^dE [ _t=1^T ( 1_d _j,t ) _s=1^t-1 X_s,δ a^(j) ]. But we already observed that d⊺=j,t0 1_d _j,t=0 for all (j,t)(j,t), hence δℒ(a)=0 ^(a)=0 for every (δa(j))j∈[d](δ a^(j))_j∈[d] and therefore ∇a(j)ℒ|conf.=d2,j∈[d]. _a^(j)L |_conf.= 0_d^2, j∈[d]. (i) The V(j)V^(j)-direction at Vj(j)=−kId×dV^(j)_j=-kI_d× d. It remains to analyse perturbations of the matrices V(j)V^(j). Recall that each V(j)V^(j) is partitioned into d blocks Vr(j)∈ℝd×dV^(j)_r ^d× d, and similarly we write δV(j)=(δV1(j),…,δVd(j))δ V^(j)=(δ V^(j)_1,…,δ V^(j)_d). From (∗V)( _V) in (58) we get δzj,t(V)=∑s=1t−1δV(j)Xs=∑r=1dδVr(j)Sr,t−1,δ z_j,t^(V)= _s=1^t-1δ V^(j)X_s= _r=1^dδ V^(j)_rS_r,t-1, since Xs=(x1,s⊺,…,xd,s⊺)⊺X_s=(x_1,s ,…,x_d,s ) . Substituting into (57) and using the Frobenius inner product ⟨A,B⟩F=tr(A⊺B) A,B _F=tr(A B), δℒ(V) ^(V) =∑j=1d[∑t=1T⟨,j,t∑r=1dδVr(j)Sr,t−1⟩] = _j=1^dE [ _t=1^T _j,t, _r=1^dδ V^(j)_rS_r,t-1 ] =∑j=1d∑r=1d⟨[∑t=1TSr,t−1⊺j,t]⏟=:Gj,r(k),δVr(j)⟩F. = _j=1^d _r=1^d E [ _t=1^T_j,tS_r,t-1 ]_=:G_j,r(k)\ ,\ δ V^(j)_r _F. Thus ∇Vr(j)ℒ|conf.=Gj,r(k)∈ℝd×d. _V^(j)_rL |_conf.=G_j,r(k) ^d× d. We now exploit the symmetries of the Gaussian model. Case rjr≠ j. At the special configuration Vr(j)=d×dV^(j)_r= O_d× d for rjr≠ j, the logits zj,tz_j,t and hence j,t depend only on the block process (xj,s)s≤T(x_j,s)_s≤ T, while the random walk (Sr,t)t≤T(S_r,t)_t≤ T is built from (xr,s)s≤T(x_r,s)_s≤ T and is independent of (xj,s)s≤T(x_j,s)_s≤ T. Therefore Gj,r(k)=[∑t=1T]j,t[Sr,t−1⊺]=d×d,G_j,r(k)=E [ _t=1^T_j,t ]\,E [S_r,t-1 ]= 0_d× d, because [Sr,t−1]=dE[S_r,t-1]= 0_d for all r,tr,t. Case r=jr=j. Fix j∈[d]j∈[d] and consider the action of coordinate permutations on the action coordinates of head j: for a permutation matrix P, xj,t↦Pxj,t,Sj,t−1↦PSj,t−1.x_j,t Px_j,t, S_j,t-1 PS_j,t-1. By (56), Vj(j)=−kId×dV^(j)_j=-kI_d× d, a(j)=0a^(j)=0 and vc(j)=vdv_c^(j)=v 1_d, and by permutation-equivariance of SoftmaxSoftmax, we also have zj,t↦Pzj,t,pj,t↦Ppj,t,↦j,tP.j,tz_j,t Pz_j,t, p_j,t Pp_j,t, _j,t P_j,t. Since the joint law of (xj,t)t≤T(x_j,t)_t≤ T is invariant under coordinate permutations and independent of the other heads, the pair (,j,tSj,t−1)t≤T(_j,t,S_j,t-1)_t≤ T has the same distribution as (P,j,tPSj,t−1)t≤T(P_j,t,PS_j,t-1)_t≤ T. Consequently, Gj,j(k)=[∑t=1TSj,t−1⊺j,t]=[∑t=1T(P)j,t(PSj,t−1)⊺]=PGj,j(k)P⊺G_j,j(k)=E [ _t=1^T_j,tS_j,t-1 ]=E [ _t=1^T(P_j,t)(PS_j,t-1) ]=PG_j,j(k)P for all permutation matrices P. By Lemma 1, there are scalars α(k),β(k)∈ℝα(k),β(k) such that Gj,j(k)=α(k)Id×d+β(k)dd⊺.G_j,j(k)=α(k)I_d× d+β(k) 1_d 1_d . Moreover, d⊺=j,t0 1_d _j,t=0 for every j,tj,t because Jsm(zj,t)⊺d=dJ_sm(z_j,t) 1_d= 0_d, so d⊺Gj,j(k)=d⊺ 1_d G_j,j(k)= 0_d . Hence Gj,j(k)=α(k),0:=0Id×d−1d⊺.G_j,j(k)=α(k)_0, _0:=I_d× d- 1d 1_d 1_d . The scalar is the same for every j by exchangeability of the heads and blocks at the stated configuration. Combining the two cases, we have shown that at the stated configuration ∇Vr(j)ℒ=α(k),0r=j,d×d,rj,j∈[d]. _V^(j)_rL= casesα(k)_0,&r=j,\\[2.0pt] O_d× d,&r≠ j, cases j∈[d]. Together with the vc(j)v_c^(j)- and a(j)a^(j)-direction results above, this implies that, for every fixed k, the only possibly non-zero component of the gradient of ℒL at the special configuration lies in the one-dimensional direction in which each Vj(j)V^(j)_j is scaled by the zero-sum projector 0. ∎ Now, we show that the stationary point is a scalar k⋆k such that ℒ′(k⋆)=0L (k )=0. Proof of the scale of the stationary point.. Define the one-dimensional function (k):=ℒ((V(j),a(j),vc(j))j∈[d]) (k):=L ((V^(j),a^(j),v_c^(j))_j∈[d] ) when, for each j∈[d]j∈[d], Vr(j)=−kId×d,r=j,d×d,rj,a(j)=d2,vc(j)=vd.V^(j)_r= cases-kI_d× d,&r=j,\\ O_d× d,&r≠ j, cases a^(j)= 0_d^2, v_c^(j)=v 1_d. By the chain rule, (k)′=∑j=1d⟨∇V(j)ℒ,∂V(j)∂k⟩F=∑j=1d⟨α(k),0−Id×d⟩F=−d(d−1)α(k), (k)= _j=1^d _V^(j)L,\, ∂ V^(j)∂ k _F= _j=1^d α(k)_0,\,-I_d× d _F=-d(d-1)α(k), since ∂Vj(j)/∂k=−Id×d∂ V^(j)_j/∂ k=-I_d× d and ∂Vr(j)/∂k=d×d∂ V^(j)_r/∂ k= O_d× d for rjr≠ j. In particular, α(k)=0⟺(k)′=0.α(k)=0 (k)=0. Let R(k)R(k) denote a random variable with the law of RT(k)R_T(k) for the single-head model, and note that R1(k,X),…,Rd(k,X)R_1(k,X),…,R_d(k,X) are independent copies of R(k)R(k) for every fixed k. Therefore (k)=[Rtot(k,X)2] (k)=E [R_tot(k,X)^2 ] =[(∑i=1dRi(k,X))2] =E [ ( _i=1^dR_i(k,X) )^2 ] =∑i=1d[Ri(k,X)2]+2∑1≤i<j≤d[Ri(k,X)Rj(k,X)] = _i=1^dE[R_i(k,X)^2]+2 _1≤ i<j≤ dE[R_i(k,X)R_j(k,X)] =d[R(k)2]+d(d−1)([R(k)])2. =d\,E[R(k)^2]+d(d-1) (E[R(k)] )^2. (59) Proposition 5. The expectation of the single-head regret is independent of k, i.e., [R(k)]E[R(k)] is independent of k. Proof. Write the single-head process as xtt=1⊺\x_t\_t=1 with xt∼(d,Id×d)x_t ( 0_d,I_d× d) i.i.d., and denote St:=∑s=1txsS_t:= _s=1^tx_s and πt(k):=Softmax(−kSt−1+(t−1)vd), _t(k):=Softmax(-kS_t-1+(t-1)v 1_d), so that R(k)=∑t=1T⟨xt,πt(k)⟩−minq∈([d])⟨∑t=1Txt,q⟩.R(k)= _t=1^T x_t, _t(k) - _q∈ ([d]) _t=1^Tx_t,\ q . First, C(X):=minq∈([d])⟨∑t=1Txt,q⟩C(X):= _q∈ ([d]) _t=1^Tx_t,\ q depends only on the losses (xt)t≤T(x_t)_t≤ T and is completely independent of the parameter k. Moreover, note that πt(k) _t(k) is measurable with respect to the σ-algebra generated by (x1,…,xt−1)(x_1,…,x_t-1) and does not depend on xtx_t. Using tower property and the fact that xtx_t is independent of (xs)s<t(x_s)_s<t and has mean zero, we obtain [⟨xt,πt(k)⟩] [ x_t, _t(k) ] =[[⟨xt,πt(k)⟩|x1,…,xt−1]] =E [E [ x_t, _t(k) \, |\,x_1,…,x_t-1 ] ] =[⟨[xt∣x1,…,xt−1],πt(k)⟩]=[⟨0,πt(k)⟩]=0. =E [ [x_t x_1,…,x_t-1],\ _t(k) ]=E [ 0, _t(k) ]=0. Summing over t gives [∑t=1T⟨xt,πt(k)⟩]=0for all k∈ℝ.E [ _t=1^T x_t, _t(k) ]=0 all k . Therefore [R(k)]=0−[C(X)]=−[minq∈([d])⟨∑t=1Txt,q⟩],E[R(k)]=0-E[C(X)]=-\,E [ _q∈ ([d]) _t=1^Tx_t,\ q ], which is a finite constant independent of k. ∎ From (59) and Proposition 5 we obtain (k)′ (k) =ddk[R(k)2]+d(d−1)dk([R(k)]2) =d\, ddkE[R(k)^2]+d(d-1)\, ddk (E[R(k)]^2 ) =ddk[R(k)2]+d(d−1)⋅2[R(k)]dk[R(k)] =d\, ddkE[R(k)^2]+d(d-1)· 2\,E[R(k)]\, ddkE[R(k)] =ddk[R(k)2](since dk[R(k)]=0). =d\, ddkE[R(k)^2] (since $ ddkE[R(k)]=0$). Recalling the external-regret objective Lext(k):=[R(k)2],L_ext(k):=E[R(k)^2], this identity can be succinctly written as (k)′=dLext′(k)for all k∈ℝ. (k)=d\,L_ext (k) all k . (60) Sign of (k)′ (k) and existence of k⋆k . The single-head analysis in Theorems 3 and 4 shows that there exist absolute constants c1,c2>0c_1,c_2>0 (independent of d,Td,T) such that: For all sufficiently large T,dT,d and all 0<k≤c1/Td,0<k≤ c_1/ Td, one has Lext′(k)<0.L_ext (k)<0. For all T,d≥2T,d≥ 2 and all k≥c2/Tpolylog(d),k≥ c_2/ T\,polylog(d), one has Lext′(k)>0.L_ext (k)>0. Combining these with (60), we obtain (k)′<0for k≤c1/Td,(k)′>0for k≥c2/Tpolylog(d). (k)<0 k≤ c_1/ Td, (k)>0 k≥ c_2/ T\,polylog(d). The function k↦(k)k (k) is smooth (SoftmaxSoftmax and the architecture are smooth and all Gaussian moments are finite), hence ′ is continuous. By the intermediate value theorem there exists k⋆∈(~(1Td),~(1T))k ∈ ( ( 1 Td ), ( 1 T ) ) such that (k⋆)′=0 (k )=0. ∎ Appendix E Additional Background E.1 Literature Review Transformers & In-context-learning. LLMs are now predominantly built upon the self-attention architecture (Vaswani et al., 2017). A central reason for their success is their remarkable ability to perform in-context learning (ICL): Transformers can construct new predictors directly from sequences of labeled examples provided in the input, without any parameter updates. This mechanism enables powerful few-shot learning capabilities (Brown et al., 2020; Garg et al., 2022; Min et al., 2022), which in turn have motivated a rapidly growing theoretical literature on ICL. For certain training losses, the minimizer of a single-layer Transformer is equivalent to performing one step of gradient descent for linear regression (Ahn et al., 2023; Zhang et al., 2023; Mahankali et al., 2023). For attention models with non-linear operators, prior work has provided provable guarantees for ICL—either through training-dynamics analyses or partial characterizations of stationary points. For example, Ahn et al. (2023) studied transformers with a ReLU operator, and Cheng et al. (2024) analyzed the SoftmaxSoftmax operator from a functional-gradient perspective. In addition, Chen et al. (2024) examined the training dynamics of multi-head Softmax attention in the context of ICL. However, none of these works characterizes the exact configuration of the stationary point of a transformer with a non-linear operator. Cheng et al. (2024) derived a stationary-point result but did not identify the precise configuration corresponding to a specific (functional) gradient-descent stepsize; Chen et al. (2024) provided a dynamical analysis for multi-head Softmax attention, but likewise did not interpret or characterize the stationary-point structure of transformers with non-linear operators. In contrast, our analysis explicitly characterizes the stationary-point configuration of a Transformer equipped with a non-linear operator, thereby yielding a provable guarantee for the no-regret behavior induced by such architectures—an independently interesting theoretical contribution. More recently, ICL has also been generalized to decision-making settings. Works such as Laskin et al. (2023); Lee et al. (2023); Lin et al. (2024) demonstrated that supervised pre-training can endow Transformers with in-context reinforcement learning abilities, enabling them to solve stochastic bandits and Markov decision processes. In comparison, regret-loss training focuses on online learning settings that may be arbitrary or even adversarial, as well as game-theoretic environments where agents interact strategically. E.2 Known Algorithms for No-Regret Learning Follow-the-Regularized-Leader (FTRL). FTRL generates the sequence xt+1=argminx∈η∑s=1tℓs(x)+R(x),x_t+1\;=\; argmin_x∈ \η _s=1^t _s(x)+R(x) \, where R is a strongly convex regularizer and η>0η>0 is the learning rate. With the negative-entropy regularizer R(x)=∑ixilogxiR(x)= _ix_i x_i, FTRL reduces to the multiplicative-weights update (or exponential weights). Smoothed Fictitious Play as Entropy-Regularized FTRL. Smoothed fictitious play is the update rule xt+1∝exp(−η∑s=1tℓs),x_t+1\; \; \! (-η _s=1^t _s ), which is exactly FTRL with entropy regularization. The smoothing (logit or softmax) arises from the convex conjugate of the negative entropy. If stepsize η=(1/T)η= (1/ T), smoothed fictitious play has a no-regret guarantee (Cesa-Bianchi and Lugosi, 2006). In this paper, we interchangeably use the terms smoothed fictitious play and FTRL with entropy regularization. Appendix F Use of AI Assistance The authors used OpenAI Codex to assist with code implementation, debugging, refactoring, and the linguistic and stylistic editing of the manuscript. All research questions, theoretical ideas, theorem statements, proofs, experimental designs, validation procedures, interpretations, and conclusions were developed and verified by the authors. In particular, the scientific results reported in this paper are the authors’ own work; Codex was used as a coding and editing aid and not as a source of scientific claims. The authors reviewed all AI-assisted material and take full responsibility for the content of the paper and the accompanying code.