論文要約：機械学習生成の代理報酬を伴う多腕バンディット問題

1. 問題設定 (Problem)

従来の多腕バンディット（MAB）アルゴリズムは、オンラインフェーズで腕を引く際に得られる真の報酬データのみを学習に利用します。しかし、実際の応用（臨床試験、推薦システムなど）では、オンライン開始前に豊富な履歴データ（過去のユーザーの共変量など）が存在することが多く、これを活用しないのは非効率です。

この論文が扱う新しい設定は以下の通りです：

• オフラインフェーズ: 真の報酬は観測できないが、機械学習（ML）モデル（事前学習済みモデルなど）を用いて、共変量から「代理報酬（Surrogate Rewards）」を生成できる。
• オンラインフェーズ: 真の報酬と代理報酬の両方を観測できる。
• 課題: 生成された代理報酬は、真の報酬と相関している場合でも、その平均値に大きなバイアス（偏り）があることが一般的です（例えば、新しい治療法や未踏の環境への外挿が必要な場合）。従来の手法はバイアスを修正するためにオフラインデータの分布がオンラインと同一であることを仮定したり、バイアスの上限を知っていることを前提としたりしますが、これらは現実的ではありません。

核心となる問い: 真の報酬と相関はあるが、平均値に任意のバイアスがある可能性のある ML 生成の代理報酬を、どのように利用してバンディット問題の累積後悔（Regret）を最小化できるか？

2. 手法 (Methodology)

著者らは、MLA-UCB (Machine Learning-Assisted Upper Confidence Bound) という新しいアルゴリズムを提案しました。この手法は、Prediction-Powered Inference (PPI) の考え方をバンディット問題に適用し、以下のステップで構成されます。

2.1 機械学習支援平均推定量 (ML-Assisted Mean Estimator)

各腕 $k$ について、オンライン観測数 $n$ とオフラインサンプル数 $N_k$ を用いて、真の平均報酬 $\mu_k$ を推定します。
推定量 $\hat{\mu}^{MLA}_{k,n}$ は、以下の式で定義されます：
$$\hat{\mu}^{MLA}_{k,n} = \bar{R}_{k,n} - \hat{\lambda}_{k,n} (\bar{\hat{R}}_{k,n} - \bar{\hat{R}}_{k, \text{off}})$$
ここで、$\bar{R}$ は真の報酬の平均、$\bar{\hat{R}}$ は代理報酬の平均、$\hat{\lambda}$ は分散最小化のための係数（回帰係数の推定値）です。
この推定量は、代理報酬のバイアス（$\bar{\hat{R}}_{k,n} - \bar{\hat{R}}_{k, \text{off}}$）を補正項として利用することで、真の報酬の推定分散を減少させます。

2.2 信頼区間の構築 (Confidence Bound Construction)

UCB アルゴリズムの核心である「上界（Upper Confidence Bound）」を構築するために、以下の工夫がなされています：

• 分散の未知性への対応: 真の報酬や代理報酬の分散、およびそれらの共分散行列を事前に知らなくてもよいように設計されています。
• t 検定の逆転: 従来の UCB が正規分布の分位数を用いるのに対し、本手法は t 分布の分位数を逆転させることで、有限サンプルにおける正確な分布特性を捉えます。
• 分散分解: 推定誤差を、代理報酬の平均のバイアスに起因する成分と、回帰モデルの切片推定の不確実性に起因する成分に分解し、それぞれに対して適切な不偏推定量（残差分散など）を用いて信頼区間を構成します。

2.3 バッチ報酬への拡張 (Batched Reward Extension)

実際の応用では、個々の単位ではなくバッチ単位で意思決定が行われることがあります（例：価格設定の頻度制限）。この場合、個々の報酬分布が非ガウス分布であっても、中心極限定理や自己正規化された中偏差（Self-normalized Moderate Deviation）の理論を用いることで、有効な信頼区間と後悔保証を導出しています。

3. 主要な貢献と理論的保証 (Key Contributions & Theoretical Results)

3.1 累積後悔の改善

真の報酬と代理報酬が二変量ガウス分布に従うと仮定した場合、MLA-UCB の累積後悔の上限は以下のようになります（$T$ は総試行回数、$\Delta_k$ は最適性ギャップ、$\rho_k$ は相関係数）：
$$E[\text{Reg}_T] \leq \sum_{k \neq k^*} \frac{2\Delta_k \log T}{\log\left(1 + \frac{\Delta_k^2}{\sigma_k^2 (1-\rho_k^2)}\right)} + O((\log T)^{5/6})$$

• バイアスへの頑健性: 代理報酬の平均が真の平均と完全に一致していなくても（バイアスが任意に大きくても）、相関 $\rho_k$ が存在すれば後悔は減少します。これは、データを集約するのではなく「分散を減少させる」ことで達成されます。
• 漸近最適性: 提案アルゴリズムは、オフラインサンプルサイズが $N_k = \Omega((\log T)^{4/3})$ 程度あれば、理論的下限（Lower Bound）と一致する漸近最適性を達成します。
• 既存手法との比較: バイアスの上限を知らなくても改善が保証される点で、既存のオフラインデータ利用バンディット手法よりも優れています。

3.2 非ガウス分布・バッチ設定への一般化

ガウス分布の仮定を外し、非ガウス分布かつバッチ処理が行われる設定においても、自己正規化された中偏差の理論を用いて、同様の分散減少効果を持つ後悔保証を導出しました。

4. 実験結果 (Results)

4.1 シミュレーション

• ガウスモデル: 相関 $\rho$ やオフラインサンプル数 $N$ を変化させた実験において、MLA-UCB は古典的な UCB アルゴリズムを大幅に上回る性能を示しました。特に、オフラインデータが増えるほど、および相関が強くなるほど後悔は減少しました。
• ML 生成の非ガウス代理報酬: 線形回帰、SVR、ニューラルネット、決定木などを用いて実際の ML モデルから代理報酬を生成したシミュレーションでも、理論的なガウス仮定が満たされない場合でも、MLA-UCB は一貫して UCB よりも低い後悔を達成しました。線形モデルのように予測精度が低い場合でも、古典的 UCB と同等以上の性能を維持しました。

4.2 実世界データへの適用

• 言語モデルの選択: 複数のプロプライエタリ LLM（GPT-4o など）の中から最適なモデルを選ぶタスクにおいて、オープンソース LLM（Llama など）の予測を代理報酬として利用しました。結果、MLA-UCB は古典的 UCB よりも効率的に最適なモデルを特定しました。
• 動画推薦: KuaiRec データセットを用いた推薦タスクにおいて、ユーザー特徴量に基づく ML 予測を代理報酬として利用しました。これも同様に、オフラインデータを活用することで累積後悔を削減しました。

5. 意義と結論 (Significance)

この研究は、機械学習の進歩に伴って利用可能になった「大量のオフラインデータ」と「事前学習済みモデル」を、意思決定の最適化（バンディット問題）に安全かつ効率的に統合するための理論的基盤を提供します。

• 実用性: 代理報酬がバイアスを持っていても（ Ranking が保たれていなくても）、相関さえあれば有効活用できるため、臨床試験や推薦システムなど、真の報酬の観測コストが高く、オフラインデータが豊富な分野での応用が期待されます。
• 理論的革新: バイアスの上限を知らずに、かつ分散が未知の状況で、相関を利用した分散減少による後悔改善を証明した点で、バンディット理論と推論理論（PPI）の融合として画期的です。
• 将来展望: 文脈バンディット（Contextual Bandits）など、より複雑な設定への拡張も今後の重要な研究方向として示唆されています。

要するに、この論文は「バイアスのある ML 予測を、統計的に厳密に補正・利用することで、探索・活用のトレードオフを劇的に改善する」新しいアルゴリズムと理論を提示したものです。