技術的概要：予算およびカバレッジ制約下における最適政策学習

1. 問題定義

本論文は、意思決定者が $N$ 個の単位からなる集団に対して限られた資源（処置）を配分し、総厚生（期待利得）を最大化する最適政策学習の問題を取り扱う。この配分は、以下の 2 つの同時制約に服する：

1. 予算制約：処置の総費用は、固定された予算 $B$（または 1 人当たり予算 $C$）を超えてはならない。
2. 最小カバレッジ制約：人口の最小割合 $\rho$ に対して処置を施さなければならない。

この問題は、効率性（利得の最大化）と公平性または政治的要請（広範なカバレッジの確保）とのバランスが求められる、公的雇用訓練、医療介入、社会給付などの文脈で生じる。核心的な課題は、最適解が指数関数的に大きい代替案の集合（$2^N$）から部分集合を選択する必要があり、これは NP 困難な組み合わせ最適化問題となる点にある。

2. 手法と理論的枠組み

2.1 双対性に基づく特徴付け

著者は、潜在結果の枠組み内で問題を定式化する。$\tau(x)$ を条件付き平均処置効果（CATE）、$c(x)$ を共変量 $x$ を持つ個人への処置費用とする。目的は、$E[\pi(X)c(X)] \leq C$ および $E[\pi(X)] \geq \rho$ の制約の下で $E[\pi(X)\tau(X)]$ を最大化することである。

ラグランジュ双対性を用いると、最適政策 $\pi^*$ がアフィン閾値則の形をとることが示される：
$$\pi^*(x) = \mathbb{1}\{ \tau(x) - \lambda^* c(x) + \nu^* \geq 0 \}$$
ここで：

• $\lambda^*$ は予算制約のシャドウプライスである。
• $\nu^*$ はカバレッジ制約のシャドウプライスである。
• この則は、カバレッジのシャドウプライスで調整された利得が、予算のシャドウプライスでスケーリングされた費用を上回る場合に個人に処置を施す。

この構造は、単純な比率則 $\tau(x)/c(x) \geq \lambda^*$ を導く標準的な予算制約付き問題とは異なり、カバレッジ制約が加法性のシフト（$\nu^*$）を導入し、不均質な決定境界を形成する点で異なる。

2.2 ナップサック問題との等価性と LP 緩和

問題の実証的対応は、追加的な基数制約を有する0-1 ナップサック問題と等価であることが示される。

• 組み合わせ形式：$\sum c_i d_i \leq nC$ および $\sum d_i \geq n\rho$ の制約の下で $\sum \hat{\tau}_i d_i$ を最大化するように、二値ベクトル $d \in \{0,1\}^n$ を選択する。
• 線形計画法（LP）緩和：二値制約を $z_i \in [0,1]$ に緩和する。

重要な理論的結果は、整数性ギャップ（最適 LP 値と最適 0-1 値の差）の分析である。本論文は以下のことを証明する：

1. LP 緩和の任意の極点解は、高々2 つの分数成分しか持たない。
2. したがって、絶対的な整数性ギャップは定数 $O(1)$（具体的には $2V_{max}$）によって有界である。
3. 1 人当たりの観点では、このギャップは $O(1/n)$ として漸近的に消滅する。これは、LP 緩和が離散的最適解と漸近的に等価であることを意味する。

2.3 実装可能なアルゴリズム

LP 緩和とアフィン閾値構造に基づき、2 つのアルゴリズムが提案される：

1. カバレッジ付き貪欲 - ラグランジュ法（GLC）：

   • メカニズム：予算のシャドウプライス $\lambda$ に対する双対探索。固定された $\lambda$ に対して、単位を $a_i(\lambda) = \hat{\tau}_i - \lambda c_i$ によってスコアリングする。
   • 手順：アルゴリズムは、スコア順に上位 $K_n$（最小必要数）の単位を処置セットに強制的に含めることでカバレッジ制約を履行し、その後、予算が尽きるまで正のスコアを持つ残りの単位を貪欲に追加する。乗数 $\lambda$ は、予算制約を満たすように二分法で調整される。
   • 計算量：$O(n \log n \cdot \log(1/\varepsilon))$。

2. ランク付けとカット（RC）：

   • メカニズム：コスト効果比 $s_i = \hat{\tau}_i / c_i$ のみで単位をランク付けする非反復的なヒューリスティック則。
   • 手順：単位を $s_i$ の降順にソートする。アルゴリズムは、予算とカバレッジの両方の制約を満たす最大の可能なプレフィックスを選択する。
   • 計算量：$O(n \log n)$。

3. 主要な結果

3.1 漸近最適性

本論文は、GLC アルゴリズムが漸近的に最適であることを確立する。LP 緩和の 1 人当たり整数性ギャップが消失するため、LP 最適解を近似する任意の実行可能な貪欲則（GLC はこれに該当する）は、元の組み合わせ問題に対しても漸近的に最適となる。

3.2 ランク付けとカット（RC）のパフォーマンス

本論文は、より単純な RC 則が近似最適となる条件を正確に特徴付ける。最適政策に対する RC の厚生損失は、RC が使用する定数閾値と、最適政策の不均質なアフィン閾値との間の不一致によって駆動される。

• 等価性の条件：RC は、以下の条件で近似最適である：
  1. 費用が均質である場合（$c(x) \approx c_0$）、または
  2. カバレッジ制約が緩やかである場合（$\nu^* \approx 0$）。
• 誤配分の条件：重大な誤配分が発生するのは、費用の不均質性が顕著であり、かつカバレッジ制約が拘束的（$\nu^* > 0$）である場合に限られる。この特定の領域では、最適政策のアフィン境界は単純な比率に基づくランク付けでは再現できず、カバレッジを満たすために低比率の単位が処置され、予算制約により高比率の単位が除外される結果となる。

3.3 モンテカルロ証拠

2 つのシミュレーション研究が理論的知見を支持する：

1. GLC と LP の比較：サンプルサイズ $n$ が増加するにつれ、GLC の厳密な最適解（MILP）に対する 1 人当たりの後悔は急速に減少し、低いレベルで安定する。LP 整数性ギャップも急速に消失し、$O(1/n)$ の収束が確認される。
2. RC と LP の比較：4 つの領域（費用の不均質性とカバレッジの厳しさを変化させたもの）にわたるシミュレーションは、費用が不均質でカバレッジが拘束的な場合を除き、RC と最適政策間の誤配分がすべてのケースで無視できることを確認する。その特定の「最悪ケース」シナリオでは、誤配分の面積は有意（約 15%）であり、理論的な相互作用効果を検証する。

4. 貢献と意義

本論文は、3 つの主要な貢献を行う：

1. 構造的表現：制約付き政策学習を、2 つのシャドウプライスを有するアフィン閾値則を伴うナップサック型問題として構造的に特徴付け、予算とカバレッジ制約間の相互作用を明示的にモデル化する。
2. 漸近的緊密性：この組み合わせ問題の LP 緩和が $O(1)$ の整数性ギャップを持つことを確立し、緩和解と離散解が 1 人当たりの観点で漸近的に等価であることを証明する。これにより、大規模応用においてより単純でスケーラブルな規則の使用が正当化される。
3. 実装と限界：2 つのスケーラブルなアルゴリズム（GLC と RC）を提案し、分析する。特に、単純な非反復的 RC 則が失敗する正確な構造的条件を特定する。本論文は、統計的政策学習と組み合わせ最適化の間の溝を埋め、理論的基盤と計算のスケーラビリティの両方を備えた枠組みを提供する。

この研究の意義は、最適政策の理論的記述を超えて、実装可能でスケーラブルな解決策を提供し、かつ性能保証を伴う点にある。それは、単純なコスト効果ランク付けがしばしば十分であることを明確にする一方で、政策決定者は、そのようなヒューリスティックが重大な厚生損失をもたらす可能性のある特定の構造的条件（不均質な費用＋拘束的なカバレッジ）を認識する必要があることを示唆している。