技術要約：情報指向サンプリングを用いた因果バンディット

問題定式化

本論文は、操作不可能な変数を含む環境におけるコンテキスト因果バンディットの問題を扱う。標準的なマルチアームバンディット問題では、未知の分布から報酬を最大化するようにアクションが選択される。因果バンディットにおいては、アクションは構造的因果モデル（SCM）に対する介入（$do(X=x)$）に対応し、報酬は共有された因果メカニズムを通じて結合されている。

ここで取り組まれている特定の課題は、報酬に影響を与えるものの、直接操作することができない変数（例：人口統計学的属性、遺伝的特性、またはマクロ経済状況）が存在する場合に生じる。これらの変数は介入することはできないが、アクション選択前に観測されるコンテキスト変数として、また介入後の観測変数として機能する。目標は、候補となるアームの集合から実行可能な介入を選択し、コンテキスト依存の期待報酬 $\mu_x(c) = E[Y | do(x), C=c]$ を効率的に最大化することである。

著者らは以下の条件を仮定している：

1. 潜在的な交絡因子が存在しない既知の因果グラフ $G$。
2. 操作不可能な変数の集合 $N \subseteq V \setminus \{Y\}$。
3. コンテキスト変数 $C$ はアクション選択前に観測され、かつ祖先関係の下で閉じている（すなわち、$An(C)=C$）。
4. 観測分布は未知であり、条件付き確率表（CPT）によってパラメータ化されている。

手法

1. ベイズ定式化とパラメータ化

著者らは、未知のパラメータ $\theta$ が観測分布の条件付き確率表で構成されるベイズフレームワークを採用している。潜在的な交絡因子がないという仮定の下では、介入分布は、切断因子化公式を通じて観測分布から識別可能である。

• パラメータの独立性: パラメータベクトル $\theta$ は、各変数の親の構成に対するCPTに対応する局所的なベクトル $\theta_{ij}$ に分解される。
• 事後分布の更新: 共役ディリクレ事前分布を仮定することで、観測されたデータに基づいて $\theta$ の事後分布を解析的に更新できる。これにより、ある介入下で収集されたサンプルが、共有されたCPTを精緻化することを通じて、他の介入に対する推定値を更新することが可能になる。

2. 候補アームの識別

操作不可能な変数を扱うために、本論文ではLeeおよびBareinboim [2019] によって導出された**「おそらく最適である最小介入集合（POMISs）」**の概念を利用している。

• 投影: 元のグラフは、操作可能な変数のみを含むグラフ $H$ に投影される。操作不可能な変数によって誘発される潜在的な交絡は、$H$ における双方向エッジとして表現される。
• アーム選択: 候補アームの集合 $\mathcal{A}$ は、投影されたグラフ $H$ のPOMISsを列挙することによって生成される。これにより、アルゴリズムは操作性の制約下で理論的に最適とされる介入のみを検討することが保証される。

3. 提案アルゴリズム

本論文では、標準的なバンディットアルゴリズムの2つの因果的バリアントを提案している。

A. 因果的トンプソンサンプリング (TS)

• メカニズム: 各ラウンド $t$ において、コンテキスト $C_t=c_t$ が与えられたとき、アルゴリズムはコンテキスト条件付き事後分布 $P(\theta | F_t, C_t=c_t)$ からパラメータ $\theta_t$ をサンプリングする。その後、サンプリングされたパラメータの下での期待報酬を最大化するアクション $a_t$ を選択する：$a_t = \arg\max_{a \in \mathcal{A}} E[Y_a | \theta_t, c_t]$。
• 後悔（Regret）解析: 著者らは、最適なアクションマッピングのエントロピー $H(\Pi^*)$ に依存する劣線形ベイズ後悔界を確立している。この界は $O(\sqrt{T |A| |C| \log |A|})$ としてスケールする。

B. 因果的情報指向サンプリング (IDS)

• メカニズム: IDSは、**情報比（information ratio）**を最小化するようにアクションの分布を選択する。情報比は、二乗された期待瞬間的後悔を、最適なアクションに関する期待情報利得で除したものである。
  • 後悔項: $\Delta_t(\pi | c_t) = \sum \pi(a) E[Y_{\Pi^*(c_t)} - Y_a]$。
  • 情報利得項: $g_t(\pi | c_t) = \sum \pi(a) D_{KL}(P(\Pi^*, Y_a) || P(\Pi^*)P(Y_a))$。
• モンテカルロ近似: 必要な事後期待値を計算するために必要な事後分布が連続的なパラメータ空間において解析的に困難であるため、アルゴリズムは事後分布からの $N$ 個のモンテカルロサンプルを用いてこれらを近似する。
• 誤差制御: 著者らは、期待後悔および情報利得のモンテカルロ推定値に関する高確率集中不等式（補題3および4）を導出している。これらの界は、近似によって導入される追加の誤差を明示的に定量化している。

主な貢献

1. 操作不可能な変数のためのベイズフレームワーク: 本論文は、観測CPTを未知のパラメータとして扱うことで、操作不可能な変数を持つコンテキスト因果バンディットを定式化した。この定式化により、一部の変数が操作不可能であっても、共有された因果メカニズムを通じて異なる介入間での情報の共有が可能になる。
2. 後悔保証を持つ因果的トンプソンサンプリング: 著者らは因果的TSアルゴリズムを提案し、エントロピー依存の劣線形ベイズ後悔界を証明した。これは、構造的な制約とコンテキストが存在する設定へとTSの保証を拡張するものである。
3. 近似解析を伴う因果的IDS: 本論文は、後悔の最小化と情報の獲得のバランスを取る因果的IDSアルゴリズムを開発した。決定的な点として、標準的な情報論的項と、モンテカルロ近似によって導入される誤差を明示的に分離した後悔界を導出している。情報比が正確に計算される場合（オラクル版）、標準的な劣線形IDSレートが回収される。
4. モンテカルロ推定のための集中不等式: 著者らは、期待瞬間的後悔およびコンテキスト依存の情報利得のモンテカルロ推定値に対する高確率信頼界を提供している。これらの結果は、事後サンプリング誤差がアルゴリズムの性能保証に与える影響を定量化するものである。

結果と評価

提案された手法は、構造化された例やランダムに生成された因果グラフを含む、複数の合成因果バンディットタスクを用いて評価された。

• 性能: 実験の結果、提案された因果的TSおよび因果的IDSアルゴリズムは、因果的および非因果的な両方のベースラインを上回ることが示された。
• メカニズム: 優れた性能は、特に操作不可能な変数が存在する場合において、共有された因果構造を介して異なる介入間で共有される情報をより効果的に活用できるという、アルゴリズムの能力に起因している。

意義

本論文は、変数の完全な制御が不可能な因果環境における意思決定のための、原理的なフレームワークを提供することで意義を持つと主張している。操作不可能な変数を因果バンディットの枠組みに統合し、近似誤差の解析を含む厳密な後悔界を提供することで、本研究は理論的な因果推論と実用的な逐次的意思決定の間の溝を埋めるものである。IDSにおけるモンテカルロ近似誤差の明示的な扱いは、主要な理論的進歩として強調されており、正確な計算が困難な場合でも情報指向サンプリングの利点が維持されることを保証している。