Differentiable Belief-based Opponent Shaping

# Differentiable Belief-based Opponent Shaping
Source: [https://arxiv.org/html/2605.29042](https://arxiv.org/html/2605.29042)
Aarav G\. Sane Department of Computer Science Purdue University sane0@purdue\.edu &Karthik Sivachandran Department of Computer Science Purdue University ksivacha@purdue\.edu Rohan R\. Paleja Department of Computer Science Purdue University rpaleja@purdue\.edu

###### Abstract

Human coordination often relies on the ability to influence the beliefs of others through strategic action\. In multi\-agent reinforcement learning, opponent shaping attempts to replicate this influence, though existing methods typically operate within an opponent’s parameter, policy, or value space\. Meanwhile, belief\-manipulation techniques in hidden\-role games often rely on hard\-coded objectives, such as deception or belief saturation\. We propose Differentiable Belief\-based Opponent Shaping \(D\-BOS\), a first\-order method that treats each observer’s belief as the shaped opponent state and differentiates throughkk\-step softmax\-Bayes belief dynamics\. Rather than explicitly rewarding deceptive or cooperative behavior, our method treats the belief state as the target for shaping\. This allows the optimal strategy to emerge naturally from the environment’s reward structure\. This belief\-space formulation provides an opponent\-shaping signal by differentiating through opponent belief updates, and naturally extends to multiple observers by aggregating gradients over their individual inferred belief trajectories\. Empirically, D\-BOS outperforms PPO and BBM in hidden\-role games, with the largest gains in mixed\-motive settings\.

## 1Introduction

Humans routinely reason about what others believe, and use that reasoning to coordinate, persuade, conceal, or reveal information\. This ability is central to Theory of Mind\(Premack and Woodruff,[1978](https://arxiv.org/html/2605.29042#bib.bib19); Wimmer and Perner,[1983](https://arxiv.org/html/2605.29042#bib.bib28)\)and has become an important motivation for computational models of human\-agent collaboration and human\-robot teaming\(Erdoganet al\.,[2022](https://arxiv.org/html/2605.29042#bib.bib7); Palejaet al\.,[2023](https://arxiv.org/html/2605.29042#bib.bib18)\)\. In collaborative settings, from shared autonomy to ad hoc teaming with heterogeneous strategies\(Chenet al\.,[2020](https://arxiv.org/html/2605.29042#bib.bib5); Palejaet al\.,[2022](https://arxiv.org/html/2605.29042#bib.bib17)\), the useful partner is not merely the one that chooses good actions in isolation, but the one that understands how its actions change what others think\(Shaftoet al\.,[2014](https://arxiv.org/html/2605.29042#bib.bib24); Hoet al\.,[2016](https://arxiv.org/html/2605.29042#bib.bib11)\)\. We study this problem in hidden\-role partially observable Markov games, such as Avalon\(Serrinoet al\.,[2019](https://arxiv.org/html/2605.29042#bib.bib23)\), Rescue\-the\-General\(Aitchisonet al\.,[2021](https://arxiv.org/html/2605.29042#bib.bib3)\), and the Multi\-Agent Coin Game\(Raileanuet al\.,[2018](https://arxiv.org/html/2605.29042#bib.bib21)\), which are controlled multi\-agent testbeds where roles, intentions, and goals are latent, and where an agent’s behavior changes the posterior beliefs of allies and adversaries\.

Current multi\-agent reinforcement learning methods struggle to capture this interaction\. Existing opponent\-shaping algorithms\(Foersteret al\.,[2018](https://arxiv.org/html/2605.29042#bib.bib8); Aghajohariet al\.,[2024](https://arxiv.org/html/2605.29042#bib.bib1); Zhaoet al\.,[2022](https://arxiv.org/html/2605.29042#bib.bib29); Williet al\.,[2022](https://arxiv.org/html/2605.29042#bib.bib27); Duqueet al\.,[2025](https://arxiv.org/html/2605.29042#bib.bib6)\)anticipate an opponent’s learning update to optimize returns, but operate in high\-dimensional spaces, require strong assumptions, and are typically restricted to two\-player settings\. Conversely, belief\-manipulation methods like BBM\(Aitchisonet al\.,[2021](https://arxiv.org/html/2605.29042#bib.bib3)\)model hidden beliefs but rely on myopic, prescribed objectives like fixed deception\. These limitations motivate a natural synthesis: an agent should shape opponent beliefs over multiple steps driven entirely by task reward\. Subordinating belief manipulation to task reward ensures it acts as an instrumental mechanism for optimal play rather than a rigid behavioral prior\.

We proposeDifferentiable Belief\-based Opponent Shaping \(D\-BOS\), a first\-order method for opponent shaping in belief space\. D\-BOS treats each observer’s \(i\.e\., any other agent in the environment\) posterior over hidden roles as the target state to be shaped\. It unrolls a differentiable softmax\-Bayes update forkksteps and backpropagates through the resulting belief trajectory, thereby explicitly optimizing the long\-term task value of the induced future belief states\. The direction of belief shaping is therefore organically determined: in an adversarial setting, D\-BOS can obscure the agent’s role, while in a cooperative setting, it can make the correct role easier to infer\. We further analyze how D\-BOS navigates mixed\-motive settings, where it may need to conceal its identity from adversaries while simultaneously revealing it to allies\.

Our contributions are:

- •Differentiable belief dynamics for opponent shaping: D\-BOS backpropagates throughkk\-step softmax\-Bayes belief updates, using the explicit softmax Jacobian to produce temporally extended belief\-shaping gradients\.
- •A LOLA\-style view in belief space: We show that, under a Bayesian observer model, shaping beliefs is equivalent to shaping the opponent’s induced policy, yielding the same meta\-gradient structure as LOLA but with a low\-dimensional belief state\.
- •Error bounds for second\-order Theory of Mind: We bound how approximation error in second\-order observations propagates through thekk\-step belief chain and into the shaping gradient, exposing the tradeoff between longer lookahead and belief\-model accuracy\.
- •Hidden\-role experiments: We evaluate D\-BOS against PPO and BBM in Rescue\-the\-General, Avalon variants, and multi\-agent CoinGame to study whether belief\-space shaping improves return, belief trajectories, and stability\.

## 2Related Work

We situate our method at the intersection of three primary lines of research: algorithms for active opponent shaping, computational models of Theory of Mind for belief manipulation, and the embedding of differentiable belief updates within neural architectures\.

##### Opponent Shaping

Opponent shaping studies how one learner can improve its own long\-term outcome by accounting for how its actions change other learners\. LOLA\(Foersteret al\.,[2018](https://arxiv.org/html/2605.29042#bib.bib8)\)introduced this idea by differentiating through an opponent’s anticipated gradient step, which yields a meta\-gradient involving mixed second derivatives and requires a differentiable model of the opponent’s learning update\. Subsequent work refined this basic formulation: SOS\(Letcheret al\.,[2019](https://arxiv.org/html/2605.29042#bib.bib13)\)modifies the shaping term to improve stability in differentiable games, COLA\(Williet al\.,[2022](https://arxiv.org/html/2605.29042#bib.bib27)\)addresses consistency when both agents use opponent\-aware updates, and POLA\(Zhaoet al\.,[2022](https://arxiv.org/html/2605.29042#bib.bib29)\)uses a proximal formulation to reduce sensitivity to policy parameterization\. M\-FOS\(Luet al\.,[2022](https://arxiv.org/html/2605.29042#bib.bib14)\)instead treats opponent shaping as a meta\-learning problem, avoiding a specific differentiable opponent optimizer\. Other work reduces or changes the object being differentiated through\. LOQA\(Aghajohariet al\.,[2024](https://arxiv.org/html/2605.29042#bib.bib1)\)assumes opponents act through softmax Q\-values rather than through an explicit policy\-gradient learner\. Advantage Alignment\(Duqueet al\.,[2025](https://arxiv.org/html/2605.29042#bib.bib6)\)shows that LOLA\- and LOQA\-style shaping terms can be expressed through advantage products, yielding a first\-order algorithm\. D\-BOS is closest in spirit to this line of work: it also seeks a first\-order shaping signal\. Rather than shaping the advantage function, D\-BOS shapes an explicit posterior belief state with a known softmax\-Bayes update\. This preserves the opponent\-shaping viewpoint while moving the differentiable update map into the hidden\-role belief dynamics\.

##### Belief Manipulation and Theory of Mind

Belief manipulation has been studied most directly in hidden\-role and deception settings\. Bayesian Belief Manipulation \(BBM\)\(Aitchisonet al\.,[2021](https://arxiv.org/html/2605.29042#bib.bib3)\)is our closest predecessor\. In this framework, the agent estimates what an observer believes about its role and computes a Bayes factor to quantify the information revealed by a specific action, as shown in Equation \([1](https://arxiv.org/html/2605.29042#S2.E1)\)\.

ρ=πz∗​\(a\|hi,j,i\)∑z∈𝒵πz​\(a\|hi,j,i\)​Pi,j​\(Aiz\)\\displaystyle\\rho=\\frac\{\\pi\_\{z^\{\*\}\}\(a\|h\_\{i,j,i\}\)\}\{\\sum\_\{z\\in\\mathcal\{Z\}\}\\pi\_\{z\}\(a\|h\_\{i,j,i\}\)P\_\{i,j\}\(A\_\{i\}^\{z\}\)\}\(1\)Here,ρ\\rhois the Bayes factor,πz∗\\pi\_\{z^\{\*\}\}is the likelihood under the shaping agent’s true rolez∗z^\{\*\}, andPi,jP\_\{i,j\}represents the observer’s current belief\.hi,j,ih\_\{i,j,i\}represents the second\-order Theory of Mind estimate of what agentAiA\_\{i\}\(the shaping agent\) thinks agentAjA\_\{j\}\(the observer\) thinksAiA\_\{i\}observes\. This value is then transformed into an intrinsic reward signal, as expressed byri​n​t=−log⁡\(ρ\)r\_\{int\}=\-\\log\(\\rho\), incentivizing deception\. While BBM provides a practical way to train deceptive agents, its shaping signal is fundamentally*myopic*, as it is computed independently at each timestep and relies on a prescribed direction \(deception\) rather than the environment’s task reward\.

More broadly, Theory\-of\-Mind models have been used to infer agents’ latent goals, beliefs, and future behavior\. ToMnet\(Rabinowitzet al\.,[2018](https://arxiv.org/html/2605.29042#bib.bib20)\)learns to model other agents from behavior, and Oguntola\(Oguntola,[2025](https://arxiv.org/html/2605.29042#bib.bib16)\)formalizes recursive Theory of Mind across several multi\-agent testbeds\. Similarly, Alon et al\. \(2023\)\(Alonet al\.,[2023](https://arxiv.org/html/2605.29042#bib.bib22)\)study how recursive reasoning can lead to deception in communication games\. These works operate primarily as passive observers or heuristic frameworks\. They do not yield a differentiable shaping gradient that can be used for end\-to\-end reinforcement learning, which precludes them from serving as active opponent\-shaping baselines\. Finally, while Model\-Based Opponent Modeling \(MBOM\)\(Yuet al\.,[2022](https://arxiv.org/html/2605.29042#bib.bib15)\)uses environment models to adapt to reasoning learners, it is distinct from D\-BOS as it focuses on adaptation based on an inferred policy of the opponent\. Furthermore, MBOM requires the training of an explicit environment transition model to simulate recursive imagination, while D\-BOS is environment\-model\-free, requiring only the differentiable map of the observer’s belief update\.

##### Differentiable Belief Updates

Differentiable filtering methods show that Bayesian updates can be embedded inside neural computation\. QMDP\-net\(Karkuset al\.,[2017](https://arxiv.org/html/2605.29042#bib.bib12)\)encodes Bayesian filtering and QMDP planning as differentiable neural network layers for partially observable control\. IPOMDP\-net\(Han and Gmytrasiewicz,[2019](https://arxiv.org/html/2605.29042#bib.bib9)\)extends this idea to multi\-agent settings with interactive belief updates\. These methods use differentiable beliefs to help an agent plan under its own uncertainty\. D\-BOS uses the same computational affordance for a different purpose: differentiating through the belief update of an*observer*to shape what that observer will believe in the future and how the agent’s actions affect these belief dynamics\. This distinction is important in hidden\-role games, where the belief state being optimized is not only the agent’s internal uncertainty, but another agent’s posterior over the shaper’s latent role\.

## 3Preliminaries

We studynn\-player*partially observable hidden\-role games*, a special case of stochastic games\(Shapley,[1953](https://arxiv.org/html/2605.29042#bib.bib25)\)and partially observable stochastic games\(Hansenet al\.,[2004](https://arxiv.org/html/2605.29042#bib.bib10)\)\. We formalize each game as a tuple⟨𝒩,𝒵,𝒮,\{𝒪i\},𝒜,T,\{ri\},Ω,γ⟩,\\langle\\mathcal\{N\},\\,\\mathcal\{Z\},\\,\\mathcal\{S\},\\,\\\{\\mathcal\{O\}^\{i\}\\\},\\,\\mathcal\{A\},\\,T,\\,\\\{r^\{i\}\\\},\\,\\Omega,\\,\\gamma\\rangle,where𝒩=\{1,…,n\}\\mathcal\{N\}=\\\{1,\\ldots,n\\\}is the set of agents;𝒵=\{0,…,\|𝒵\|−1\}\\mathcal\{Z\}=\\\{0,\\ldots,\|\\mathcal\{Z\}\|\-1\\\}is a finite set of*hidden role hypotheses*\(e\.g\. agent identities or communication slots\);𝒮\\mathcal\{S\}is the shared world state;𝒪i\\mathcal\{O\}^\{i\}is agentii’s private observation space;𝒜\\mathcal\{A\}is the joint action space;T:𝒮×𝒜→Δ​\(𝒮\)T:\\mathcal\{S\}\\times\\mathcal\{A\}\\to\\Delta\(\\mathcal\{S\}\)is the transition kernel;ri:𝒮×𝒜→ℝr^\{i\}:\\mathcal\{S\}\\times\\mathcal\{A\}\\to\\mathbb\{R\}is agentii’s reward;Ω:𝒮→∏iΔ​\(𝒪i\)\\Omega:\\mathcal\{S\}\\to\\prod\_\{i\}\\Delta\(\\mathcal\{O\}^\{i\}\)is the observation function; andγ∈\(0,1\)\\gamma\\in\(0,1\)is the discount factor\. At the start of each episode, a latent rolez∈𝒵z\\in\\mathcal\{Z\}is sampled and held fixed; agents hold knowledge of their assigned role\. All agents share a role\-conditioned policy networkπθ​\(a∣o,z\)\\pi\_\{\\theta\}\(a\\mid o,z\), which outputs action probabilities given a local observation and a role hypothesis\. To clarify the interaction dynamics within our framework, we distinguish between two primary entities:

- •Agent: We refer to the entity that shapes and optimizes the belief\-based meta\-gradient as the agent\.
- •Observers: All other participants in the environment whose internal beliefs are the target of the shaping process are referred to as observers\.

In any given environment, an observer maintains a belief distribution over the set of possible role assignmentsz∈𝒵z\\in\\mathcal\{Z\}\. While the specific composition and size of𝒵\\mathcal\{Z\}vary according to the rules of the environment, we treat𝒵\\mathcal\{Z\}as a generic discrete set for our mathematical formulation\.

### 3\.1Learning with Opponent\-Learning Awareness \(LOLA\)

LOLA\(Foersteret al\.,[2018](https://arxiv.org/html/2605.29042#bib.bib8)\)studies games in a two\-player setting, where an agent \(agent 1\) accounts for how its own policy parametersθ1\\theta\_\{1\}influence the anticipated update of the observer \(agent 2\), as shown in Eq\. \([2](https://arxiv.org/html/2605.29042#S3.E2)\):

Δ​θ1=∇θ1V1​\(θ1,θ2\+Δ​θ2\)\\Delta\\theta\_\{1\}=\\nabla\_\{\\theta\_\{1\}\}V\_\{1\}\(\\theta\_\{1\},\\theta\_\{2\}\+\\Delta\\theta\_\{2\}\)\(2\)In Equation \([2](https://arxiv.org/html/2605.29042#S3.E2)\),V1V\_\{1\}is the value function of the agent andΔ​θ2\\Delta\\theta\_\{2\}is the observer’s learning step\. LOLA optimizes through this parameter update, which typically requires second\-order derivatives and knowledge of the observer’s learning dynamics\.

### 3\.2BBM and Second\-Order Belief Updates

BBM\(Aitchisonet al\.,[2021](https://arxiv.org/html/2605.29042#bib.bib3)\)adopts a second\-order Theory of Mind \(ToM\) framework where the agent estimates an observer’s posterior over the agent’s hidden role\. Because the agent cannot directly access an observerjj’s private view of the agentii, it must estimate what the observer thinks the agent can see\. This second\-order observation estimate is denoted aso^i,j,i\\hat\{o\}\_\{i,j,i\}\. The agent’s approximation of the observer’s belief update is defined in Equation \([3](https://arxiv.org/html/2605.29042#S3.E3)\)\.

b^t\+1\(j\),z=πθ​\(ati∣o^i,j,i,z\)​b^t\(j\),z∑z′∈Zπθ​\(ati∣o^i,j,i,z′\)​b^t\(j\),z′\\hat\{b\}\_\{t\+1\}^\{\(j\),z\}=\\frac\{\\pi\_\{\\theta\}\(a\_\{t\}^\{i\}\\mid\\hat\{o\}\_\{i,j,i\},z\)\\hat\{b\}\_\{t\}^\{\(j\),z\}\}\{\\sum\_\{z^\{\\prime\}\\in Z\}\\pi\_\{\\theta\}\(a\_\{t\}^\{i\}\\mid\\hat\{o\}\_\{i,j,i\},z^\{\\prime\}\)\\hat\{b\}\_\{t\}^\{\(j\),z^\{\\prime\}\}\}\(3\)In Equation \([3](https://arxiv.org/html/2605.29042#S3.E3)\),b^t\+1\(j\),z\\hat\{b\}\_\{t\+1\}^\{\(j\),z\}is the agent’s estimate of the probability that observerjjassigns to agentii’s role beingzz, andπθ​\(at∣o^i,j,i,z\)\\pi\_\{\\theta\}\(a\_\{t\}\\mid\\hat\{o\}\_\{i,j,i\},z\)is the role\-conditioned action likelihood for rolezz\.

### 3\.3Observation Proxies

The implementation ofo^i,j,i\\hat\{o\}\_\{i,j,i\}in Equation \([3](https://arxiv.org/html/2605.29042#S3.E3)\) requires a proxy for the observer’s perspective\. We utilize two distinct modes depending on the social complexity of the environment:

- •Canonical Mode: In environments where observers share a fundamentally similar perspective, the agent uses its own observation as a robust heuristic stand\-in\. This reduces approximation error from additional learned modules and serves as our primary baseline\.
- •Estimated Mode: In mixed\-motive settings, an agent must simultaneously deceive adversaries and coordinate with allies, requiring distinct belief trajectories for each observer\. To achieve true multi\-observer shaping, we deploy a learned backward\-prediction module to explicitly infero^i,j,i\\hat\{o\}\_\{i,j,i\}\(what observerjjbelieves agentiican see\)\.

Because the Estimated Mode is uniquely suited for navigating conflicting observer perspectives, we focus its evaluation on our mixed\-motive testbed, Avalon, while relying on the Canonical proxy alongside public state information for the other environments\.

## 4Method

### 4\.1Differentiable Belief Shaping of Opponents

The Bayesian belief update \(Eq\.[3](https://arxiv.org/html/2605.29042#S3.E3)\) involves a ratio: a likelihood multiplied by a prior, divided by a normalizing constant\. This is functionally equivalent to the softmax operation applied in log\-space\. To make the dependence onθ\\thetaexplicit and differentiable, we first define a log\-likelihood vectorℓt∈ℝ\|𝒵\|\\boldsymbol\{\\ell\}\_\{t\}\\in\\mathbb\{R\}^\{\|\\mathcal\{Z\}\|\}, where each elementℓtz=log⁡πθ​\(at∣ot,z\)\\ell\_\{t\}^\{z\}=\\log\\pi\_\{\\theta\}\(a\_\{t\}\\mid o\_\{t\},z\)\. We then rewrite the belief update as expressed in Equation \([4](https://arxiv.org/html/2605.29042#S4.E4)\)\.

𝐛t\+1=softmax​\(ℓt\+log⁡𝐛t\)\\mathbf\{b\}\_\{t\+1\}=\\text\{softmax\}\\\!\\left\(\\boldsymbol\{\\ell\}\_\{t\}\+\\log\\mathbf\{b\}\_\{t\}\\right\)\(4\)In Equation \([4](https://arxiv.org/html/2605.29042#S4.E4)\), the softmax operates over the latent role dimension\|𝒵\|\|\\mathcal\{Z\}\|, ensuring the belief vector remains a valid probability distribution\. The Jacobian of this softmax operation provides a clean gradient flow through each update step, as defined as∂bt\+1z′∂ℓtz=bt\+1z′​\(𝟙​\[z′=z\]−bt\+1z\)\\frac\{\\partial b^\{z^\{\\prime\}\}\_\{t\+1\}\}\{\\partial\\ell\_\{t\}^\{z\}\}=b^\{z^\{\\prime\}\}\_\{t\+1\}\\\!\\left\(\\mathds\{1\}\[z^\{\\prime\}=z\]\-b^\{z\}\_\{t\+1\}\\right\)\. Here𝟙\\mathds\{1\}is a function evaluating to11when the target rolez′z^\{\\prime\}matches the hypothesis rolezz, and0otherwise\.

Given this differentiable update rule, we train a*BeliefCritic*, which acts as a learned value function of the agent’s local state and the joint estimated belief state of allmmobservers in the environment\. We define the multi\-observer belief matrix as𝐁^t∈\(Δ\|𝒵\|\)m\\hat\{\\mathbf\{B\}\}\_\{t\}\\in\(\\Delta^\{\|\\mathcal\{Z\}\|\}\)^\{m\}, where each row corresponds to a specific observer’s tracked posterior over the agent’s role\. This function is defined in Equation \([5](https://arxiv.org/html/2605.29042#S4.E5)\)\.

Vϕ:𝒪i×\(Δ\|𝒵\|\)m→ℝ,Vϕ​\(ot\(i\),𝐁^t\)≈𝔼​\[∑s≥tγs−t​rsext\|ot\(i\),𝐁^t,πθ\]V\_\{\\phi\}:\\mathcal\{O\}^\{i\}\\times\(\\Delta^\{\|\\mathcal\{Z\}\|\}\)^\{m\}\\to\\mathbb\{R\},\\qquad V\_\{\\phi\}\(o\_\{t\}^\{\(i\)\},\\hat\{\\mathbf\{B\}\}\_\{t\}\)\\approx\\mathbb\{E\}\\\!\\left\[\\,\\sum\_\{s\\geq t\}\\gamma^\{s\-t\}r^\{\\text\{ext\}\}\_\{s\}\\,\\Big\|\\,o\_\{t\}^\{\(i\)\},\\hat\{\\mathbf\{B\}\}\_\{t\},\\pi\_\{\\theta\}\\right\]\(5\)In Equation \([5](https://arxiv.org/html/2605.29042#S4.E5)\),VϕV\_\{\\phi\}takes the full observer belief matrix𝐁^t\\hat\{\\mathbf\{B\}\}\_\{t\}as a direct input, learning the task\-value of the environment’s overall belief configuration for the agent under the current reward structure\. By formalizing the domain over\(Δ\|𝒵\|\)m\(\\Delta^\{\|\\mathcal\{Z\}\|\}\)^\{m\}, the critic naturally scales to environments with multiple distinct observers \(such as the Estimated Mode\), while supporting scenarios where observers share identical proxy trajectories \(such as the Canonical Mode\) without altering the underlying architecture\.VϕV\_\{\\phi\}is trained alongsideπθ\\pi\_\{\\theta\}via standard temporal difference \(TD\) regression against bootstrapped returns\. We formalize thekk\-step D\-BOS loss asℒBOSk=−Vϕ​\(ot\+k\(i\),𝐁t\+k\)\\mathcal\{L\}\_\{\\text\{BOS\}\}^\{k\}=\-V\_\{\\phi\}\\\!\\left\(o\_\{t\+k\}^\{\(i\)\},\\,\\mathbf\{B\}\_\{t\+k\}\\right\)Here, the multi\-observer belief matrix𝐁^t\+k\\hat\{\\mathbf\{B\}\}\_\{t\+k\}is obtained by chainingkksoftmax\-Bayes updates for all modeled observers\. MinimizingℒBOSk\\mathcal\{L\}\_\{\\text\{BOS\}\}^\{k\}drives the policy parametersθ\\thetatoward actions whose inducedkk\-step joint belief trajectories land in high\-value regions\. The critic parametersϕ\\phiare held fixed when computing the D\-BOS gradient; the gradient flows exclusively through𝐁^t\+k\\hat\{\\mathbf\{B\}\}\_\{t\+k\}’s dependence onθ\\theta\.

Training AlgorithmAlgorithmically, D\-BOS is implemented as PPO with an additional belief\-shaping correction computed from the on\-policy rollout\. Algorithm[1](https://arxiv.org/html/2605.29042#alg1)gives the implementation\-independent training loop\. In practice, we instantiate the correction either by directly differentiating thekk\-step belief critic objective or by using an equivalent likelihood\-coefficient surrogate that detaches the endpoint coefficients for stability; Appendix[A\.5](https://arxiv.org/html/2605.29042#A1.SS5)gives the exact implementation details\.

Multiple observers and observation modes\.When several agents observe the shaper, D\-BOS can theoretically maintain a separate belief trajectory𝐛t:t\+kj\\mathbf\{b\}^\{j\}\_\{t:t\+k\}for each observerAjA\_\{j\}, aggregating the shaping loss across observers\. However, the capacity to uniquely shape multiple observers depends on the chosen observation proxy \(Section[3\.3](https://arxiv.org/html/2605.29042#S3.SS3)\)\. Under the*canonical mode*, the agent uses its own observationot\(i\)o^\{\(i\)\}\_\{t\}for all observers, effectively collapsing the update into a single, generalized hypothetical observer\. True multi\-observer shaping, where distinct belief trajectories are modeled, requires the*estimated mode*, which provides observer\-specific proxieso^i,j,i\\hat\{o\}\_\{i,j,i\}\.

#### 4\.1\.1Gradient Correction \(LOLA\-Style\)

Rather than addingℒBOSk\\mathcal\{L\}\_\{\\text\{BOS\}\}^\{k\}directly to the PPO surrogate loss, D\-BOS follows the LOLA paradigm and injects the shaping gradient as a fixed correction\. The total shaping gradient is computed*once*from the on\-policy rollout trajectoryπθ0\\pi\_\{\\theta\_\{0\}\}prior to any PPO minibatch updates, as shown in Equation \([6](https://arxiv.org/html/2605.29042#S4.E6)\):

gBOS=∇θλT−k\+1​∑tℒBOSk​\(t\)\|θ=θ0g\_\{\\text\{BOS\}\}=\\nabla\_\{\\theta\}\\frac\{\\lambda\}\{T\-k\+1\}\\sum\_\{t\}\\mathcal\{L\}\_\{\\text\{BOS\}\}^\{k\}\(t\)\\;\\Big\|\_\{\\theta=\\theta\_\{0\}\}\(6\)Hereλ\\lambdacontrols the scale of the shaping vector andθ0\\theta\_\{0\}denotes the rollout parameters\. During optimization, PPO performsMMtotal inner gradient steps \(whereM=epochs×minibatchesM=\\text\{epochs\}\\times\\text\{minibatches\}\)\. At each of these steps, the parameter update is applied as shown in Equation \([7](https://arxiv.org/html/2605.29042#S4.E7)\):

θ←θ−α​\(∇θℒPPO\+gBOSM\)\\theta\\leftarrow\\theta\-\\alpha\\\!\\left\(\\nabla\_\{\\theta\}\\mathcal\{L\}\_\{\\text\{PPO\}\}\+\\frac\{g\_\{\\text\{BOS\}\}\}\{M\}\\right\)\(7\)Our implementation also supports a likelihood\-coefficient form that computes the same endpoint value sensitivity with respect to role\-conditioned action likelihoods, detaches these coefficients, and optimizes a stable surrogate policy loss during PPO\. Both forms use the same softmax\-Bayes chain and the same endpoint criticVϕ​\(ot\+k,Bt\+k\)V\_\{\\phi\}\(o\_\{t\+k\},B\_\{t\+k\}\); they differ only in how the resulting correction is applied numerically\. Further details of our algorithm are provided in Appendix[A\.5](https://arxiv.org/html/2605.29042#A1.SS5)\.

#### 4\.1\.2Belief as a Sufficient Statistic for Opponent Policy

In hidden\-role games, we can represent a Bayesian\-rational opponent conditioning their actions on their posterior belief about the shaping agent’s role:

πopp∗​\(a∣ot\)=∑z∈Zbtz⋅πopp∗​\(a∣ot,z\)\\pi\_\{\\text\{opp\}\}^\{\*\}\(a\\mid o\_\{t\}\)=\\sum\_\{z\\in Z\}b\_\{t\}^\{z\}\\cdot\\pi\_\{\\text\{opp\}\}^\{\*\}\(a\\mid o\_\{t\},z\)\(8\)
###### Proposition 1\(Belief is a sufficient statistic\)\.

Let the opponent be Bayesian\-rational with policy taking the role\-mixture form \(Eq\.[8](https://arxiv.org/html/2605.29042#S4.E8)\), and assume the role\-conditioned responsesπopp∗\(⋅∣ot,z\)\\pi\_\{\\text\{opp\}\}^\{\*\}\(\\cdot\\mid o\_\{t\},z\)are independent of the shaper’s parametersθ1\\theta\_\{1\}\. Then the marginal action distributionπopp∗\(⋅∣ot\)\\pi\_\{\\text\{opp\}\}^\{\*\}\(\\cdot\\mid o\_\{t\}\)depends onθ1\\theta\_\{1\}only throughbtb\_\{t\}:

∂πopp∗​\(a∣ot\)∂θ1=∑z∈Z∂btz∂θ1⋅πopp∗​\(a∣ot,z\)\{\\frac\{\\partial\\pi\_\{\\text\{opp\}\}^\{\*\}\(a\\mid o\_\{t\}\)\}\{\\partial\\theta\_\{1\}\}=\\sum\_\{z\\in Z\}\\frac\{\\partial b\_\{t\}^\{z\}\}\{\\partial\\theta\_\{1\}\}\\cdot\\pi\_\{\\text\{opp\}\}^\{\*\}\(a\\mid o\_\{t\},z\)\}\(9\)The gradient of the opponent’s policy w\.r\.t\. the shaper’s parametersθ1\\theta\_\{1\}is fully determined by∂𝐛t/∂θ1\\partial\\mathbf\{b\}\_\{t\}/\\partial\\theta\_\{1\}, the D\-BOS gradient\.

A proof is provided in Appendix[A\.7](https://arxiv.org/html/2605.29042#A1.SS7)\.

#### 4\.1\.3A Meta\-Gradient View \(and Relation to LOLA\)

Opponent shaping methods can be seen as differentiating through an*opponent update map*\. To make this precise, we introduce an opponent internal stateηt\\eta\_\{t\}that parameterizes their behavior \(e\.g\., network weights, beliefs, or a sufficient statistic\)\.

###### Theorem 1\(Opponent shaping via differentiable opponent state\)\.

Let the opponent act according to a policyπopp\(⋅∣ot,ηt\)\\pi\_\{\\text\{opp\}\}\(\\cdot\\mid o\_\{t\},\\eta\_\{t\}\)and update an internal stateηt∈ℝd\\eta\_\{t\}\\in\\mathbb\{R\}^\{d\}via a differentiable map

ηt\+1=U​\(ηt,θ1,ξt\),\\eta\_\{t\+1\}=U\(\\eta\_\{t\},\\theta\_\{1\},\\xi\_\{t\}\),\(10\)whereθ1\\theta\_\{1\}are the shaper’s parameters andξt\\xi\_\{t\}collects variables observed by the opponent \(including the shaper’s action\)\. For any objectiveJ1​\(θ1,ηt\)J\_\{1\}\(\\theta\_\{1\},\\eta\_\{t\}\)differentiable in both arguments,

∇θ1J1​\(θ1,ηt\)=∂J1∂θ1\|ηt⏟direct term\+\(∇θ1ηt\)⊤​∇ηtJ1​\(θ1,ηt\)⏟shaping term\.\\nabla\_\{\\theta\_\{1\}\}J\_\{1\}\(\\theta\_\{1\},\\eta\_\{t\}\)=\\underbrace\{\\frac\{\\partial J\_\{1\}\}\{\\partial\\theta\_\{1\}\}\\bigg\|\_\{\\eta\_\{t\}\}\}\_\{\\text\{direct term\}\}\+\\underbrace\{\\left\(\\nabla\_\{\\theta\_\{1\}\}\\eta\_\{t\}\\right\)^\{\\top\}\\nabla\_\{\\eta\_\{t\}\}J\_\{1\}\(\\theta\_\{1\},\\eta\_\{t\}\)\}\_\{\\text\{shaping term\}\}\.\(11\)Moreover,∇θ1ηt\\nabla\_\{\\theta\_\{1\}\}\\eta\_\{t\}is obtained by differentiating through the recursion in Eq\.[10](https://arxiv.org/html/2605.29042#S4.E10)\.

A proof is provided in Appendix[A\.8](https://arxiv.org/html/2605.29042#A1.SS8)\.

###### Corollary 1\(D\-BOS as belief\-state shaping\)\.

Under a Bayesian\-rational observer model \(Eq\.[8](https://arxiv.org/html/2605.29042#S4.E8)\), we may takeηt=𝐛t\\eta\_\{t\}=\\mathbf\{b\}\_\{t\}andUUto be the Bayes/softmax update \(Eq\.[4](https://arxiv.org/html/2605.29042#S4.E4)\)\. Here, the shaping term in Eq\.[11](https://arxiv.org/html/2605.29042#S4.E11)depends on∇θ1𝐛t\\nabla\_\{\\theta\_\{1\}\}\\mathbf\{b\}\_\{t\}, which D\-BOS computes by backpropagating through thekk\-step belief chain\.

###### Corollary 2\(LOLA as parameter\-state shaping\)\.

LOLA is recovered as another instantiation of Theorem[1](https://arxiv.org/html/2605.29042#Thmtheorem1)by takingηt=θ2\\eta\_\{t\}=\\theta\_\{2\}\(opponent parameters\) and the update map

U​\(θ2,θ1,⋅\)=θ2\+α​∇θ2J2​\(θ1,θ2\)\.U\(\\theta\_\{2\},\\theta\_\{1\},\\cdot\)=\\theta\_\{2\}\+\\alpha\\,\\nabla\_\{\\theta\_\{2\}\}J\_\{2\}\(\\theta\_\{1\},\\theta\_\{2\}\)\.\(12\)Differentiating through thisUUintroduces the mixed Hessian∂2J2/∂θ1​∂θ2\\partial^\{2\}J\_\{2\}/\\partial\\theta\_\{1\}\\partial\\theta\_\{2\}that characterizes LOLA\.

This framing shows thatD\-BOS and LOLA share the same meta\-gradient structure, but D\-BOS chooses an opponent state \(belief\) with a known, low\-dimensional, closed\-form update map\.

#### 4\.1\.4Advantages of Belief\-Space Shaping

Dimensionality\.𝐛t∈Δ\|Z\|\\mathbf\{b\}\_\{t\}\\in\\Delta^\{\|Z\|\}has dimension\|Z\|−1\|Z\|\-1, which is typically far smaller than the parameter space of a deep opponent policy\. This compact state makes it tractable to maintain and shape separate belief trajectories for multiple observers at the same time\.

First\-order belief gradients\.The softmax\-Bayes formulation in Eq\.[4](https://arxiv.org/html/2605.29042#S4.E4)makes the observer belief update differentiable with respect to the shaper’s policy parameters through the likelihood of the shaper’s observed actions\. D\-BOS therefore obtains a first\-order shaping signal through the belief update itself, rather than differentiating through an opponent optimizer\.

Different assumptions\.D\-BOS models the state of the observer’s posterior rather than the opponent’s optimizer state\. The opponent need not literally execute Bayes’ rule; the belief is a differentiable surrogate maintained by the shaper to model and influence what the observer is likely to infer\.

## 5Theoretical Analysis: Gradient Error from ToM Approximation

The D\-BOS gradient is computed through the shaper’s model of what each observer believes\. This model may use a second\-order estimateo^i,j,i\\hat\{o\}\_\{i,j,i\}that differs from the observation proxyoj,io\_\{j,i\}used by the observer’s ideal Bayesian update\. We bound how this approximation error propagates through thekk\-step belief chain and into the shaping gradient\.

### 5\.1Per\-Step Belief Error

###### Definition 1\(Log\-likelihood error\)\.

For observerAjA\_\{j\}at steptt, define the per\-step log\-likelihood error as:

εt\(j\)=maxz∈Z\|logπθ\(at∣oj,i,z\)−logπθ\(at∣o^i,j,i,z\)\|\\varepsilon^\{\(j\)\}\_\{t\}=\\max\_\{z\\in Z\}\\left\|\\log\\pi\_\{\\theta\}\(a\_\{t\}\\mid o\_\{j,i\},z\)\-\\log\\pi\_\{\\theta\}\(a\_\{t\}\\mid\\hat\{o\}\_\{i,j,i\},z\)\\right\|\(13\)This measures the worst\-case discrepancy over roles between the log\-likelihoods computed with the observer’s true estimate versus the shaper’s second\-order estimate\.

###### Lemma 1\(Softmax Lipschitz property\)\.

For any two input vectorsx,y∈ℝ\|Z\|x,y\\in\\mathbb\{R\}^\{\|Z\|\}:

‖softmax​\(x\)−softmax​\(y\)‖1≤2​‖x−y‖∞\\left\\\|\\mathrm\{softmax\}\(x\)\-\\mathrm\{softmax\}\(y\)\\right\\\|\_\{1\}\\leq 2\\left\\\|x\-y\\right\\\|\_\{\\infty\}\(14\)

A proof is provided in Appendix[A\.9](https://arxiv.org/html/2605.29042#A1.SS9)\.

###### Proposition 2\(kk\-step belief error\)\.

Let𝐛t\+k\(j\)\\mathbf\{b\}\_\{t\+k\}^\{\(j\)\}be the observer’s true belief afterkksteps and𝐛^t\+k\(j\)\\hat\{\\mathbf\{b\}\}\_\{t\+k\}^\{\(j\)\}be the shaper’s approximation usingo^i,j,i\\hat\{o\}\_\{i,j,i\}at each step\. Assume the initial beliefs agree:𝐛^t\(j\)=𝐛t\(j\)\\hat\{\\mathbf\{b\}\}\_\{t\}^\{\(j\)\}=\\mathbf\{b\}\_\{t\}^\{\(j\)\}\. Then:

‖𝐛^t\+k\(j\)−𝐛t\+k\(j\)‖1≤2​∑s=0k−1εt\+s\(j\)\\left\\\|\\hat\{\\mathbf\{b\}\}\_\{t\+k\}^\{\(j\)\}\-\\mathbf\{b\}\_\{t\+k\}^\{\(j\)\}\\right\\\|\_\{1\}\\leq 2\\sum\_\{s=0\}^\{k\-1\}\\varepsilon\_\{t\+s\}^\{\(j\)\}\(15\)If the per\-step error is bounded uniformly byε\(j\)=maxt⁡εt\(j\)\\varepsilon^\{\(j\)\}=\\max\_\{t\}\\varepsilon\_\{t\}^\{\(j\)\}:

‖𝐛^t\+k\(j\)−𝐛t\+k\(j\)‖1≤2​k​ε\(j\)\\left\\\|\\hat\{\\mathbf\{b\}\}\_\{t\+k\}^\{\(j\)\}\-\\mathbf\{b\}\_\{t\+k\}^\{\(j\)\}\\right\\\|\_\{1\}\\leq 2k\\varepsilon^\{\(j\)\}\(16\)

A proof is provided in Appendix[A\.10](https://arxiv.org/html/2605.29042#A1.SS10)\.

### 5\.2Gradient Error Bound

###### Theorem 2\(Gradient error from ToM approximation\)\.

Assume: \(1\) the per\-step log\-likelihood error is bounded byε\(j\)\\varepsilon^\{\(j\)\}, \(2\) the policy gradient is Lipschitz in observations with constantLπL\_\{\\pi\}, \(3\) beliefs are bounded away from zero:bt\+s\(j\),z≥bmin\>0b^\{\(j\),z\}\_\{t\+s\}\\geq b\_\{\\min\}\>0andb^t\+s\(j\),z≥bmin\>0\\hat\{b\}^\{\(j\),z\}\_\{t\+s\}\\geq b\_\{\\min\}\>0for allz,sz,s, \(4\) the future\-state value functionVϕ​\(ot\+k\(i\),⋅\)V\_\{\\phi\}\(o^\{\(i\)\}\_\{t\+k\},\\cdot\)isLVL\_\{V\}\-Lipschitz in its belief argument, and \(5\) the gradient∇bVϕ​\(ot\+k\(i\),⋅\)\\nabla\_\{b\}V\_\{\\phi\}\(o^\{\(i\)\}\_\{t\+k\},\\cdot\)isLgL\_\{g\}\-Lipschitz in its belief argument \(in∥⋅∥1\\\|\\cdot\\\|\_\{1\}\)\. Then the gradient error over akk\-step window satisfies:

‖∇θLappr\.\(j\)−∇θLtrue\(j\)‖2≤C​\(𝒵\)⋅k⋅max⁡\(LV,Lg\)bmin2⋅\(k​ε\(j\)​Gπ\+Lπ⋅supt‖oj,i−o^i,j,i‖∞\),\\left\\\|\\nabla\_\{\\theta\}L^\{\(j\)\}\_\{\\mathrm\{appr\.\}\}\-\\nabla\_\{\\theta\}L^\{\(j\)\}\_\{\\mathrm\{true\}\}\\right\\\|\_\{2\}\\leq\\frac\{C\(\\mathcal\{Z\}\)\\cdot k\\cdot\\max\(L\_\{V\},L\_\{g\}\)\}\{b\_\{\\min\}^\{2\}\}\\cdot\\left\(k\\varepsilon^\{\(j\)\}G\_\{\\pi\}\+L\_\{\\pi\}\\cdot\\sup\_\{t\}\\\|o\_\{j,i\}\-\\hat\{o\}\_\{i,j,i\}\\\|\_\{\\infty\}\\right\),\(17\)whereGπ=maxt,z∥∇θlogπθ\(at∣o^i,j,i,z\)∥2G\_\{\\pi\}=\\max\_\{t,z\}\\\|\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(a\_\{t\}\\mid\\hat\{o\}\_\{i,j,i\},z\)\\\|\_\{2\}is the maximum per\-role policy\-gradient norm andC​\(𝒵\)=\(22​\|𝒵\|−18\)C\(\\mathcal\{Z\}\)=\(22\|\\mathcal\{Z\}\|\-18\)

A complete proof is provided in Appendix[A\.11](https://arxiv.org/html/2605.29042#A1.SS11)\.

### 5\.3Implications

The bound highlights three practical tradeoffs:

Window sizekkvs\. ToM accuracy\.The gradient error grows with the length of the belief rollout\. Longer lookahead windows can expose useful multi\-step belief trajectories, but they also amplify errors in the shaper’s second\-order observation model\. This predicts the empirical need to tunekkrather than always choosing the longest available horizon\.

Number of observers\.Observers for which the shaper has poor ToM estimates \(largeε\(j\)\\varepsilon^\{\(j\)\}\) contribute disproportionately to the gradient error\. This suggests observer weighting as a natural extension, e\.g\., allocating more shaping weight to observers whose beliefs can be modeled reliably\.

Belief concentration\.The1/bmin21/b\_\{\\min\}^\{2\}factor means the gradient error is amplified when the observer’s belief is nearly certain about some role\. This is intuitive: when the observer is very confident, a small error in the estimated belief corresponds to a large error in the log\-belief gradient\. In practice, this suggests that the D\-BOS gradient is most reliable when the observer is still uncertain, before the belief state has saturated\.

Comparison to BBM\.BBM also uses a second\-order observer estimate, but only to construct a single\-step intrinsic reward\. D\-BOS trades this myopic reward for a differentiablekk\-step belief trajectory\. The benefit is temporal credit assignment over future beliefs; the cost is that approximation error can accumulate through the unrolled belief updates\. The bound makes this tradeoff explicit\.

## 6Experiments and Results

We evaluate D\-BOS across three environments of varying social complexity: Rescue\-the\-General, Avalon, and Multi\-Agent Coin Game\. Our experiments aim to answer three questions\. First, can differentiating through belief dynamics produce a nonzero shaping signal that is meaningfully coupled to future return? Second, does increasing the belief\-planning horizonkkimprove performance in controlled mixed\-motive settings? Third, how stable is the shaping signal in richer hidden\-role games with several observers and nonstationary co\-trained policies?

##### Baselines

1. 1\.PPO / no shaping: role\-conditioned PPO trained on extrinsic reward only\.
2. 2\.BBM\(Aitchisonet al\.,[2021](https://arxiv.org/html/2605.29042#bib.bib3)\): PPO with the per\-timestep Bayes\-factor intrinsic reward\.
3. 3\.D\-BOS \(ours\):kk\-step differentiable belief\-based opponent shaping with differentkk

We omit parameter\-space opponent\-shaping and meta\-learning baselines, such as LOLA, Advantage Alignment\(Duqueet al\.,[2025](https://arxiv.org/html/2605.29042#bib.bib6)\), and M\-FOS\(Luet al\.,[2022](https://arxiv.org/html/2605.29042#bib.bib14)\)due to computational intractability\. In our architecture, the D\-BOS correction cleanly updates the low\-dimensional role\-conditioned policy head, leaving the shared visual encoder unchanged\. Conversely, parameter\-space methods require differentiating through an opponent’s learning step over shared parameters, introducing prohibitive cross\-role mixed second derivatives\. Even first\-order or meta\-learning variants operate over high\-dimensional spaces, rendering them computationally infeasible in visually complex grid worlds and incompatible with the exact, head\-only decomposition provided by explicit belief\-space shaping\. For these reasons we stick to BBM and PPO as our baselines\.

##### Metrics

For each environment, we report the shaping agent’s score or win rate when available\. The specific role hypotheses𝒵\\mathcal\{Z\}vary by setting:

- •Avalon: A 5\-player social deduction game where spies \(team of 2\) use social actions to deceive resistance members \(team of 3\) and sabotage missions\.
- •Rescue\-the\-General \(RTG\): A 6\-agent visual grid world where a red team aims to eliminate a general before a blue team can successfully rescue them\.
- •Multi\-agent CoinGame: A spatial game where a shaper with a randomized role \(altruistic vs\. selfish\) competes against three observers to collect coins\.

We provide specific environment details in Appendix[A\.2](https://arxiv.org/html/2605.29042#A1.SS2)

### 6\.1Results

Tables[3](https://arxiv.org/html/2605.29042#S6.T3),[3](https://arxiv.org/html/2605.29042#S6.T3), and[3](https://arxiv.org/html/2605.29042#S6.T3)summarize the performance of D\-BOS against the PPO and BBM baselines across all three environments\. A consistent finding across environments is that BBM actively underperforms vanilla PPO in both Avalon \(win rate0\.2430\.243vs\.0\.3430\.343\) and RTG \(win rate0\.0470\.047vs\.0\.1010\.101\)\. This empirically validates a core motivation of D\-BOS: hardcoded, myopic deception objectives are fundamentally brittle\. An agent that greedily minimizes a Bayes factor at every timestep behaves with such artificial caution that observers easily detect it through second\-order reasoning\. D\-BOS avoids this pathology by letting the environment’s task reward organically dictate the direction and magnitude of belief shaping over a multi\-step horizon\.

Table 1:Rescue\-the\-General \(RTG\) Evaluation Win Rates for the Red agent\. We report the mean±\\pmstandard error at the end of co\-training
Table 2:Multi\-Agent Coin Game Returns for the red agent \(the shaper agent\)\. Higher coin return is better\. We report the mean±\\pmstandard error at the end of co\-training and evaluating against frozen policies
Table 3:Avalon Evaluation Win Rates\. We report the mean±\\pmstandard error at the end of co\-training and evaluating against frozen policies

##### Avalon: Social Deduction with Mixed\-Motive Shaping\.

Avalon is our primary testbed; its information asymmetry requires the agent to shape multiple competing observer beliefs using purely social actions\. As Table[3](https://arxiv.org/html/2605.29042#S6.T3)shows, canonical D\-BOS \(k≥3k\\geq 3\) strongly outperforms PPO and BBM, proving the necessity of multi\-step belief planning in social deduction\. Crucially, because Avalon is a mixed\-motive setting, relying on a shared Canonical proxy limits the agent’s ability to model distinct perspectives\. Using theEstimated Modeto actively model these conflicting viewpoints yields our strongest overall result\. By minimizing belief\-update error via observer\-specific proxies, the agent generates accurate shaping gradients that simultaneously deceive adversaries and coordinate with allies, thus performing well in a mixed\-motive setting\.

##### Rescue\-the\-General \(RTG\): High\-Dimensional Scaling\.

RTG introduces severe visual complexity, which inherently inflates the Theory of Mind approximation error \(ε\\varepsilon\)\. As Theorem[2](https://arxiv.org/html/2605.29042#Thmtheorem2)predicts, maintaining a stable gradient here mathematically requires shorter belief horizons\. Table[3](https://arxiv.org/html/2605.29042#S6.T3)confirms this dynamic: D\-BOS peaks atk=3k=3but collapses atk=5k=5as compounding errors overwhelm the shaping signal\. While visual deception natively suffers from high variance\(Aitchisonet al\.,[2021](https://arxiv.org/html/2605.29042#bib.bib3)\)and both PPO and BBM policies collapse during training, D\-BOS establishes a robust performance trend\. Full training curves in Appendix[A\.12](https://arxiv.org/html/2605.29042#A1.SS12)explicitly visualize the late\-stage bifurcation predicted by our belief\-saturation bounds\. This motivates more balanced hyper\-parameter tuning but D\-BOS shows potential even in highly complex games\.

##### CoinGame: Boundary Conditions\.

CoinGame tests a strict algorithmic limitation: latent roles resample ephemerally and signaling is purely spatial\. Here, D\-BOS achieves only modest gains over PPO\. This cleanly delineates the method’s scope: multi\-step belief shaping excels with persistent identities and rich communication, but provides limited advantage when roles constantly reset and belief channels carry sparse information\.

## 7Discussion and Limitations

BOS is best viewed as an explicit mechanism for belief\-space opponent shaping, not as a drop\-in reward bonus that automatically dominates PPO\. The experiments show that the mechanism is active: the belief critic can learn future belief\-state value, the softmax\-Bayes chain produces differentiable gradients, and these gradients are injected into the policy update\. They also show the main optimization challenge\. In complex hidden\-role games, the shaping signal can be small or noisy relative to the policy gradient\. Increasingλ\\lambdaor adaptively amplifying the gradient makes the effect visible, but can hurt performance if the critic or belief trajectory introduces error\.

Broader impacts and interpretability\.Beyond the specific hidden\-role games studied here, D\-BOS addresses a fundamental challenge in multi\-agent systems: how an agent should systematically influence the mental models others form about it\. This dynamic arises whenever agents with private information must coordinate or compete\. Practical examples include autonomous vehicles signaling intent to human drivers, assistive robots communicating capabilities to human teammates, and negotiation algorithms managing impressions in strategic interactions\. By grounding opponent shaping in an explicit, low\-dimensional belief simplex rather than opaque parameter perturbations, D\-BOS provides an auditable, realistic mechanism\. Further, practitioners can directly inspect what the agent is attempting to make observers believe by analyzing the critic’s value assignments over the belief space\. This transparency is a strict requirement for deploying influence\-aware agents in domains where accountability is necessary\.

Evaluation against co\-trained opponents\.Because D\-BOS shapes the beliefs of opponents that are simultaneously being trained, the resulting policies are adapted to each other\. The win rates reflect co\-trained evaluation, and transferability to unseen opponents remains an open question\. Evaluating D\-BOS against held\-out or independently trained opponents would provide a stronger test of whether the learned shaping strategies generalize beyond the co\-training distribution\.

Future directions\.Extending D\-BOS to continuous belief spaces \([A\.1](https://arxiv.org/html/2605.29042#A1.SS1)\), analyzing performance withnn\-order Theory of Mind, and developing adaptive observer\-weighting schemes \(as suggested by the per\-observer error bound in Theorem[2](https://arxiv.org/html/2605.29042#Thmtheorem2)\) are natural next steps\. We also notice that recursive modeling reducesε\\varepsilonbut introduces additional learned modules whose own approximation error must be controlled, motivating a joint search over the horizonkkand reasoning depthnn\.

## 8Conclusion

We introduced Belief\-based Opponent Shaping, an opponent\-shaping method that treats opponent belief states as the differentiable opponent state\. D\-BOS backpropagates throughkksteps of softmax\-Bayes belief dynamics, allowing the reward function rather than a hand\-coded deception objective to determine whether beliefs should move toward cooperation, concealment, or adversarial confusion\. Our theory connects the method to meta\-gradient opponent shaping and bounds the cost of approximate second\-order Theory of Mind\. Empirically, D\-BOS produces real shaping gradients and can improve controlled mixed\-motive behavior, while richer hidden\-role games reveal the sensitivity of belief\-space shaping to critic quality and gradient scale\. We see this as a first step toward opponent shaping methods that operate on the beliefs agents form about one another, rather than directly on policy parameters\.

## References

- \[1\]\(2024\)LOQA: learning with opponent q\-learning awareness\.InInternational Conference on Learning Representations, ICLR 2024,Cited by:[§1](https://arxiv.org/html/2605.29042#S1.p2.1),[§2](https://arxiv.org/html/2605.29042#S2.SS0.SSS0.Px1.p1.1)\.
- \[2\]M\. Aitchison, L\. Benke, and P\. Sweetser\(2021\)Learning to deceive in multi\-agent hidden role games\.InFirst International Workshop on Deceptive AI,Communications in Computer and Information Science\.Cited by:[§A\.13](https://arxiv.org/html/2605.29042#A1.SS13.SSS0.Px1.p1.4),[§1](https://arxiv.org/html/2605.29042#S1.p1.1),[§1](https://arxiv.org/html/2605.29042#S1.p2.1),[§2](https://arxiv.org/html/2605.29042#S2.SS0.SSS0.Px2.p1.10),[§3\.2](https://arxiv.org/html/2605.29042#S3.SS2.p1.3),[item 2](https://arxiv.org/html/2605.29042#S6.I1.i2.p1.1),[§6\.1](https://arxiv.org/html/2605.29042#S6.SS1.SSS0.Px2.p1.3)\.
- \[3\]N\. Alon, L\. Schulz, J\. S\. Rosenschein, and P\. Dayan\(2023\)A \(dis\-\)information theory of revealed and unrevealed preferences: emerging deception and skepticism via theory of mind\.Open Mind\.Cited by:[§2](https://arxiv.org/html/2605.29042#S2.SS0.SSS0.Px2.p2.1)\.
- \[4\]L\. Chen, R\. Paleja, M\. Ghuy, and M\. Gombolay\(2020\)Joint goal and strategy inference across heterogeneous demonstrators via reward network distillation\.InProceedings of the 2020 ACM/IEEE International Conference on Human\-Robot Interaction \(HRI\),Cited by:[§1](https://arxiv.org/html/2605.29042#S1.p1.1)\.
- \[5\]J\. A\. Duque, M\. Aghajohari, T\. Cooijmans, R\. Ciuca, T\. Zhang, G\. Gidel, and A\. Courville\(2025\)Advantage alignment algorithms\.InInternational Conference on Learning Representations \(ICLR\),Note:OralCited by:[§A\.1](https://arxiv.org/html/2605.29042#A1.SS1.p1.6),[§1](https://arxiv.org/html/2605.29042#S1.p2.1),[§2](https://arxiv.org/html/2605.29042#S2.SS0.SSS0.Px1.p1.1),[§6](https://arxiv.org/html/2605.29042#S6.SS0.SSS0.Px1.p2.1)\.
- \[6\]E\. Erdogan, F\. Dignum, R\. Verbrugge, and P\. Yolum\(2022\)Abstracting minds: computational theory of mind for human\-agent collaboration\.InHHAI2022: Augmenting Human Intellect,Cited by:[§1](https://arxiv.org/html/2605.29042#S1.p1.1)\.
- \[7\]J\. N\. Foerster, R\. Y\. Chen, M\. Al\-Shedivat, S\. Whiteson, P\. Abbeel, and I\. Mordatch\(2018\)Learning with opponent\-learning awareness\.InProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems \(AAMAS\),Cited by:[§1](https://arxiv.org/html/2605.29042#S1.p2.1),[§2](https://arxiv.org/html/2605.29042#S2.SS0.SSS0.Px1.p1.1),[§3\.1](https://arxiv.org/html/2605.29042#S3.SS1.p1.1)\.
- \[8\]Y\. Han and P\. J\. Gmytrasiewicz\(2019\)IPOMDP\-net: A deep neural network for partially observable multi\-agent planning using interactive pomdps\.InProceedings of the Thirty\-Third AAAI Conference on Artificial Intelligence and Thirty\-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence,Cited by:[§2](https://arxiv.org/html/2605.29042#S2.SS0.SSS0.Px3.p1.1)\.
- \[9\]E\. A\. Hansen, D\. S\. Bernstein, and S\. Zilberstein\(2004\)Dynamic programming for partially observable stochastic games\.InAAAI Workshop \- Technical Report,Cited by:[§3](https://arxiv.org/html/2605.29042#S3.p1.15)\.
- \[10\]M\. K\. Ho, M\. L\. Littman, J\. MacGlashan, F\. Cushman, and J\. L\. Austerweil\(2016\)Showing versus doing: teaching by demonstration\.InAnnual Conference on Neural Information Processing Systems 2016,Cited by:[§1](https://arxiv.org/html/2605.29042#S1.p1.1)\.
- \[11\]P\. Karkus, D\. Hsu, and W\. S\. Lee\(2017\)QMDP\-net: deep learning for planning under partial observability\.InAnnual Conference on Neural Information Processing Systems 2017,Cited by:[§2](https://arxiv.org/html/2605.29042#S2.SS0.SSS0.Px3.p1.1)\.
- \[12\]A\. Letcher, J\. N\. Foerster, D\. Balduzzi, T\. Rocktäschel, and S\. Whiteson\(2019\)Stable opponent shaping in differentiable games\.In7th International Conference on Learning Representations, ICLR 2019,Cited by:[§2](https://arxiv.org/html/2605.29042#S2.SS0.SSS0.Px1.p1.1)\.
- \[13\]C\. Lu, T\. Willi, C\. A\. S\. de Witt, and J\. N\. Foerster\(2022\)Model\-free opponent shaping\.InInternational Conference on Machine Learning, ICML 2022,Cited by:[§2](https://arxiv.org/html/2605.29042#S2.SS0.SSS0.Px1.p1.1),[§6](https://arxiv.org/html/2605.29042#S6.SS0.SSS0.Px1.p2.1)\.
- \[14\]I\. Oguntola\(2025\)Theory of mind in multi\-agent systems\.Ph\.D\. Thesis,Carnegie Mellon University\.Cited by:[§2](https://arxiv.org/html/2605.29042#S2.SS0.SSS0.Px2.p2.1)\.
- \[15\]R\. Paleja, M\. Ghuy, N\. R\. Arachchige, R\. Jensen, and M\. Gombolay\(2022\)The utility of explainable ai in ad hoc human\-machine teaming\.External Links:2209\.03943,[Link](https://arxiv.org/abs/2209.03943)Cited by:[§1](https://arxiv.org/html/2605.29042#S1.p1.1)\.
- \[16\]R\. Paleja, A\. Silva, L\. Chen, and M\. Gombolay\(2023\)Human\-robot teaming: grand challenges\.Current Robotics Reports\.Cited by:[§1](https://arxiv.org/html/2605.29042#S1.p1.1)\.
- \[17\]D\. Premack and G\. Woodruff\(1978\)Does the chimpanzee have a theory of mind?\.Behavioral and Brain Sciences\.Cited by:[§1](https://arxiv.org/html/2605.29042#S1.p1.1)\.
- \[18\]N\. C\. Rabinowitz, F\. Perbet, H\. F\. Song, C\. Zhang, S\. M\. A\. Eslami, and M\. Botvinick\(2018\)Machine theory of mind\.InProceedings of the 35th International Conference on Machine Learning, ICML 2018,Proceedings of Machine Learning Research\.Cited by:[§2](https://arxiv.org/html/2605.29042#S2.SS0.SSS0.Px2.p2.1)\.
- \[19\]R\. Raileanu, E\. Denton, A\. Szlam, and R\. Fergus\(2018\)Modeling others using oneself in multi\-agent reinforcement learning\.InProceedings of the 35th International Conference on Machine Learning, ICML 2018,Proceedings of Machine Learning Research\.Cited by:[§1](https://arxiv.org/html/2605.29042#S1.p1.1)\.
- \[20\]J\. Serrino, M\. Kleiman\-Weiner, D\. C\. Parkes, and J\. Tenenbaum\(2019\)Finding friend and foe in multi\-agent games\.InAdvances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8\-14, 2019, Vancouver, BC, Canada,Cited by:[§1](https://arxiv.org/html/2605.29042#S1.p1.1)\.
- \[21\]P\. Shafto, N\. D\. Goodman, and T\. L\. Griffiths\(2014\)A rational account of pedagogical reasoning: teaching by, and learning from, examples\.Cognitive Psychology\.Cited by:[§1](https://arxiv.org/html/2605.29042#S1.p1.1)\.
- \[22\]L\. S\. Shapley\(1953\)Stochastic games\.Proceedings of the National Academy of Sciences\.Cited by:[§3](https://arxiv.org/html/2605.29042#S3.p1.15)\.
- \[23\]T\. Willi, A\. Letcher, J\. Treutlein, and J\. N\. Foerster\(2022\)COLA: consistent learning with opponent\-learning awareness\.InInternational Conference on Machine Learning, ICML 2022,Cited by:[§1](https://arxiv.org/html/2605.29042#S1.p2.1),[§2](https://arxiv.org/html/2605.29042#S2.SS0.SSS0.Px1.p1.1)\.
- \[24\]H\. Wimmer and J\. Perner\(1983\)Beliefs about beliefs: representation and constraining function of wrong beliefs in young children’s understanding of deception\.Cognition\(1\)\.Cited by:[§1](https://arxiv.org/html/2605.29042#S1.p1.1)\.
- \[25\]X\. Yu, J\. Jiang, W\. Zhang, H\. Jiang, and Z\. Lu\(2022\)Model\-based opponent modeling\.InAnnual Conference on Neural Information Processing Systems 2022, NeurIPS 2022,Cited by:[§2](https://arxiv.org/html/2605.29042#S2.SS0.SSS0.Px2.p2.1)\.
- \[26\]S\. Zhao, C\. Lu, R\. B\. Grosse, and J\. N\. Foerster\(2022\)Proximal learning with opponent\-learning awareness\.InNeural Information Processing Systems 2022,Cited by:[§1](https://arxiv.org/html/2605.29042#S1.p2.1),[§2](https://arxiv.org/html/2605.29042#S2.SS0.SSS0.Px1.p1.1)\.

## Appendix ATechnical appendices and supplementary material

### A\.1Continuous Role Spaces

A natural question is whether our method only applies to discrete role spaces\. While we focus on a discrete role setZZ, the opponent\-state view in Theorem[1](https://arxiv.org/html/2605.29042#Thmtheorem1)suggests a generalization to*continuous*latent rolesz∈𝒵⊂ℝmz\\in\\mathcal\{Z\}\\subset\\mathbb\{R\}^\{m\}\. In that setting, the observer maintains a belief densitybt​\(z\)b\_\{t\}\(z\)and performs a Bayes update:

bt\+1​\(z\)∝πθ​\(at∣ot,z\)​bt​\(z\),b\_\{t\+1\}\(z\)\\propto\\pi\_\{\\theta\}\(a\_\{t\}\\mid o\_\{t\},z\)\\,b\_\{t\}\(z\),\(18\)This remains a differentiable opponent update map\. Practically, computing the normalizer requires integration over𝒵\\mathcal\{Z\}, so one would representbtb\_\{t\}with an approximate family \(e\.g\., particles, Gaussian/mixture variational beliefs, or a normalizing\-flow posterior\) and differentiate through the resulting approximate filter\. This would preserve the key benefit of belief\-space shaping, i\.e\., differentiating through a known state update map, while trading exactness for approximate inference in continuous spaces\. This direction is complementary to first\-order LOLA approximations such as Advantage Alignment\[[5](https://arxiv.org/html/2605.29042#bib.bib6)\], which remove Hessians in*parameter*\-space shaping; here, the goal is to shift the shaped opponent state from parametersθ2\\theta\_\{2\}to an explicit latent belief representation\.

### A\.2Environment Details

For fair comparison across methods, we use the same architectural backbone within each environment\. For Rescue\-the\-General, we use the default CNN policy path, whereas for Avalon and CoinGame, we use an MLP policy path\. The rollout length and total training budget vary by environment\.

##### Rescue\-the\-General \(RTG\)\.

RTG is a partially observable grid\-world hidden\-role game with six agents: one red agent, one green agent, and four blue agents\. The main evaluation scenario uses a32×3232\\times 32map with local RGB observations\. With the default view radius used in the paper runs, each agent receives a3×45×453\\times 45\\times 45uint8 egocentric crop containing terrain, visible agents, projectiles, bodies, vote information, and task objects\. Roles are not globally revealed; visibility depends on the scenario’s role\-visibility setting and local observation\.

The discrete action set has ten actions:

\{noop,up,down,left,right,act,shoot\-up,shoot\-down,shoot\-left,shoot\-right\}\.\\\{\\textsc\{noop\},\\textsc\{up\},\\textsc\{down\},\\textsc\{left\},\\textsc\{right\},\\textsc\{act\},\\textsc\{shoot\-up\},\\textsc\{shoot\-down\},\\textsc\{shoot\-left\},\\textsc\{shoot\-right\}\\\}\.\(19\)Movement changes the agent’s grid location subject to walls and map constraints\. Shooting actions damage the first target in the selected direction subject to range and cooldown\. Theactaction is context dependent: it can interact with the general or map objects, and it can initiate a vote when the agent is near a dead body or vote button\. During a vote, actions are interpreted as vote choices rather than movement/shooting commands\.

The red team’s objective is to find and kill or prevent rescue of the general; the blue team attempts to rescue the general; the green agent is an additional role\-conditioned participant in the RTG benchmark dynamics\. Terminal outcomes are logged with RTG\-compatible strings:general\_killedcorresponds to a red win andgeneral\_rescued/blue\_wincorresponds to a blue win\. We train RTG with the CNN policy path, role\-conditioned policy/value heads, and a deception/backward\-prediction module when estimated\-observation ablations are enabled\. The main RTG runs use 64 parallel environments, rollout length 16, and one million environment interactions per logged epoch\.

##### Avalon5\.

Avalon5 is a five\-player Resistance/Avalon\-style social deduction environment\. It has two spies and three resistance players\. The game alternates through three phases:propose,vote, andquest\. In the proposal phase, the current leader selects a mission team\. In the voting phase, all five players simultaneously approve or reject the proposal\. A strict majority approves the team; five consecutive rejected proposals give the spies a win\. In the quest phase, mission\-team members choose success/fail actions; spies may sabotage by choosing fail, while resistance players are forced to contribute success\. The first side to win three missions wins the game\.

The observation is a compact public\-history vector with shape\(128,1,1\)\(128,1,1\)\. It contains played mission history, proposed team masks, vote records, mission outcomes, sabotage counts, the current round, phase, leader identity, whether the observing player is leader or on the proposed team, consecutive rejection count, current spy/resistance mission scores, current mission size, and private bits\. Private bits include whether the observing player is a spy and whether the observing player is currently on mission\. In the non\-blind variant, spies additionally observe a partner\-spy bitmask; inavalon5\_blind, this partner\-spy bit is removed\. Thus all agents know their own role, but resistance players do not observe spy identities and blind spies do not observe the other spy\.

The action space has size ten\. In the proposal phase, the leader’s action indexes one of the valid mission\-team combinations of the required size; non\-leader actions are ignored\. In the voting phase, actions are thresholded into approve/reject votes\. In the quest phase, selected spies can play success or fail, while selected resistance actions are interpreted as success\. Rewards are team based: each mission gives\+1\+1to the winning side and−1\-1to the losing side, and the terminal game bonus is±10\\pm 10\. For D\-BOS, role 0 is the primary shaper spy, role 1 is the second spy, and roles 2–4 are resistance players\. Avalon5 uses the MLP policy path with role\-conditioned policy/value heads; adapter runs add a shaper\-specific adapter and role\-0 policy correction so the D\-BOS gradient is restricted to the shaper role path\.

##### Multi\-agent CoinGame\.

The multi\-agent CoinGame is a controlled mixed\-motive hidden\-role grid environment\. One fixed red shaper acts with a latent rolez∈\{0,1\}z\\in\\\{0,1\\\}, and there are three blue observers\. Each episode is a toroidal grid game with grid size 5 and horizon 30\. At reset, all agents and a single coin are placed uniformly at random, and the red role is sampled uniformly\.

Each agent observes a 10\-dimensional vector:

\[t/T,xa,ya,xr,yr,xb1,yb1,xc,yc,c\],\[t/T,\\;x\_\{a\},\\;y\_\{a\},\\;x\_\{r\},\\;y\_\{r\},\\;x\_\{b\_\{1\}\},\\;y\_\{b\_\{1\}\},\\;x\_\{c\},\\;y\_\{c\},\\;c\],\(20\)where\(xa,ya\)\(x\_\{a\},y\_\{a\}\)is the observing agent position,\(xr,yr\)\(x\_\{r\},y\_\{r\}\)is red’s position,\(xb1,yb1\)\(x\_\{b\_\{1\}\},y\_\{b\_\{1\}\}\)is the first blue observer position,\(xc,yc\)\(x\_\{c\},y\_\{c\}\)is the coin position, andccencodes the coin color together with the number of blue observers\. Coordinates are normalized before conversion to uint8\. The action space has four movement actions: up, down, left, and right, with wrap\-around at grid boundaries\.

Collecting any coin gives the collector\+1\+1\. If red collects a blue coin, the blue observers receive a total penalty of−2\-2shared equally across blue agents\. If red’s latent role is altruistic, red also receives an additional−1\-1for collecting a blue coin\. If a blue observer collects a red coin, red receives−2\-2\. The red return is the primary plotted score and blue score is the sum over blue observers\. D\-BOS beliefs are over red’s latent role; because blue observers share the same reward structure but maintain separate belief rows, CoinGame is a lightweight testbed for whether a matrix belief critic can aggregate multiple observer beliefs\.

### A\.3Implementation Stabilization for the Belief Bound

The gradient bound in Theorem[2](https://arxiv.org/html/2605.29042#Thmtheorem2)assumes all belief coordinates stay abovebmin\>0b\_\{\\min\}\>0\. This is not only a technical assumption: hidden\-role likelihoods can become extremely sharp, pushing posterior beliefs to the simplex boundary\. Near the boundary,log⁡bz\\log b^\{z\}has derivative1/bz1/b^\{z\}, so converting belief error to log\-belief error introduces the1/bmin1/b\_\{\\min\}factors in Lemma[2](https://arxiv.org/html/2605.29042#Thmlemma2)\. If the implementation allowedbz→0b^\{z\}\\rightarrow 0, the theoretical constant would become vacuous, and the numerical gradient throughlog⁡bz\\log b^\{z\}could become unstable\.

In code, we handle this in three ways\. First, all Bayes updates are performed in log space, followed by a softmax, so the update remains differentiable and normalized:

bt\+1=softmax​\(ℓt\+log⁡bt\)\.b\_\{t\+1\}=\\mathrm\{softmax\}\(\\ell\_\{t\}\+\\log b\_\{t\}\)\.\(21\)Second, in the MLP environments, we use an optional belief floor\. After each update, the posterior is mixed with a uniform distribution in \([22](https://arxiv.org/html/2605.29042#A1.E22)\):

b~t\+1=\(1−αfloor\)​bt\+1\+αfloor​𝟏\|𝒵\|,\\tilde\{b\}\_\{t\+1\}=\(1\-\\alpha\_\{\\textrm\{floor\}\}\)b\_\{t\+1\}\+\\alpha\_\{\\textrm\{floor\}\}\\frac\{\\mathbf\{1\}\}\{\|\\mathcal\{Z\}\|\},\(22\)whereαfloor=belief floor\\alpha\_\{\\textrm\{floor\}\}=\\textrm\{belief floor\}\. This impliesb~t\+1z≥α/\|𝒵\|\\tilde\{b\}\_\{t\+1\}^\{z\}\\geq\\alpha/\|\\mathcal\{Z\}\|, so in the theorem one may takebmin=α/\|𝒵\|b\_\{\\min\}=\\alpha/\|\\mathcal\{Z\}\|for runs using this floor\. We also use likelihood temperature defined in \([23](https://arxiv.org/html/2605.29042#A1.E23)\) withτ\>1\\tau\>1in some ablations, which prevents a single action likelihood from saturating the posterior too early\.

ℓt←ℓt/τ,\\ell\_\{t\}\\leftarrow\\ell\_\{t\}/\\tau,\(23\)
Third, we also added a coefficient implementation that gates or clips unstable updates\. Windows whose terminal beliefs are already too certain are assigned zero coefficient, since these are exactly the windows where the softmax\-Bayes Jacobian is least informative\. The coefficients can also be RMS\-normalized and clipped\. This does not change the formal belief\-error bound, but it prevents the applied policy correction from being dominated by rare high\-magnitude windows\. In RTG, the CNN path additionally clips the final shaping gradient to the same maximum norm scale used by PPO and optionally caps adaptive amplification relative to the PPO gradient norm\. Thus, thebminb\_\{\\min\}dependence is handled both analytically, by assuming beliefs remain inside the simplex interior, and operationally, by keeping beliefs away from zero and clipping the applied shaping correction\.

### A\.4Canonical and Estimated Observation Models

The Bayes likelihood in the paper is written asπθ​\(ai∣hi,j,i,z\)\\pi\_\{\\theta\}\(a\_\{i\}\\mid h\_\{i,j,i\},z\), wherehi,j,ih\_\{i,j,i\}is the shaper’s estimate of what observerjjbelieves the shaper observes\. In the canonical approximation, we sethi,j,ih\_\{i,j,i\}equal to the shaper’s own local observation\. This means all observers share the same role\-conditioned action likelihood at a given timestep, but maintain separate priorsbt\(j\)b\_\{t\}^\{\(j\)\}\. Thus, the canonical setting shapes a matrix of observer beliefs, while the evidence model is shared unless observers have distinct priors or visibility weights\.

In estimated\-observation ablations,hi,j,ih\_\{i,j,i\}is predicted rather than copied\. In RTG, this is the existing backwards observation\-prediction head in the deception model: during training, it is supervised with observer\-local observations, and D\-BOS uses the predicted observer observation in the differentiable Bayes likelihood\. In the MLP environments, the estimated\-observation ablation uses a small LSTM predictor trained from rollout targets\. Its inputs are the shaper observation trajectory together with observer role and observer slot embeddings; its target is the observer’s local observation\. The D\-BOS likelihood is given in Equation \([24](https://arxiv.org/html/2605.29042#A1.E24)\)

ℓtj,z=log⁡πθ​\(ati∣o^i,j,i,t,z\),\\ell\_\{t\}^\{j,z\}=\\log\\pi\_\{\\theta\}\(a\_\{t\}^\{i\}\\mid\\hat\{o\}\_\{i,j,i,t\},z\),\(24\)Here,o^i,j,i,t\\hat\{o\}\_\{i,j,i,t\}is the predicted observer\-conditioned observation\. We do not use the observer’s true private observation directly for final claims; using it directly would be a privileged\-information diagnostic rather than an inferred Theory\-of\-Mind model\.

### A\.5Likelihood\-Coefficient D\-BOS Correction

The direct autograd form of D\-BOS minimizes

ℒBOSk​\(θ\)=−Vϕ​\(ot\+k,Bt\+k\),\\mathcal\{L\}\_\{\\mathrm\{BOS\}\}^\{k\}\(\\theta\)=\-V\_\{\\phi\}\(o\_\{t\+k\},B\_\{t\+k\}\),\(25\)whereBt\+kB\_\{t\+k\}is the full observer\-by\-role belief matrix obtained by chainingkksoftmax\-Bayes updates\. Backpropagating this loss through the belief chain is conceptually simple, but in practice, it can create noisy gradients through repeated softmax Jacobians\. Our coefficient implementation computes the endpoint sensitivity in likelihood space and then applies it as a stable surrogate policy loss\.

For a window starting attt, letℓsj,z=log⁡πθ​\(asi∣o^i,j,i,s,z\)\\ell\_\{s\}^\{j,z\}=\\log\\pi\_\{\\theta\}\(a\_\{s\}^\{i\}\\mid\\hat\{o\}\_\{i,j,i,s\},z\)be the log\-likelihood of the shaper’s observed action under role hypothesiszzfor observerjj\. The belief chain is

Bs\+1=U​\(Bs,ℓs\),s=t,…,t\+k−1,B\_\{s\+1\}=U\(B\_\{s\},\\ell\_\{s\}\),\\qquad s=t,\\ldots,t\+k\-1,\(26\)whereUUapplies the softmax\-Bayes update row\-wise over observer beliefs\. We first compute

csj,z=∂\[−Vϕ​\(ot\+k,Bt\+k\)\]∂ℓsj,z\.c\_\{s\}^\{j,z\}=\\frac\{\\partial\[\-V\_\{\\phi\}\(o\_\{t\+k\},B\_\{t\+k\}\)\]\}\{\\partial\\ell\_\{s\}^\{j,z\}\}\.\(27\)These coefficients already contain the product of the endpoint value gradient, the intervening belief Jacobians, and the softmax\-Bayes Jacobian\. We then detachcsc\_\{s\}and optimize the surrogate

ℒ~BOS=1k​∑s=tt\+k−11\|𝒥\|​\|𝒵\|​∑j,zc¯sj,z​ℓsj,z,\\tilde\{\\mathcal\{L\}\}\_\{\\mathrm\{BOS\}\}=\\frac\{1\}\{k\}\\sum\_\{s=t\}^\{t\+k\-1\}\\frac\{1\}\{\|\\mathcal\{J\}\|\|\\mathcal\{Z\}\|\}\\sum\_\{j,z\}\\bar\{c\}\_\{s\}^\{j,z\}\\,\\ell\_\{s\}^\{j,z\},\(28\)wherec¯s\\bar\{c\}\_\{s\}denotes the optionally gated, normalized, and clipped coefficient tensor\. Detaching the coefficients makes the correction first\-order with respect to the policy parameters in the PPO update while preserving the direction computed by the differentiable belief planner at the rollout parameters\.

For hidden\-role shaping, adapter runs apply the D\-BOS correction only to the shaper’s role\-conditioned policy path rather than to opponent\-role policy rows\. In coefficient mode, this is implemented by zeroing all coefficient entries except the shaper\-role entryz=0z=0before normalization and clipping\. This prevents the shaping term from directly modifying observer\-role policies while keeping the base PPO training pipeline shared across methods\.

The coefficient implementation logs the mean absolute coefficient, RMS coefficient, entropy\-gate fraction, clipping fraction, approximate KL, pre/post clipping D\-BOS gradient norms, and final injected D\-BOS gradient norm\. These diagnostics are used to verify that the shaping term is present but not overwhelming the PPO gradient\.

### A\.6Algorithm outlined

Algorithm 1Differentiable Belief\-based Opponent Shaping \(D\-BOS\) with PPO1:Role\-conditioned policy

πθ​\(a∣o,z\)\\pi\_\{\\theta\}\(a\\mid o,z\); belief critic

VϕV\_\{\\phi\}; rollout length

TT; shaping horizon

kk; shaping weight

λ\\lambda; observers

𝒥\\mathcal\{J\}
2:Initialize per\-observer beliefs

\{𝐛^0j\}j∈𝒥\\\{\\hat\{\\mathbf\{b\}\}\_\{0\}^\{j\}\\\}\_\{j\\in\\mathcal\{J\}\}
3:for

t=0,…,T−1t=0,\\dots,T\-1do

4:Sample shaper action

at∼πθ\(⋅∣ot\(i\),zi\)a\_\{t\}\\sim\\pi\_\{\\theta\}\(\\cdot\\mid o\_\{t\}^\{\(i\)\},z\_\{i\}\)and step the environment

5:foreach observer

j∈𝒥j\\in\\mathcal\{J\}do

6:Choose observer proxy

o^i,j,i,t\\hat\{o\}\_\{i,j,i,t\}: estimated DeceptionModel proxy when available, otherwise canonical proxy

7:Compute role likelihoods

ℓtj,z←log⁡πθ​\(at∣o^i,j,i,t,z\)\\ell\_\{t\}^\{j,z\}\\leftarrow\\log\\pi\_\{\\theta\}\(a\_\{t\}\\mid\\hat\{o\}\_\{i,j,i,t\},z\)for all

z∈𝒵z\\in\\mathcal\{Z\}
8:Update belief

𝐛^t\+1j←softmax​\(ℓtj\+log⁡𝐛^tj\)\\hat\{\\mathbf\{b\}\}\_\{t\+1\}^\{j\}\\leftarrow\\mathrm\{softmax\}\(\\ell\_\{t\}^\{j\}\+\\log\\hat\{\\mathbf\{b\}\}\_\{t\}^\{j\}\)
9:endfor

10:Store

\(ot,at,rt,zi,log⁡πθ​\(at∣ot\(i\),zi\),\{𝐛^tj\}j∈𝒥\)\(o\_\{t\},a\_\{t\},r\_\{t\},z\_\{i\},\\log\\pi\_\{\\theta\}\(a\_\{t\}\\mid o\_\{t\}^\{\(i\)\},z\_\{i\}\),\\\{\\hat\{\\mathbf\{b\}\}\_\{t\}^\{j\}\\\}\_\{j\\in\\mathcal\{J\}\}\)in the rollout buffer

11:endfor

12:Compute bootstrapped extrinsic returns

\{Rt\}t=0T−1\\\{R\_\{t\}\\\}\_\{t=0\}^\{T\-1\}
13:Train

VϕV\_\{\\phi\}by MSE regression on future endpoints:

14:

Vϕ​\(ot\+k\(i\),𝐁^t\+k\)≈Rt\+k,t=0,…,T−k−1\\displaystyle V\_\{\\phi\}\(o\_\{t\+k\}^\{\(i\)\},\\hat\{\\mathbf\{B\}\}\_\{t\+k\}\)\\approx R\_\{t\+k\},\\quad t=0,\\dots,T\-k\-1
15:Freeze

ϕ\\phiand compute a rollout\-level belief correction

gBOSg\_\{\\mathrm\{BOS\}\}from

\{−Vϕ​\(ot\+k\(i\),𝐁^t\+k\)\}t=0T−k−1\\\{\-V\_\{\\phi\}\(o\_\{t\+k\}^\{\(i\)\},\\hat\{\\mathbf\{B\}\}\_\{t\+k\}\)\\\}\_\{t=0\}^\{T\-k\-1\}
16:Clip, gate, or adaptively scale

gBOSg\_\{\\mathrm\{BOS\}\}using rollout diagnostics

17:foreach PPO minibatchdo

18:Compute PPO gradient

gPPO←∇θℒPPOg\_\{\\mathrm\{PPO\}\}\\leftarrow\\nabla\_\{\\theta\}\\mathcal\{L\}\_\{\\mathrm\{PPO\}\}
19:Apply the PPO update with the D\-BOS correction to the shaper policy path:

20:

θ←θ−α​\(gPPO\+Apply​\(gBOS\)\)\\theta\\leftarrow\\theta\-\\alpha\\\!\\left\(g\_\{\\mathrm\{PPO\}\}\+\\mathrm\{Apply\}\(g\_\{\\mathrm\{BOS\}\}\)\\right\)
21:endfor

##### Construction ofot\+ko\_\{t\+k\}andBt\+kB\_\{t\+k\}\.

The implementation loops over valid rollout windowst=0,…,T−k−1t=0,\\ldots,T\-k\-1\. For each environment and each observerjj, it initializes the observer belief from the rollout buffer,

Bt=\{𝐛tj\}j∈𝒥,B\_\{t\}=\\\{\\mathbf\{b\}\_\{t\}^\{j\}\\\}\_\{j\\in\\mathcal\{J\}\},\(29\)wherebuf\.per\_obs\_beliefs\[t\]stores one role posterior per observer\. It then applies exactlykkrow\-wise softmax\-Bayes updates using the shaper action likelihoods at rollout timest,…,t\+k−1t,\\ldots,t\+k\-1:

𝐛s\+1j=Reg​\[softmax​\(ℓsj\+log⁡𝐛sj\)\],s=t,…,t\+k−1,\\mathbf\{b\}\_\{s\+1\}^\{j\}=\\mathrm\{Reg\}\\\!\\left\[\\mathrm\{softmax\}\\\!\\left\(\\ell\_\{s\}^\{j\}\+\\log\\mathbf\{b\}\_\{s\}^\{j\}\\right\)\\right\],\\qquad s=t,\\ldots,t\+k\-1,\(30\)whereℓsj=\(ℓsj,z\)z∈𝒵\\ell\_\{s\}^\{j\}=\(\\ell\_\{s\}^\{j,z\}\)\_\{z\\in\\mathcal\{Z\}\}andReg\\mathrm\{Reg\}denotes the belief floor/regularization used to avoid simplex\-boundary saturation\. After the final update, the code flattens the matrixBt\+k∈ℝ\|𝒥\|×\|𝒵\|B\_\{t\+k\}\\in\\mathbb\{R\}^\{\|\\mathcal\{J\}\|\\times\|\\mathcal\{Z\}\|\}into a vector and evaluates the belief critic on the shaper’s future observation:

ot\+k=buf\.obs\[t\+k, shaper\_index\],Vϕ​\(ot\+k,vec​\(Bt\+k\)\)\.o\_\{t\+k\}=\\texttt\{buf\.obs\[t\+k, shaper\\\_index\]\},\\qquad V\_\{\\phi\}\(o\_\{t\+k\},\\mathrm\{vec\}\(B\_\{t\+k\}\)\)\.\(31\)The belief critic is trained on the same indexing convention: for role\-0/shaper samples, it regressesVϕ​\(ot\+k,Bt\+k\)V\_\{\\phi\}\(o\_\{t\+k\},B\_\{t\+k\}\)to the rollout return stored at timet\+kt\+k\. Thus the shaping query and critic target both use the same future pair\(ot\+k,Bt\+k\)\(o\_\{t\+k\},B\_\{t\+k\}\)\.

### A\.7Proof of Proposition[1](https://arxiv.org/html/2605.29042#Thmproposition1): Belief is a sufficient statistic

###### Proof\.

Sinceπopp∗​\(a∣ot,z\)\\pi\_\{\\text\{opp\}\}^\{\*\}\(a\\mid o\_\{t\},z\)is independent ofθ1\\theta\_\{1\}by assumption, the only dependence onθ1\\theta\_\{1\}in Eq\.[8](https://arxiv.org/html/2605.29042#S4.E8)is throughbtzb\_\{t\}^\{z\}\. Therefore holdingbtb\_\{t\}fixed, the marginal distributionπopp∗​\(a∣ot\)\\pi\_\{\\text\{opp\}\}^\{\*\}\(a\\mid o\_\{t\}\)is fully determined and does not depend onθ1\\theta\_\{1\}, meaning thatbtb\_\{t\}is a sufficient statistic\. Differentiating Eq\.[8](https://arxiv.org/html/2605.29042#S4.E8)with respect toθ1\\theta\_\{1\}using the product rule:

∂πo​p​p∗​\(a\|ot\)∂θ1=∑z∂btz∂θ1⋅πo​p​p∗​\(a\|ot,z\)\+∑zbtz⋅∂πo​p​p∗​\(a\|ot,z\)∂θ1⏟=0​\(by assumption\)=∑z∂btz∂θ1⋅πopp∗​\(a∣ot,z\)\\frac\{\\partial\\pi^\{\*\}\_\{opp\}\(a\|o\_\{t\}\)\}\{\\partial\\theta\_\{1\}\}=\\sum\_\{z\}\\frac\{\\partial b\_\{t\}^\{z\}\}\{\\partial\\theta\_\{1\}\}\\cdot\\pi^\{\*\}\_\{opp\}\(a\|o\_\{t\},z\)\+\\sum\_\{z\}b\_\{t\}^\{z\}\\cdot\\underbrace\{\{\\frac\{\\partial\\pi^\{\*\}\_\{opp\}\(a\|o\_\{t\},z\)\}\{\\partial\\theta\_\{1\}\}\}\}\_\{=0\\text\{ \(by assumption\)\}\}=\\sum\_\{z\}\\frac\{\\partial b\_\{t\}^\{z\}\}\{\\partial\\theta\_\{1\}\}\\cdot\\pi\_\{\\text\{opp\}\}^\{\*\}\(a\\mid o\_\{t\},z\)The gradient flows entirely throughbtb\_\{t\}\. ∎

### A\.8Proof of Theorem[1](https://arxiv.org/html/2605.29042#Thmtheorem1): Opponent shaping via differentiable opponent state

###### Proof\.

SinceJ1J\_\{1\}is differentiable in both arguments andηt\\eta\_\{t\}depends onθ1\\theta\_\{1\}through the differentiable recursion in Eq\.[10](https://arxiv.org/html/2605.29042#S4.E10), the chain rule gives

∇θ1J1​\(θ1,ηt\)=∂J1∂θ1\|ηt\+\(∇θ1ηt\)⊤​∇ηtJ1​\(θ1,ηt\),\\nabla\_\{\\theta\_\{1\}\}J\_\{1\}\(\\theta\_\{1\},\\eta\_\{t\}\)=\\frac\{\\partial J\_\{1\}\}\{\\partial\\theta\_\{1\}\}\\bigg\|\_\{\\eta\_\{t\}\}\+\\left\(\\nabla\_\{\\theta\_\{1\}\}\\eta\_\{t\}\\right\)^\{\\top\}\\nabla\_\{\\eta\_\{t\}\}J\_\{1\}\(\\theta\_\{1\},\\eta\_\{t\}\),\(32\)which is Eq\.[11](https://arxiv.org/html/2605.29042#S4.E11)\.

To compute∇θ1ηt\\nabla\_\{\\theta\_\{1\}\}\\eta\_\{t\}, differentiate the state recursion \(Eq\.[10](https://arxiv.org/html/2605.29042#S4.E10)\):

∇θ1ηt\+1=∂U∂ηt​∇θ1ηt\+∂U∂θ1,\\nabla\_\{\\theta\_\{1\}\}\\eta\_\{t\+1\}=\\frac\{\\partial U\}\{\\partial\\eta\_\{t\}\}\\,\\nabla\_\{\\theta\_\{1\}\}\\eta\_\{t\}\+\\frac\{\\partial U\}\{\\partial\\theta\_\{1\}\},\(33\)where the partial derivatives are evaluated at\(ηt,θ1,ξt\)\(\\eta\_\{t\},\\theta\_\{1\},\\xi\_\{t\}\)\. We Initialize with∇θ1η0=0\\nabla\_\{\\theta\_\{1\}\}\\eta\_\{0\}=0since the initial stateη0\\eta\_\{0\}is independent ofθ1\\theta\_\{1\}\. Unrolling this recursion yields an explicit expression for∇θ1ηt\\nabla\_\{\\theta\_\{1\}\}\\eta\_\{t\}in terms of Jacobians ofUU:

∇θ1ηt\+1=∑i=0t\(∏j=i\+1t∂U∂ηj\)​∂U∂θ1\|t=i\\nabla\_\{\\theta\_\{1\}\}\\eta\_\{t\+1\}=\\sum\_\{i=0\}^\{t\}\\left\(\\prod\_\{j=i\+1\}^\{t\}\\frac\{\\partial U\}\{\\partial\\eta\_\{j\}\}\\right\)\\frac\{\\partial U\}\{\\partial\\theta\_\{1\}\}\\bigg\|\_\{t=i\}\(34\)∎

### A\.9Proof of Lemma[1](https://arxiv.org/html/2605.29042#Thmlemma1): Softmax Lipschitz property

###### Proof\.

Letf​\(x\)=softmax​\(x\)f\(x\)=\\mathrm\{softmax\}\(x\)\. For anyxxwriteb=f​\(x\)b=f\(x\)\. The Jacobian offfatxxhas entries

Jz′,z​\(x\)=bz′​\(𝟏​\[z′=z\]−bz\),J\_\{z^\{\\prime\},z\}\(x\)=b^\{z^\{\\prime\}\}\\,\(\\mathbf\{1\}\[z^\{\\prime\}=z\]\-b^\{z\}\),\(35\)or equivalentlyJ​\(x\)=diag​\(b\)−b​b⊤J\(x\)=\\mathrm\{diag\}\(b\)\-bb^\{\\top\}\.

Bounding‖J​\(x\)‖∞→1\\\|J\(x\)\\\|\_\{\\infty\\to 1\}\.For any vectorv∈ℝ\|𝒵\|v\\in\\mathbb\{R\}^\{\|\\mathcal\{Z\}\|\},

J​\(x\)​v=diag​\(b\)​v−b​\(b⊤​v\)=b⊙v−\(b⊤​v\)​b,J\(x\)\\,v=\\mathrm\{diag\}\(b\)\\,v\-b\\,\(b^\{\\top\}v\)=b\\odot v\-\(b^\{\\top\}v\)\\,b,\(36\)where⊙\\odotdenotes component\-wise multiplication\. Taking the 1\-norm and applying the triangle inequality,

‖J​\(x\)​v‖1≤‖b⊙v‖1\+\|b⊤​v\|⋅‖b‖1\.\\\|J\(x\)v\\\|\_\{1\}\\leq\\\|b\\odot v\\\|\_\{1\}\+\|b^\{\\top\}v\|\\cdot\\\|b\\\|\_\{1\}\.\(37\)Each term:‖b⊙v‖1=∑zbz​\|vz\|≤‖b‖1⋅‖v‖∞=‖v‖∞\\\|b\\odot v\\\|\_\{1\}=\\sum\_\{z\}b^\{z\}\|v^\{z\}\|\\leq\\\|b\\\|\_\{1\}\\cdot\\\|v\\\|\_\{\\infty\}=\\\|v\\\|\_\{\\infty\}\(since‖b‖1=1\\\|b\\\|\_\{1\}=1for a probability vector\) and\|b⊤​v\|≤‖b‖1​‖v‖∞=‖v‖∞\|b^\{\\top\}v\|\\leq\\\|b\\\|\_\{1\}\\\|v\\\|\_\{\\infty\}=\\\|v\\\|\_\{\\infty\}by Hölder\. Combining,

‖J​\(x\)​v‖1≤‖v‖∞\+‖v‖∞=2​‖v‖∞\.\\\|J\(x\)v\\\|\_\{1\}\\leq\\\|v\\\|\_\{\\infty\}\+\\\|v\\\|\_\{\\infty\}=2\\\|v\\\|\_\{\\infty\}\.\(38\)Hence‖J​\(x\)‖∞→1≤2\\\|J\(x\)\\\|\_\{\\infty\\to 1\}\\leq 2at everyxx\.

Definez​\(t\)=y\+t​\(x−y\)z\(t\)=y\+t\(x\-y\)\. By the fundamental theorem of calculus,

‖f​\(x\)−f​\(y\)‖1\\displaystyle\\\|f\(x\)\-f\(y\)\\\|\_\{1\}=‖∫01J​\(z​\(t\)\)​\(x−y\)​𝑑t‖1\\displaystyle=\\left\\\|\\int\_\{0\}^\{1\}J\(z\(t\)\)\(x\-y\)\\,dt\\right\\\|\_\{1\}≤∫01‖J​\(z​\(t\)\)​\(x−y\)‖1​𝑑t\(triangle inequality\)\\displaystyle\\leq\\int\_\{0\}^\{1\}\\\|J\(z\(t\)\)\(x\-y\)\\\|\_\{1\}\\,dt\\quad\\text\{\(triangle inequality\)\}\(39\)≤∫012​‖x−y‖∞​𝑑t\(operator norm bound\)\\displaystyle\\leq\\int\_\{0\}^\{1\}2\\\|x\-y\\\|\_\{\\infty\}\\,dt\\quad\\text\{\(operator norm bound\)\}\(40\)=2​‖x−y‖∞\.\\displaystyle=2\\\|x\-y\\\|\_\{\\infty\}\.\(41\)∎

### A\.10Proof of Proposition[2](https://arxiv.org/html/2605.29042#Thmproposition2):kk\-step belief error

###### Proof\.

Recall the per\-step log\-likelihood vector

ℓr:=log⁡πθ​\(ar∣or,⋅\)∈ℝ\|𝒵\|,\\ell\_\{r\}:=\\log\\pi\_\{\\theta\}\(a\_\{r\}\\mid o\_\{r\},\\cdot\)\\in\\mathbb\{R\}^\{\|\\mathcal\{Z\}\|\},\(42\)whosezz\-th entryℓrz=log⁡πθ​\(ar∣or,z\)\\ell\_\{r\}^\{z\}=\\log\\pi\_\{\\theta\}\(a\_\{r\}\\mid o\_\{r\},z\)is the log\-probability that rolezzwould have taken actionara\_\{r\}given observationoro\_\{r\}\. The approximate versionℓ^r:=log⁡πθ​\(ar∣o^r,⋅\)\\hat\{\\ell\}\_\{r\}:=\\log\\pi\_\{\\theta\}\(a\_\{r\}\\mid\\hat\{o\}\_\{r\},\\cdot\)uses RED’s second\-order observation estimateo^r\\hat\{o\}\_\{r\}in place of the observer’s true estimateoro\_\{r\}\.

Define the cumulative log\-likelihood vectors

Lt\+k:=log⁡bt\+∑i=0k−1ℓt\+i,L^t\+k:=log⁡bt\+∑i=0k−1ℓ^t\+i,L\_\{t\+k\}:=\\log b\_\{t\}\+\\sum\_\{i=0\}^\{k\-1\}\\ell\_\{t\+i\},\\qquad\\hat\{L\}\_\{t\+k\}:=\\log b\_\{t\}\+\\sum\_\{i=0\}^\{k\-1\}\\hat\{\\ell\}\_\{t\+i\},\(43\)where the starting log\-belieflog⁡bt\\log b\_\{t\}is shared \(sincebt=b^tb\_\{t\}=\\hat\{b\}\_\{t\}by assumption\)\. Applyingkksoftmax\-Bayes updates is equivalent to a single softmax of the cumulative logits:

bt\+k=softmax​\(Lt\+k\),b^t\+k=softmax​\(L^t\+k\)\.b\_\{t\+k\}=\\mathrm\{softmax\}\(L\_\{t\+k\}\),\\qquad\\hat\{b\}\_\{t\+k\}=\\mathrm\{softmax\}\(\\hat\{L\}\_\{t\+k\}\)\.\(44\)
Applying Lemma[1](https://arxiv.org/html/2605.29042#Thmlemma1),

‖b^t\+k−bt\+k‖1=‖softmax​\(L^t\+k\)−softmax​\(Lt\+k\)‖1≤2​‖L^t\+k−Lt\+k‖∞\.\\\|\\hat\{b\}\_\{t\+k\}\-b\_\{t\+k\}\\\|\_\{1\}=\\\|\\mathrm\{softmax\}\(\\hat\{L\}\_\{t\+k\}\)\-\\mathrm\{softmax\}\(L\_\{t\+k\}\)\\\|\_\{1\}\\leq 2\\\|\\hat\{L\}\_\{t\+k\}\-L\_\{t\+k\}\\\|\_\{\\infty\}\.\(45\)The cumulative difference is

L^t\+k−Lt\+k=∑i=0k−1\(ℓ^t\+i−ℓt\+i\),\\hat\{L\}\_\{t\+k\}\-L\_\{t\+k\}=\\sum\_\{i=0\}^\{k\-1\}\\big\(\\hat\{\\ell\}\_\{t\+i\}\-\\ell\_\{t\+i\}\\big\),\(46\)so by the triangle inequality and the per\-step error bound‖ℓ^t\+i−ℓt\+i‖∞≤εt\+i\\\|\\hat\{\\ell\}\_\{t\+i\}\-\\ell\_\{t\+i\}\\\|\_\{\\infty\}\\leq\\varepsilon\_\{t\+i\}by definition[1](https://arxiv.org/html/2605.29042#Thmdefinition1),

‖L^t\+k−Lt\+k‖∞≤∑i=0k−1‖ℓ^t\+i−ℓt\+i‖∞≤∑i=0k−1εt\+i\.\\\|\\hat\{L\}\_\{t\+k\}\-L\_\{t\+k\}\\\|\_\{\\infty\}\\leq\\sum\_\{i=0\}^\{k\-1\}\\\|\\hat\{\\ell\}\_\{t\+i\}\-\\ell\_\{t\+i\}\\\|\_\{\\infty\}\\leq\\sum\_\{i=0\}^\{k\-1\}\\varepsilon\_\{t\+i\}\.\(47\)Combining,

‖b^t\+k−bt\+k‖1≤2​∑i=0k−1εt\+i≤2​k​ε\\\|\\hat\{b\}\_\{t\+k\}\-b\_\{t\+k\}\\\|\_\{1\}\\leq 2\\sum\_\{i=0\}^\{k\-1\}\\varepsilon\_\{t\+i\}\\leq 2k\\varepsilon\(48\)under the uniform boundε=maxt⁡εt\\varepsilon=\\max\_\{t\}\\varepsilon\_\{t\}\. ∎

### A\.11Proof of Theorem[2](https://arxiv.org/html/2605.29042#Thmtheorem2): Gradient error from ToM approximation

We prove Theorem 2 in stages\. First we establish two auxiliary results: a log\-conversion lemma and a trajectory\-drift corollary\. We then bound the magnitude of each factor in the chain\-rule expansion of∇θL\(j\)\\nabla\_\{\\theta\}L^\{\(j\)\}\.

Throughout, we drop the observer index\(j\)\(j\)for compactness, fixing one observerjj\. The bound applies per\-observer, aggregation across observers is handled separately\. We use the norm conventions:∥⋅∥1\\\|\\cdot\\\|\_\{1\}on belief vectors,∥⋅∥∞\\\|\\cdot\\\|\_\{\\infty\}on log\-beliefs and log\-likelihood vectors,∥⋅∥2\\\|\\cdot\\\|\_\{2\}on parameter\-space vectors\.

###### Lemma 2\(Log conversion lemma\)\.

Letb,b^∈Δ\|𝒵\|b,\\hat\{b\}\\in\\Delta^\{\|\\mathcal\{Z\}\|\}satisfybz≥bminb^\{z\}\\geq b\_\{\\min\}andb^z≥bmin\\hat\{b\}^\{z\}\\geq b\_\{\\min\}for allz∈𝒵z\\in\\mathcal\{Z\}, wherebmin\>0b\_\{\\min\}\>0\. Then

‖log⁡b^−log⁡b‖∞≤1bmin​‖b^−b‖1\.\\\|\\log\\hat\{b\}\-\\log b\\\|\_\{\\infty\}\\leq\\frac\{1\}\{b\_\{\\min\}\}\\\|\\hat\{b\}\-b\\\|\_\{1\}\.\(49\)

###### Proof\.

Letz∗∈arg⁡maxz⁡\|log⁡b^z−log⁡bz\|z^\{\*\}\\in\\arg\\max\_\{z\}\|\\log\\hat\{b\}^\{z\}\-\\log b^\{z\}\|, so that

‖log⁡b^−log⁡b‖∞=\|log⁡b^z∗−log⁡bz∗\|\.\\\|\\log\\hat\{b\}\-\\log b\\\|\_\{\\infty\}=\|\\log\\hat\{b\}^\{z^\{\*\}\}\-\\log b^\{z^\{\*\}\}\|\.\(50\)Bothbz∗b^\{z^\{\*\}\}andb^z∗\\hat\{b\}^\{z^\{\*\}\}lie in\[bmin,1\]\[b\_\{\\min\},1\]\. By the Mean Value Theorem applied tof​\(x\)=log⁡xf\(x\)=\\log xon this interval, there existsc∈\[bmin,1\]c\\in\[b\_\{\\min\},1\]such that

log⁡b^z∗−log⁡bz∗=1c​\(b^z∗−bz∗\)\.\\log\\hat\{b\}^\{z^\{\*\}\}\-\\log b^\{z^\{\*\}\}=\\frac\{1\}\{c\}\\big\(\\hat\{b\}^\{z^\{\*\}\}\-b^\{z^\{\*\}\}\\big\)\.\(51\)Taking absolute values and usingc≥bminc\\geq b\_\{\\min\}:

\|log⁡b^z∗−log⁡bz∗\|=1c​\|b^z∗−bz∗\|≤1bmin​\|b^z∗−bz∗\|\.\|\\log\\hat\{b\}^\{z^\{\*\}\}\-\\log b^\{z^\{\*\}\}\|=\\frac\{1\}\{c\}\|\\hat\{b\}^\{z^\{\*\}\}\-b^\{z^\{\*\}\}\|\\leq\\frac\{1\}\{b\_\{\\min\}\}\|\\hat\{b\}^\{z^\{\*\}\}\-b^\{z^\{\*\}\}\|\.\(52\)Finally, the absolute difference at any single coordinate is bounded by the totalℓ1\\ell\_\{1\}difference:

\|b^z∗−bz∗\|≤∑z\|b^z−bz\|=‖b^−b‖1\.\|\\hat\{b\}^\{z^\{\*\}\}\-b^\{z^\{\*\}\}\|\\leq\\sum\_\{z\}\|\\hat\{b\}^\{z\}\-b^\{z\}\|=\\\|\\hat\{b\}\-b\\\|\_\{1\}\.\(53\)Combining these,

‖log⁡b^−log⁡b‖∞≤1bmin​‖b^−b‖1\.∎\\\|\\log\\hat\{b\}\-\\log b\\\|\_\{\\infty\}\\leq\\frac\{1\}\{b\_\{\\min\}\}\\\|\\hat\{b\}\-b\\\|\_\{1\}\.\\qed\(54\)
Proposition[2](https://arxiv.org/html/2605.29042#Thmproposition2)establishes that for the endpoint of akk\-steps,

‖b^t\+k−bt\+k‖1≤2​∑s=0k−1εt\+s≤2​k​ε,\\\|\\hat\{b\}\_\{t\+k\}\-b\_\{t\+k\}\\\|\_\{1\}\\leq 2\\sum\_\{s=0\}^\{k\-1\}\\varepsilon\_\{t\+s\}\\leq 2k\\varepsilon,\(55\)whereε=maxt⁡εt\\varepsilon=\\max\_\{t\}\\varepsilon\_\{t\}\. The same induction applies at every intermediate step, giving the following trajectory\-wide drift bound\.

###### Corollary 3\(Log\-belief trajectory drift\)\.

Under the assumptions of Proposition[2](https://arxiv.org/html/2605.29042#Thmproposition2), for everym∈\{0,1,…,k\}m\\in\\\{0,1,\\dots,k\\\},

‖b^t\+m−bt\+m‖1≤2​∑s=0m−1εt\+s≤2​m​ε\.\\\|\\hat\{b\}\_\{t\+m\}\-b\_\{t\+m\}\\\|\_\{1\}\\leq 2\\sum\_\{s=0\}^\{m\-1\}\\varepsilon\_\{t\+s\}\\leq 2m\\varepsilon\.\(56\)

###### Proof\.

Apply Proposition[2](https://arxiv.org/html/2605.29042#Thmproposition2)with horizonmmin place ofkk\. The induction in the proof of Proposition[2](https://arxiv.org/html/2605.29042#Thmproposition2)makes no use ofkkbeing distinguished from any other horizon length ∎

Combining Corollary[3](https://arxiv.org/html/2605.29042#Thmcorollary3)with Lemma[2](https://arxiv.org/html/2605.29042#Thmlemma2)gives the corresponding bound in∞\\infty\-norm of log\-beliefs, which we use in subsequent steps\.

###### Corollary 4\.

Under the assumptions of Proposition[2](https://arxiv.org/html/2605.29042#Thmproposition2)and Theorem[2](https://arxiv.org/html/2605.29042#Thmtheorem2), for everym∈0,1,…,km\\in\{0,1,\.\.\.,k\}

‖log⁡b^t\+m−log⁡bt\+m‖∞≤2​m​εbmin\.\\\|\\log\\hat\{b\}\_\{t\+m\}\-\\log b\_\{t\+m\}\\\|\_\{\\infty\}\\leq\\frac\{2m\\varepsilon\}\{b\_\{\\min\}\}\.\(57\)

###### Proof\.

Apply Lemma[2](https://arxiv.org/html/2605.29042#Thmlemma2)tobt\+mb\_\{t\+m\}andb^t\+m\\hat\{b\}\_\{t\+m\}:

‖log⁡b^t\+m−log⁡bt\+m‖∞≤1bmin​‖b^t\+m−bt\+m‖1≤2​m​εbmin\.∎\\\|\\log\\hat\{b\}\_\{t\+m\}\-\\log b\_\{t\+m\}\\\|\_\{\\infty\}\\leq\\frac\{1\}\{b\_\{\\min\}\}\\\|\\hat\{b\}\_\{t\+m\}\-b\_\{t\+m\}\\\|\_\{1\}\\leq\\frac\{2m\\varepsilon\}\{b\_\{\\min\}\}\.\\qed\(58\)

#### A\.11\.1Chain\-rule expansion of∇θL\\nabla\_\{\\theta\}L

We expand∇θL=−∇θVϕ​\(ot\+k,bt\+k\)\\nabla\_\{\\theta\}L=\-\\nabla\_\{\\theta\}V\_\{\\phi\}\(o\_\{t\+k\},b\_\{t\+k\}\)using the chain rule\. The parameterθ\\thetaenters the loss throughkkseparate channels, one per step in the window: at steps∈\{t,…,t\+k−1\}s\\in\\\{t,\\dots,t\+k\-1\\\},θ\\thetacontrols the log\-likelihood vector

ℓs:=log⁡πθ​\(as∣os,⋅\)∈ℝ\|𝒵\|,\\ell\_\{s\}:=\\log\\pi\_\{\\theta\}\(a\_\{s\}\\mid o\_\{s\},\\cdot\)\\in\\mathbb\{R\}^\{\|\\mathcal\{Z\}\|\},\(59\)which then propagates through softmax\-Bayes updatesbr\+1=softmax​\(ℓr\+log⁡br\)b\_\{r\+1\}=\\mathrm\{softmax\}\(\\ell\_\{r\}\+\\log b\_\{r\}\)until reachingbt\+kb\_\{t\+k\}, which feeds intoVϕV\_\{\\phi\}\.

By the multivariate chain rule, summing over allkkentry points,

∇θL=∑s=tt\+k−1∂L∂bt\+k⋅\(∏r=s\+1t\+k−1∂br\+1∂br\)⋅∂bs\+1∂ℓs⋅∇θℓs\.\\nabla\_\{\\theta\}L=\\sum\_\{s=t\}^\{t\+k\-1\}\\frac\{\\partial L\}\{\\partial b\_\{t\+k\}\}\\cdot\\left\(\\prod\_\{r=s\+1\}^\{t\+k\-1\}\\frac\{\\partial b\_\{r\+1\}\}\{\\partial b\_\{r\}\}\\right\)\\cdot\\frac\{\\partial b\_\{s\+1\}\}\{\\partial\\ell\_\{s\}\}\\cdot\\nabla\_\{\\theta\}\\ell\_\{s\}\.\(60\)For compactness, denote the four kinds of factors as

g\\displaystyle g:=∂L∂bt\+k\\displaystyle:=\\frac\{\\partial L\}\{\\partial b\_\{t\+k\}\}\(endpoint gradient\),\(61\)Jr\\displaystyle J\_\{r\}:=∂br\+1∂br\\displaystyle:=\\frac\{\\partial b\_\{r\+1\}\}\{\\partial b\_\{r\}\}\(belief\-to\-belief Jacobian\),\(62\)Ss\\displaystyle S\_\{s\}:=∂bs\+1∂ℓs\\displaystyle:=\\frac\{\\partial b\_\{s\+1\}\}\{\\partial\\ell\_\{s\}\}\(softmax Jacobian\),\(63\)Gs\\displaystyle G\_\{s\}:=∇θℓs\\displaystyle:=\\nabla\_\{\\theta\}\\ell\_\{s\}\(policy\-gradient matrix\)\.\(64\)and let

Πs:=∏r=s\+1t\+kJr\\Pi\_\{s\}:=\\prod\_\{r=s\+1\}^\{t\+k\}J\_\{r\}\(65\)denote the belief\-Jacobian chain from steps\+1s\+1to stept\+kt\+k\. Equation[60](https://arxiv.org/html/2605.29042#A1.E60)can compactly be written as

∇θL=∑s=tt\+k−1g⋅Πs⋅Ss⋅Gs\.\\nabla\_\{\\theta\}L=\\sum\_\{s=t\}^\{t\+k\-1\}g\\cdot\\Pi\_\{s\}\\cdot S\_\{s\}\\cdot G\_\{s\}\.\(66\)
The approximate gradient∇θLapprox\\nabla\_\{\\theta\}L\_\{\\text\{approx\}\}has the same form as Eq\.[66](https://arxiv.org/html/2605.29042#A1.E66), but every factor is evaluated along the approximate trajectory\(b^s\)s=tt\+k\(\\hat\{b\}\_\{s\}\)\_\{s=t\}^\{t\+k\}generated usingo^s\\hat\{o\}\_\{s\}in place ofoso\_\{s\}\. We denote the approximate factors with hats:g^,J^r,S^s,G^s,Π^s\\hat\{g\},\\hat\{J\}\_\{r\},\\hat\{S\}\_\{s\},\\hat\{G\}\_\{s\},\\hat\{\\Pi\}\_\{s\}\. Both trajectories share the same starting belief,b^t=bt\\hat\{b\}\_\{t\}=b\_\{t\}\.

#### A\.11\.2Magnitude bounds on the chain\-rule factors

We bound each of the chain\-rule factors in the appropriate operator norm\.

###### Proposition 3\(Magnitude bounds\)\.

Under the assumptions of Theorem[2](https://arxiv.org/html/2605.29042#Thmtheorem2), the factors of Eq\.[66](https://arxiv.org/html/2605.29042#A1.E66)satisfy

‖g‖∞\\displaystyle\\\|g\\\|\_\{\\infty\}≤LV,\\displaystyle\\leq L\_\{V\},\(67\)‖Ss‖∞→1\\displaystyle\\\|S\_\{s\}\\\|\_\{\\infty\\to 1\}≤2,\\displaystyle\\leq 2,\(68\)‖Gs‖2→∞\\displaystyle\\\|G\_\{s\}\\\|\_\{2\\to\\infty\}≤Gπ\.\\displaystyle\\leq G\_\{\\pi\}\.\(69\)The same bounds hold forg^,S^s,G^s\\hat\{g\},\\hat\{S\}\_\{s\},\\hat\{G\}\_\{s\}along the approximate trajectory\.

###### Proof\.

Bound ongg\.Assumption \(4\) states thatVϕ​\(o,⋅\)V\_\{\\phi\}\(o,\\cdot\)isLVL\_\{V\}\-Lipschitz in∥⋅∥1\\\|\\cdot\\\|\_\{1\}:

\|Vϕ​\(o,b\)−Vϕ​\(o,b′\)\|≤LV​‖b−b′‖1∀b,b′∈Δ\|𝒵\|\.\|V\_\{\\phi\}\(o,b\)\-V\_\{\\phi\}\(o,b^\{\\prime\}\)\|\\leq L\_\{V\}\\\|b\-b^\{\\prime\}\\\|\_\{1\}\\quad\\forall b,b^\{\\prime\}\\in\\Delta^\{\|\\mathcal\{Z\}\|\}\.\(70\)By the duality between∥⋅∥1\\\|\\cdot\\\|\_\{1\}and∥⋅∥∞\\\|\\cdot\\\|\_\{\\infty\}, the gradientg=∂L/∂bt\+k=−∂Vϕ/∂bt\+kg=\\partial L/\\partial b\_\{t\+k\}=\-\\partial V\_\{\\phi\}/\\partial b\_\{t\+k\}satisfies

‖g‖∞=sup‖δ​b‖1≤1\|g⋅δ​b\|≤LV\.\\\|g\\\|\_\{\\infty\}=\\sup\_\{\\\|\\delta b\\\|\_\{1\}\\leq 1\}\|g\\cdot\\delta b\|\\leq L\_\{V\}\.\(71\)
Bound onSsS\_\{s\}\.Recallbs\+1=softmax​\(ℓs\+log⁡bs\)b\_\{s\+1\}=\\mathrm\{softmax\}\(\\ell\_\{s\}\+\\log b\_\{s\}\), soSs=∂bs\+1/∂ℓsS\_\{s\}=\\partial b\_\{s\+1\}/\\partial\\ell\_\{s\}is the Jacobian ofsoftmax\\mathrm\{softmax\}evaluated atℓs\+log⁡bs\\ell\_\{s\}\+\\log b\_\{s\}\. Lemma[1](https://arxiv.org/html/2605.29042#Thmlemma1)states

‖softmax​\(x\)−softmax​\(y\)‖1≤2​‖x−y‖∞∀x,y∈ℝ\|𝒵\|,\\\|\\mathrm\{softmax\}\(x\)\-\\mathrm\{softmax\}\(y\)\\\|\_\{1\}\\leq 2\\\|x\-y\\\|\_\{\\infty\}\\quad\\forall x,y\\in\\mathbb\{R\}^\{\|\\mathcal\{Z\}\|\},\(72\)i\.e\.,softmax\\mathrm\{softmax\}is22\-Lipschitz from∥⋅∥∞\\\|\\cdot\\\|\_\{\\infty\}to∥⋅∥1\\\|\\cdot\\\|\_\{1\}\. For any directionv∈ℝ\|𝒵\|v\\in\\mathbb\{R\}^\{\|\\mathcal\{Z\}\|\}andη\>0\\eta\>0, applying this tox=u\+η​vx=u\+\\eta vandy=uy=ugives

‖softmax​\(u\+η​v\)−softmax​\(u\)‖1≤2​η​‖v‖∞\.\\\|\\mathrm\{softmax\}\(u\+\\eta v\)\-\\mathrm\{softmax\}\(u\)\\\|\_\{1\}\\leq 2\\eta\\\|v\\\|\_\{\\infty\}\.\(73\)Dividing byη\\etaand takingη→0\\eta\\to 0yields‖Jsoftmax​\(u\)​v‖1≤2​‖v‖∞\\\|J\_\{\\mathrm\{softmax\}\}\(u\)\\,v\\\|\_\{1\}\\leq 2\\\|v\\\|\_\{\\infty\}for allvv, so the softmax Jacobian satisfies‖Jsoftmax​\(u\)‖∞→1≤2\\\|J\_\{\\mathrm\{softmax\}\}\(u\)\\\|\_\{\\infty\\to 1\}\\leq 2at every inputuu\. In particular, evaluating atu=ℓs\+log⁡bsu=\\ell\_\{s\}\+\\log b\_\{s\},

‖Ss‖∞→1≤2\.\\\|S\_\{s\}\\\|\_\{\\infty\\to 1\}\\leq 2\.\(74\)
Bound onGsG\_\{s\}\.The matrixGs∈ℝ\|𝒵\|×dθG\_\{s\}\\in\\mathbb\{R\}^\{\|\\mathcal\{Z\}\|\\times d\_\{\\theta\}\}has rowsGsz,:=∇θlog⁡πθ​\(as∣os,z\)∈ℝdθG\_\{s\}^\{z,:\}=\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(a\_\{s\}\\mid o\_\{s\},z\)\\in\\mathbb\{R\}^\{d\_\{\\theta\}\}indexed by rolezz\. For anyx∈ℝdθx\\in\\mathbb\{R\}^\{d\_\{\\theta\}\}, thezz\-th coordinate ofGs​xG\_\{s\}xis the dot productGsz,:⋅xG\_\{s\}^\{z,:\}\\cdot x, so

‖Gs​x‖∞=maxz⁡\|Gsz,:⋅x\|\.\\\|G\_\{s\}x\\\|\_\{\\infty\}=\\max\_\{z\}\|G\_\{s\}^\{z,:\}\\cdot x\|\.\(75\)Taking the supremum over‖x‖2≤1\\\|x\\\|\_\{2\}\\leq 1and exchangingsup\\supandmax\\max,

‖Gs‖2→∞=sup‖x‖2≤1maxz⁡\|Gsz,:⋅x\|=maxz​sup‖x‖2≤1\|Gsz,:⋅x\|\.\\\|G\_\{s\}\\\|\_\{2\\to\\infty\}=\\sup\_\{\\\|x\\\|\_\{2\}\\leq 1\}\\max\_\{z\}\|G\_\{s\}^\{z,:\}\\cdot x\|=\\max\_\{z\}\\,\\sup\_\{\\\|x\\\|\_\{2\}\\leq 1\}\|G\_\{s\}^\{z,:\}\\cdot x\|\.\(76\)The inner supremum is the dual norm ofGsz,:G\_\{s\}^\{z,:\}under∥⋅∥2\\\|\\cdot\\\|\_\{2\}; since∥⋅∥2\\\|\\cdot\\\|\_\{2\}is self\-dual, Cauchy–Schwarz givessup‖x‖2≤1\|Gsz,:⋅x\|=‖Gsz,:‖2\\sup\_\{\\\|x\\\|\_\{2\}\\leq 1\}\|G\_\{s\}^\{z,:\}\\cdot x\|=\\\|G\_\{s\}^\{z,:\}\\\|\_\{2\}, with equality attained atx=Gsz,:/‖Gsz,:‖2x=G\_\{s\}^\{z,:\}/\\\|G\_\{s\}^\{z,:\}\\\|\_\{2\}\. Hence

∥Gs∥2→∞=maxz∥Gsz,:∥2=maxz∥∇θlogπθ\(as∣os,z\)∥2≤Gπ,\\\|G\_\{s\}\\\|\_\{2\\to\\infty\}=\\max\_\{z\}\\\|G\_\{s\}^\{z,:\}\\\|\_\{2\}=\\max\_\{z\}\\\|\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(a\_\{s\}\\mid o\_\{s\},z\)\\\|\_\{2\}\\leq G\_\{\\pi\},\(77\)where the last inequality follows from the definition ofGπG\_\{\\pi\}\.

The bounds for the approximate factorsg^,S^s,G^s\\hat\{g\},\\hat\{S\}\_\{s\},\\hat\{G\}\_\{s\}follow from the same arguments applied along the approximate trajectory\. ∎

#### A\.11\.3Decomposition of the gradient error

Define the per\-summand contributions to∇θL\\nabla\_\{\\theta\}Land∇θLapprox\\nabla\_\{\\theta\}L\_\{\\text\{approx\}\}as

Ts:=g⋅Πs⋅Ss⋅Gs,T^s:=g^⋅Π^s⋅S^s⋅G^s,T\_\{s\}:=g\\cdot\\Pi\_\{s\}\\cdot S\_\{s\}\\cdot G\_\{s\},\\qquad\\hat\{T\}\_\{s\}:=\\hat\{g\}\\cdot\\hat\{\\Pi\}\_\{s\}\\cdot\\hat\{S\}\_\{s\}\\cdot\\hat\{G\}\_\{s\},\(78\)so that∇θLapprox−∇θLtrue=∑s=tt\+k−1\(T^s−Ts\)\\nabla\_\{\\theta\}L\_\{\\text\{approx\}\}\-\\nabla\_\{\\theta\}L\_\{\\text\{true\}\}=\\sum\_\{s=t\}^\{t\+k\-1\}\(\\hat\{T\}\_\{s\}\-T\_\{s\}\)\.

Within each summand, the hat and no\-hat versions differ in all four factors\. To isolate one source of error at a time, we telescope by swapping one factor at a time, from left to right\. Adding and subtracting intermediate hybrids,

T^s−Ts\\displaystyle\\hat\{T\}\_\{s\}\-T\_\{s\}=\(g^−g\)​Π^s​S^s​G^s⏟\(A\)\+g​\(Π^s−Πs\)​S^s​G^s⏟\(B\)\\displaystyle=\\underbrace\{\(\\hat\{g\}\-g\)\\,\\hat\{\\Pi\}\_\{s\}\\hat\{S\}\_\{s\}\\hat\{G\}\_\{s\}\}\_\{\\text\{\(A\)\}\}\+\\underbrace\{g\\,\(\\hat\{\\Pi\}\_\{s\}\-\\Pi\_\{s\}\)\\hat\{S\}\_\{s\}\\hat\{G\}\_\{s\}\}\_\{\\text\{\(B\)\}\}\+g​Πs​\(S^s−Ss\)​G^s⏟\(C\)\+g​Πs​Ss​\(G^s−Gs\)⏟\(D\)\.\\displaystyle\\quad\+\\underbrace\{g\\,\\Pi\_\{s\}\(\\hat\{S\}\_\{s\}\-S\_\{s\}\)\\hat\{G\}\_\{s\}\}\_\{\\text\{\(C\)\}\}\+\\underbrace\{g\\,\\Pi\_\{s\}S\_\{s\}\(\\hat\{G\}\_\{s\}\-G\_\{s\}\)\}\_\{\\text\{\(D\)\}\}\.\(79\)Each piece isolates the perturbation of a single factor\. Summing overssand applying the triangle inequality in∥⋅∥2\\\|\\cdot\\\|\_\{2\},

‖∇θLapprox−∇θLtrue‖2≤∑s=tt\+k−1\(‖\(A\)s‖2\+‖\(B\)s‖2\+‖\(C\)s‖2\+‖\(D\)s‖2\)\.\\big\\\|\\nabla\_\{\\theta\}L\_\{\\text\{approx\}\}\-\\nabla\_\{\\theta\}L\_\{\\text\{true\}\}\\big\\\|\_\{2\}\\leq\\sum\_\{s=t\}^\{t\+k\-1\}\\Big\(\\\|\\text\{\(A\)\}\_\{s\}\\\|\_\{2\}\+\\\|\\text\{\(B\)\}\_\{s\}\\\|\_\{2\}\+\\\|\\text\{\(C\)\}\_\{s\}\\\|\_\{2\}\+\\\|\\text\{\(D\)\}\_\{s\}\\\|\_\{2\}\\Big\)\.\(80\)The four pieces are bounded individually in the following subsections\.

#### A\.11\.4Bound on piece \(D\): policy\-gradient error

Piece \(D\) isolates the error from evaluating the policy gradient ato^s\\hat\{o\}\_\{s\}instead ofoso\_\{s\}:

\(D\)s=g⋅Πs⋅Ss⋅\(G^s−Gs\)\.\(D\)\_\{s\}=g\\cdot\\Pi\_\{s\}\\cdot S\_\{s\}\\cdot\(\\hat\{G\}\_\{s\}\-G\_\{s\}\)\.\(81\)By submultiplicativity of operator norms,

‖\(D\)s‖2≤‖g‖∞⋅‖Πs‖1→1⋅‖Ss‖∞→1⋅‖G^s−Gs‖2→∞\.\\\|\(D\)\_\{s\}\\\|\_\{2\}\\leq\\\|g\\\|\_\{\\infty\}\\cdot\\\|\\Pi\_\{s\}\\\|\_\{1\\to 1\}\\cdot\\\|S\_\{s\}\\\|\_\{\\infty\\to 1\}\\cdot\\\|\\hat\{G\}\_\{s\}\-G\_\{s\}\\\|\_\{2\\to\\infty\}\.\(82\)
The first three factors are bounded via Proposition 3 and Section[A\.11\.7](https://arxiv.org/html/2605.29042#A1.SS11.SSS7)\. We bound the difference factor[A\.11\.7](https://arxiv.org/html/2605.29042#A1.SS11.SSS7)‖G^s−Gs‖2→∞\\\|\\hat\{G\}\_\{s\}\-G\_\{s\}\\\|\_\{2\\to\\infty\}here\.

The matrixG^s−Gs∈ℝ\|𝒵\|×dθ\\hat\{G\}\_\{s\}\-G\_\{s\}\\in\\mathbb\{R\}^\{\|\\mathcal\{Z\}\|\\times d\_\{\\theta\}\}has rows

\(G^s−Gs\)z,:=∇θlog⁡πθ​\(as\|o^s,z\)−∇θlog⁡πθ​\(as\|os,z\)∈ℝdθ\.\(\\hat\{G\}\_\{s\}\-G\_\{s\}\)^\{z,:\}=\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(a\_\{s\}\|\\hat\{o\}\_\{s\},z\)\-\\nabla\_\{\\theta\}\\log\\pi\_\{\\theta\}\(a\_\{s\}\|o\_\{s\},z\)\\in\\mathbb\{R\}^\{d\_\{\\theta\}\}\.\(83\)By Assumption \(2\), each row satisfies

‖\(G^s−Gs\)z,:‖2≤Lπ​‖o^s−os‖∞\.\\\|\(\\hat\{G\}\_\{s\}\-G\_\{s\}\)^\{z,:\}\\\|\_\{2\}\\leq L\_\{\\pi\}\\\|\\hat\{o\}\_\{s\}\-o\_\{s\}\\\|\_\{\\infty\}\.\(84\)Following the same argument as in the proof of Proposition 3 \(the2→∞2\\to\\inftyoperator norm equals the maximum row 2\-norm\),

‖G^s−Gs‖2→∞=maxz⁡‖\(G^s−Gs\)z,:‖2≤Lπ​‖o^s−os‖∞\.\\\|\\hat\{G\}\_\{s\}\-G\_\{s\}\\\|\_\{2\\to\\infty\}=\\max\_\{z\}\\\|\(\\hat\{G\}\_\{s\}\-G\_\{s\}\)^\{z,:\}\\\|\_\{2\}\\leq L\_\{\\pi\}\\\|\\hat\{o\}\_\{s\}\-o\_\{s\}\\\|\_\{\\infty\}\.\(85\)
Combining with the magnitude bounds from Proposition 3 \(‖g‖∞≤LV\\\|g\\\|\_\{\\infty\}\\leq L\_\{V\},‖Ss‖∞→1≤2\\\|S\_\{s\}\\\|\_\{\\infty\\to 1\}\\leq 2\), Eq\.[82](https://arxiv.org/html/2605.29042#A1.E82)becomes

‖\(D\)s‖2≤2​LV⋅‖Πs‖1→1⋅Lπ​‖o^s−os‖∞,\\\|\(D\)\_\{s\}\\\|\_\{2\}\\leq 2L\_\{V\}\\cdot\\\|\\Pi\_\{s\}\\\|\_\{1\\to 1\}\\cdot L\_\{\\pi\}\\\|\\hat\{o\}\_\{s\}\-o\_\{s\}\\\|\_\{\\infty\},\(86\)where the bound on‖Πs‖1→1\\\|\\Pi\_\{s\}\\\|\_\{1\\to 1\}is established in Section[A\.11\.7](https://arxiv.org/html/2605.29042#A1.SS11.SSS7)\.

#### A\.11\.5Bound on piece \(A\): endpoint error

By submultiplicativity of operator norms,

‖\(A\)s‖2≤‖g^−g‖∞⋅‖Π^s‖1→1⋅‖S^s‖∞→1⋅‖G^s‖2→∞\.\\\|\(A\)\_\{s\}\\\|\_\{2\}\\leq\\\|\\hat\{g\}\-g\\\|\_\{\\infty\}\\cdot\\\|\\hat\{\\Pi\}\_\{s\}\\\|\_\{1\\to 1\}\\cdot\\\|\\hat\{S\}\_\{s\}\\\|\_\{\\infty\\to 1\}\\cdot\\\|\\hat\{G\}\_\{s\}\\\|\_\{2\\to\\infty\}\.\(87\)Bounding‖g^−g‖∞\\\|\\hat\{g\}\-g\\\|\_\{\\infty\}uses Assumption 5 that∇bVϕ\\nabla\_\{b\}V\_\{\\phi\}itself be Lipschitz inbb, with some constantLgL\_\{g\}\. Under this assumption,

‖g^−g‖∞≤Lg​‖b^t\+k−bt\+k‖1≤2​k​ε⋅Lg\\\|\\hat\{g\}\-g\\\|\_\{\\infty\}\\leq L\_\{g\}\\\|\\hat\{b\}\_\{t\+k\}\-b\_\{t\+k\}\\\|\_\{1\}\\leq 2k\\varepsilon\\cdot L\_\{g\}\(88\)by Corollary 3\.

Substituting into Eq\.[87](https://arxiv.org/html/2605.29042#A1.E87)and using Proposition 3,

‖\(A\)s‖2≤2​k​ε​Lg⋅‖Π^s‖1→1⋅2⋅Gπ=4​k​ε​Lg​Gπ⋅‖Π^s‖1→1,\\\|\(A\)\_\{s\}\\\|\_\{2\}\\leq 2k\\varepsilon L\_\{g\}\\cdot\\\|\\hat\{\\Pi\}\_\{s\}\\\|\_\{1\\to 1\}\\cdot 2\\cdot G\_\{\\pi\}=4k\\varepsilon L\_\{g\}G\_\{\\pi\}\\cdot\\\|\\hat\{\\Pi\}\_\{s\}\\\|\_\{1\\to 1\},\(89\)where the bound on‖Π^s‖1→1\\\|\\hat\{\\Pi\}\_\{s\}\\\|\_\{1\\to 1\}is established in Section[A\.11\.7](https://arxiv.org/html/2605.29042#A1.SS11.SSS7)\.

#### A\.11\.6Bound on piece \(C\): softmax error

By submultiplicativity,

‖\(C\)s‖2≤‖g‖∞⋅‖Πs‖1→1⋅‖S^s−Ss‖∞→1⋅‖G^s‖2→∞\.\\\|\(C\)\_\{s\}\\\|\_\{2\}\\leq\\\|g\\\|\_\{\\infty\}\\cdot\\\|\\Pi\_\{s\}\\\|\_\{1\\to 1\}\\cdot\\\|\\hat\{S\}\_\{s\}\-S\_\{s\}\\\|\_\{\\infty\\to 1\}\\cdot\\\|\\hat\{G\}\_\{s\}\\\|\_\{2\\to\\infty\}\.\(90\)
The softmax Jacobian admits the closed formSs=diag​\(bs\+1\)−bs\+1​bs\+1⊤S\_\{s\}=\\mathrm\{diag\}\(b\_\{s\+1\}\)\-b\_\{s\+1\}b\_\{s\+1\}^\{\\top\}\. Lettingδ:=b^s\+1−bs\+1\\delta:=\\hat\{b\}\_\{s\+1\}\-b\_\{s\+1\}and usingx^​x^⊤−x​x⊤=x^​δ⊤\+δ​x⊤\\hat\{x\}\\hat\{x\}^\{\\top\}\-xx^\{\\top\}=\\hat\{x\}\\delta^\{\\top\}\+\\delta x^\{\\top\},

S^s−Ss=diag​\(δ\)−b^s\+1​δ⊤−δ​bs\+1⊤\.\\hat\{S\}\_\{s\}\-S\_\{s\}=\\mathrm\{diag\}\(\\delta\)\-\\hat\{b\}\_\{s\+1\}\\delta^\{\\top\}\-\\delta b\_\{s\+1\}^\{\\top\}\.\(91\)
We bound each of the three terms in∞→1\\infty\\to 1operator norm\. For the diagonal term,‖diag​\(δ\)​x‖1=∑z\|δz​xz\|≤‖δ‖1​‖x‖∞\\\|\\mathrm\{diag\}\(\\delta\)x\\\|\_\{1\}=\\sum\_\{z\}\|\\delta\_\{z\}x\_\{z\}\|\\leq\\\|\\delta\\\|\_\{1\}\\\|x\\\|\_\{\\infty\}\. For each rank\-one termu​v⊤uv^\{\\top\}, the outputu​\(v⊤​x\)u\(v^\{\\top\}x\)has 1\-norm‖u‖1⋅\|v⊤​x\|≤‖u‖1​‖v‖1​‖x‖∞\\\|u\\\|\_\{1\}\\cdot\|v^\{\\top\}x\|\\leq\\\|u\\\|\_\{1\}\\\|v\\\|\_\{1\}\\\|x\\\|\_\{\\infty\}by Hölder’s inequality, and since‖bs\+1‖1=‖b^s\+1‖1=1\\\|b\_\{s\+1\}\\\|\_\{1\}=\\\|\\hat\{b\}\_\{s\+1\}\\\|\_\{1\}=1\(probability vectors\), each rank\-one term contributes at most‖δ‖1\\\|\\delta\\\|\_\{1\}\. By the triangle inequality,

‖S^s−Ss‖∞→1≤3​‖b^s\+1−bs\+1‖1≤6​k​ε\\\|\\hat\{S\}\_\{s\}\-S\_\{s\}\\\|\_\{\\infty\\to 1\}\\leq 3\\\|\\hat\{b\}\_\{s\+1\}\-b\_\{s\+1\}\\\|\_\{1\}\\leq 6k\\varepsilon\(92\)where the second inequality is Corollary[3](https://arxiv.org/html/2605.29042#Thmcorollary3)\.

Combining with Proposition 3,

‖\(C\)s‖2≤6​k​ε​LV​Gπ⋅‖Πs‖1→1\.\\\|\(C\)\_\{s\}\\\|\_\{2\}\\leq 6k\\varepsilon L\_\{V\}G\_\{\\pi\}\\cdot\\\|\\Pi\_\{s\}\\\|\_\{1\\to 1\}\.\(93\)

#### A\.11\.7Bound on piece \(B\): Jacobian\-chain error

The chainΠs\\Pi\_\{s\}is a product oft\+k−s−1t\+k\-s\-1belief\-to\-belief Jacobians\. We establish that the chainΠs\\Pi\_\{s\}*collapses algebraically*to a single Jacobian whose form depends only on the starting beliefbs\+1b\_\{s\+1\}and the ending beliefbt\+kb\_\{t\+k\}, with all intermediate beliefs disappearing\. This collapse keeps the dependence on1/bmin1/b\_\{\\min\}polynomial\.

###### Lemma 3\(Jacobian\-chain collapse\)\.

For anyrrandm≥0m\\geq 0,

Jr\+m⋅Jr\+m−1​⋯​Jr\+1⋅Jr=Dr\+m\+1​\(I−𝟏​br\+m\+1⊤\)​Dr−1\.J\_\{r\+m\}\\cdot J\_\{r\+m\-1\}\\cdots J\_\{r\+1\}\\cdot J\_\{r\}=D\_\{r\+m\+1\}\\,\(I\-\\mathbf\{1\}\\,b\_\{r\+m\+1\}^\{\\top\}\)\\,D\_\{r\}^\{\-1\}\.\(94\)In particular, applying this withr=s\+1r=s\+1andm=t\+k−s−2m=t\+k\-s\-2,

Πs=Dt\+k​\(I−𝟏​bt\+k⊤\)​Ds\+1−1,Π^s=D^t\+k​\(I−𝟏​b^t\+k⊤\)​D^s\+1−1,\\Pi\_\{s\}=D\_\{t\+k\}\\,\(I\-\\mathbf\{1\}\\,b\_\{t\+k\}^\{\\top\}\)\\,D\_\{s\+1\}^\{\-1\},\\qquad\\hat\{\\Pi\}\_\{s\}=\\hat\{D\}\_\{t\+k\}\\,\(I\-\\mathbf\{1\}\\,\\hat\{b\}\_\{t\+k\}^\{\\top\}\)\\,\\hat\{D\}\_\{s\+1\}^\{\-1\},\(95\)whereDr:=diag​\(br\)D\_\{r\}:=\\mathrm\{diag\}\(b\_\{r\}\)andD^r:=diag​\(b^r\)\\hat\{D\}\_\{r\}:=\\mathrm\{diag\}\(\\hat\{b\}\_\{r\}\)\.

###### Proof\.

By induction onmm\.

*Base case \(m=0m=0\)\.*The claim reads

Jr=Dr\+1​\(I−𝟏​br\+1⊤\)​Dr−1\.J\_\{r\}=D\_\{r\+1\}\(I\-\\mathbf\{1\}\\,b\_\{r\+1\}^\{\\top\}\)\\,D\_\{r\}^\{\-1\}\.\(96\)We derive this from the chain rule\. The forward computation isbr\+1=softmax​\(ℓr\+log⁡br\)b\_\{r\+1\}=\\mathrm\{softmax\}\(\\ell\_\{r\}\+\\log b\_\{r\}\), whereℓr:=log⁡πθ​\(ar∣or,⋅\)∈ℝ\|𝒵\|\\ell\_\{r\}:=\\log\\pi\_\{\\theta\}\(a\_\{r\}\\mid o\_\{r\},\\cdot\)\\in\\mathbb\{R\}^\{\|\\mathcal\{Z\}\|\}is the log\-likelihood vector at steprr\. Note thatℓr\\ell\_\{r\}depends onθ\\theta,ara\_\{r\}, andoro\_\{r\}but not onbrb\_\{r\}\. Writingu:=ℓr\+log⁡bru:=\\ell\_\{r\}\+\\log b\_\{r\}for the input to softmax, the dependency chain is

br⟶log⁡br⟶u=ℓr\+log⁡br⟶br\+1=softmax​\(u\),b\_\{r\}\\;\\longrightarrow\\;\\log b\_\{r\}\\;\\longrightarrow\\;u=\\ell\_\{r\}\+\\log b\_\{r\}\\;\\longrightarrow\\;b\_\{r\+1\}=\\mathrm\{softmax\}\(u\),\(97\)giving by the chain rule

Jr=∂br\+1∂br=∂br\+1∂u⋅∂u∂\(log⁡br\)⋅∂\(log⁡br\)∂br\.J\_\{r\}=\\frac\{\\partial b\_\{r\+1\}\}\{\\partial b\_\{r\}\}=\\frac\{\\partial b\_\{r\+1\}\}\{\\partial u\}\\cdot\\frac\{\\partial u\}\{\\partial\(\\log b\_\{r\}\)\}\\cdot\\frac\{\\partial\(\\log b\_\{r\}\)\}\{\\partial b\_\{r\}\}\.\(98\)We compute each factor\.

The mapbr↦log⁡brb\_\{r\}\\mapsto\\log b\_\{r\}acts component\-wise withd​log⁡x/d​x=1/xd\\log x/dx=1/x, so its Jacobian is the diagonal matrix

∂\(log⁡br\)∂br=diag​\(1/br\)=Dr−1\.\\frac\{\\partial\(\\log b\_\{r\}\)\}\{\\partial b\_\{r\}\}=\\mathrm\{diag\}\(1/b\_\{r\}\)=D\_\{r\}^\{\-1\}\.\(99\)
Sinceℓr\\ell\_\{r\}does not depend onbrb\_\{r\},

∂u∂\(log⁡br\)=∂ℓr∂\(log⁡br\)\+∂\(log⁡br\)∂\(log⁡br\)=0\+I=I\.\\frac\{\\partial u\}\{\\partial\(\\log b\_\{r\}\)\}=\\frac\{\\partial\\ell\_\{r\}\}\{\\partial\(\\log b\_\{r\}\)\}\+\\frac\{\\partial\(\\log b\_\{r\}\)\}\{\\partial\(\\log b\_\{r\}\)\}=0\+I=I\.\(100\)
The standard softmax Jacobian formula gives, forbr\+1=softmax​\(u\)b\_\{r\+1\}=\\mathrm\{softmax\}\(u\),

∂br\+1∂u=diag​\(br\+1\)−br\+1​br\+1⊤\.\\frac\{\\partial b\_\{r\+1\}\}\{\\partial u\}=\\mathrm\{diag\}\(b\_\{r\+1\}\)\-b\_\{r\+1\}b\_\{r\+1\}^\{\\top\}\.\(101\)Usingbr\+1=diag​\(br\+1\)​𝟏b\_\{r\+1\}=\\mathrm\{diag\}\(b\_\{r\+1\}\)\\mathbf\{1\}, we factorbr\+1​br\+1⊤=diag​\(br\+1\)​1​br\+1⊤b\_\{r\+1\}b\_\{r\+1\}^\{\\top\}=\\mathrm\{diag\}\(b\_\{r\+1\}\)\\,\\mathbf\{1\}\\,b\_\{r\+1\}^\{\\top\}, hence

∂br\+1∂u=diag​\(br\+1\)​\[I−𝟏​br\+1⊤\]=Dr\+1​\(I−𝟏​br\+1⊤\)\.\\frac\{\\partial b\_\{r\+1\}\}\{\\partial u\}=\\mathrm\{diag\}\(b\_\{r\+1\}\)\\,\\big\[I\-\\mathbf\{1\}\\,b\_\{r\+1\}^\{\\top\}\\big\]=D\_\{r\+1\}\(I\-\\mathbf\{1\}\\,b\_\{r\+1\}^\{\\top\}\)\.\(102\)
*Combining the three factors,*

Jr=Dr\+1​\(I−𝟏​br\+1⊤\)⋅I⋅Dr−1=Dr\+1​\(I−𝟏​br\+1⊤\)​Dr−1\.J\_\{r\}=D\_\{r\+1\}\(I\-\\mathbf\{1\}\\,b\_\{r\+1\}^\{\\top\}\)\\cdot I\\cdot D\_\{r\}^\{\-1\}=D\_\{r\+1\}\\,\(I\-\\mathbf\{1\}\\,b\_\{r\+1\}^\{\\top\}\)\\,D\_\{r\}^\{\-1\}\.\(103\)This establishes the base case\.

*Inductive step\.*Assume the claim holds formm\. Multiplying on the left byJr\+m\+1=Dr\+m\+2​\(I−𝟏​br\+m\+2⊤\)​Dr\+m\+1−1J\_\{r\+m\+1\}=D\_\{r\+m\+2\}\(I\-\\mathbf\{1\}b\_\{r\+m\+2\}^\{\\top\}\)D\_\{r\+m\+1\}^\{\-1\}:

Jr\+m\+1⋅\(Jr\+m​⋯​Jr\)\\displaystyle J\_\{r\+m\+1\}\\cdot\\big\(J\_\{r\+m\}\\cdots J\_\{r\}\\big\)=Dr\+m\+2​\(I−𝟏​br\+m\+2⊤\)​Dr\+m\+1−1⋅Dr\+m\+1​\(I−𝟏​br\+m\+1⊤\)​Dr−1\\displaystyle=D\_\{r\+m\+2\}\(I\-\\mathbf\{1\}b\_\{r\+m\+2\}^\{\\top\}\)\\,D\_\{r\+m\+1\}^\{\-1\}\\cdot D\_\{r\+m\+1\}\(I\-\\mathbf\{1\}b\_\{r\+m\+1\}^\{\\top\}\)\\,D\_\{r\}^\{\-1\}=Dr\+m\+2​\(I−𝟏​br\+m\+2⊤\)​\(I−𝟏​br\+m\+1⊤\)​Dr−1,\\displaystyle=D\_\{r\+m\+2\}\(I\-\\mathbf\{1\}b\_\{r\+m\+2\}^\{\\top\}\)\(I\-\\mathbf\{1\}b\_\{r\+m\+1\}^\{\\top\}\)\\,D\_\{r\}^\{\-1\},\(104\)whereDr\+m\+1−1​Dr\+m\+1=ID\_\{r\+m\+1\}^\{\-1\}D\_\{r\+m\+1\}=Icancels\. We claim that

\(I−𝟏​br\+m\+2⊤\)​\(I−𝟏​br\+m\+1⊤\)=I−𝟏​br\+m\+2⊤\.\(I\-\\mathbf\{1\}b\_\{r\+m\+2\}^\{\\top\}\)\(I\-\\mathbf\{1\}b\_\{r\+m\+1\}^\{\\top\}\)=I\-\\mathbf\{1\}b\_\{r\+m\+2\}^\{\\top\}\.\(105\)For anyxx, the right\-hand factor gives\(I−𝟏​br\+m\+1⊤\)​x=x−𝟏​\(br\+m\+1⊤​x\)\(I\-\\mathbf\{1\}b\_\{r\+m\+1\}^\{\\top\}\)x=x\-\\mathbf\{1\}\(b\_\{r\+m\+1\}^\{\\top\}x\)\. Applying the left\-hand factor and using\(I−𝟏​br\+m\+2⊤\)​𝟏=𝟏−𝟏​\(br\+m\+2⊤​𝟏\)=0\(I\-\\mathbf\{1\}b\_\{r\+m\+2\}^\{\\top\}\)\\mathbf\{1\}=\\mathbf\{1\}\-\\mathbf\{1\}\\,\(b\_\{r\+m\+2\}^\{\\top\}\\mathbf\{1\}\)=0\(sincebr\+m\+2⊤​𝟏=1b\_\{r\+m\+2\}^\{\\top\}\\mathbf\{1\}=1\), the second term vanishes, leaving\(I−𝟏​br\+m\+2⊤\)​x\(I\-\\mathbf\{1\}b\_\{r\+m\+2\}^\{\\top\}\)x\. Equation[105](https://arxiv.org/html/2605.29042#A1.E105)follows\. Substituting,

Jr\+m\+1​⋯​Jr=Dr\+m\+2​\(I−𝟏​br\+m\+2⊤\)​Dr−1,J\_\{r\+m\+1\}\\cdots J\_\{r\}=D\_\{r\+m\+2\}\(I\-\\mathbf\{1\}b\_\{r\+m\+2\}^\{\\top\}\)\\,D\_\{r\}^\{\-1\},\(106\)which is the inductive claim form\+1m\+1\. ∎

The closed form in Eq\.[95](https://arxiv.org/html/2605.29042#A1.E95)reducesΠs\\Pi\_\{s\}to three matrix factors\. We now bound the magnitude‖Πs‖1→1\\\|\\Pi\_\{s\}\\\|\_\{1\\to 1\}, which is used in the bounds on pieces \(A\), \(C\), \(D\), and the difference‖Π^s−Πs‖1→1\\\|\\hat\{\\Pi\}\_\{s\}\-\\Pi\_\{s\}\\\|\_\{1\\to 1\}used in piece \(B\)\.

###### Lemma 4\(Magnitude bound onΠs\\Pi\_\{s\}\)\.

Under the assumptions of Theorem 2,

‖Πs‖1→1≤\|𝒵\|−1bmin\.\\\|\\Pi\_\{s\}\\\|\_\{1\\to 1\}\\leq\\frac\{\|\\mathcal\{Z\}\|\-1\}\{b\_\{\\min\}\}\.\(107\)The same bound holds for‖Π^s‖1→1\\\|\\hat\{\\Pi\}\_\{s\}\\\|\_\{1\\to 1\}\.

###### Proof\.

Recall the identity‖M‖1→1=maxj​∑i\|Mi​j\|\\\|M\\\|\_\{1\\to 1\}=\\max\_\{j\}\\sum\_\{i\}\|M\_\{ij\}\|\(maximum column 1\-norm\)\. By Eq\.[95](https://arxiv.org/html/2605.29042#A1.E95)and submultiplicativity of operator norms,

‖Πs‖1→1≤‖Dt\+k‖1→1⋅‖I−𝟏​bt\+k⊤‖1→1⋅‖Ds\+1−1‖1→1\.\\\|\\Pi\_\{s\}\\\|\_\{1\\to 1\}\\leq\\\|D\_\{t\+k\}\\\|\_\{1\\to 1\}\\cdot\\\|I\-\\mathbf\{1\}b\_\{t\+k\}^\{\\top\}\\\|\_\{1\\to 1\}\\cdot\\\|D\_\{s\+1\}^\{\-1\}\\\|\_\{1\\to 1\}\.\(108\)We bound each factor\.

*Bound on‖Dt\+k‖1→1\\\|D\_\{t\+k\}\\\|\_\{1\\to 1\}\.*Each column ofDt\+kD\_\{t\+k\}has a single nonzero entrybt\+kj∈\[0,1\]b\_\{t\+k\}^\{j\}\\in\[0,1\], so

‖Dt\+k‖1→1=maxj⁡bt\+kj≤1\.\\\|D\_\{t\+k\}\\\|\_\{1\\to 1\}=\\max\_\{j\}b\_\{t\+k\}^\{j\}\\leq 1\.\(109\)
*Bound on‖Ds\+1−1‖1→1\\\|D\_\{s\+1\}^\{\-1\}\\\|\_\{1\\to 1\}\.*Each column ofDs\+1−1D\_\{s\+1\}^\{\-1\}has a single nonzero entry1/bs\+1j1/b\_\{s\+1\}^\{j\}\.

‖Ds\+1−1‖1→1=maxj⁡1bs\+1j=1minj⁡bs\+1j≤1bmin\.\\\|D\_\{s\+1\}^\{\-1\}\\\|\_\{1\\to 1\}=\\max\_\{j\}\\frac\{1\}\{b\_\{s\+1\}^\{j\}\}=\\frac\{1\}\{\\min\_\{j\}b\_\{s\+1\}^\{j\}\}\\leq\\frac\{1\}\{b\_\{\\min\}\}\.\(110\)
*Bound on‖I−𝟏​bt\+k⊤‖1→1\\\|I\-\\mathbf\{1\}b\_\{t\+k\}^\{\\top\}\\\|\_\{1\\to 1\}\.*Columnjjin‖I−𝟏​bt\+k⊤‖1→1\\\|I\-\\mathbf\{1\}b\_\{t\+k\}^\{\\top\}\\\|\_\{1\\to 1\}has entry\(1−bt\+kj\)\(1\-b\_\{t\+k\}^\{j\}\)at positionjjand−bt\+kj\-b\_\{t\+k\}^\{j\}at each of the other\|𝒵\|−1\|\\mathcal\{Z\}\|\-1positions\. Its 1\-norm is

\(1−bt\+kj\)\+\(\|𝒵\|−1\)​bt\+kj=1\+\(\|𝒵\|−2\)​bt\+kj≤\|𝒵\|−1\.\(1\-b\_\{t\+k\}^\{j\}\)\+\(\|\\mathcal\{Z\}\|\-1\)\\,b\_\{t\+k\}^\{j\}=1\+\(\|\\mathcal\{Z\}\|\-2\)\\,b\_\{t\+k\}^\{j\}\\leq\|\\mathcal\{Z\}\|\-1\.\(111\)
*Combining,*

‖Πs‖1→1≤1⋅\(\|𝒵\|−1\)⋅1bmin=\|𝒵\|−1bmin\.\\\|\\Pi\_\{s\}\\\|\_\{1\\to 1\}\\leq 1\\cdot\(\|\\mathcal\{Z\}\|\-1\)\\cdot\\frac\{1\}\{b\_\{\\min\}\}=\\frac\{\|\\mathcal\{Z\}\|\-1\}\{b\_\{\\min\}\}\.\(112\)The same bound applies to‖Π^s‖1→1\\\|\\hat\{\\Pi\}\_\{s\}\\\|\_\{1\\to 1\}via the analogous argument along the approximate trajectory\. ∎

We now bound the difference‖Π^s−Πs‖1→1\\\|\\hat\{\\Pi\}\_\{s\}\-\\Pi\_\{s\}\\\|\_\{1\\to 1\}, which feeds directly into piece \(B\)\.

###### Lemma 5\(Perturbation bound onΠs\\Pi\_\{s\}\)\.

Under the assumptions of Theorem[2](https://arxiv.org/html/2605.29042#Thmtheorem2),

‖Π^s−Πs‖1→1≤\(6​\|𝒵\|−4\)​k​εbmin2,\\\|\\hat\{\\Pi\}\_\{s\}\-\\Pi\_\{s\}\\\|\_\{1\\to 1\}\\leq\\frac\{\(6\|\\mathcal\{Z\}\|\-4\)k\\,\\varepsilon\}\{b\_\{\\min\}^\{2\}\},\(113\)

###### Proof\.

By the closed forms in Eq\.[95](https://arxiv.org/html/2605.29042#A1.E95)and add\-subtract telescoping along the three factors,

Π^s−Πs\\displaystyle\\hat\{\\Pi\}\_\{s\}\-\\Pi\_\{s\}=\(D^t\+k−Dt\+k\)​\(I−𝟏​b^t\+k⊤\)​D^s\+1−1⏟\(i\)\\displaystyle=\\underbrace\{\(\\hat\{D\}\_\{t\+k\}\-D\_\{t\+k\}\)\(I\-\\mathbf\{1\}\\hat\{b\}\_\{t\+k\}^\{\\top\}\)\\hat\{D\}\_\{s\+1\}^\{\-1\}\}\_\{\\text\{\(i\)\}\}\+Dt\+k​1​\(bt\+k−b^t\+k\)⊤​D^s\+1−1⏟\(ii\)\\displaystyle\\quad\+\\underbrace\{D\_\{t\+k\}\\,\\mathbf\{1\}\(b\_\{t\+k\}\-\\hat\{b\}\_\{t\+k\}\)^\{\\top\}\\,\\hat\{D\}\_\{s\+1\}^\{\-1\}\}\_\{\\text\{\(ii\)\}\}\+Dt\+k​\(I−𝟏​bt\+k⊤\)​\(D^s\+1−1−Ds\+1−1\)⏟\(iii\),\\displaystyle\\quad\+\\underbrace\{D\_\{t\+k\}\(I\-\\mathbf\{1\}b\_\{t\+k\}^\{\\top\}\)\(\\hat\{D\}\_\{s\+1\}^\{\-1\}\-D\_\{s\+1\}^\{\-1\}\)\}\_\{\\text\{\(iii\)\}\},\(114\)where in \(ii\) theII’s cancel and the rank\-one difference\(I−𝟏​b^t\+k⊤\)−\(I−𝟏​bt\+k⊤\)=𝟏​\(bt\+k−b^t\+k\)⊤\(I\-\\mathbf\{1\}\\hat\{b\}\_\{t\+k\}^\{\\top\}\)\-\(I\-\\mathbf\{1\}b\_\{t\+k\}^\{\\top\}\)=\\mathbf\{1\}\(b\_\{t\+k\}\-\\hat\{b\}\_\{t\+k\}\)^\{\\top\}remains\. We bound each piece in∥⋅∥1→1\\\|\\cdot\\\|\_\{1\\to 1\}via submultiplicativity, using the magnitude bounds from the proof of Lemma[4](https://arxiv.org/html/2605.29042#Thmlemma4)and Corollary[3](https://arxiv.org/html/2605.29042#Thmcorollary3)\.

*Piece \(i\)\.*The diagonal difference satisfies‖D^t\+k−Dt\+k‖1→1=maxz⁡\|b^t\+kz−bt\+kz\|≤‖b^t\+k−bt\+k‖1≤2​k​ε\\\|\\hat\{D\}\_\{t\+k\}\-D\_\{t\+k\}\\\|\_\{1\\to 1\}=\\max\_\{z\}\|\\hat\{b\}\_\{t\+k\}^\{z\}\-b\_\{t\+k\}^\{z\}\|\\leq\\\|\\hat\{b\}\_\{t\+k\}\-b\_\{t\+k\}\\\|\_\{1\}\\leq 2k\\varepsilon\. Combined with‖I−𝟏​b^t\+k⊤‖1→1≤\|𝒵\|−1\\\|I\-\\mathbf\{1\}\\hat\{b\}\_\{t\+k\}^\{\\top\}\\\|\_\{1\\to 1\}\\leq\|\\mathcal\{Z\}\|\-1and‖D^s\+1−1‖1→1≤1/bmin\\\|\\hat\{D\}\_\{s\+1\}^\{\-1\}\\\|\_\{1\\to 1\}\\leq 1/b\_\{\\min\},

‖\(i\)‖1→1≤2​k​ε⋅\(\|𝒵\|−1\)⋅1bmin=2​\(\|𝒵\|−1\)​k​εbmin\.\\\|\\text\{\(i\)\}\\\|\_\{1\\to 1\}\\leq 2k\\varepsilon\\cdot\(\|\\mathcal\{Z\}\|\-1\)\\cdot\\frac\{1\}\{b\_\{\\min\}\}=\\frac\{2\(\|\\mathcal\{Z\}\|\-1\)\\,k\\varepsilon\}\{b\_\{\\min\}\}\.\(115\)
*Piece \(ii\)\.*The rank\-one matrix𝟏​\(bt\+k−b^t\+k\)⊤\\mathbf\{1\}\(b\_\{t\+k\}\-\\hat\{b\}\_\{t\+k\}\)^\{\\top\}has columnjjequal to\(bt\+kj−b^t\+kj\)​𝟏\(b\_\{t\+k\}^\{j\}\-\\hat\{b\}\_\{t\+k\}^\{j\}\)\\mathbf\{1\}, whose 1\-norm is\|𝒵\|⋅\|bt\+kj−b^t\+kj\|\|\\mathcal\{Z\}\|\\cdot\|b\_\{t\+k\}^\{j\}\-\\hat\{b\}\_\{t\+k\}^\{j\}\|\. Hence‖𝟏​\(bt\+k−b^t\+k\)⊤‖1→1≤\|𝒵\|​‖bt\+k−b^t\+k‖∞≤2​\|𝒵\|​k​ε\\\|\\mathbf\{1\}\(b\_\{t\+k\}\-\\hat\{b\}\_\{t\+k\}\)^\{\\top\}\\\|\_\{1\\to 1\}\\leq\|\\mathcal\{Z\}\|\\,\\\|b\_\{t\+k\}\-\\hat\{b\}\_\{t\+k\}\\\|\_\{\\infty\}\\leq 2\|\\mathcal\{Z\}\|k\\varepsilon\. Combined with‖Dt\+k‖1→1≤1\\\|D\_\{t\+k\}\\\|\_\{1\\to 1\}\\leq 1and‖D^s\+1−1‖1→1≤1/bmin\\\|\\hat\{D\}\_\{s\+1\}^\{\-1\}\\\|\_\{1\\to 1\}\\leq 1/b\_\{\\min\},

‖\(ii\)‖1→1≤1⋅2​\|𝒵\|​k​ε⋅1bmin=2​\|𝒵\|​k​εbmin\.\\\|\\text\{\(ii\)\}\\\|\_\{1\\to 1\}\\leq 1\\cdot 2\|\\mathcal\{Z\}\|k\\varepsilon\\cdot\\frac\{1\}\{b\_\{\\min\}\}=\\frac\{2\|\\mathcal\{Z\}\|\\,k\\varepsilon\}\{b\_\{\\min\}\}\.\(116\)
*Piece \(iii\)\.*The diagonal differenceD^s\+1−1−Ds\+1−1\\hat\{D\}\_\{s\+1\}^\{\-1\}\-D\_\{s\+1\}^\{\-1\}has entries

1b^s\+1z−1bs\+1z=bs\+1z−b^s\+1zbs\+1z​b^s\+1z\.\\frac\{1\}\{\\hat\{b\}\_\{s\+1\}^\{z\}\}\-\\frac\{1\}\{b\_\{s\+1\}^\{z\}\}=\\frac\{b\_\{s\+1\}^\{z\}\-\\hat\{b\}\_\{s\+1\}^\{z\}\}\{b\_\{s\+1\}^\{z\}\\hat\{b\}\_\{s\+1\}^\{z\}\}\.\(117\)Usingbs\+1z,b^s\+1z≥bminb\_\{s\+1\}^\{z\},\\hat\{b\}\_\{s\+1\}^\{z\}\\geq b\_\{\\min\}from Assumption \(3\),

‖D^s\+1−1−Ds\+1−1‖1→1≤maxz⁡\|bs\+1z−b^s\+1z\|bs\+1z​b^s\+1z≤2​k​εbmin2\.\\\|\\hat\{D\}\_\{s\+1\}^\{\-1\}\-D\_\{s\+1\}^\{\-1\}\\\|\_\{1\\to 1\}\\leq\\max\_\{z\}\\frac\{\|b\_\{s\+1\}^\{z\}\-\\hat\{b\}\_\{s\+1\}^\{z\}\|\}\{b\_\{s\+1\}^\{z\}\\hat\{b\}\_\{s\+1\}^\{z\}\}\\leq\\frac\{2k\\varepsilon\}\{b\_\{\\min\}^\{2\}\}\.\(118\)Combined with‖Dt\+k‖1→1≤1\\\|D\_\{t\+k\}\\\|\_\{1\\to 1\}\\leq 1and‖I−𝟏​bt\+k⊤‖1→1≤\|𝒵\|−1\\\|I\-\\mathbf\{1\}b\_\{t\+k\}^\{\\top\}\\\|\_\{1\\to 1\}\\leq\|\\mathcal\{Z\}\|\-1,

‖\(iii\)‖1→1≤1⋅\(\|𝒵\|−1\)⋅2​k​εbmin2=2​\(\|𝒵\|−1\)​k​εbmin2\.\\\|\\text\{\(iii\)\}\\\|\_\{1\\to 1\}\\leq 1\\cdot\(\|\\mathcal\{Z\}\|\-1\)\\cdot\\frac\{2k\\varepsilon\}\{b\_\{\\min\}^\{2\}\}=\\frac\{2\(\|\\mathcal\{Z\}\|\-1\)\\,k\\varepsilon\}\{b\_\{\\min\}^\{2\}\}\.\(119\)
*Combining\.*By the triangle inequality applied to Eq\.[114](https://arxiv.org/html/2605.29042#A1.E114), and using1/bmin≤1/bmin21/b\_\{\\min\}\\leq 1/b\_\{\\min\}^\{2\}sincebmin≤1b\_\{\\min\}\\leq 1,

‖Π^s−Πs‖1→1\\displaystyle\\\|\\hat\{\\Pi\}\_\{s\}\-\\Pi\_\{s\}\\\|\_\{1\\to 1\}≤2​\(\|𝒵\|−1\)​k​εbmin\+2​\|𝒵\|​k​εbmin\+2​\(\|𝒵\|−1\)​k​εbmin2\\displaystyle\\leq\\frac\{2\(\|\\mathcal\{Z\}\|\-1\)\\,k\\varepsilon\}\{b\_\{\\min\}\}\+\\frac\{2\|\\mathcal\{Z\}\|\\,k\\varepsilon\}\{b\_\{\\min\}\}\+\\frac\{2\(\|\\mathcal\{Z\}\|\-1\)\\,k\\varepsilon\}\{b\_\{\\min\}^\{2\}\}≤\(6​\|𝒵\|−4\)​k​εbmin2\.\\displaystyle\\leq\\frac\{\(6\|\\mathcal\{Z\}\|\-4\)\\,k\\varepsilon\}\{b\_\{\\min\}^\{2\}\}\.\(120\)∎

We can now bound piece \(B\)\. By submultiplicativity,

‖\(B\)s‖2≤‖g‖∞⋅‖Π^s−Πs‖1→1⋅‖S^s‖∞→1⋅‖G^s‖2→∞\.\\\|\(B\)\_\{s\}\\\|\_\{2\}\\leq\\\|g\\\|\_\{\\infty\}\\cdot\\\|\\hat\{\\Pi\}\_\{s\}\-\\Pi\_\{s\}\\\|\_\{1\\to 1\}\\cdot\\\|\\hat\{S\}\_\{s\}\\\|\_\{\\infty\\to 1\}\\cdot\\\|\\hat\{G\}\_\{s\}\\\|\_\{2\\to\\infty\}\.\(121\)Combining Lemma[5](https://arxiv.org/html/2605.29042#Thmlemma5)with the magnitude bounds from Proposition[3](https://arxiv.org/html/2605.29042#Thmproposition3),

‖\(B\)s‖2≤LV⋅\(6​\|𝒵\|−4\)​k​εbmin2⋅2⋅Gπ=2​\(6​\|𝒵\|−4\)​k​ε​LV​Gπbmin2\.\\\|\(B\)\_\{s\}\\\|\_\{2\}\\leq L\_\{V\}\\cdot\\frac\{\(6\|\\mathcal\{Z\}\|\-4\)\\,k\\varepsilon\}\{b\_\{\\min\}^\{2\}\}\\cdot 2\\cdot G\_\{\\pi\}=\\frac\{2\(6\|\\mathcal\{Z\}\|\-4\)\\,k\\varepsilon\\,L\_\{V\}\\,G\_\{\\pi\}\}\{b\_\{\\min\}^\{2\}\}\.\(122\)

#### A\.11\.8Assembly: combining the four pieces

We combine the bounds on pieces \(A\), \(B\), \(C\), \(D\), together with the bound‖Πs‖1→1≤\(\|𝒵\|−1\)/bmin\\\|\\Pi\_\{s\}\\\|\_\{1\\to 1\}\\leq\(\|\\mathcal\{Z\}\|\-1\)/b\_\{\\min\}from Lemma[4](https://arxiv.org/html/2605.29042#Thmlemma4), to produce the final bound stated in Theorem[2](https://arxiv.org/html/2605.29042#Thmtheorem2)\.

##### Per\-summand bounds\.

Substituting Lemma[4](https://arxiv.org/html/2605.29042#Thmlemma4)into Eqs\. 80, 83, and 87:

‖\(D\)s‖2\\displaystyle\\\|\(D\)\_\{s\}\\\|\_\{2\}≤2​\(\|𝒵\|−1\)​LV​Lπ​‖o^s−os‖∞bmin,\\displaystyle\\leq\\frac\{2\(\|\\mathcal\{Z\}\|\-1\)L\_\{V\}L\_\{\\pi\}\\\|\\hat\{o\}\_\{s\}\-o\_\{s\}\\\|\_\{\\infty\}\}\{b\_\{\\min\}\},\(123\)‖\(A\)s‖2\\displaystyle\\\|\(A\)\_\{s\}\\\|\_\{2\}≤4​\(\|𝒵\|−1\)​k​ε​Lg​Gπbmin,\\displaystyle\\leq\\frac\{4\(\|\\mathcal\{Z\}\|\-1\)k\\varepsilon L\_\{g\}G\_\{\\pi\}\}\{b\_\{\\min\}\},\(124\)‖\(C\)s‖2\\displaystyle\\\|\(C\)\_\{s\}\\\|\_\{2\}≤6​\(\|𝒵\|−1\)​k​ε​LV​Gπbmin,\\displaystyle\\leq\\frac\{6\(\|\\mathcal\{Z\}\|\-1\)k\\varepsilon L\_\{V\}G\_\{\\pi\}\}\{b\_\{\\min\}\},\(125\)‖\(B\)s‖2\\displaystyle\\\|\(B\)\_\{s\}\\\|\_\{2\}≤2​\(6​\|𝒵\|−4\)​k​ε​LV​Gπbmin2\([5](https://arxiv.org/html/2605.29042#Thmlemma5)\)\.\\displaystyle\\leq\\frac\{2\(6\|\\mathcal\{Z\}\|\-4\)k\\varepsilon L\_\{V\}G\_\{\\pi\}\}\{b\_\{\\min\}^\{2\}\}\\quad\\text\{\(\\ref\{lem:Pi\-difference\}\)\}\.\(126\)

##### Sum across the window\.

Summing each piece acrosss=t,…,t\+k−1s=t,\\ldots,t\+k\-1\(withkksummands\), and using‖o^s−os‖∞≤supt‖o^t−ot‖∞\\\|\\hat\{o\}\_\{s\}\-o\_\{s\}\\\|\_\{\\infty\}\\leq\\sup\_\{t\}\\\|\\hat\{o\}\_\{t\}\-o\_\{t\}\\\|\_\{\\infty\}:

∑s‖\(D\)s‖2\\displaystyle\\sum\_\{s\}\\\|\(D\)\_\{s\}\\\|\_\{2\}≤2​\(\|𝒵\|−1\)​k​LV​Lπ​supt‖o^t−ot‖∞bmin,\\displaystyle\\leq\\frac\{2\(\|\\mathcal\{Z\}\|\-1\)kL\_\{V\}L\_\{\\pi\}\\sup\_\{t\}\\\|\\hat\{o\}\_\{t\}\-o\_\{t\}\\\|\_\{\\infty\}\}\{b\_\{\\min\}\},\(127\)∑s‖\(A\)s‖2\\displaystyle\\sum\_\{s\}\\\|\(A\)\_\{s\}\\\|\_\{2\}≤4​\(\|𝒵\|−1\)​k2​ε​Lg​Gπbmin,\\displaystyle\\leq\\frac\{4\(\|\\mathcal\{Z\}\|\-1\)k^\{2\}\\varepsilon L\_\{g\}G\_\{\\pi\}\}\{b\_\{\\min\}\},\(128\)∑s‖\(C\)s‖2\\displaystyle\\sum\_\{s\}\\\|\(C\)\_\{s\}\\\|\_\{2\}≤6​\(\|𝒵\|−1\)​k2​ε​LV​Gπbmin,\\displaystyle\\leq\\frac\{6\(\|\\mathcal\{Z\}\|\-1\)k^\{2\}\\varepsilon L\_\{V\}G\_\{\\pi\}\}\{b\_\{\\min\}\},\(129\)∑s‖\(B\)s‖2\\displaystyle\\sum\_\{s\}\\\|\(B\)\_\{s\}\\\|\_\{2\}≤2​\(6​\|𝒵\|−4\)​k2​ε​LV​Gπbmin2\.\\displaystyle\\leq\\frac\{2\(6\|\\mathcal\{Z\}\|\-4\)k^\{2\}\\varepsilon L\_\{V\}G\_\{\\pi\}\}\{b\_\{\\min\}^\{2\}\}\.\(130\)

##### Final assembly\.

By Eq\. 74,‖∇θLapprox−∇θLtrue‖2\\\|\\nabla\_\{\\theta\}L\_\{\\mathrm\{approx\}\}\-\\nabla\_\{\\theta\}L\_\{\\mathrm\{true\}\}\\\|\_\{2\}is bounded by the sum of the four\. Using1/bmin≤1/bmin21/b\_\{\\min\}\\leq 1/b\_\{\\min\}^\{2\}\(sincebmin≤1b\_\{\\min\}\\leq 1\) to put all terms on a common denominator, andmax⁡\(LV,Lg\)\\max\(L\_\{V\},L\_\{g\}\)to absorb both Lipschitz constants, theGπG\_\{\\pi\}contributions from \(A\), \(B\), \(C\) combine as

\[4​\(\|𝒵\|−1\)\+6​\(\|𝒵\|−1\)\+2​\(6​\|𝒵\|−4\)\]​k2​ε​max⁡\(LV,Lg\)​Gπbmin2=\(22​\|𝒵\|−18\)​k2​ε​max⁡\(LV,Lg\)​Gπbmin2,\\frac\{\\big\[4\(\|\\mathcal\{Z\}\|\-1\)\+6\(\|\\mathcal\{Z\}\|\-1\)\+2\(6\|\\mathcal\{Z\}\|\-4\)\\big\]\\,k^\{2\}\\varepsilon\\,\\max\(L\_\{V\},L\_\{g\}\)\\,G\_\{\\pi\}\}\{b\_\{\\min\}^\{2\}\}=\\frac\{\(22\|\\mathcal\{Z\}\|\-18\)\\,k^\{2\}\\varepsilon\\,\\max\(L\_\{V\},L\_\{g\}\)\\,G\_\{\\pi\}\}\{b\_\{\\min\}^\{2\}\},\(131\)while theLπL\_\{\\pi\}contribution from \(D\) is bounded by2​\(\|𝒵\|−1\)​k​LV​Lπ​supt‖o^t−ot‖∞bmin2\\frac\{2\(\|\\mathcal\{Z\}\|\-1\)kL\_\{V\}L\_\{\\pi\}\\sup\_\{t\}\\\|\\hat\{o\}\_\{t\}\-o\_\{t\}\\\|\_\{\\infty\}\}\{b\_\{\\min\}^\{2\}\}\.

Combining,

‖∇θLapprox−∇θLtrue‖2≤\(22​\|𝒵\|−18\)⋅k⋅max⁡\(LV,Lg\)bmin2​\[k​ε​Gπ\+Lπ​supt‖o^t−ot‖∞\]\.\\big\\\|\\nabla\_\{\\theta\}L\_\{\\mathrm\{approx\}\}\-\\nabla\_\{\\theta\}L\_\{\\mathrm\{true\}\}\\big\\\|\_\{2\}\\leq\\frac\{\(22\|\\mathcal\{Z\}\|\-18\)\\cdot k\\cdot\\max\(L\_\{V\},L\_\{g\}\)\}\{b\_\{\\min\}^\{2\}\}\\Big\[k\\varepsilon G\_\{\\pi\}\+L\_\{\\pi\}\\sup\_\{t\}\\\|\\hat\{o\}\_\{t\}\-o\_\{t\}\\\|\_\{\\infty\}\\Big\]\.\(132\)This completes the proof of Theorem[2](https://arxiv.org/html/2605.29042#Thmtheorem2)\.

### A\.12Additional Training and Diagnostic Figures

The main Avalon comparison in Figure[1](https://arxiv.org/html/2605.29042#A1.F1)uses a 3\-seed evaluation shared by PPO, BBM, and D\-BOS \(42,43,4442,43,44\)\. Estimated\-observation Avalon runs are also included in the graphs\. We noticed a performance boost with using the estimated\-observation mode as our agent is now able to shape multiple agents at the same time\.

![Refer to caption](https://arxiv.org/html/2605.29042v1/figures/avalon_runs_eval.png)Figure 1:Avalon Evaluation metrics over time\. The estimated runs dip much earlier compared to the other methods, but regain performance over time to end with a higher win rate, suggesting that shaping multiple observers probably sacrifices performance earlier in the runs for better rewards later\.We further show in Table[4](https://arxiv.org/html/2605.29042#A1.T4), how the Avalon Estimated\-observations runs perform per seed\. We notice that the estimated observation mode consistently outperforms baseline showcasing its effectiveness in maintaining a better win rate than baselines\.

Table 4:Per\-seed evaluation win rates in Avalon\. While hidden\-role environments naturally exhibit high inter\-seed variance, breaking down the performance by independent runs demonstrates that D\-BOS consistently outperforms baselines across initializations\. \(Note: D\-BOSk=1k=1Estimated significantly dominates on Seed 44\)\.Figure[2](https://arxiv.org/html/2605.29042#A1.F2)showcases the training graphs for the Rescue\-the\-General environment for multiple different methods\. We can see that D\-BOS sustains performance for a longer period of time compared to baselines\. All methods eventually drop in performance due to the environment dynamics, where blue ends up winning\. We also notice a drop in performance proportional to the value ofkkas suggested by Theorem[2](https://arxiv.org/html/2605.29042#Thmtheorem2)\.

![Refer to caption](https://arxiv.org/html/2605.29042v1/figures/pportg.png)

\(a\) PPO \(No shaping\)

![Refer to caption](https://arxiv.org/html/2605.29042v1/figures/bbmrtg.png)

\(b\) BBM

![Refer to caption](https://arxiv.org/html/2605.29042v1/figures/dbosk1rtg.png)

\(c\) D\-BOSk=1k=1

![Refer to caption](https://arxiv.org/html/2605.29042v1/figures/dbosk3rtg.png)

\(d\) D\-BOSk=3k=3

![Refer to caption](https://arxiv.org/html/2605.29042v1/figures/dbosk5rtg.png)

\(e\) D\-BOSk=5k=5

Figure 2:Rescue\-the\-General Training graphs over time\. We observe that D\-BOS withk=1k=1sustains performance significantly longer than baseline methods before the characteristic performance drop at 120M steps\.![Refer to caption](https://arxiv.org/html/2605.29042v1/figures/Multi-Agent_Coin_Game.png)Figure 3:This figure shows the graphs for the Multi\-Agent Coin Game evaluation across 3 seeds\. We can see that in this method, it becomes quite hard for D\-BOS to shape beliefs when the role is changing every episode\. However, this serves as a stress test, and it motivates future work as D\-BOS shows potential in such environments
### A\.13Compute and Hyperparameters

All methods within an environment use the same rollout budget, optimizer family, policy architecture, and seed set\. RTG uses the CNN policy path with 64 parallel environments, rollout length 16, PPO learning rate2\.5×10−42\.5\\times 10^\{\-4\}, discountγ=0\.99\\gamma=0\.99, GAEλ=0\.95\\lambda=0\.95, and checkpoints/evaluation points every1010M environment steps\. The main RTG runs use150150million environment steps per seed\. Avalon5 and CoinGame use the MLP policy path with 16 parallel environments, rollout length 32, two PPO epochs, two minibatches, learning rate5×10−45\\times 10^\{\-4\}, discountγ=0\.99\\gamma=0\.99, GAEλ=0\.95\\lambda=0\.95, and a 20M\-step training budget\. Avalon uses a hidden dimension 128 and an entropy coefficient of 0\.02; CoinGame uses hidden dimension of 64 and an entropy coefficient of 0\.01\.

We ran the experiments on A100\-40GB, A100\-80GB, and A30 GPUs\. RTG was the most expensive setting, taking roughly two days per method/seed at the final budget\. Avalon and CoinGame runs were substantially lighter, typically completing overnight for each method/seed, depending on the queue and GPU type\. The dominant compute difference is across environments rather than across PPO, BBM, and D\-BOS within the same environment\.

##### Shaping\-strength settings\.

The scalar shaping coefficient is not directly comparable across BBM and D\-BOS\. BBM scales an auxiliary belief\-manipulation reward, while D\-BOS scales a belief\-gradient correction\. We therefore select the shaping strength separately for each shaping mechanism while keeping the environment, architecture, optimizer, rollout budget, and seeds fixed\. In Avalon, BBM usesλ=0\.5\\lambda=0\.5, matching the setting reported in the BBM reference paper\[[2](https://arxiv.org/html/2605.29042#bib.bib3)\]and the best stable value from our quick validation runs\. The final Avalon D\-BOS runs useλ=1\\lambda=1, which gave the most reliable behavior in our tuning runs\. In CoinGame, both BBM and D\-BOS useλ=0\.5\\lambda=0\.5; in RTG, D\-BOS and BBM both useλ=0\.5\\lambda=0\.5\. These coefficients should be interpreted as method\-specific tuning parameters rather than matched parameters

### A\.14Broader Impact and Societal Considerations

D\-BOS provides agents with the ability to influence what others believe\. While we study this capability in controlled game environments, the underlying mechanism of optimizing actions to shape observer posteriors has a dual\-use potential\. On the positive side, belief\-aware agents can improve coordination in human\-robot teaming, make autonomous systems more legible to human partners, and enable more effective communication under information asymmetry\. On the negative side, the same mechanism could in principle be applied to train agents that systematically deceive human users or manipulate beliefs in adversarial settings\. We note that D\-BOS operates within a fixed game structure with known role sets and does not generalize to open\-ended deception in natural language or unconstrained environments\. Nevertheless, as belief\-shaping methods mature, careful attention to deployment contexts and the development of counter\-deception methods will be important\. While we do test in an adversarial setting, our goal is to eventually use our method for better cooperation amongst humans and robots and do not condone the misuse of belief\-based opponent shaping\.

### A\.15LLM Usage

We used large language models as a writing and editing aid during manuscript preparation, including assistance with prose drafting, LaTeX formatting, and proof presentation and formatting\. All technical content, mathematical derivations, experimental design, implementation, and scientific claims are the original work of the authors\. We referred to some help from LLMs in implementing and refining our codebase, but LLMs were not an important part of the research, nor did they contribute any technical details integral to our methods\.