Anytime-valid Optimal Policy Identification

技術要約：任意のタイミングで有効な最適方策の識別

1. 問題設定

本論文は、ログに記録されたコンテキスト・バンディット・データを用いて、有限の候補クラス $\Pi = \{\pi_1, \dots, \pi_m\}$ から最適方策 ($\pi^\star$) を識別するという課題に取り組んでいる。多くの実用的な設定では、データはアナリストが制御できない外部的に決定されたロギング方策 ($h_t$) によって生成される。このロギング方策は、固定されたランダム化である場合もあれば、アナリストの特定の目的（例：誤情報の最小化）ではなく、別の目的（例：ユーザー・エンゲージメントの最大化）に合わせて調整された適応的アルゴリズムである場合もある。

核心となる困難さは、以下の2つの制約にある：

1. オフポリシー設定： アナリストは、識別目標に向けてデータ収集を誘導する能力がない状態で、異なる方策 $h_t$ の下で収集されたデータを用いて、ターゲット方策 $\nu(\pi)$ を推論しなければならない。
2. 逐次的モニタリング： 実務者は、データを継続的に監視し、データが蓄積されるにつれて明らかに劣った方策を排除し、固定されたサンプルサイズ ($N$) を事前に決定するのではなく、最適方策が特定された時点でデータ収集を停止したいと考えることが多い。

既存の文献における最適方策の識別は、通常、アナリストがデータ収集を制御している（適応的サンプリング）、あるいは、あらかじめ指定された固定サンプルサイズに対してのみ推論の保証を提供することを前提としている。本論文は、オフポリシーにおける最適方策識別のための**任意のタイミングで有効な（anytime-valid）**保証を提供することで、このギャップを埋めることを目的としている。

2. 手法

提案されるフレームワークは、データが到着するにつれて進化する、時間インデックスを持つ候補最適方策の集合 $S_t$ を構築する。この手法は、主に以下の3つのコンポーネントに基づいている。

A. 二重にロバストな擬似アウトカム（Doubly Robust Pseudo-Outcomes）
ログデータから方策の値 $\nu(\pi)$ を推定するために、本手法は重要度重み $w_t(\pi) = \pi(A_t|X_t) / h_t(A_t|X_t)$ を利用する。効率性と安定性を向上させるため、これらは報酬モデル $b_{rt}(x,a)$ と組み合わされ、二重にロバストな（DR）擬似アウトカムを構成する。具体的には、下限および上限の擬似アウトカム（$\phi^{DRL}_t$ および $\phi^{DRU}_t$）が定義されており、それらの条件付き期待値は真の方策値 $\nu(\pi)$ および $1-\nu(\pi)$ に等しくなる。決定的なことに、妥当性は報酬モデルが正しく指定されているかには依存せず、既知のロギング確率のみに依存する。

B. 任意のタイミングで有効な信頼区間（Confidence Sequences: CS）
Waudby-Smithら（2024）の研究に基づき、本論文は方策値の信頼区間を構築する。一連の区間 $[L_t(\pi), U_t(\pi)]$ が $(1-\alpha)$-CS であるとは、すべての $t \geq 1$ において、確率少なくとも $1-\alpha$ で真の値 $\nu(\pi)$ がその区間内に留まることを意味する。これらの区間は、DR擬似アウトカムと、証拠の蓄積を考慮した分散プロセス $V_t(\pi)$ を用いて構築される。区間の幅は $O(\sqrt{(\log \log t + \log m)/t})$ のレートで縮小する。

C. 逐次的排除と停止規則
方策クラス $\Pi$ に対する和集合（union bound）を用いることで、本手法は全方策に対する同時信頼区間を構築する。候補集合 $S_t$ は以下のように定義される：
$$S_t := \left\{ \pi \in \Pi : U_t\left(\pi; \frac{\alpha}{m}\right) \geq \max_{\pi' \in \Pi} L_t\left(\pi'; \frac{\alpha}{m}\right) \right\}$$
ある方策の期待値の上限が、競合する他の方策の最大下限を下回ったとき、その方策は $S_t$ から排除される。手順は、$S_\tau$ が単一の要素（一つの方策のみを含む状態）になったときのデータ依存的な時刻 $\tau$ で停止する。

3. 主な貢献

本論文は、主に2つの理論的貢献を行っている。

1. 任意のタイミングで有効な被覆保証： 著者らは、構築された集合 $S_t$ が以下の一様被覆保証を満たすことを証明している：
   $$P(\Pi^\star \subseteq S_t \text{ for all } t \geq 1) \geq 1 - \alpha$$
   ここで $\Pi^\star$ は真の最適方策の集合である。これは、アナリストがいつ停止を選択しようとも、高確率で最適な方策が排除されることはないことを保証している。

2. サンプル複雑性の境界： 最適方策 $\pi^\star$ が一意である場合、本論文はそれを識別するための停止時刻 $\tau$ を定義する。線形分散成長という正則性条件（仮定1）の下で、サンプル複雑度は以下のように導出される：
   $$\tau = O\left( \frac{\log m + \log \log(1/\Delta_{\min})}{\Delta_{\min}^2} \right)$$
   ここで $\Delta_{\min}$ は、最良の方策と次点のベストの方策との間の値の差である。この境界は、必要なサンプル数が方策クラスのサイズに対して対数的にスケールし、劣最適性のギャップに対しては逆二乗でスケールすることを示している。

4. 実証結果

本論文は、3つの実証デモンストレーションを通じてフレームワークを検証している。

• 合成シミュレーションによる例示： 6つの方策を持つコンテキスト・バンディットの設定を用いたシミュレーションにおいて、本フレームワークは、明らかに劣った方策をデータストリームの早い段階で排除し、最適方策が唯一特定されるまで保持することに成功した。方策値の信頼区間は、期待通りに真の値へと収束した。
• サンプル効率： 固定-$N$ 設計（$N$ はターゲットとなるギャップに基づいて計算される）と、任意のタイミングで有効な手順を比較した結果、真の劣最適性ギャップがターゲットのギャップよりも大きい場合、大幅なサンプル節約が可能であることが判明した。例えば、真のギャップがターゲットのギャップの2倍であった場合、本手法は平均して計画されたサンプルサイズの60〜80%を節約した。
• 実世界への適用： 本手法は、誤情報の拡散を減めることを目的とした、ケニアおよびナイジェリアの15,292人のユーザーを対象とした大規模な適応実験（Offer-Westort et al., 2024）に適用された。フレームワークは、元の研究の結論（「正確性のナッジ」と「Facebookのヒント」がトップパフォーマーであることの特定）を再現しつつ、証拠蓄積の動的なビューを提供した。最も成績の悪い方策は、最終データのわずかな一部だけで排除できる一方で、トップの候補は一貫して候補集合に留まり続けていることが示された。

5. 意義と限界

意義：
本論文は、オフポリシー設定における逐次的モニタリングのための厳密な推論フレームワークを提供している。これにより、アナリストは統計的保証を無効にすることなく、データ依存の停止決定を行うことが可能となり、固定-$N$ アプローチの主要な限界に対処している。これは、データ収集が外部のロギング方策によって制約され、リソースが限られている実世界のアプリケーションにおいて特に価値が高い。

限界：
著者らは、以下の2つの限界を明示している：

1. 時不変性： 本フレームワークは、方策の値が時間を通じて一定であることを前提としている。現在、治療効果が進化する（例：斬新性や疲労による）非定常な環境には対応していない。
2. オーバーラップの要件： 本手法は、すべてのターゲット方策がロギング方策に対して絶対連続であることを要求する（厳密なオーバーラップ）。これは、ターゲット方策が取る可能性のあるアクションに対して、ロギング方策が決定的にゼロの確率を割り当てるシナリオ（例：UCBスタイルの高度に集中した適応的アルゴリズム）を除外するものである。

本論文は、これらの限界はあるものの、本フレームワークが実務で一般的に見られる広範な確率的ロギング方策に対して、堅牢な解決策を提供すると結論付けている。