Paper deep dive

Counterfactual Shapley Credit Assignment

Mingxuan Li, Kaizhan-Lee, Elias Bareinboim

Year: 2026Venue: arXiv preprintArea: cs.LGType: PreprintEmbeddings: 114

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%

Last extracted: 7/21/2026, 4:25:39 AM

Summary

The paper introduces Counterfactual Shapley Credit Assignment, a framework for solving the Credit Assignment Problem in Reinforcement Learning using causal theory. It utilizes Counterfactual Shapley Values (ϕ-values) to attribute credit to actions based on their causal contribution to rewards, distinguishing between skill and luck. The authors derive an efficient estimator for these values and propose ϕ-PPO, a policy gradient method combined with Prioritized Trajectory Replay, demonstrating superior sample efficiency in environments with sparse causality, high stochasticity, and delayed rewards.

Entities (18)

Counterfactual Shapley Credit Assignment · methodframework · 98%Counterfactual Shapley Credit Assignment · methodframework · 98%Counterfactual Shapley Value · conceptmathematical-tool · 97%Credit Assignment Problem · problem · 97%Counterfactual Shapley Value · concept · 96%PPO · algorithm · 96%$\phi$-PPO · algorithm · 95%Credit Assignment Problem · problem · 95%Prioritized Trajectory Replay · technique · 94%Prioritized Trajectory Replay · technique · 92%Structural Causal Models · theoretical-framework · 92%Structural Causal Models · framework · 90%Combinatorial Lock · benchmarkenvironment · 88%PPO · baseline-algorithm · 88%REINFORCE · baseline-algorithm · 88%SkillLuck · benchmarkenvironment · 88%PPO · algorithm · 85%REINFORCE · algorithm · 85%

Relation Signals (15)

Counterfactual Shapley Credit Assignment → uses → Counterfactual Shapley Value

confidence 97% · attributes credit and blame via the Counterfactual Shapley Value ($ϕ$-value)

Counterfactual Shapley Credit Assignment → solves → Credit Assignment Problem

confidence 96% · The Credit Assignment Problem (CAP) is fundamental... We introduce Counterfactual Shapley Credit Assignment... A principled approach to CAP must isolate the true causal drivers

Counterfactual Shapley Credit Assignment → solves → Credit Assignment Problem

confidence 95% · We introduce Counterfactual Shapley Credit Assignment, a novel framework grounded in causal theory that attributes credit and blame... A principled approach to CAP must isolate the true causal drivers

Counterfactual Shapley Credit Assignment → uses → Counterfactual Shapley Value

confidence 95% · attributes credit and blame via the Counterfactual Shapley Value ($\phi$-value).

Counterfactual Shapley Credit Assignment → enables → PPO

confidence 94% · enabling a new class of policy gradient methods, ϕ-PPO

$\phi$-PPO → isbasedon → Counterfactual Shapley Credit Assignment

confidence 92% · enabling a new class of policy gradient methods, $\phi$-PPO

PPO → uses → Prioritized Trajectory Replay

confidence 92% · ϕ-PPO, combined with Prioritized Trajectory Replay (PTR)

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:The Credit Assignment Problem (CAP) is fundamental to developing efficient and explainable Reinforcement Learning (RL) agents. Existing frameworks, whether relying on temporal contiguity or hindsight-conditioned reward reweighting, frequently fail to attribute properly between an agent's policy (skill) and environmental stochasticity (luck). A principled approach to CAP must isolate the true causal drivers of observed outcomes from spurious correlations and environmental randomness. We introduce Counterfactual Shapley Credit Assignment, a novel framework grounded in causal theory that attributes credit and blame via the Counterfactual Shapley Value ($\phi$-value). By redistributing environmental rewards, $\phi$-values enhance temporal credit assignment across three critical dimensions: sparse causality, high stochasticity, and delayed rewards, all while preserving the optimal policy. We derive a consistent estimator that computes $\phi$-values efficiently, enabling a new class of policy gradient methods, $\phi$-PPO, combined with Prioritized Trajectory Replay (PTR). Empirical results demonstrate that $\phi$-values align precisely to the ground truth causes of task rewards with superior sample efficiency in challenging environments where prior state-of-the-art methods fail to converge.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

112,340 characters extracted from source content.

Expand or collapse full text

Counterfactual Shapley Credit Assignment Mingxuan Li, Kai-Zhan Lee, Elias Bareinboim Keywords: temporal credit assignment, counterfactual Shapley values, causal inference Summary The Credit Assignment Problem (CAP) is fundamental to developing efficient and explainable Reinforcement Learning (RL) agents. Existing frameworks, whether relying on temporal contiguity or hindsight-conditioned reward reweighting, frequently fail to attribute properly between an agent’s policy (skill) and environmental stochasticity (luck). A principled approach to CAP must isolate the true causal drivers of observed outcomes from spurious correlations and environmental randomness. We introduce Counterfactual Shapley Credit Assignment, a novel framework grounded in causal theory that attributes credit and blame via the Counterfactual Shapley Value (ϕφ-value). By redistributing environmental rewards, ϕφ-values enhance temporal credit assignment across three critical dimensions: sparse causality, high stochasticity, and delayed rewards, all while preserving the optimal policy. We derive a consistent estimator that computes ϕφ-values efficiently, enabling a new class of policy gradient methods, ϕφ-PPO, combined with Prioritized Trajectory Replay (PTR). Empirical results demonstrate that ϕφ-values align precisely to the ground truth causes of task rewards with superior sample efficiency in challenging environments where prior state-of-the-art methods fail to converge. Contribution(s) 1. We apply the Counterfactual Shapley Value (ϕφ-value) framework lee2025 to RL temporal credit assignment, showing that ϕφ-values yield a reward redistribution that preserves the optimal policy and concentrates credit on causal actions. We show that the proposed framework satisfies the four causal credit assignment criteria: (1) Causal Admissibility (2) Causal Power (3) Causal Normality and (4) Causal Effect Scaling. The four criteria together guarantee that the proposed framework allocates credits faithful to how much causal contribution each action has to the outcome compared to a baseline policy, effectively rectifying the long-standing challenges in RL temporal credit assignment: sparsity, high stochasticity and delayed rewards. Context: Prior credit assignment methods, including HCA (hindsightcredit), CCA (pmlr-v139-mesnard21a), CoCoA (meulemans2023would), RUDDER (arjona2019rudder), and Synthetic Returns (raposo2021synthetic), are not grounded in counterfactuals in the Structural Causal Model (SCM) framework (pearl2009causality; bareinboim2022pearl). 2. We derive a consistent ϕφ-value function estimator converging to the true causal contributions in probability given sufficient samples with amortized O(1)O(1) time per action and a tunable bias–variance tradeoff via λ-bootstrapping. Context: Previous work on estimating Shapley values (shapley:book1952) and ϕφ-values (lee2025) don’t consider bootstrapping with value function approximators. Thus, they usually suffer from either exponential sample complexity or biased estimation. 3. We introduce ϕφ-PPO with Prioritized Trajectory Replay (PTR) and demonstrate superior sample efficiency on the SkillLuck and Combinatorial Lock benchmarks, where prior methods either take much longer to learn or fail to converge; through ablation, we show that both ϕφ-values and PTR are necessary. Context: Compared against PPO and REINFORCE (schulman2017ppo; williams1992simple), HCA (harutyunyan2019hindsight), CCA (pmlr-v139-mesnard21a), CoCoA (meulemans2023would), QCA (mesnard2023quantile), RUDDER (arjona2019rudder), Synthetic Returns (raposo2021synthetic), and H-DICE (velu2024hindsightdice) in three classical tabular environments characterizing the challenges in temporal credit assignment. Abstract The Credit Assignment Problem (CAP) is fundamental to developing efficient and explainable Reinforcement Learning (RL) agents. Existing frameworks, whether relying on temporal contiguity or hindsight-conditioned reweighting of rewards, frequently fail to distribute credit properly between an agent’s policy (skill) and environmental stochasticity (luck). A principled approach to the CAP must isolate the causes of observed rewards from spurious correlated features and environmental randomness. We introduce Counterfactual Shapley Credit Assignment, a novel causal credit assignment framework based on the counterfactual Shapley value (ϕφ-value). By redistributing rewards, ϕφ-values enhance credit assignment across three critical dimensions: high stochasticity, sparse causality, and delayed rewards, all while theoretically preserving the original optimal policy. We derive a consistent estimator that computes each ϕφ-value in amortized constant time complexity, enabling a new class of policy gradient methods, ϕφ-PPO. Empirical results demonstrate that ϕφ-values align precisely with the ground truth causes of task rewards. Furthermore, we show its superior sample efficiency in challenging environments where prior state-of-the-art methods fail to converge. 1 Introduction Reinforcement learning (RL) agents have achieved remarkable success in domains such as healthcare (yu2020reinforcementlearninghealthcaresurvey), autonomous driving (shaoSurveyDeepReinforcement2019a), and code generation (claude2024; yang2025qwen3technicalreport), driven by advances in deep RL (mnihHumanlevelControlDeep2015a; silverMasteringGameGo2017; akkaya2019solvingcube; schrittwieserMasteringAtariGo2020; Guo_2025deepseek). As RL scales to more challenging domains with longer horizons, sparse and delayed rewards, and greater stochasticity, the long-standing Credit Assignment Problem (CAP) grows increasingly relevant: learning depends on successfully “distributing credit for success of a complex strategy among the many decisions that were involved” (minsky1961). We argue that this credit distribution must be causal: the credit each action receives should reflect its causal effect on the total discounted reward. s1s_1s2s_2⋯·ssNs_NsFs_Fs2′s_2 ⋯·ssN′s_N sF′s_F x1=0x_1=0x1=1x_1=1xN=0y=0 subarraycx_N=0\\ y=0 subarray∀xN,y∼Bern⁡(0.5) subarrayc∀ x_N,\\ y (0.5) subarray“Luck"xN=1y=1.0 subarraycx_N=1\\ y=1.0 subarray“Skill" Figure 1: Among all tested methods, only causal credit assignment correctly distinguishes Skill from Luck. Left: A SkillLuck MDP under a uniform random policy. The first action selects the branch; on the top branch, xN=1x_N=1 yields reward 11 with certainty (“Skill,” red) while xN=0x_N=0 yields 0 (gray). On the bottom branch, the reward is drawn from Bern(0.5)Bern(0.5) regardless of xNx_N (“Luck,” blue). Center: Only our causal credit assignment assigns more credit to the first action on the Skill trajectory (x1=0x_1=0) than on the Luck trajectory (x1=1x_1=1). Right: On the Luck trajectory, xNx_N has no causal effect on the reward. Only the advantage and our method correctly assign zero credit to xNx_N. However, locating the true causes of the rewards is challenging (pignatelli2024creditsurvey). In Figure 1, we construct a simple MDP to reflect this intricate nature of CAP. Under a uniform random policy, the agent’s first action determines which branch it follows. On the top branch, the last action determines the reward: one choice yields reward 11 with certainty (“Skill,” red) while the other yields 0 (gray). On the bottom branch, the reward is 0 or 11 with equal probability regardless of the last action (“Luck,” blue). Thus, a good credit assignment method should assign bigger positive credit to both the first and last actions on Skill trajectory than those on Luck, since changing either one would have altered the return distribution. On the Luck trajectory, the last action has no causal effect on the return and should receive zero credit. Surprisingly, as we show in Figure 1, none of the prominent existing methods produces the fully correct credit assignment (see Appendix G for a detailed discussion). Humans, on the other hand, routinely perform credit assignment which does not seem to be challenging as it appears to machines. One possible reason is that we are endowed with causal reasoning capabilities that enable us to allocate credit counterfactually. Chess masters, for instance, replay key positions after every game, analyzing what would have happened under different moves. As kasparov2007life writes, “it is so important to question success as vigorously as you question failure.” Structural causal models (SCMs) (pearl2009causality; bareinboim2022pearl) formalize this type of counterfactual reasoning: given an observed trajectory, we can simulate the outcome under a different action at any step while holding all other factors fixed, isolating the causal effect of that decision. This type of counterfactual analysis lays the foundation for a fine-grained attribution for individual actions in each trajectory regardless of delayed effect, stochasticity and sparsity of the reward signals. In this work, building on the Counterfactual Shapley Value (ϕφ-value) framework of lee2025, we distribute the total causal effect across actions using Shapley values (shapley:book1952), which provide the unique allocation satisfying efficiency, symmetry, and null-player axioms. The resulting ϕφ-MDP replaces the environment’s reward signal with per-step ϕφ-values, providing dense causal learning signals even when the original reward is delayed or sparse. We prove this redistribution preserves the optimal policy (Theorem 3.7) and derive a consistent estimator computing all T values from a single coalition sample in O(T)O(T) time (Theorem 4.2). We integrate these into ϕφ-PPO, which replaces per-step rewards with ϕφ-values and uses Prioritized Trajectory Replay (PTR). PTR selects subtrajectories by causal importance, in contrast to PER (schaul2015per) which prioritizes individual transitions by TD error. Our contributions are summarized as follows. • Credit Assignment via ϕφ-values. We show that credit assignment via ϕφ-values is equivalent to a reward redistribution that preserves the optimal policy and spikes only on causal actions. • Tractable ϕφ-value Estimation. We propose a consistent ϕφ-value estimator that achieves linear time complexity, with a tunable bias–variance tradeoff via λ-bootstrapping. • Efficient and Explainable Policy Optimization. We propose ϕφ-PPO and demonstrate its strong empirical performance in several challenging credit assignment testbeds. 2 Preliminaries In this section, we establish foundational concepts to facilitate our discussion. Throughout the paper, we use uppercase letters to denote random variables (X), lowercase for their realizations (x) and bold letters for sets (V). 2.1 Structural Causal Models and MDPs Structural Causal Models (SCMs) lay the mathematical foundations for counterfactual reasoning needed to isolate causal contributions (bareinboim2022pearl). Definition 2.1 (Structural Causal Model). An SCM is ℳ=⟨,,ℱ,P()⟩M= ,U,F,P(U) where V is endogenous variables, U is exogenous variables, ℱ=fiF=\f_i\ are structural equations Vi=fi(i,i)V_i=f_i(Pa_i,U_i), and P()P(U) is exogenous distribution. Under this definition, the counterfactual V()V_x(u) is the value of V when X is set to x while =U=u. Then we cast MDPs as SCMs to ground the credit assignment discussion with causal semantics. Definition 2.2 (MDP-SCM). An MDP-SCM is an SCM with endogenous variables =St,Xt,Ytt=1T∪YV=\S_t,X_t,Y_t\_t=1^T∪\Y\ (states, actions, per-step rewards, and outcome Y=fY(Y1:T)Y=f_Y(Y_1:T)), mutually independent exogenous variables =USt,UXt,UYtt=1TU=\U_S_t,U_X_t,U_Y_t\_t=1^T, and structural equations defining system dynamics: S1=fS(US1),St+1=fS(St,Xt,USt+1),Xt=π(St,UXt),Yt=r(St,Xt,UYt)S_1=f_S(U_S_1),S_t+1=f_S(S_t,X_t,U_S_t+1),X_t=π(S_t,U_X_t),\ Y_t=r(S_t,X_t,U_Y_t). We use P(S)P(S) to denote the initial state distribution induced by US1U_S_1 and the discounted total reward as the outcome Y=∑tγt−1YtY= _tγ^t-1Y_t. Value functions V(s)V(s), Q-values Q(s,x)Q(s,x), and advantages A(s,x)A(s,x) under MDP-SCM follow the standard RL definitions (sutton2018, Sec. 3.1). 2.2 Policy Gradients The goal of reinforcement learning is to find the policy that maximizes the cumulative reward (outcome), π∗=arg⁡maxπ⁡τ∼ℳπ[Y],π^*= _πE_τ ^π[Y], where trajectory τ∼ℳπτ ^π is sampled from the environment MDP ℳπM^π under policy π. Optimizing this objective with respect to a parameterized policy πθ _θ leads to the basic form of policy gradients (williams1992simple), [∑t≥0γt∇θlog⁡π(xt|st)(∑t′≥tγt′−tYt′−V(st))] [ _t≥ 0γ^t _θ π(x_t|s_t) ( _t ≥ tγ^t -tY_t -V(s_t) ) ] (1) where V(st)=[∑t′≥tγt′−tYt′|st]V(s_t)=E [ _t ≥ tγ^t -tY_t |s_t ] is the value function. Here it serves as a baseline with respect to which the advantage of taking the specific action xtx_t instead of others is strengthened. Subtracting the baseline will not bias the gradient as long as the baseline is a function of state sts_t. Modern policy gradient methods use generalized advantages (schulmanHighDimensionalContinuousControl2016a) and gradient clipping (schulman2017ppo) to reduce variance. In this work, we base our learning algorithm on proximal policy gradient (PPO) (schulman2017ppo), whose objective is to maximize the following, min⁡(rt(θ)A^t,clip(rt(θ),1−ϵclip,1+ϵclip)A^t) (r_t(θ) A_t,\;clip(r_t(θ),1- _clip,1+ _clip) A_t ) (2) where A^t=∑ℓ=0T−t+1(γλ)ℓδt+ℓ,δt=Yt+γV(st+1)−V(st) A_t= _ =0^T-t+1(γλ) _t+ ,\ _t=Y_t+γ V(s_t+1)-V(s_t) is the generalized advantage and rt(θ)=πθ(xt|st)πθold(xt|st)r_t(θ)= _θ(x_t|s_t) _ _old(x_t|s_t) is the importance ratio between the current policy distribution and the previous policy collecting the data. 2.3 Counterfactual Shapley Values Shapley values (shapley1953) fairly distribute credit among players in cooperative games. Given players X and value function f:2→ℝf:2^X , a coalition ⊆Z is a subset of players, and f()f(Z) measures their joint contribution. The Shapley value ϕt _t quantifies player XtX_t’s fair share of the total value f()−f(∅)f(X)-f( ): ϕt=∑⊆∖Xt||!(T−||−1)!T![f(∪Xt)−f()]. _t= _Z \X_t\ |Z|!(T-|Z|-1)!T! [f(Z∪\X_t\)-f(Z) ]. (3) Shapley values satisfy desirable properties (shapley1953), including efficiency: ∑tϕt=f()−f(∅) _t _t=f(X)-f( ). For credit assignment, actions =X1,…,XTX=\X_1,…,X_T\ are players, and given trajectory τ=(s1:T,x1:T,y1:T)τ=(s_1:T,x_1:T,y_1:T) (the evidence for counterfactual reasoning), the Shapley value ϕt _t quantifies how much XtX_t contributed to outcome Y. Causal Contributions. We use counterfactual natural total effect (lee2025) to measure a set of actions’ causal contributions to the outcome. It is the expected difference between the observed outcome and a counterfactual outcome where a subset of actions are replaced. “Natural” means the comparison uses the posterior P(∣τ)P(U τ) rather than the prior, ensuring the counterfactual is consistent with the observed trajectory: f() f(Z) =NTE(,Y∣τ)=′∼P(),∼P(∣τ)[Y()−Y(′)()], =NTE(Z,Y τ)=E_ subarraycu P(U),u P(U τ) subarray [Y(u)-Y_Z(u )(u) ], (4) where Y()Y(u) is the observed outcome and Y(′)()Y_Z(u )(u) is the counterfactual with coalition actions replaced by baseline alternatives (′)Z(u ) sampled from a baseline policy πbase _base (Sec. 3.1), while exogenous u is fixed. Kernel Formulation. The standard Shapley formula sums over T!T! permutations; the kernel formulation (lundberg2017) sums over 2T2^T coalitions, enabling amortization (Section 4). Let ∈0,1Tz∈\0,1\^T denote the coalition mask (zt=1z_t=1 iff Xt∈X_t ): ϕt=∑∈0,1Tκt()⋅f(), _t= _z∈\0,1\^T _t(z)· f(z), (5) where ||=∑tzt|z|= _tz_t and κt()=1T(T−1||−1) _t(z)= 1T T-1|z|-1 if zt=1z_t=1 while κt()=−1T(T−1||) _t(z)=- 1T T-1|z| if zt=0z_t=0. 3 Counterfactual Credit Assignment MDP MMrewards YtY_tϕφ-MDP ℳπϕM^φ_πrewards rπϕr^φ_πRedistribute RewardsSection 3.2Estimationτ∼(M,π)τ (M,π)τ^zϕ^t φ_tCounterfactual Sim.Section 3.1Credit AssignmentSection 4estimates rπϕr^φ_π Figure 2: Our counterfactual Shapley values assigns causal credits to each action via reward redistribution. Top: The MDP M is transformed into ϕφ-MDP ℳπϕM^φ_π by redistributing rewards YtY_t into rπϕ(s,x)=[ϕt∣St=s,Xt=x]r^φ_π(s,x)=E[ _t S_t=s,X_t=x]. Both MDPs share the same optimal policy (Theorem 3.7). Bottom: The estimation pipeline samples a trajectory τ∼πτ π and a coalition mask ∼Q∗z Q^*, then simulates the counterfactual trajectory τ^z (Sec. 3.1). Action credits are estimated based on sampled counterfactual trajectories (Algo. 1) and used for policy optimization (Sec. 4). In the remainder of the text, we introduce our proposed causal solution to CAP. In Section 3, we formalize the credit assignment problem from a causal perspective, propose ϕφ-values as a principled solution and its related calculations in the RL context. In Section 4, we develop efficient estimators for ϕφ-values and incorporate them into policy learning. Figure 2 visualizes the conceptual structures. First, we define the Credit Assignment Problem (CAP) as a causal inference problem: only actions that causally contribute to the outcome should receive credit, proportional to their contributions. Definition 3.1 (Causal Credit Assignment, Informal). A causal credit assignment function is a mapping ϕφ that maps a trajectory, an action at a time step and a baseline policy to a real number denoting its causal contribution to the outcome observed in the trajectory, ϕ:τ×T×Π↦ℝT φ:τ×X× T× ^T (6) where τ∼ℳπτ _π is a trajectory sampled from the baseline policy and Π is the policy space. The causal assignment ϕφ should satisfy the following desiderata, 1D_1 Causal Admissibility : Non-cause actions should be assigned zero credit; 2D_2 Causal Power : Actions causing the rewards should be assigned non-zero credit; 3D_3 Causal Normality : Actions against more probable baseline policies get more credit; 4D_4 Causal Effect Scaling : Given the same baseline policy, actions affecting the outcome more should be allocated more credit. A complete formal version of the causal credit assignment desiderata is presented in App. C, Def. C.3. Here, we measure each action’s causal contribution to the outcome as the counterfactual natural total effect (Eq. 4). Unlike discounted summation of rewards, the counterfactual natural total effect is the difference between the returns under baseline policy and returns had we acted differently given an already realized trajectory. Advantage function shares a similar idea but they cannot capture counterfactual outcomes with respect to specific trajectories or quantify an action’s full potential under different action selections at other time steps. Counterfactual natural total effect provides a fair source of credit pool as the basis for allocation and these desiderata are axioms embedded in human credit assignment systems, which a causal credit assignment function should satisfy. ,D_1,D_2 together guarantee that the credit assignment function generates both sufficient and necessary allocations. That is, actions get credit if and only if they cause the outcome. ,D_3,D_4 require that the scale of the allocated credit should reflect an action’s relative contribution compared against a baseline policy. We show that counterfactual Shapley values (ϕφ-values, Eq. 5) calculated from counterfactual natural total effect satisfy the above desiderata (lee2025) and is a desirable credit assignment method. Theorem 3.2 (ϕφ-Values are Causal). ϕφ-values satisfy the causal credit assignment criteria, −D_1-D_4. Next, we present the details in calculating ϕφ-values and ϕφ-MDP, an MDP that redistributes rewards according to Counterfactual Shapley values, as our solution to the Causal Credit Assignment Problem. 3.1 Counterfactual Simulation =(0,0,0,0,0)z=(0,0,0,0,0)z1=0z_1\!=\!0z2=0z_2\!=\!0z3=0z_3\!=\!0z4=0z_4\!=\!0z5=0z_5\!=\!0s1s_1x1x_1s2s_2x2x_2s3s_3x3x_3s4s_4x4x_4s5s_5x5x_5onononononY=Y^z=Y (all reused)=(0,1,0,1,1)z=(0,1,0,1,1)z1=0z_1\!=\!0z2=1z_2\!=\!1z3=0z_3\!=\!0z4=1z_4\!=\!1z5=1z_5\!=\!1s1s_1x1x_1s2s_2x2x^z_2s3s^z_3x3x^z_3s4s_4x4x^z_4s5s^z_5x5x^z_5ononoffonoffY≠Y^z≠ Y (diverged)reuseinterventionoff-track Figure 3: Counterfactual simulation (T=5T=5). Left: =z=0, all values reused, Y=Y^z=Y. Right: =(0,1,0,1,1)z=(0,1,0,1,1); intervention at t=2t\!=\!2 causes divergence, returns on-track at t=4t\!=\!4 (s4=s4s^z_4=s_4 by chance), diverges again at t=5t\!=\!5. To compute Shapley values ϕt _t, we need a causal contribution function f:2→ℝf:2^X measuring X’s contribution under a given coalition z. The NTE from Section 2.3 averages over both posterior and prior exogenous variables; here, we condition on the observed trajectory, giving the conditional causal contribution: f()=Y−Yσ,f(z)=Y-Y_ _z, where Y is the observed return and YσY_ _z is the counterfactual return under intervention σ _z which specifies counterfactual actions based on coalition membership ∈0,1Tz∈\0,1\^T and trajectory state: σ(t)=xtzt=0,st=stx∼π(⋅∣st)zt=0,st≠stx∼πbase(⋅∣st)zt=1 _z(t)= casesx_t&z_t=0,\ s^z_t=s_t\\ x π(· s^z_t)&z_t=0,\ s^z_t≠ s_t\\ x _base(· s^z_t)&z_t=1 cases (7) where sts^z_t is the counterfactual state at time t. The baseline πbase _base defines the “default” actions for intervened time steps. Options include: uniform random (πbase(x∣s)=1/|| _base(x s)=1/|A|), measuring contribution relative to random behavior; a fixed reference policy π0 _0, measuring improvement over π0 _0; or self-baseline (πbase=π _base=π), isolating whether the specific action xtx_t matters versus what the same policy typically does. We use self-baseline throughout training (Section 5.3 illustrates the effect of alternative baselines on attributions). The intervention design rests on the following assumption. Assumption 3.3 (Counterfactual Independence). Exogenous noise is independent across steps: (St+1)St,Xt⟂(St+1)St′,Xt′(S_t+1)_S_t,X_t (S_t+1)_S _t,X _t for (St,Xt)≠(St′,Xt′)(S_t,X_t)≠(S _t,X _t), and (Xt)St⟂(Xt)St′(X_t)_S_t (X_t)_S _t for St≠St′S_t≠ S _t. This assumption does not constrain the MDP, only its SCM representation. Since any distribution can be sampled via inverse CDF with independent uniform noise, any MDP admits an SCM with independent exogenous variables and the same optimal policy; the assumption selects this representation. The consequence is simple: when parents match the observed trajectory, the observed value is the counterfactual; when parents differ, we resample. For actions (parent StS_t): when zt=0z_t=0 and st=sts^z_t=s_t, the counterfactual equals the observed xtx_t; when st≠sts^z_t≠ s_t, we resample from π(⋅∣st)π(· s^z_t). When zt=1z_t=1, we resample from πbase _base. For transitions and rewards (parents (St,Xt)(S_t,X_t)): when (st,xt)=(st,xt)(s^z_t,x^z_t)=(s_t,x_t), we reuse (st+1,yt)(s_t+1,y_t); otherwise, we resample. See Fig. 3 for a visualization of the counterfactual simulation process. The full pseudo-code is provided in Algo. 2 in appendix Sec. A; Section 4 makes exact computation tractable via coalition sampling. 3.2 Reward Redistribution With the counterfactual Shapley values, we can define a new rewarding system based on ϕt _t while keeping the system dynamics unchanged. This leads to the ϕφ-MDP, a reward-redistributed counterpart of the original MDP. Definition 3.4 (ϕφ-MDP). Given an MDP-SCM ℳM and baseline policy πbase _base, the ϕφ-MDP ℳπϕM^φ_π replaces the reward function r with the policy-induced Shapley reward: rπϕ(s,x)=τ∼π[ϕt∣St=s,Xt=x], r^φ_π(s,x)=E_τ π[ _t S_t=s,X_t=x], (8) where the expectation is over trajectories τ sampled from π, conditioned on visiting (St,Xt)=(s,x)(S_t,X_t)=(s,x). Lemma 3.5 (Gradient Equivalence). For any baseline policy πbase _base: π[∑tϕt⋅∇log⁡π(Xt∣St)]=π[Y⋅∑t∇log⁡π(Xt∣St)]E_π[ _t _t·∇ π(X_t S_t)]=E_π[Y· _t∇ π(X_t S_t)]. Remark 3.6 (Independence under self-baseline). The proof uses Y′⟂Xt∣StY X_t S_t where Y′=YσY =Y_ _1 is the full-baseline outcome. Under self-baseline, Y′Y is computed on a counterfactual trajectory using fresh action samples X1:T′∼π(⋅∣S1:T)X _1:T π(· S^1_1:T), where S1:TS^1_1:T denotes the counterfactual state sequence. Crucially, Y′Y carries no information about which specific action XtX_t was taken at the observed state StS_t: the counterfactual uses fresh action samples independent of XtX_t. The score function identity Xt∼π[∇log⁡π(Xt∣St)]=0E_X_t π[∇ π(X_t S_t)]=0 then gives [Y′∇log⁡πt]=0E[Y ∇ _t]=0. Gradient equivalence means policy gradient algorithms receive the same update direction in expectation whether maximizing returns from MDP ℳM or its dual ϕφ-MDP. Theorem 3.7 (Optimal Policy Equivalence). ϕφ-MDP preserves optimal policies as the original MDP. More specifically, arg⁡maxθ⁡πθ[∑tϕt]=arg⁡maxθ⁡πθ[Y] _θE_ _θ[ _t _t]= _θE_ _θ[Y], so ϕφ-MDP is a drop-in replacement: any policy gradient algorithm applied to the redistributed rewards converges to the same optimal policy. One caveat: the ϕφ-MDP is undiscounted (γϕ=1 _φ=1). Since the NTE game outcome Y=∑tγt−1rtY= _tγ^t-1r_t already incorporates temporal discounting, applying γ to ϕt _t would double-discount. The undiscounted ϕφ-return ∑tϕt _t _t equals Y−Y-Y^1 by Shapley efficiency. 3.3 How Causal Credit Assignment Helps Learning We have shown that the ϕφ-MDP provides a principled credit assignment while preserving the optimal policy, but does it also improve learning efficiency? As an overview, Fig. 4 illustrates each mechanism visually. Below, we present the formal conditions our method helps policy optimization under the assumption of a finite second moment. Assumption 3.8 (Finite Second Moment). ∀t,[Yt2]≤σ2∀ t,E[Y_t^2]≤σ^2. (a) Sparse CausalityTDall Tϕ k′k ϕt=0 _t=0 for non-causal actions (b) High StochasticityTDxtx_tdiff. u, high varianceϕ _tsame u, low variance Shared u cancels noise (c) Delayed RewardTDs1s_1s2s_2s3s_3s4s_4YYep1ep2ep3O(T)O(T)ϕ 1s_1s2s_2s3s_3s4s_4YYO(1)O(1) Counterfactual sim ⇒ instant credit Figure 4: Three dimensions where ϕφ-redistribution reduces variance. (a) Sparse causality. TD updates all T actions; ϕφ updates only the k′k causal actions, reducing variance by factor k′/Tk /T. (b) High stochasticity. TD compares returns under different noise realizations (high variance); ϕφ uses shared exogenous noise u, so the noise cancels in the difference. (c) Delayed reward. TD(0) propagates credit one step per episode, requiring O(T)O(T) episodes; ϕφ assigns credit to all steps in one episode via counterfactual simulation. Proposition 3.9 (Sparse Causality). Let k′=|t:ϕt≠0|k =|\t: _t≠ 0\|, σϕ2=maxt⁡Var[ϕt∇log⁡πt]σ^2_φ= _tVar[ _t∇\! _t], and ρ¯∈[0,1] ρ∈[0,1] the maximal pairwise correlation among causal terms. Then Var[g^ϕ]≤k′(1+(k′−1)ρ¯)σϕ2Var[ g^φ]≤ k (1+(k -1) ρ)\,σ^2_φ. When few actions influence the outcome (k′≪Tk T), ϕφ-values assign zero credit to non-causal actions, so only k′k terms contribute to gradient variance. The cross-correlation ρ¯ ρ is small in practice: the score function identity [∇log⁡πs∣Ss]=0E[∇\! _s S_s]=0 decorrelates terms at distinct timesteps, and ρ¯=0 ρ=0 exactly in deterministic environments (Appendix C). Proposition 3.10 (High Stochasticity). Let ′=z =z with zt=1z_t=1 and ρY=Corr[Y′,Y] _Y=Corr[Y^z ,Y^z] under shared exogenous randomness. Then Var[ϕt]∝(1−ρY)Var[ _t] (1- _Y). Proposition 3.10 holds in expectation over coalitions ∼Q∗z Q^* and trajectories. Define the effective coupling ρ¯Y=∼Q∗[Corr[Y′,Y]] ρ_Y=E_z Q^*[Corr[Y^z ,Y^z]], averaging over the optimal coalition distribution. When a counterfactual trajectory diverges (off-track), fresh noise is sampled, reducing Corr[Y′,Y]Corr[Y^z ,Y^z] for that sample. The effective coupling ρ¯Y ρ_Y is high when: (1) coalitions are small; (2) transitions are nearly deterministic; or (3) rewards depend on shared exogenous factors (unobserved confounders). Variance reduction is proportional to (1−ρ¯Y)(1- ρ_Y). Proposition 3.11 (Direct Propagation). Tabular TD(0) with terminal-only reward requires O(T)O(T) episodes for credit to reach the initial state. ϕφ-redistribution provides credit in O(1)O(1) episodes via O(TMδ,ϵ)O(TM_δ,ε) counterfactual simulations. Remark 3.12 (Propagation Complexity). For terminal-only reward: TD(0) requires O(T)O(T) episodes and O(T2)O(T^2) updates; ϕφ-redistribution requires O(1)O(1) episodes and O(TMδ,ϵ)O(TM_δ,ε) counterfactual simulations. This shows that ϕφ-values avoid the delayed-effect and inefficient propagation problem of TD(0) methods. Though n-step returns, TD(λ) and the use of replay buffers mitigate this problem (daley2025multistep, Sec. 1.2-1.3), their core credit assumption rests on temporal proximity (pignatelli2024creditsurvey). As the trajectory rolls out, reward in a distant step is deemed to be exponentially less likely caused by a given action (by the discounting factor). This clearly does not reflect an action’s true causal contribution as we have demonstrated in Fig. 1. And we will also see in experiment Sec. 5 that even with all the modern DRL techniques (schulman2017ppo; DBLP:journals/corr/SchaulQAS15prioritizedexpreplay), existing algorithms still cannot solve those seemingly naive tabular MDPs due to the implicit time proximity assumption in credit assignment. And the most important implication of Prop. 3.11 is that our proposed ϕφ-value can allocate credit in a lossless and faithful way w.r.t each action’s actual causal contribution. To sum, the “sweet spot” occurs when all three dimensions favor ϕφ-values: sparse causality (k′≪Tk T), high stochasticity (ρY≈1 _Y≈ 1), and delayed reward. When both sparsity and stochasticity benefits apply, the variance reduction factors multiply: sparsity reduces contributing terms from T to k′k , while coupled comparison reduces each term’s variance by (1−ρY)(1- _Y), giving combined ratio k′T(1−ρY) k T(1- _Y). On the other hand, there are cases when ϕφ-methods offer marginal advantage in terms of learning efficiency other than explanatory benefits over the standard TD methods when: (1) rewards are dense (k′≈Tk ≈ T); (2) environment is deterministic (ρY _Y is high); or (3) actions are rewarded immediately. 4 Estimating Counterfactual credit for Policy Optimization This section develops efficient estimators for counterfactual Shapley values with O(TMδ,ϵ)O(TM_δ,ε) total complexity, where Mδ,ϵ=σ2/((1−γ)2δϵ2)M_δ,ε=σ^2/((1-γ)^2δε^2), and integrates them into policy optimization as ϕφ-PPO. Importance Sampling Equivalence. Each coalition evaluation f()f(z) requires O(T)O(T) simulation time (Algo. 2). Computing T Shapley values independently would require M samples per value, yielding O(T2M)O(T^2M) total cost. The kernel formulation (Eq. 5) amortizes this: a single coalition evaluation updates all T values via different kernel weights κt() _t(z), reducing cost to O(TM)O(TM). Definition 4.1 (Coalition Estimator). Given samples (m)∼Qz^(m) Q and NTE f()=Y−Yf(z)=Y-Y^z, where Y≡YσY^z≡ Y_ _z is the counterfactual return, the coalition estimator is ϕ^t=1M∑m=1Mκt((m))Q((m))⋅f((m)). φ_t= 1M _m=1^M _t(z^(m))Q(z^(m))· f(z^(m)). Under a mild assumption, we can derive the variance-reduction optimal proposal distribution Q∗()Q^*(z) for coalition sampling. Theorem 4.2 (Optimal Proposal). Under Assumption 3.8, the variance-minimizing proposal is Q∗()=qk∗/(Tk)Q^*(z)=q^*_k/ Tk where k=||k=|z| and qk∗∝ckq^*_k c_k with: ck=1T(1k+1T−k)k∈1,…,T−11T2k=T c_k= cases 1T ( 1k+ 1T-k )&k∈\1,…,T-1\\\[4.0pt] 1T^2&k=T cases (9) Under Q∗Q^*, the estimator achieves (ϵ,δ)(ε,δ)-accuracy with M=O(Mδ,ϵ)M=O(M_δ,ε) samples. The optimal qk∗∝ckq^*_k c_k concentrates on extreme coalition sizes (k≈1k≈ 1 or k≈T−1k≈ T-1) where kernel weights |κt|| _t| are largest. In contrast to uniform sampling, which induces variance exponential in T (extreme sizes have probability O(2−T)O(2^-T)), the optimal proposal achieves O(1)O(1) second moment. Variance is low because Y and Y^z share exogenous noise via common random numbers (glasserman1992commonrandomnumbers): the difference f()=Y−Yf(z)=Y-Y^z isolates the effect of action choices while canceling environmental stochasticity. In practice, we also use antithetic sampling (covert2021improving): each coalition z is paired with its complement −1-z to further reduce variance. Bootstrapped Estimation. The basic estimator Def. (4.1) requires full trajectory simulation for each coalition. Bootstrapping with a learned value function V≈VπV≈ V_π reduces variance by replacing future counterfactual rewards with value estimates. We use TD-λ (sutton2018, Sec. 12.2) that interpolates between Monte Carlo and bootstrapped estimates: Gt,λ=yt+γ[(1−λ)V(st+1)+λGt+1,λ], G^z,λ_t=y^z_t+γ[(1-λ)V(s^z_t+1)+λ G^z,λ_t+1], (10) where λ=1λ=1 yields pure Monte Carlo (Gt,1=YtG^z,1_t=Y^z_t) and λ=0λ=0 yields one-step TD (Gt,0=yt+γV(st+1)G^z,0_t=y^z_t+γ V(s^z_t+1)). Then we define λ-bootstrapped NTE to decompose Y^z into exact rewards before step t and λ-returns from t onwards. Let Rt=∑s<tγs−1ysR^z_t= _s<tγ^s-1y^z_s denote the cumulative counterfactual reward before step t. The per-step treatment effect is ft=Y−(Rt+γt−1Gt,λ). f^z_t=Y-(R^z_t+γ^t-1G^z,λ_t). (11) When λ=1λ=1, we have Rt+γt−1Gt,1=YR^z_t+γ^t-1G^z,1_t=Y^z, so ft=f()f^z_t=f(z) recovers the exact NTE. For λ<1λ<1, the identity [Gt,λ∣st]=Vπ(st)+O(ϵV)E[G^z,λ_t s^z_t]=V_π(s^z_t)+O( _V) implies [ft]=f()+O(ϵV)E[f^z_t]=f(z)+O( _V) where ϵV=‖V−Vπ‖∞ _V=\|V-V_π\|_∞. Definition 4.3 (λ-Bootstrapped Estimator). Given the per-step treatment effect ftf^z_t Eq. (11), the λ-bootstrapped estimator is ϕ^tλ=1M∑m=1Mκt((m))Q∗((m))⋅ft(m). φ^λ_t= 1M _m=1^M _t(z^(m))Q^*(z^(m))· f^z^(m)_t. By incorporating the contraction rate of λ-return (tsitsiklis1997analysis), we derive the following bias bound for our ϕφ-value estimator. Theorem 4.4 (Bias Bound for ϕ^λ φ^λ). Under Assumptions 3.3, 3.8: |[ϕ^tλ]−ϕt|≤2γ(1−λ)1−γλ‖V−Vπ‖∞.|E[ φ^λ_t]- _t|≤ 2γ(1-λ)1-γλ\|V-V_π\|_∞. The estimator is unbiased when λ=1λ=1 (pure MC) or ϵV=0 _V=0 (perfect value function). Decreasing λ trades bias for variance by truncating the effective horizon (sutton2018, Ch. 12). Algo. 1 summarizes the overall procedure for counterfactual Shapley estimation. Algorithm 1 L3Est: Counterfactual Shapley Estimation 0: Trajectory τ of length T; value network VψV_ψ; coalition samples M 0: Attributions ϕ^1:T φ_1:T, TD errors δ1:T _1:T, δ1:T,1:Mδ^z_1:T,1:M 1: for m=1m=1 to M do 2: Sample coalition (m)∼Q∗z^(m) Q^* for T players Thm. 4.2 3: Simulate counterfactual τ(m)τ^z^(m) via CtfSim Algo. 2 4: for t=1t=1 to T do 5: Compute δt(m)←Gt(m),λ−V(st(m))δ^z^(m)_t← G^z^(m),λ_t-V(s^z^(m)_t) 6: end for 7: end for 8: Compute TD-error δ1:T _1:T from observed trajectory 9: Compute ϕ^1:T φ_1:T by averaging over M samples Def. 4.3 10: return ϕ^1:T,δ1:T,δ1:T,1:M φ_1:T, _1:T,δ^z_1:T,1:M ϕφ-PPO. ϕφ-PPO integrates Shapley credit assignment into PPO (schulman2017ppo) via two mechanisms. First, the ϕφ-MDP ℳπϕM^φ_π (Definition 3.4) reformulates credit as per-step reward rπϕ(s,x)=[ϕt∣St=s,Xt=x]r^φ_π(s,x)=E[ _t S_t=s,X_t=x], enabling standard actor-critic methods. Second, Prioritized Trajectory Replay (PTR) focuses updates on high-|ϕ||φ| subtrajectories rather than individual transitions as in PER (DBLP:journals/corr/SchaulQAS15prioritizedexpreplay). See Algo. 3 and Sec. B in appendix for the details. In each iteration, ϕφ-PPO samples sub-trajectories via PTR, computes ϕφ-estimates, and updates both values and policy networks. Advantages are normalized by batch standard deviation (not z-scored, to preserve ϕ=0φ=0 as the no-effect baseline). We admit that Algo. 1 requires O(TM)O(TM) value network evaluations per trajectory (one per counterfactual state per coalition sample) while standard PPO requires O(T)O(T) evaluations. But this overhead is acceptable when: (1) value inference is cheaper than environment simulation for complex environments; (2) the M evaluations can be batched for GPU efficiency. In practice, we use M=1M=1 coalition sample per trajectory, matching standard actor-critic overhead while still benefiting from counterfactual variance reduction. 5 Experiments We evaluate ϕφ-PPO on two training benchmarks: SkillLuck (Sec. 5.1) and Combinatorial Lock (Sec. 5.2), illustrate ϕφ-value attributions on DoorKey (Sec. 5.3), and provide a controlled ablation on the Fork MDP in Appendix E.1. Throughout, a run succeeds iff P(optimal)>0.9P(optimal)>0.9 at all causal states for 200200 consecutive episodes. We compare all methods on total environment steps: ϕφ-PPO uses (1+M)T(1+M)T steps per episode (11 observed trajectory plus M counterfactual rollouts); all baselines use T steps per episode. No method receives extra simulator access (full hyperparameters in Table 3). We compare against PPO, REINFORCE, and eight prior credit assignment methods: HCA-state, HCA-return (harutyunyan2019hindsight), CCA (pmlr-v139-mesnard21a), CoCoA (meulemans2023would), QCA (mesnard2023quantile), RUDDER (arjona2019rudder), Synthetic Returns (raposo2021synthetic), and H-DICE (velu2024hindsightdice). Q1: Do ϕφ-values assign credit accurately, and does this translate into a learning advantage? Q2: Can ϕφ-PPO learn the optimal policy under delayed, sparse, and highly stochastic rewards? Q3: How sample efficient is ϕφ-PPO compared to vanilla PPO and prior credit assignment methods? 5.1 Skill vs. Luck The SkillLuck MDP separates skill-based from luck-based rewards to test whether correct causal attributions translate into learning (Q1, Q2, Q3). The agent chooses from =0,1A=\0,1\ at each of T=100T=100 steps (γ=0.999γ=0.999, M=1M=1). Every reward includes i.i.d. noise (0,σ2)N(0,σ^2); we sweep σ∈0,3σ∈\0,3\ to test robustness to stochasticity. The first action x1x_1 selects one of two branches. Actions at intermediate steps (2≤t≤T−22≤ t≤ T-2) do not affect the trajectory or reward. On the skill branch, the final action determines the reward: xT−1=1x_T-1=1 yields reward 11, while xT−1=0x_T-1=0 yields 0. On the luck branch, the agent receives a reward of Bern⁡(0.5)⋅γT−3Bern(0.5)·γ^T-3 at step 22, regardless of any action. The γT−3γ^T-3 scaling ensures both branches yield returns of comparable magnitude. Under the optimal final action, the skill branch has expected discounted return γT−2γ^T-2 while the luck branch has 0.5γT−20.5γ^T-2, so the optimal policy chooses skill. On the skill branch, two actions are causal: x1x_1 and xT−1x_T-1. On the luck branch, only x1x_1 is causal because it determines the branch; all subsequent actions have zero causal effect. Predictions. ϕφ-values should assign zero credit to xT−1x_T-1 on luck (D1) and more credit to x1x_1 on skill than luck (D4); Figure 1 confirms this. HCA fails because skill and luck branches share the same terminal observation. At T=100T=100, methods that cannot propagate delayed credit default to the luck branch. s1s_1s2s_2⋯·ssT−1s_T\!-\!1s2′s_2 ⋯·ssT−1′s_T\!-\!1 sFs_FsWs_Wx1=0x_1=0x1=1x_1=1xT−1=1,Y=1x_T\!-\!1=1,\;Y=1xT−1=0x_T\!-\!1=0∀xT−1∀ x_T\!-\!1skillluckY∼Bern⁡(12)Y Bern( 12) Figure 5: Skill vs. Luck results (T=100T=100, γ=0.999γ=0.999, M=1M=1, n=50n=50 seeds per condition). Left: MDP structure; the first action selects skill or luck, and only the final action on the skill branch affects the reward. (a) Success rate with Wilson 95% CIs across noise levels σ∈0,3,10,30,100σ∈\0,3,10,30,100\. (b) Mean episodes to convergence with bootstrap 95% CIs; failures imputed at the budget limit (3,0003,000 episodes). Results (Figure 5). At σ=0σ=0, several baselines match or exceed ϕφ-PPO because the noiseless setting poses no variance challenge; ϕφ-PPO’s slight shortfall reflects M=1M=1 approximation noise. HCA fails as predicted. At σ=3σ=3, the ranking reverses: ϕφ-PPO outperforms all baselines because shared noise cancels in the counterfactual difference (Proposition 3.10), while all other methods degrade. REINFORCE and PPO both fail, consistent with predictions. Among successful runs (right panel), ϕφ-PPO also converges fastest. 5.2 Combinatorial Lock 011⋯·sTTY=1Y=1γT2 γ^T2γT−12 γ^T\!-\!12correct (Y=0Y=0)shortcut Figure 6: Combinatorial Lock results (T∈5,10,15,20,25T∈\5,10,15,20,25\, n=20n=20 seeds, each seeded with one optimal trajectory). Left: MDP structure; Correct advances one step (zero reward) until the final transition yields Y=1Y=1 (discounted return γT−1γ^T-1, twice any shortcut’s γT/2γ^T/2), while Shortcut from position p terminates with γT−p/2γ^T-p/2. (a) Success rate with Wilson 95% CIs. (b) Mean episodes to convergence with bootstrap 95% CIs; failures imputed at the budget limit (10,00010,000 episodes). Solid lines are ϕφ-PPO variants; dashed lines are baselines. The Combinatorial Lock is a T-step chain with tempting immediate rewards that tests delayed credit assignment (Q2, Q3). The agent chooses from =0,1A=\0,1\ at each position p∈0,…,T−1p∈\0,…,T-1\: action 0 (Correct) advances to p+1p+1 with zero immediate reward; action 11 (Shortcut) terminates with immediate reward γT−p/2γ^T-p/2. Reaching position T via T consecutive Correct actions yields reward +1+1 (discounted return γT−1γ^T-1). The ratio of shortcut to optimal return is γ/2<1γ/2<1 at every position, so the shortcut is always suboptimal despite positive immediate reward. We sweep T∈5,10,15,20,25T∈\5,10,15,20,25\ with γ=0.99γ=0.99 and M=16M=16 coalition samples. Every run begins with one optimal trajectory in the replay buffer so that all methods start from the same initial information. This isolates exploitation (can the method propagate credit from a known success?) from exploration, which becomes vanishingly unlikely as T grows. Predictions. Every action along the optimal path is causal (k′/T=1k /T=1), so the sparse causality benefit (Proposition 3.9) does not apply. Combinatorial Lock isolates the delayed reward benefit (Proposition 3.11): (1) ϕφ-PPO should propagate credit from the terminal reward to position 0 in O(1)O(1) episodes by evaluating full counterfactual returns; (2) TD-based methods require O(T)O(T) bootstrap steps, and the shortcut temptation should lock the policy before credit reaches position 0, causing baseline success to collapse as T grows. Results (Figure 6). Both predictions are confirmed. In the left panel, ϕφ-PPO + PTR (solid blue) is the only method that scales beyond T=10T=10; every baseline (dashed) collapses by T=15T=15. The right panel confirms that ϕφ-PPO + PTR converges at a roughly constant episode count across chain lengths, consistent with O(1)O(1) propagation, while baselines flatline at the budget ceiling. Without PTR (solid orange), the seed trajectory is diluted by failures; PPO + PTR/PER (dashed) also fail, confirming that neither prioritized replay nor ϕφ-values alone suffice—both are necessary. Performance degrades at large T because random coalition swaps are exponentially unlikely to preserve the full optimal path, so most counterfactual rollouts return zero and estimator variance increases. 5.3 DoorKey Figure 7: DoorKey attributions (M=4096M=4096, γ=0.99γ=0.99, 20 seeds). Left: the agent (red) must collect the key, unlock the door, and reach the goal (green). Top right: uniform random baseline. Bottom right: navigation-only baseline that follows the shortest path ignoring walls. We compute ϕφ-value attributions along an optimal trajectory in the 5×55×5 DoorKey environment from MiniGrid (gym_minigrid) (Q1). The agent selects from 7 actions (navigation, pickup, toggle, etc.) across ||=400|S|=400 states (5×55×5 grid × 4 orientations × 2 key states × 2 door states). The optimal trajectory reaches the goal in 13 steps. Baseline choice determines the causal story. Under a uniform random baseline (top right), ϕt _t is nearly uniform because DoorKey is a serial dependency chain in which every step must be correct for success. Values taper after the door toggle (t=8t=8) because a random agent increasingly reaches the goal by chance from nearby states. Under a navigation-only baseline (bottom right), the causal story changes entirely. The navigator already takes the correct action at post-door states, so those actions receive ϕt≈0 _t≈ 0 (D1, causal admissibility). Pickup, toggle, and first-room navigation steps that the navigator cannot replicate receive nonzero ϕt _t (D2, causal power), splitting the total credit equally. ϕφ-values thus measure credit relative to the baseline policy, not in absolute terms. Notably, the key pickup (t=3t=3) receives comparable ϕt _t to the door toggle (t=8t=8) under both baselines, despite zero immediate reward; its value reflects the downstream effect of enabling the toggle five steps later, confirming that ϕφ-values propagate credit through dependent subgoal chains (Proposition 3.11). Across all benchmarks, ϕφ-PPO converges in fewer episodes than every baseline. At M=1M=1 (SkillLuck), the 2×2× per-episode cost is offset by ≥4×≥4× fewer episodes; at M=16M=16 (Lock), ϕφ-PPO wins on episode efficiency but not total simulation budget, motivating future variance reduction work. 6 Conclusion We introduced Counterfactual Shapley Credit Assignment, a principled framework that addresses the fundamental temporal credit assignment problem by grounding reward attribution in causal theory via Structural Causal Models. By utilizing the Counterfactual Shapley Value (ϕφ-value), we isolate an agent’s true causal contribution from environmental stochasticity and spurious correlations, inducing a dual ϕφ-MDP that preserves the original optimal policy while providing significantly clearer learning signals. Our framework specifically addresses the challenges of high stochasticity, sparse causality, and delayed rewards through a computationally efficient linear-time estimator and the resulting ϕφ-PPO algorithm. Empirical results across challenging benchmarks demonstrate that ϕφ-PPO achieves superior sample efficiency and convergence compared to existing baselines, offering a scalable and theoretically sound path toward more efficient and explainable reinforcement learning. Acknowledgments This research is supported in part by the NSF, ONR, AFOSR, DoE, Amazon, JP Morgan, and The Alfred P. Sloan Foundation. References Supplementary Materials The following content was not necessarily subject to peer review. Appendix Contents A Counterfactual Simulation B ϕφ-PPO C Theory Details D Proofs E Additional Experiments F Limitations and Future Work G Credit Assignment Methods: Detailed Comparison Appendix A Counterfactual Simulation Algorithm 2 CtfSim: Counterfactual Trajectory Simulation 0: Coalition ∈0,1Tz∈\0,1\^T, trajectory τ=(s1:T,x1:T,y1:T)τ=(s_1:T,x_1:T,y_1:T), policies π, πbase _base 0: (s1:T,y1:T,Y)(s^z_1:T,y^z_1:T,Y^z): counterfactual states, rewards, and total return 1: s1←s1s^z_1← s_1 2: for t=1t=1 to T do 3: if zt=0z_t=0 and st=sts^z_t=s_t then 4: xt←xtx^z_t← x_t On-track: reuse observed 5: else if zt=0z_t=0 then 6: xt∼π(⋅∣st)x^z_t π(· s^z_t) Off-track: sample from π 7: else 8: xt∼πbase(⋅∣st)x^z_t _base(· s^z_t) Intervention 9: end if 10: if (st,xt)=(st,xt)(s^z_t,x^z_t)=(s_t,x_t) then 11: (st+1,yt)←(st+1,yt)(s^z_t+1,y^z_t)←(s_t+1,y_t) Reuse observed 12: else 13: st+1∼P(⋅∣st,xt)s^z_t+1 P(· s^z_t,x^z_t) 14: yt∼r(st,xt,⋅)y^z_t r(s^z_t,x^z_t,·) 15: end if 16: end for 17: Y←∑t=1Tγt−1ytY^z← _t=1^Tγ^t-1y^z_t Discounted return 18: return (s1:T,y1:T,Y)(s^z_1:T,y^z_1:T,Y^z) Appendix B ϕφ-PPO ϕφ-PPO integrates Shapley credit assignment into PPO (schulman2017ppo) via two mechanisms. First, the ϕφ-MDP ℳπϕM^φ_π (Definition 3.4) reformulates credit as per-step reward rπϕ(s,x)=[ϕt∣St=s,Xt=x]r^φ_π(s,x)=E[ _t S_t=s,X_t=x], enabling standard actor-critic methods. Second, Prioritized Trajectory Replay (PTR) focuses policy updates on high-|ϕ||φ| actions when credit is sparse. Intuition. Compared to standard PPO, ϕφ-PPO makes three changes: (1) replace per-step rewards rtr_t with Shapley values ϕ^t φ_t, which isolate causal contribution from return noise; (2) add a second value network VψV_ψ for bootstrapping counterfactual simulations (Algo. 1); the standard PPO value network VωϕV^φ_ω remains, now estimating advantages on the ϕφ-MDP; (3) use PTR to select trajectories for replay. Compared to standard PER (schaul2015per), PTR prioritizes by |ϕt|| _t| (causal impact) rather than TD error |δt|| _t|. Consider Pong: when the ball moves away from the paddle, actions have no causal effect on the outcome, yet TD error may be high if the value network is inaccurate. TD-error PER would wastefully prioritize these non-causal states; PTR correctly assigns low priority since |ϕt|≈0| _t|≈ 0. Conversely, if the policy network learns slower than the value network, TD error is low but the policy remains suboptimal at causally important states. PTR correctly prioritizes these states because |ϕt|| _t| reflects whether the action matters, not whether the value estimate is accurate. Realized estimates ϕ^t φ_t yield unbiased policy gradients when substituted for rπϕr^φ_π. By Theorem 4.4 with λ=1λ=1, [ϕ^t∣τ]=ϕtE[ φ_t τ]= _t, where τ=(s1:T,x1:T,y1:T)τ=(s_1:T,x_1:T,y_1:T) denotes the trajectory. The law of iterated expectations then gives [ϕ^t∣st,xt]=rπϕ(st,xt)E[ φ_t s_t,x_t]=r^φ_π(s_t,x_t). The algorithm maintains two value networks: Vψ≈VπV_ψ≈ V_π for bootstrapping counterfactual simulations in Algo. 1, and Vωϕ≈VπϕV^φ_ω≈ V^φ_π for computing ϕφ-advantages. ϕφ-Advantages. Let ϕ^t φ_t denote the Shapley estimate from Algo. 1. The ϕφ-TD error measures one-step prediction error using ϕ^t φ_t as reward: δtϕ=ϕ^t+Vωϕ(st+1)−Vωϕ(st). _t^φ= φ_t+V^φ_ω(s_t+1)-V^φ_ω(s_t). (12) The ϕφ-advantage generalizes GAE (schulman2015high) to the ϕφ-MDP: Atϕ=∑ℓ=0T−t(λϕ)ℓδt+ℓϕ, A_t^φ= _ =0^T-t(λ^φ) _t+ ^φ, (13) where λϕ∈[0,1]λ^φ∈[0,1] controls the bias-variance tradeoff (distinct from λ in Algo. 1, which controls bootstrapping depth). The ϕφ-return is Gtϕ=∑ℓ=0T−tϕ^t+ℓ, G_t^φ= _ =0^T-t φ_t+ , (14) which serves as the training target for VωϕV^φ_ω (Eq. 22). Shapley efficiency ensures ∑tϕt=Y−Y∅ _t _t=Y-Y_ , where Y∅Y_ is the baseline return (all-default actions); the sum of per-step credit equals the total reward improvement. Adaptive fresh/replay ratio. Each training iteration mixes fresh rollouts with replay from the priority buffer. A static fresh probability ξ is suboptimal: early in training, fresh rollouts discover high-|ϕ||φ| states; later, replay exploits known high-impact actions. We adapt ξ via Thompson sampling (russo2018tutorial). Let pj=maxt⁡pj,tp_j= _tp_j,t denote the trajectory-level priority, where pj,tp_j,t is the priority from Eq. (20) below. A fresh trajectory “wins” if pj>p¯ℬp_j> p_B. Here p¯ℬ=∑i∈ℬpi2/∑i∈ℬpi p_B= _i p_i^2/ _i p_i is the expected priority under proportional sampling. Let u∈[0,1]u∈[0,1] denote the fraction of fresh trajectories that win. We track (α,β)(α,β), initialized to (1,1)(1,1), via exponential moving averages with decay γξ<1 _ξ<1: α←γξα+u,β←γξβ+(1−u). α← _ξα+u, β← _ξβ+(1-u). (15) The decay discounts old observations to adapt to non-stationarity. At steady state α+β→1/(1−γξ)α+β→ 1/(1- _ξ), bounding the effective sample size. At each iteration, sample ξ∼Beta(α+1,β+1)ξ (α+1,β+1) and collect nfresh=clamp(⌊ξB⌋,1,B−1)n_fresh=clamp( ξ B ,1,B-1) fresh rollouts. Stratified sampling reduces variance in the fresh/replay ratio compared to per-trajectory Bernoulli sampling. Importance-sampling corrections. The IS correction depends on the trajectory source. Both fresh and replay trajectories use the PPO ratio for multi-epoch updates: rj,t=πθ(xj,t∣sj,t)/πθold(xj,t∣sj,t), r_j,t= _θ(x_j,t s_j,t)/ _ _old(x_j,t s_j,t), (16) where πθold _ _old is the policy snapshot at the start of the current training step. The clipped surrogate objective (schulman2017ppo) prevents large policy updates: ℓ(r,A)=−min⁡(rA,clip(r,1−ϵclip,1+ϵclip)A). (r,A)=- (rA,\;clip(r,1- _clip,1+ _clip)A ). (17) Replay trajectories additionally require a PTR importance-sampling weight to correct for priority-based sampling. Let Pj=pj/∑i∈ℬpiP_j=p_j/ _i p_i denote the sampling probability for trajectory j from buffer ℬB. The normalized IS weight is: wj=(|ℬ|⋅Pj)−βis/maxj′∈ℬ(|ℬ|⋅Pj′)−βis. w_j=(|B|· P_j)^- _is / _j (|B|· P_j )^- _is. (18) The exponent βis _is anneals from 0 to 11 over training; at βis=1 _is=1, the weights fully correct for non-uniform sampling. Since ϕφ-values are recomputed for replay trajectories using the current policy and value function, no policy importance weight is needed. The full policy loss applies the PTR weight only to replay trajectories: ℒθPTR=1B∑j=1Bw~j∑t=1Tℓ(rj,t,Atϕ),w~j=1if j is freshwjif j is replay. _θ^PTR= 1B _j=1^B w_j _t=1^T (r_j,t,A_t^φ), w_j= cases1&if j is fresh\\ w_j&if j is replay cases. (19) PTR: Priority computation. When credit is sparse, PTR focuses updates on high-impact actions. The priority for state sts_t is pt=(ϕt(2))αptr/2+ϵptr, p_t=(φ^(2)_t) _ptr/2+ _ptr, (20) where ϕt(2)φ^(2)_t is a bias-corrected exponential moving average (kingma2014adam) of squared Shapley estimates. The priority ϕ(2) φ^(2) is an exponentially-weighted root-mean-square (RMS), capturing both mean magnitude and variance: [ϕ2]=μ2+σ2 E[φ^2]= μ^2+σ^2. This prioritizes states where (i) actions have consistent causal impact (high |μ||μ|), and (i) the action choice matters but the policy has not yet converged (high σ with μ≈0μ≈ 0). The exponent αptr _ptr controls priority sharpness; ϵptr _ptr prevents starvation. Priority decay. Priorities become stale as the policy improves. Each iteration, all priorities decay by pj←γppjp_j← _pp_j, where γp∈[0.99,0.9999] _p∈[0.99,0.9999]. Trajectories with pj<ϵevictp_j< _evict are evicted, implicitly bounding the buffer size to O(log⁡(ϵevict)/log⁡(γp))O( ( _evict)/ ( _p)) iterations of data. Training. Three components train jointly. The value network VψV_ψ for counterfactual bootstrapping trains on both actual and counterfactual TD errors from Algo. 1: ℒV=1(M+1)BT(∑j,tδj,t2+∑j,t,m(δj,t(m))2). _V= 1(M+1)BT ( _j,t _j,t^2+ _j,t,m(δ^z^(m)_j,t)^2 ). (21) The ϕφ-critic VωϕV^φ_ω regresses to the ϕφ-return: ℒVϕ=1BT∑j,t(Gj,tϕ−Vωϕ(sj,t))2. _V^φ= 1BT _j,t(G_j,t^φ-V^φ_ω(s_j,t))^2. (22) Following schulman2017ppo, all three components train via a single combined loss with gradient clipping (norm gmaxg_ ): ℒ∗=ℒθPTR+c1ℒV+c2ℒVϕ−c3H(πθ), ^*=L_θ^PTR+c_1L_V+c_2L_V^φ-c_3H( _θ), (23) where c1,c2c_1,c_2 weight the value losses and c3c_3 weights the entropy bonus H(πθ)=−s∼dπ[∑xπθ(x∣s)log⁡πθ(x∣s)]H( _θ)=-E_s d_π [ _x _θ(x s) _θ(x s) ] (schulman2017ppo) (Table 3). Algorithm. Algo. 3 summarizes ϕφ-PPO. Each iteration samples subtrajectories via PTR, computes ϕφ-estimates, and updates all three networks. Advantages are normalized by batch standard deviation (not z-scored, to preserve ϕ=0φ=0 as the no-effect baseline). Algorithm 3 ϕφ-PPO 0: Policy πθ _θ; value networks VψV_ψ, VωϕV^φ_ω; batch size B; coalition samples M; epochs K; decays γξ,γp _ξ, _p 0: Updated parameters θ,ψ,ωθ,ψ,ω 1: Initialize priority buffer ℬ←∅B← ; pseudo-counts α,β←0α,β← 0 2: for iteration =1,2,…=1,2,… do 3: Sample ξ∼Beta(α+1,β+1)ξ (α+1,β+1); set nfresh←clamp(⌊ξB⌋,1,B−1)n_fresh ( ξ B ,1,B-1) 4: ∀j∈ℬ∀ j : pj←γppjp_j← _pp_j; evict if pj<ϵevictp_j< _evict priority decay 5: for j=1j=1 to B do 6: if ℬ=∅B= or j≤nfreshj≤ n_fresh then 7: Roll out fresh τ∼πθτ _θ; set w~j←1 w_j← 1 8: else 9: Sample τ∝pτ p_τ from ℬB; set w~j w_j via Eq. 18 10: end if 11: Compute ϕ^1:T,δ1:T,δ1:T,1:M←L3Est(τ,M) φ_1:T, _1:T,δ^z_1:T,1:M← L3Est(τ,M) Algo. 1 12: Compute ϕφ-advantages A1:TϕA^φ_1:T Eq. 13 13: A1:Tϕ←A1:Tϕ/std(Aϕ)A^φ_1:T← A^φ_1:T/std(A^φ) normalize, preserve ϕ=0φ=0 14: Compute priorities p1:Tτp^τ_1:T; update ℬB Eq. 20 15: end for 16: Update α←γξα+uα← _ξα+u, β←γξβ+(1−u)β← _ξβ+(1-u) u: fresh win rate 17: Optimize ℒ∗L^* w.r.t. θ,ψ,ωθ,ψ,ω for K epochs Eq. 23 18: end for Guarantees. ϕφ-PPO inherits theoretical properties from its components. Gradient equivalence. By Lemma 3.5, ϕφ-values produce the same expected policy gradient as original returns: [∑tϕt∇log⁡πt]=[Y∑t∇log⁡πt]E[ _t _t∇ _t]=E[Y _t∇ _t]. Thus ϕφ-PPO targets the same optimum as standard PPO. Bootstrap bias. The λ-return (Eq. 10) introduces bias bounded by O(γ(1−λ)ϵV/(1−γλ))O(γ(1-λ) _V/(1-γλ)) where ϵV=‖V−Vπ‖∞ _V=\|V-V_π\|_∞ (Theorem 4.4). This bias vanishes as Vψ→VπV_ψ→ V_π. Trajectory replay. Because ϕφ-values are defined over trajectories (Definition 3.4), PTR replays entire subtrajectories rather than individual transitions. This is sound by Corollary C.4: for any state s and horizon n, the optimal policy in the undiscounted truncated ϕφ-MDP ℳnϕ(s)M^φ_n(s) equals the optimal policy in ℳM. Since Vϕ,∗=0V^φ,*=0 under self-baseline at optimality, no bootstrap is needed in the exact case; in practice, V^ϕ≈0 V^φ≈ 0 during training. IS weights (Eq. 18) correct for the prioritized sampling distribution, ensuring unbiased gradient estimates. Hyperparameters are in Table 3; proofs in Appendix D.4. Appendix C Theory Details Definition C.1 (Functional Dependence). Given world (ℳ,)(M,u), the functional dependence of Y on X under baseline z=(x′,′)z=(x ,z ) is: c(ℳ,,X,Y,z)=Y′()−Y′,x′() c(M,u,X,Y,z)=Y_z (u)-Y_z ,x (u) (24) The baseline space is =(x′,′):x′∈X,⊆∖X,′∈Z=\(x ,z ):x _X,Z \X\,z _Z\ equipped with probability measure Pℳ(,X)P^M(Z,X). This measures the outcome difference when X changes from baseline x′x to its actual value, with other variables held at ′z . When ′=∅z = , this reduces to the unit-level total effect Y()−Yx′()Y(u)-Y_x (u). Functional dependence captures the counterfactual test: if changing X changes Y, then X is responsible for Y. This condition is necessary for causation across major definitions in the actual causation literature (halpern2016actual; beckers2018principled; beckers2021counterfactual). To formalize the condition, we introduce the why-query Why(Y∣;)Why(Y ;X), composed of three parts: (1) the event being explained, or explanandum, Y=yY=y, inducing alternate values, or foils, Y=y′≠yY=y ≠ y; (2) the evidence =E=e, the observed context used to infer causes; and (3) the explanatory variables ⊆X , which prescribe the subset of variables to attribute to.111Explicitly selecting the set of explanatory variables as a subset of observed variables allows us to exclude irrelevant or unobserved causes such as “Alice arriving” or “the Big Bang”, even though it is true that if Alice did not arrive, or the Big Bang did not occur, the funding outcome would be different! We write Why(y∣)Why(y ) as shorthand for Why(Y=y∣;)Why(Y=y ;X) when X is clear from context. Given a why-query, an Explanatory Variable Attribution (EVA) assigns a numerical attribution to each explanatory variable in X. Definition C.2 (Explanatory Variable Attribution). An explanatory variable attribution (EVA) is a function ϕ:Ω×→ℝφ: ×W×X , where Ω is the space of SCMs over V and W is the space of why-queries Why(Y∣;)Why(Y ;X) asking why Y=y∈Y=y , given evidence =E=e, in terms of variables ⊆∖YX \Y\. With EVA, we are ready to formally define the Causal Credit Assignment criteria from Def. 3.1. Definition C.3 (Causal Credit Assignment, formal). We define four desiderata as mappings D1:4:Ω×ℂ×Φ→0,1D_1:4: ×C× →\0,1\, where ℂC is the space of causal measures and Φ is the space of EVAs. Given SCM ℳ∈ΩM∈ , causal measure c∈ℂc , and EVA ϕ∈Φφ∈ , we say Di(ℳ,c,ϕ)=1D_i(M,c,φ)=1 when: D1: D_1: c=0⟹ϕ= c=0 φ=0 (Causal Admissibility) D2: D_2: ∃,z:c≠0⟹ϕ≠ ,z:c≠ 0 φ 0 (Causal Power) D3: D_3: cℳ=cℳ′∧Pc¯ℳ(Z)≢Pc¯ℳ′(Z)∧P+ℳ(z)≥P+ℳ′(z) c_M=c_M P^M_ c(Z) ≡ P^M _ c(Z) P^M_+(z)≥ P^M _+(z) ⟹ϕℳ>ϕℳ′ _M> _M (Causal Normality) D4: D_4: cℳ≥cℳ′∧Pℳ(Z)≡Pℳ′(Z)∧Pℳ(cZ)≢Pℳ′(cZ) c_M≥ c_M P^M(Z)≡ P^M (Z) P^M(c_Z) ≡ P^M (c_Z) ⟹ϕℳ>ϕℳ′ _M> _M (Causal Effect Scaling) Quantification: all premises universally quantified unless marked ∃. Notation: c, cℳc_M abbreviate c(ℳ,,X,Y,z)c(M,u,X,Y,z); ϕφ, ϕℳ _M abbreviate ϕX(ℳ,w) _X(M,w); P≡P′P≡ P denotes distributional equality; Pc¯ℳ(Z)≔Pℳ(Z∣c≠0)P^M_ c(Z) P^M(Z c≠ 0); P+ℳ(z)≔sign(cℳ)⋅Pℳ(z)P^M_+(z) (c_M)· P^M(z). Chunk-size Updates. Theorem 3.7 establishes optimality equivalence for full-length trajectories optimization. In practice, we chunk trajectories: each chunk begins at an arbitrary state s (sampled from a replay buffer) and extends for n steps with a value bootstrap at the end. The following corollary shows that both modifications—arbitrary starting state and finite-horizon truncation—preserve the optimal policy. Corollary C.4 (Chunked ϕφ-Learning). For any state s and horizon n, let ℳnϕ(s)M^φ_n(s) denote the undiscounted ϕφ-MDP starting from s with actions x1:nx_1:n and terminal value Vϕ(sn)V^φ(s_n). The optimal policy in ℳnϕ(s)M^φ_n(s) equals the optimal policy in ℳM. The corollary holds for any state s, not only the initial state distribution. This justifies experience replay: sampling (st,xt)(s_t,x_t) from a buffer and computing ϕt:t+n _t:t+n yields correct policy updates regardless of trajectory origin. Under self-baseline at optimality, Vϕ,∗(s)=0V^φ,*(s)=0 for all s (Shapley efficiency), so no bootstrap is needed in the exact case. In practice, V^ϕ≈0 V^φ≈ 0 during training, and the bootstrap error vanishes as the policy converges. This enables Prioritized Trajectory Replay (PTR) using |ϕt|| _t| as priority. TD-error prioritization samples states where the value function is inaccurate, but accurate values do not guarantee optimal actions. In contrast, |ϕt|| _t| measures causal contribution: large |ϕt|| _t| indicates the action significantly affected the outcome. Policy improvement at states with large |ϕt|| _t| affects returns the most. When credit is sparse (k′≪Tk T causal actions), non-causal state-action pairs have ϕt≈0 _t≈ 0 and receive minimal priority, concentrating updates on the causally-relevant subset. Table 1: Three dimensions where ϕφ-methods improve sample complexity. Dimension Improvement Condition TD Failure Sparse causality ×k′/T×\,k /T variance k′≪Tk T Wasted updates High stochasticity ×(1−ρY)×\,(1- _Y) variance ρY≈1 _Y≈ 1 Noise swamps signal Delayed reward O(T)→O(1)O(T)→ O(1) episodes Large delay Slow propagation Appendix D Proofs This appendix contains proofs and additional material omitted from the main text. D.1 Notation Table 2: Notation glossary Symbol Meaning SCM and MDP ,V,U Endogenous, exogenous variables τ Trajectory: (s1:T,x1:T,y1:T)(s_1:T,x_1:T,y_1:T) St,Xt,YtS_t,X_t,Y_t State, action, reward at time t π(x∣s)π(x s) Policy (action distribution given state) γ∈(0,1)γ∈(0,1) Discount factor T Horizon (episode length) Coalitions and Counterfactuals ∈0,1Tz∈\0,1\^T Coalition mask (zt=1⇔Xtz_t=1 X_t intervened) ||=k|z|=k Coalition size s,Ys^z,Y^z Counterfactual state, outcome under mask z Shapley Values and Credit ϕt _t Counterfactual Shapley value of action XtX_t κt() _t(z) Shapley kernel weight GtG_t Observed return from time t: ∑k≥0γkyt+k _k≥ 0γ^ky_t+k GtϕG_t^φ ϕφ-return from time t: ∑τ≥tγτ−tϕτ _τ≥ tγ^τ-t _τ ℳπϕM^φ_π ϕφ-MDP (reward-redistributed MDP) rπϕ(s,x)r^φ_π(s,x) ϕφ-MDP reward: [ϕt∣St=s,Xt=x]E[ _t S_t=s,X_t=x] ϕφ-PPO (Algo. 3) VψV_ψ Value network for original MDP (bootstrapping) VωϕV^φ_ω Value network for ϕφ-MDP (advantages) B Batch size (number of trajectories) wjw_j PTR importance-sampling weight for sample j Analysis (ϵ,δ)(ε,δ) Accuracy parameters Mδ,ϵM_δ,ε Sample complexity: σ2/((1−γ)2δϵ2)σ^2/((1-γ)^2δε^2) k′k Number of causal actions (with ϕt≠0 _t≠ 0) λ NTE mixing parameter (0: bootstrap, 11: Monte Carlo) λϕλ^φ GAE mixing for ϕφ-advantage estimation ρY _Y Outcome correlation under shared exogenous noise D.2 Problem Setting (Section 3) Lemma D.1 (Variance of Discounted Sum). If [Yt2]≤σ2E[Y_t^2]≤σ^2 for all t, then Var[Y]≤σ2/(1−γ)2Var[Y]≤σ^2/(1-γ)^2 where Y=∑t=1Tγt−1YtY= _t=1^Tγ^t-1Y_t. Proof. By Cauchy-Schwarz and Var[Yt]≤[Yt2]≤σ2Var[Y_t] [Y_t^2]≤σ^2, we have |Cov[Yt,Ys]|≤σ2|Cov[Y_t,Y_s]|≤σ^2. Thus: Var[Y]=∑t,sγt+s−2Cov[Yt,Ys]≤σ2(∑t=1∞γt−1)2=σ2(1−γ)2. [Y]= _t,sγ^t+s-2Cov[Y_t,Y_s]≤σ^2 ( _t=1^∞γ^t-1 )^2= σ^2(1-γ)^2. (25) ∎ Proposition D.2 (Sample Complexity is γ-Independent). For relative error targets ϵrel=ϵ/|ϕ| _rel=ε/|φ|, Mδ,ϵrel=O(σ2/(δϵrel2Rmax2))M_δ, _rel=O(σ^2/(δ _rel^2R_ ^2)). Proof. Returns scale as O(Rmax/(1−γ))O(R_ /(1-γ)), so ϵ=O(ϵrelRmax/(1−γ))ε=O( _relR_ /(1-γ)). Substituting: Mδ,ϵ=σ2/((1−γ)2δϵ2)=σ2/(δϵrel2Rmax2)M_δ,ε=σ^2/((1-γ)^2δε^2)=σ^2/(δ _rel^2R_ ^2). ∎ D.3 Credit Assignment (Section 3) See 3.2 Proof. We show ϕφ-values (Shapley values of the NTE game f()=Y−Yσf(z)=Y-Y_ _z) satisfy each desideratum (formal definitions in Appendix C). D1 (Causal Admissibility). Suppose c=0c=0: the functional dependence of Y on XtX_t is zero for all contexts (,z)(u,z). Then changing XtX_t’s intervention status does not affect the counterfactual outcome: Y∪t=Y^z∪\t\=Y^z for every coalition z. All marginal contributions vanish: f(∪t)−f()=Y−Y∪t=0f(z∪\t\)-f(z)=Y^z-Y^z∪\t\=0. By the Shapley null player axiom, ϕt=0 _t=0. D2 (Causal Power). Suppose ∃,z∃\,u,z such that c(ℳ,,Xt,Y,z)≠0c(M,u,X_t,Y,z)≠ 0. Then there exists a coalition ∗z^* (corresponding to context z) where the marginal contribution is nonzero: f(∗∪t)−f(∗)≠0f(z^*∪\t\)-f(z^*)≠ 0. Since all Shapley weights w()=||!(T−||−1)!T!>0w(z)= |z|!(T-|z|-1)!T!>0, the weighted sum ϕt=∑:zt=0w()[f(∪t)−f()] _t= _z:z_t=0w(z)[f(z∪\t\)-f(z)] includes a nonzero term with a strictly positive weight. Therefore ϕt≠0 _t≠ 0. D3 (Causal Normality). Consider two SCMs ℳ,ℳ′M,M with identical causal effects (cℳ=cℳ′c_M=c_M ) but different baseline distributions satisfying P+ℳ(z)≥P+ℳ′(z)P^M_+(z)≥ P^M _+(z). The NTE game value f()f(z) depends on the SCM through the counterfactual simulation, which samples baseline actions from πbase _base. When P+ℳ(z)≥P+ℳ′(z)P^M_+(z)≥ P^M _+(z), the baseline under ℳM assigns weakly higher probability to baselines that produce positive causal effects. Each marginal contribution f(∪t)−f()f(z∪\t\)-f(z) measures the additional effect of intervening at step t. Under ℳM, the “default” behavior (baseline) is more aligned with positive outcomes, so the departure from baseline caused by XtX_t receives greater credit. Formally, the Shapley value is the expected marginal contribution over uniformly random orderings; since each marginal contribution under ℳM weakly exceeds that under ℳ′M (by the monotonicity of the NTE in baseline probabilities when the causal effect sign is fixed), we obtain ϕℳ>ϕℳ′ _M> _M . D4 (Causal Effect Scaling). Consider two SCMs with identical baseline distributions (Pℳ(Z)≡Pℳ′(Z)P^M(Z)≡ P^M (Z)) but cℳ≥cℳ′c_M≥ c_M (larger causal effect in ℳM). Larger causal effects directly increase the magnitude of counterfactual outcome differences: for each coalition z, |Y−Y∪t||Y^z-Y^z∪\t\| is weakly larger under ℳM. Since baseline distributions are identical, the Shapley weights are the same in both games. By the Shapley monotonicity property (if player t’s marginal contribution in game v weakly exceeds that in game v′v for every coalition, then ϕt(v)≥ϕt(v′) _t(v)≥ _t(v )), we obtain ϕℳ>ϕℳ′ _M> _M . ∎ See 3.5 Proof. By Shapley efficiency, ∑tϕt=Y−Y _t _t=Y-Y^1 where Y=YσY^1=Y_ _1 is the full-baseline outcome. We show [Y⋅∑t∇log⁡πt]=0E[Y^1· _t∇ _t]=0. Under any baseline policy πbase _base (including self-baseline), the counterfactual Y^1 replaces all observed actions with fresh samples X1:T∼πbase(⋅∣S1:T)X^1_1:T _base(· S^1_1:T). These samples are drawn independently of the observed actions X1:TX_1:T. We claim Y⟂Xt∣StY^1 X_t S_t. By the Markov property of the MDP, Xt∼π(⋅∣St)X_t π(· S_t) is conditionally independent of all preceding random variables given StS_t. The baseline outcome Y^1 is a deterministic function of the shared initial state S1S_1 and the counterfactual noise (actions from πbase _base and resampled transitions), all of which are independent of XtX_t. Although Y^1 depends on S1S_1, which is an ancestor of StS_t, the Markov property ensures S1⟂Xt∣StS_1 X_t S_t. Therefore Y⟂Xt∣StY^1 X_t S_t for any baseline policy. By the score function identity: [Y⋅∇log⁡π(Xt∣St)]=St[[Y∣St]⋅Xt[∇log⁡π(Xt∣St)]]=0. [Y^1·∇ π(X_t S_t)]=E_S_t[E[Y^1 S_t]·E_X_t[∇ π(X_t S_t)]]=0. (26) ∎ See 3.7 Proof. By Lemma 3.5, ∇θJϕ(θ)=∇θJ(θ) _θJ_φ(θ)= _θJ(θ) for all θ. Two functions with identical gradients everywhere have identical stationary points (where the gradient vanishes). Therefore both objectives share the same critical points, including maxima. Explicitly, by Shapley efficiency, Jϕ(θ)=J(θ)−πθ[Y]J_φ(θ)=J(θ)-E_ _θ[Y^1]. The term πθ[Y]E_ _θ[Y^1] (expected baseline return under self-baseline) has zero gradient by the same argument as Lemma 3.5: Y^1 is independent of the realized actions XtX_t, so [Y∇log⁡π]=0E[Y^1∇ π]=0. Thus JϕJ_φ and J differ by a function with zero gradient, and arg⁡max⁡Jϕ=arg⁡max⁡J J_φ= J. ∎ Corollary D.3 (ϕφ-Value Function). The ϕφ-MDP ℳπϕM^φ_π has a well-defined value function Vϕ(s)=[∑ℓ≥0ϕt+ℓ∣St=s]V^φ(s)=E[ _ ≥ 0 _t+ S_t=s] satisfying the Bellman equation Vϕ(s)=x∼π[rπϕ(s,x)+s′∼P(⋅∣s,x)[Vϕ(s′)]]V^φ(s)=E_x π[r^φ_π(s,x)+E_s P(· s,x)[V^φ(s )]]. The ϕφ-MDP is undiscounted (γϕ=1 _φ=1): discounting is already incorporated into the Shapley values via the NTE game outcome Y=∑tγt−1rtY= _tγ^t-1r_t. Proof. The ϕφ-MDP ℳπϕM^φ_π is a valid MDP with state space S, action space A, transition P(s′∣s,x)P(s s,x), discount γϕ=1 _φ=1, and reward rπϕ(s,x)=[ϕt∣St=s,Xt=x]r^φ_π(s,x)=E[ _t S_t=s,X_t=x]. Discounting is not applied to ϕφ-rewards because the Shapley game outcome Y=∑tγt−1rtY= _tγ^t-1r_t already incorporates temporal discounting; applying γ again would double-discount. Since [|ϕt|]<∞E[| _t|]<∞ (bounded by [|Y|]<∞E[|Y|]<∞ via efficiency) and episodes are finite (T<∞T<∞), the undiscounted return ∑tϕt _t _t is integrable. Standard MDP theory applies: value functions exist and satisfy Bellman equations. ∎ See C.4 Proof. The proof proceeds in two steps, corresponding to the two truncations. Step 1: Arbitrary initial state. Theorem 3.7 shows that the optimal policy in ℳϕM^φ equals the optimal policy in ℳM. By the Markov property, the optimal policy π∗(x∣s)π^*(x s) depends only on the current state s, not on the initial state distribution or the trajectory history. Therefore, π∗π^* is optimal in ℳϕ(s)M^φ(s) for any starting state s. This justifies experience replay: transitions sampled from a buffer correspond to different starting states, but all yield the same optimal policy. Step 2: Finite horizon with value bootstrap. Consider the n-step truncated ϕφ-MDP ℳnϕ(s)M^φ_n(s) with terminal value Vϕ(sn)V^φ(s_n). Since the ϕφ-MDP is undiscounted (γϕ=1 _φ=1, Corollary D.3), the objective is: Jnϕ(s)=π[∑t=1nϕt+Vϕ(sn)∣S1=s]. J_n^φ(s)=E_π [ _t=1^n _t+V^φ(s_n) S_1=s ]. (27) Under self-baseline at the optimal policy π∗π^*, Shapley efficiency gives π∗[∑tϕt∣S1=s]=π∗[Y−Y∣S1=s]=V∗(s)−V∗(s)=0E_π^*[ _t _t S_1=s]=E_π^*[Y-Y^1 S_1=s]=V^*(s)-V^*(s)=0 for all s. Therefore Vϕ,∗(s)=0V^φ,*(s)=0 for all s, and the n-step objective simplifies to Jnϕ(s)=π[∑t=1nϕt∣S1=s]J_n^φ(s)=E_π[ _t=1^n _t S_1=s]. By Lemma 3.5 applied to the n-step game (the proof uses Assumption 3.3 step-by-step and carries through for any finite horizon), ∇θπ[∑t=1nϕt]=∇θπ[∑t=1nγt−1rt] _θE_π[ _t=1^n _t]= _θE_π[ _t=1^nγ^t-1r_t]. The RHS is the gradient of the standard n-step return, whose maximizer is π∗π^*. Since JnϕJ_n^φ and the standard objective share the same gradient for all θ, they have the same maximizer. Approximate case. In practice, VϕV^φ is learned, not zero, so we bootstrap with V^ϕ(sn)≈Vϕ,∗(sn)=0 V^φ(s_n)≈ V^φ,*(s_n)=0. The bootstrap error |V^ϕ(sn)|| V^φ(s_n)| introduces bias; as training converges (V^ϕ→0 V^φ→ 0), the bias vanishes. This parallels the standard n-step bias-variance tradeoff: shorter chunks reduce variance from trajectory noise at the cost of bootstrap bias. ∎ D.4 Estimation (Section 4) See 4.2 Proof. The second moment of the IS estimator is [(κt()/Q())2f()2]E[( _t(z)/Q(z))^2f(z)^2]. Since Var[f()]≤σ2/(1−γ)2Var[f(z)]≤σ^2/(1-γ)^2 (Assumption 3.8), we minimize: minQ∑κt()2Q()subject to ∑Q()=1. _Q _z _t(z)^2Q(z) to _zQ(z)=1. (28) The k=0k=0 coalition (=z=0, no interventions) has f()=Y−Y=0f(0)=Y-Y=0 deterministically, so it contributes nothing and is excluded from sampling. Using two-level sampling over k∈1,…,Tk∈\1,…,T\ (size k with probability qkq_k, then uniform within size k): Q()=qk/(Tk)Q(z)=q_k/ Tk. The objective becomes ∑k=1Tck/qk _k=1^Tc_k/q_k where ck=1T(1k+1T−k)c_k= 1T( 1k+ 1T-k) for k<Tk<T and cT=1/T2c_T=1/T^2. By Cauchy-Schwarz, qk∗∝ckq^*_k c_k minimizes this. Chebyshev gives (ϵ,δ)(ε,δ)-accuracy with M=O(Mδ,ϵ)M=O(M_δ,ε) samples. ∎ See 4.4 Proof. The λ-bootstrapped estimator (Definition 4.3) replaces the exact counterfactual return from step t onward with a λ-return Gt,λG^z,λ_t (Eq. 10). We bound the bias introduced by this substitution. Step 1: λ-return bias. The λ-return is a mixture of n-step returns: Gt,λ=(1−λ)∑n=1∞λn−1Gt(n)G^z,λ_t=(1-λ) _n=1^∞λ^n-1G^(n)_t, where Gt(n)=∑k=0n−1γkyt+k+γnV(st+n)G^(n)_t= _k=0^n-1γ^ky^z_t+k+γ^nV(s^z_t+n). Taking conditional expectations given sts^z_t: [Gt(n)∣st]=Vπ(st)+γn[V(st+n)−Vπ(st+n)∣st]. [G^(n)_t s^z_t]=V_π(s^z_t)+γ^nE[V(s^z_t+n)-V_π(s^z_t+n) s^z_t]. (29) Since |V(s)−Vπ(s)|≤ϵV|V(s)-V_π(s)|≤ _V for all s: |[Gt,λ∣st]−Vπ(st)| |E[G^z,λ_t s^z_t]-V_π(s^z_t)| ≤(1−λ)∑n=1∞λn−1γnϵV=γ(1−λ)1−γλϵV. ≤(1-λ) _n=1^∞λ^n-1γ^n _V= γ(1-λ)1-γλ _V. (30) Step 2: Per-coalition NTE bias. The exact NTE is f()=Y−Y=Y−Rt−γt−1Gt,MCf(z)=Y-Y^z=Y-R^z_t-γ^t-1G^z,MC_t, where Gt,MC=∑s≥tγs−tysG^z,MC_t= _s≥ tγ^s-ty^z_s is the Monte Carlo return. The bootstrapped NTE is ft=Y−Rt−γt−1Gt,λf^z_t=Y-R^z_t-γ^t-1G^z,λ_t. Their difference is: |E[ft]−f()|=γt−1|[Gt,MC−Gt,λ]|≤γt−1⋅γ(1−λ)1−γλϵV≤γ(1−λ)1−γλϵV, |E[f^z_t]-f(z)|=γ^t-1|E[G^z,MC_t-G^z,λ_t]|≤γ^t-1· γ(1-λ)1-γλ _V≤ γ(1-λ)1-γλ _V, (31) where the last inequality uses γt−1≤1γ^t-1≤ 1 for t≥1t≥ 1. Step 3: Shapley bias. The estimator is ϕ^tλ=∑κt()ft φ^λ_t= _z _t(z)f^z_t (in expectation over the proposal Q∗Q^*). The true Shapley value is ϕt=∑κt()f() _t= _z _t(z)f(z). Using the marginal contribution form with non-negative Shapley weights w()≥0w(z)≥ 0 summing to 11: |[ϕ^tλ]−ϕt| |E[ φ^λ_t]- _t| =|∑:zt=0w()([ft∪t−ft]−[f(∪t)−f()])| = | _z:z_t=0w(z) (E[f^z∪\t\_t-f^z_t]-[f(z∪\t\)-f(z)] ) | (32) ≤∑:zt=0w()(|[ft∪t]−f(∪t)|+|[ft]−f()|) ≤ _z:z_t=0w(z) (|E[f^z∪\t\_t]-f(z∪\t\)|+|E[f^z_t]-f(z)| ) (33) ≤2γ(1−λ)1−γλϵV.∎ ≤ 2γ(1-λ)1-γλ _V. (34) The last line uses Step 2 for each of the two bias terms and ∑w()=1Σ w(z)=1. Both coalitions z and ∪tz∪\t\ share the same counterfactual states up to step t (the intervention at step t only affects states from t+1t+1 onward), so both bootstrap from the same starting state sts^z_t, and the bound from Step 2 applies to each. The factor of 22 arises because the continuation trajectories diverge after step t (different actions), so the two bootstrap biases do not cancel in general. D.5 PTR Buffer Design (Section B) PTR stores full trajectories with per-timestep priorities. The priority formula uses a smoothed estimate: pt=(ϕt(2))αptr/2+ϵptr, p_t=(φ^(2)_t) _ptr/2+ _ptr, (35) where ϕt(2)φ^(2)_t is a bias-corrected exponential moving average (kingma2014adam) of squared Shapley estimates, αptr _ptr controls priority sharpness, and ϵptr _ptr prevents starvation. Sampling selects (trajectory, starting timestep) pairs proportionally to ptp_t using the Gumbel-max trick for efficient vectorized sampling. When the buffer reaches capacity, the trajectory with lowest total priority ∑tpt _tp_t is evicted. Following standard PER (schaul2015per), we apply importance sampling (IS) correction to account for the non-uniform sampling distribution. Let pip_i denote the priority of sample i in the buffer. Each sampled subtrajectory receives weight wi=(|ℬ|⋅pi/∑jpj)−βisw_i=(|B|· p_i/ _jp_j)^- _is, normalized by maxi⁡wi _iw_i for stability. The exponent βis _is anneals from β0 _0 (e.g., 0.4) to 1 over training, providing full bias correction at convergence while allowing faster early learning. D.6 When Credit Helps (Section 3.3) See 3.9 Proof. By the Shapley null player axiom (D1), ϕt=0 _t=0 whenever XtX_t has no causal effect on Y, so g^ϕ=∑t∈gt g^φ= _t g_t where gt=ϕt∇log⁡π(Xt∣St)g_t= _t∇ π(X_t S_t) and ||=k′|C|=k . Expanding the variance of the sum: Var[g^ϕ] [ g^φ] =∑t∈Var[gt]+2∑t,s∈t<sCov[gt,gs]. = _t Var[g_t]+2\!\! _ subarrayct,s \\ t<s subarrayCov[g_t,g_s]. (36) The diagonal terms are bounded by k′σϕ2k σ^2_φ. For the cross-terms, |Cov[gt,gs]|≤ρ¯σϕ2|Cov[g_t,g_s]|≤ ρ\,σ^2_φ by definition of ρ¯ ρ and Cauchy-Schwarz on covariance, and there are (k′2) k 2 pairs. Combining: Var[g^ϕ]≤k′σϕ2+k′(k′−1)ρ¯σϕ2=k′(1+(k′−1)ρ¯)σϕ2Var[ g^φ]≤ k σ^2_φ+k (k -1) ρ\,σ^2_φ=k (1+(k -1) ρ)\,σ^2_φ. Why ρ¯ ρ is small. For t<st<s, condition on (Ss,St,Xt)(S_s,S_t,X_t) and integrate over Xs∼π(⋅∣Ss)X_s π(· S_s): Cov[gt,gs]=[gt⋅[ϕs∇log⁡πs∣Ss,St,Xt]]−[gt][gs]. [g_t,g_s]=E [g_t·E[ _s∇\! _s S_s,S_t,X_t] ]-E[g_t]E[g_s]. (37) The score function identity [∇log⁡π(Xs∣Ss)∣Ss]=0E[∇ π(X_s S_s) S_s]=0 drives the inner expectation to zero whenever ϕs _s is independent of XsX_s given SsS_s. Under self-baseline, ϕs _s depends on XsX_s through the on-track condition (s=s^z_s=s_s when the observed action is reused), introducing a residual correlation. This dependence is weak because: (i) the on-track condition at step s is primarily determined by interventions at earlier steps, not by XsX_s itself; and (i) the optimal proposal Q∗Q^* concentrates on extreme coalition sizes where the on-track probability is either very high (||≈0|z|≈ 0) or very low (||≈T|z|≈ T). In deterministic environments, ρ¯=0 ρ=0 for on-track coalitions since ϕs _s given SsS_s depends on XsX_s only through the on-track indicator, which is determined by prior interventions. In contrast, standard REINFORCE has g^=Y∑t=1T∇log⁡πt g=Y _t=1^T∇ _t where all T terms contribute regardless of causal structure, giving Var[g^]=O(TσY2)Var[ g]=O(Tσ^2_Y). The variance ratio is k′(1+(k′−1)ρ¯)/T≈k′/Tk (1+(k -1) ρ)/T≈ k /T when ρ¯≪1 ρ 1. ∎ See 3.10 Proof. The Counterfactual Shapley value is a weighted sum of marginal contributions: ϕt=∑:zt=0w()⋅[f(∪t)−f()], _t= _z:z_t=0w(z)·[f(z∪\t\)-f(z)], (38) where w()≥0w(z)≥ 0 are Shapley weights summing to 1. Each marginal contribution compares outcomes Y∪tY^z∪\t\ and Y^z under shared exogenous noise U. Let σ2=Var[Y]σ^2=Var[Y^z] (approximately equal for nearby coalitions) and ρY=Corr[Y∪t,Y] _Y=Corr[Y^z∪\t\,Y^z]. The variance of a single marginal contribution is: Var[Y∪t−Y] [Y^z∪\t\-Y^z] =Var[Y∪t]+Var[Y]−2Cov[Y∪t,Y] =Var[Y^z∪\t\]+Var[Y^z]-2Cov[Y^z∪\t\,Y^z] (39) =2σ2−2σ2ρY=2σ2(1−ρY). =2σ^2-2σ^2 _Y=2σ^2(1- _Y). (40) When environment stochasticity dominates action effects, ρY≈1 _Y≈ 1 (both outcomes are driven by the same exogenous noise), and variance vanishes. By convexity of variance, Var[ϕt]≤max⁡Var[f(∪t)−f()]=O(σ2(1−ρY))Var[ _t]≤ _zVar[f(z∪\t\)-f(z)]=O(σ^2(1- _Y)). In contrast, independent sampling (different U for each outcome) gives ρY=0 _Y=0 and variance 2σ22σ^2, a factor of 1/(1−ρY)1/(1- _Y) larger. ∎ See 3.11 Proof. Consider tabular TD(0) with terminal-only reward RTR_T (all Rt=0R_t=0 for t<Tt<T). Initialize V(s)=0V(s)=0 for all states. The TD(0) update at step t is: V(St)←V(St)+α[Rt+γV(St+1)−V(St)]V(S_t)← V(S_t)+α[R_t+γ V(S_t+1)-V(S_t)]. Episode 1: Only the transition (ST−1,ST)(S_T-1,S_T) has nonzero TD target (RT+γ⋅0=RTR_T+γ· 0=R_T). After episode 1: V(ST−1)>0V(S_T-1)>0, all other values remain 0. Episode n: The TD target at step T−nT-n becomes nonzero (since V(ST−n+1)>0V(S_T-n+1)>0 from previous episodes). Credit propagates backward by one step per episode. After T episodes: V(S1)V(S_1) receives its first nonzero update. This requires T episodes for credit to reach the initial state. In contrast, ϕφ-redistribution computes ϕt _t for all t from a single trajectory via O(T⋅Mδ,ϵ)O(T· M_δ,ε) counterfactual simulations. All timesteps receive credit signal in O(1)O(1) episodes. The trade-off: fewer episodes but O(T⋅M)O(T· M) simulation cost per episode. ∎ See 3.12 Proof. Follows directly from Proposition 3.11. For TD(0), each episode updates one state; propagating terminal reward across T states requires O(T)O(T) episodes with O(T)O(T) updates each, totaling O(T2)O(T^2). For ϕφ-redistribution, a single trajectory yields ϕt _t for all T timesteps via O(T⋅Mδ,ϵ)O(T· M_δ,ε) counterfactual simulations, so one episode suffices. ∎ Appendix E Additional Experiments This section contains additional experiments validating the theoretical predictions. E.1 Fork MDP S1S_1⋯·s11⋯·s0X1=0X_1=0X1=1X_1=1YT∼(1,σ2)Y_T N(1,σ^2)YT∼(0,σ2)Y_T N(0,σ^2)Yt∼(0,σ2)Y_t (0,σ^2) (t<Tt<T) Figure 8: Fork MDP results (n=1,000n=1,000 runs per condition; shaded bands are 95% CIs). Left: MDP structure; only the first c actions affect the terminal reward. Top row (a–c): Success rate across noise σ, horizon T, and causal steps c. Bottom row (d–f): Mean episodes to convergence. The Fork MDP isolates the three variance reduction benefits of ϕφ-PPO. The agent chooses from =0,1A=\0,1\ at each of T steps (γ=0.99γ=0.99). Only the first c actions affect the terminal reward: YT∼(1,σ2)Y_T (1,σ^2) if x1=⋯=xc=0x_1=·s=x_c=0 (the optimal actions), YT∼(0,σ2)Y_T (0,σ^2) otherwise. Intermediate rewards are i.i.d. noise Yt∼(0,σ2)Y_t (0,σ^2) for t<Tt<T. The environment combines sparse causality (k′=c≪Tk =c T, Proposition 3.9), high stochasticity (shared noise cancels in the counterfactual difference, Proposition 3.10), and delayed reward (YTY_T only, Proposition 3.11). Results (Figure 8). At the default configuration (T=100T=100, σ=10σ=10, c=1c=1), ϕφ-PPO achieves 100%100\% success, while REINFORCE degrades to ∼58% 58\% and PPO fails at ∼5% 5\%. Each column isolates one benefit: noise cancellation (a), horizon independence (b), and causal isolation (c). The bottom row confirms that ϕφ-PPO also converges fastest: median episodes remain low across all sweeps, while PPO and REINFORCE slow dramatically as conditions worsen. PPO’s clipping saturates under high-variance advantages, preventing meaningful policy updates. REINFORCE drifts randomly in parameter space, converging roughly half the time. With M=1M=1, ϕφ-PPO requires 2T2T steps per episode (one counterfactual rollout), yielding 4×4× episode efficiency but 2×2× simulation efficiency over PPO. Table 3: Hyperparameters for ϕφ-PPO (Section B) and Fork MDP experiments (Section E.1). Parameter Symbol Value ϕφ-PPO (Algo. 3) Discount factor γ 0.99 Trajectory length (chunk size) TchunkT_chunk 128 Batch size (trajectories) B 64 Policy epochs K 4 Coalition samples M 1 NTE mixing λ 1.0 (pure MC) GAE mixing λϕλ^φ 0.95 PPO clip ϵclip _clip 0.2 Value loss coefficient c1c_1 0.5 ϕφ-value loss coefficient c2c_2 0.5 Entropy coefficient c3c_3 0.01 Gradient clip norm gmaxg_ 0.5 Exploration decay γξ _ξ 0.99 PTR (Appendix D.5) Priority exponent αptr _ptr 0.6 UCB coefficient βucb _ucb 1.0 Priority floor ϵptr _ptr 0.01 EMA decay αema _ema 0.99 IS exponent βis _is β0→1 _0→ 1 IS exponent start β0 _0 0.4 IS annealing iters MβM_β 100000 Priority decay γp _p 0.999 Eviction threshold ϵevict _evict 10−610^-6 Optimization Learning rate η 0.10.1 Fork MDP environment Episode horizon TepT_ep 100 Causal actions c 1 Noise std σ 10 Network architecture – MLP [64, 64] E.2 Coin Flip MDP: High Stochasticity A single-step MDP: U∼Bernoulli(0.5)U (0.5), action X∈0,1X∈\0,1\, return Y=100U+XY=100U+X. The action’s causal effect is ϕ=1φ=1 with zero variance, while Var[Y]=2500Var[Y]=2500. Correlation ρ=Corr[Y(0,U),Y(1,U)]≈0.9998ρ=Corr[Y(0,U),Y(1,U)]≈ 0.9998. E.3 Treasure Hunt MDP: Delayed Reward A T=4T=4 step MDP with terminal reward only. Each step: collect treasure or skip. Reward Y3=#collectedY_3=\#\collected\. All actions are causal (k′=4k =4). ϕφ-TD provides signal in 1 episode; standard TD requires O(T)=4O(T)=4 episodes for credit propagation. Appendix F Limitations and Future Work Scope. Our approach requires a simulator to compute counterfactual trajectories, limiting applicability to environments with resettable state. Limitations. Our approach requires simulator access for counterfactual trajectories. Sample complexity scales with σ2/(1−γ)2σ^2/(1-γ)^2, which can be large when γ≈1γ≈ 1. We assume counterfactual independence (Assumption 3.3), excluding correlated exogenous noise. Future work. Finite-sample bounds via Bernstein concentration; relaxing counterfactual independence; empirical validation on Atari/MuJoCo benchmarks. Appendix G Credit Assignment Methods: Detailed Comparison To facilitate the discussion, here we entail the additional notations we use for related work comparison. αi→j _i→ j: learned attention weight from token j to token i. g(Δ0:t)g( _0:t): LSTM hidden state after processing trajectory up to step t. Pπ(Xt=x∣St,ST)P^π(X_t=x S_t,S_T): hindsight posterior over actions given a future state. Pπ(Xt=x∣St,Z)P^π(X_t=x S_t,Z): hindsight posterior over actions given observed return Z. ϕ⋆(s,x,z)φ (s,x,z): optimal DICE density-ratio estimator; χπ(z∣s)χ^π(z s): return distribution under π from state s. Φt _t: learned hindsight statistic of the future trajectory, constrained to satisfy Xt⟂Φt∣StX_t _t S_t. U′U : encoding of a future step (S′,X′,Y′)(S ,X ,Y ); choices include U′=S′U =S (state), U′=Y′U =Y (reward), or a learned encoding. (s,x,τ)Q(s,x,τ): quantile function—inverse CDF of the return distribution Fηs,x−1(τ)F^-1_ _s,x(τ) at quantile level τ∈[0,1]τ∈[0,1]. τ τ: inferred quantile level of the observed return, τ^=FηSt,Xt(Z) τ=F_ _S_t,X_t(Z). Bπ(s,x,s′)=V(s′)−S′∼p(⋅|s,x)[V(S′)]B^π(s,x,s )=V(s )-E_S p(·|s,x)[V(S )]: luck (nature’s contribution to the transition). First we provide an overview of the credit assignment methods we compare against in table 4 with their credit expressions and descriptions. Then table 5 evaluates each method against desirable credit assignment properties (3.1) on the Fork MDP (Section E.1: T=100T=100, σ=10σ=10, only X1X_1 causal). Below we discuss the details of each category of credit assignment methods in the literature. A. Temporal: discounted reward. In the existing credit assignment literature, action values/advantages often serve as a key proxy for actions’ influence on the rewards (watkins1992q; sutton1988temporaldiff; suttonMDPsSemimdpsFramework1999; pmlr-v37-schaul15; 10.5555/2031678.2031726generalvaluefunc; pmlr-v139-chang21bmodularity; pan2024skillorluck; auzina-intrinsic-credit-assignment-2026). Although action values and advantages yield unbiased gradients, they assign credit by actions’ temporal proximity to the reward, rather than their causal effects. This is both inefficient and biased in terms of credit assignment in that recent actions with no causal effect on the reward add noise to the gradient, while causally relevant actions that occur earlier receive discounted credit. Intuitively, credit should correspond to actions cause the outcome: we credit studying hard for a good grade, rather than flipping over the returned test to view the grade. B. Memory: learned models Another line of work utilizes learnable sequence models to automatically distribute the credit over actions (DBLP:conf/nips/ChenLRLGLASM21; arjona2019rudder; ijcai2020selfattentionalcredit; raposo2021synthetic; deng2026densegrpo), dropping the reliance on the time contiguity assumption. However, such methods conflate agent’s actions influence over rewards with environment stochasticity. As a result, they are unable to distinguish skill from luck in learning. Also, learned models suffer from the same problem as black box models that they are also in lack of explainability. C. Hindsight: posterior/prior ratios and conditional baselines The line of hindsight conditioning (hindsightcredit; velu2024hindsightdice; pmlr-v139-mesnard21a; mesnard2023quantile; meulemans2023would; ramesh2025improving)222For clarity, prior uses of the term ’counterfactual’ in this literature refer to hindsight conditioning not counterfactuals defined in the causal theory (pearl2009causality). partially addresses the skill-luck issue by conditioning on future events and credit each action by how relevant it is to the given event. The fundamental limitation of those is that isolating each single action during attribution overlooks subsequent actions’ collective influence on the rewards. Thus, the skill-luck issue still persists as we demonstrate in Figure 1. Table 4: Credit assignment methods: expressions and descriptions. Method Expression Description A. Temporal: discounted reward TD (williams1992simple), Options (suttonMDPsSemimdpsFramework1999), UVFA (pmlr-v37-schaul15), Horde (10.5555/2031678.2031726generalvaluefunc) γT−tYTγ^T-tY_T Reward YTY_T discounted by γT−tγ^T-t, the temporal distance from action XtX_t to reward Direct Adv. Estimation (pan2024skillorluck) A^(s,x) A(s,x) Fit Y=V(S0)+∑tA(St,Xt)+∑tBπ(St,Xt,St+1)Y=V(S_0)+ _tA(S_t,X_t)+ _tB^π(S_t,X_t,S_t+1) by least squares. A A: agent’s causal effect (skill); BπB^π: environment’s effect (luck) QCA (mesnard2023quantile) (s,x,τ^)−∑x′π(x′)(s,x′,τ^) subarraycQ(s,x, τ)\\ -\! _x \!π(x )Q(s,x , τ) subarray Quantile level τ^=Fηs,x(Z) τ=F_ _s,x(Z) indexes “luck.” Credit: action’s quantile value minus the policy-averaged quantile value at the same luck level B. Memory: learned models DT (DBLP:conf/nips/ChenLRLGLASM21) αT→t _T→ t Transformer trained via cross-entropy on actions, conditioned on returns-to-go Y^t=∑t′≥tYt′ Y_t= _t ≥ tY_t . Credit implicit via attention weights αT→t _T→ t RUDDER (arjona2019rudder) g(Δ0:t)−g(Δ0:t−1)g( _0:t)-g( _0:t-1) LSTM g trained via MSE on total return Y. Credit to step t: change in predicted return after observing (St,Xt)(S_t,X_t) SECRET (ijcai2020selfattentionalcredit) αt←TYT _t← T\,Y_T Transformer trained via weighted cross-entropy on sign(YT)sign(Y_T). Credit: attention αt←T _t← T on (St,Xt)(S_t,X_t), scaled by YTY_T C. Hindsight: posterior/prior ratios and conditional baselines HCA (hindsightcredit) Pπ(Xt=x∣St,ST)π(x∣St) P^π(X_t=x S_t,S_T)π(x S_t) Posterior over XtX_t given future state STS_T, divided by prior π. Ratio > 1>\,1: action became more likely given the future H-DICE (velu2024hindsightdice) π(x∣s)Pπ(Xt=x∣St,Z) π(x s)P^π(X_t=x S_t,Z) Same hindsight ratio as HCA (conditioned on return Z instead of state). Estimated via DICE variational objective ϕ⋆⋅χπφ \!·\!χ^π instead of direct density ratio CCA (pmlr-v139-mesnard21a) Gt−[Gt∣St,Φt]G_t-E[G_t\! \!S_t, _t] Φt _t: learned compression of future trajectory (S,X,Y)t+1:T(S,X,Y)_t+1:T, trained to predict GtG_t while satisfying Xt⟂Φt∣StX_t _t S_t. Baseline [Gt∣St,Φt]E[G_t S_t, _t] fit by regression COCOA (meulemans2023would) Pπ(U′∣St,Xt)Pπ(U′∣St)−1 P^π(U S_t,X_t)P^π(U S_t)-1 U′U : encoding of a future step (S′,X′,Y′)(S ,X ,Y ); typically U′=Y′U =Y (reward). Ratio measures how much XtX_t increased the probability of observing U′U . Estimated by supervised learning D. Ours: counterfactual simulation ϕφ-values −Y-Y^z, shared U Replay trajectory in simulator with alternative action Xt′∼πX _t π and same exogenous noise U. Credit: difference in outcomes Y−Y-Y^z Table 5: Desirable credit assignment properties, following the axiomatic framework of lee2025. D1 (Admissibility): non-causal actions receive zero credit. D2 (Power): causal actions receive nonzero credit. D3 (Normality): given equal causal effects, actions whose counterfactual baselines are more probable under π receive higher credit (actions π would have taken anyway get less credit). D4 (Effect scaling): given equal baselines, actions with larger causal effects receive proportionally more credit. D5 (Efficiency): credit sum to total return, ∑tϕt=Y−Y _t _t=Y-Y^0. ✓: satisfied. ∼ : partially or in principle but not in practice. ×: violated. Method D1 D2 D3 D4 D5 Admiss. Power Normal. Scaling Effic. A. Temporal TD × ∼ × ∼ × Options × ∼ × ∼ × UVFA × ∼ × ∼ × Horde × ∼ × ∼ × Direct Advantage Estimation ∼ × × × × QCA (exact) ✓ ✓ × ✓ × QCA (learned) ✓ × × × × B. Memory DT × × × × × RUDDER × ∼ × × ✓ SECRET × × × × ∼ C. Hindsight HCA ∼ × ∼ × × H-DICE ∼ × ∼ × × CCA ∼ ∼ × ∼ × COCOA ✓ × ∼ × × D. Ours ϕφ-values ✓ ✓ ✓ ✓ ✓

Instant research discovery