Counterfactual Shapley Credit Assignment
Abstract Overview
This paper frames temporal credit assignment in reinforcement learning as a causal attribution problem and proposes Counterfactual Shapley Credit Assignment based on counterfactual Shapley values. The method treats actions along a trajectory as contributors to the final return and uses counterfactual simulations under a baseline policy to redistribute reward into per-step causal credits. The authors show that this reward redistribution defines a φ-MDP that preserves the original optimal policy, and they derive a consistent estimator with amortized linear-time complexity across a trajectory. They then instantiate the idea in a policy optimization method, φ-PPO, combined with prioritized trajectory replay to focus updates on causally important subtrajectories.
Novelty
The distinctive contribution is the use of counterfactual Shapley values as a principled causal credit assignment mechanism for reinforcement learning, explicitly separating skill-driven effects from luck or environmental stochasticity. The paper also combines this causal attribution framework with a tractable estimator and a PPO-style training procedure, yielding a concrete learning algorithm rather than only an explanatory analysis.
Results
Empirically, the method assigns credit in line with the designed causal structure in the SkillLuck and DoorKey analyses, including zero credit for non-causal actions under appropriate baselines. In training benchmarks, φ-PPO performs best in the noisy SkillLuck setting and is the only compared method reported to scale beyond length 10 in the Combinatorial Lock task, where baselines collapse by length 15. The paper also reports faster convergence in episodes than baselines across benchmarks, while noting that higher counterfactual simulation cost can limit gains in total simulation budget in some settings.
Key Points
- The method redistributes returns into per-step causal credits via counterfactual Shapley values and theoretically preserves the original optimal policy.
- A consistent estimator computes trajectory-wide φ-values in amortized linear time and supports a bias-variance tradeoff through λ-bootstrapping.
- Experiments indicate better handling of stochasticity and delayed rewards than prior baselines, especially when standard PPO-style methods fail to converge.