CAPO: Counterfactual Credit Assignment in Sequential Cooperative Teams

1. 問題定義と背景

背景:
協調型マルチエージェントシステム（例：大規模言語モデル（LLM）のパイプラインやツール使用エージェント）では、チーム全体が得た報酬を個々のエージェントにどう割り当てるかが重要な課題です。

核心的な課題:

1. クレジット割り当ての難しさ: チーム報酬は共有されているため、個々のエージェントの貢献度を特定するのは未決定問題（under-determined）です。
2. 逐次更新による非定常性: 従来の同時実行設定とは異なり、エージェントが固定された順序（1, 2, ..., K）で行動し、学習バッチ内でエージェントごとに逐次更新される場合、上流のエージェントのポリシーが更新されると、下流のエージェントの行動分布が変化します。
   • これにより、バッチ内で収集されたデータは、後続の更新ステップにおいて「オフポリシー（off-policy）」となり、既存の手法（重要性サンプリングなど）では分散が指数関数的に増大するか、推定が困難になります。

2. 提案手法：CAPO (Counterfactual Advantage Policy Optimization)

CAPO は、クリティック（価値関数）を必要としない方策勾配（Policy Gradient）アルゴリズムです。その核心は、Sequential Aristocrat Utility (SeqAU) という新しい学習信号の導出と、それを効率的に推定する仕組みにあります。

2.1 理論的基盤：Sequential Aristocrat Utility (SeqAU)

• Wolpert and Tumer (2002) の拡張: 従来の「Aristocrat Utility (AU)」を、同時実行から逐次実行の文脈へ拡張しました。
• 定義: エージェント $k$ の SeqAU は、チーム報酬 $R$ から、そのエージェントの行動 $a_k$ に依存しない「前接（prefix）条件付き」の基準値を差し引いたものです。
  $$A^{SeqAU}_k = E[R | a_{\le k}] - E[R | a_{<k}]$$
• 最適性: この基準値（$E[R | a_{<k}]$）は、個々のエージェントの学習可能性（Learnability）を最大化する唯一の基準値であることが証明されています（定理 1）。これにより、他のエージェントのノイズに埋もれず、自身の行動の影響を明確に捉えることができます。

2.2 アルゴリズムの 3 つの主要要素

CAPO は、SeqAU を実用的な推定量に変換するために以下の 3 つの技術を採用しています。

1. 加法的報酬分解 (Additive Reward Decomposition):

   • チーム報酬を個々のエージェントの寄与の和としてモデル化します（$R \approx \sum \phi_k(a_k)$）。
   • ridge 回帰（最小二乗法）を用いて、バッチデータから各エージェントの寄与 $\phi_k$ を**閉形式（closed-form）**で推定します。これにより、学習されたクリティック（ニューラルネット）が不要になります。

2. 上流キャンセルの恒等式 (Upstream Cancellation Identity):

   • 推定されたアドバンテージを計算する際、上流のエージェント（$j < k$）の寄与は、条件付き期待値の差において正確に相殺（キャンセル）されることが示されました。
   • これにより、推定すべき量は「直接効果（Direct Effect）」と「間接効果（Indirect Effect）」の 2 つに簡略化されます。

3. 架空サンプリング (Fictitious Sampling) による間接効果の推定:

   • 直接効果: 現在のエージェントの行動変化による即時的な報酬変化（閉形式で計算可能）。
   • 間接効果: 現在のエージェントの行動が、下流のエージェントの行動分布を変化させ、結果として報酬に影響を与える部分。
   • CAPO は、実際の環境再実行や重み付け（重要性サンプリング）を行わず、**現在の共同方策 $\pi^{(k-1)}$ に基づいて下流の行動を「架空にサンプリング」**することで、この間接効果を推定します。これにより、環境呼び出しのオーバーヘッドを最小限に抑えつつ、非定常性への対応を可能にしています。

3. 主要な貢献

1. Sequential Aristocrat Utility (SeqAU) の導出:
   • 逐次協調チームにおける学習可能性を最大化する唯一の基準値を数学的に特定し、従来の同時実行フレームワークを一般化しました。
2. CAPO アルゴリズムの提案:
   • クリティック不要、環境再実行不要、累積重要性サンプリング不要という、計算効率と統計的安定性を両立する新しい方策勾配法を提案しました。
3. 解析的なバイアスと分散の解析:
   • バイアス: 報酬の加法性からの乖離（非加法的残差）に比例して線形に増加することを示しました。
   • 分散: 共有ベースライン手法（MA-GRPO など）の $\Theta(K)$ や、累積重要性サンプリング手法（HA-GRPO など）の指数関数的な分散に対し、CAPO はエージェント数 $K$ に依存しない（または $O(K-k)$ 程度）分散特性を持つことを証明しました。
4. 理論と実験の整合性:
   • 制御された逐次バンドット環境において、理論的な予測通り、チームサイズが大きくなるほど CAPO が他手法を凌駕することを実証しました。

4. 実験結果

実験設定:

• 協調型逐次バンドット環境（エージェント数 $K$、行動数 $A$）。
• 報酬は加法的な部分と、エージェント間の相互作用（非加法的）部分で構成。
• 比較対象：MA-GRPO（共有ベースライン）、HA-GRPO（累積重要性サンプリング）、C3（リプレイベース）。

結果:

1. アドバンテージ推定の精度 (MSE):
   • エージェント数 $K$ が増加するにつれて、CAPO の推定誤差（MSE）はほぼ一定（フラット）に保たれました。
   • 対照的に、MA-GRPO は $K$ に比例して増加し、HA-GRPO は $K$ に対してより急激に増加しました。
   • $K=16$ の場合、CAPO の誤差は C3 の約半分、MA-GRPO の約 1/30、HA-GRPO の約 1/46 でした。
2. 非加法的報酬への頑健性:
   • 報酬の相互作用強度が増しても、CAPO の誤差は理論予測通り線形的に増加し、他の手法と比較して全体的に良好な性能を維持しました。
3. エンドツーエンドの最適化性能:
   • 小規模チーム（$K=2$）では既存手法と同等ですが、$K \ge 4$ 以降、CAPO の性能が MA-GRPO を上回り、$K=10$ 付近ではその差が顕著になりました。
   • HA-GRPO は $K$ が増えると急激に性能が劣化しました。
4. アブレーション研究:
   • 「間接効果」の補正を除去した CAPO-Direct との比較において、エージェント間の依存関係（非定常性）が高い場合（$\rho$ が大きい）、間接効果の推定が性能向上に不可欠であることが確認されました。

5. 意義と将来展望

• LLM パイプラインへの適用: 現代のマルチエージェント LLM システム（例：Reasoner-Solver パイプライン）は本質的に逐次的であり、CAPO のような「クリティック不要かつ反実仮説的」なアプローチは、環境評価（Reward Evaluation）が高コストな場合に特に有効です。
• 計算効率: 環境とのインタラクションを最小限に抑えつつ、現在のポリシーに基づいたサンプリングを行うことで、大規模チームでのスケーラビリティを実現しています。
• 理論的裏付け: 分散とバイアスに関する厳密な解析は、マルチエージェント強化学習の理論的基盤を強化するものです。

結論:
CAPO は、逐次協調マルチエージェントシステムにおけるクレジット割り当ての難問に対し、理論的に最適化された学習信号（SeqAU）と、効率的な推定手法（加法的分解＋架空サンプリング）を組み合わせることで、既存手法の限界（分散の増大や計算コスト）を克服する画期的なアプローチです。特に、大規模な LLM ベースの協調システムにおける実用的な学習アルゴリズムとしての可能性を大きく拓くものです。