Offline-to-Online Learning in Linear Bandits

技術要約：線形バンディットにおけるオフライン・ツー・オンライン学習

問題提起
本論文は、確率的線形バンディットの設定におけるオフライン・ツー・オンライン学習の問題に取り組んでいる。このシナリオでは、学習者はホライゾン $n$ にわたって累積報酬を最大化するために、集合 $\mathcal{A} \subset \mathbb{R}^d$ から行動を逐次的に選択するが、事前に存在するオフラインデータセット $\mathcal{D}$ にアクセスできる。オフラインデータは、固定された非適応的なデザイン（決定論的な行動回数）を通じて収集されており、劣ガウスノイズを伴う線形報酬モデルに従う。

核心となる課題は、以下の2つの相反する目的の間のトレードオフにある：

1. オンライン後悔 ($R_n$): 最適な行動 $\mu^*$ に対する後悔を最小化すること。標準的なオンラインアルゴリズム（例：LinUCB）は、探索のために楽観主義に依存しており、劣線形な後悔を達成するが、オフラインデータを無視すると初期の後悔が高くなる可能性がある。
2. オフライン後疑 ($R_n^{off}$): オフラインデータセットの平均報酬 ($\mu_{off}$) に対する後悔を最小化すること。標準的なオフラインアルゴリズム（例：LinLCB）は、既知のデータを活用するために悲観主義に依存しており、$\mu_{off}$ に近い性能を保証するが、探索に失敗するため、オフラインデータが劣っている場合やホライゾンが長い場合には線形な後悔を招く。

既存の研究は、これら2つのレジームを別々に扱ったり、行動数の数に応じて後悔がスケールするマルチアームバンディット（MAB）に焦点を当てたりすることが多かった。本論文は、後悔が行動空間のサイズではなく次元 $d$ にスケールすべき構造化された（線形）環境において、そのギャップを埋めることを目的としている。

手法：LinOtO アルゴリズム
著者らは、探索予算を管理することで探索と活用のバランスを動的に調整するアルゴリズムである LinOtO (Linear Offline-to-Online) を提案している。このアルゴリズムは、オフラインおよびオンラインの両方のデータから構築された信頼集合 $C_t$ に基づいて、2つの戦略を切り替えることで動作する：

1. 信頼集合: アルゴリズムは、最小二乗推定値 $\hat{\theta}_t$ と、真のパラメータ $\theta^*$ の周囲の信頼楕円体 $C_t$ を保持する。この集合の半径には、オフラインデータからの不確実性 ($\beta_{off}$) とオンラインの相互作用からの不確実性 ($\beta_t$) の両方が組み込まれている。
2. 楽観的 vs 悲観的行動:
   • UCB 行動 ($U_t$): $C_t$ 内で上限信頼境界（Upper Confidence Bound）を最大化する行動。これは探索を促進し $R_n$ を減少させるが、$R_n^{off}$ を増加させるリスクがある。
   • LCB 行動 ($L_t$): 下限信頼境界（具体的には、時間の経過に伴う最小信頼境界の最大値）を最大化する行動。これはオフラインデータの活用を促進し $R_n^{off}$ を減少させるが、$R_n$ を増大させる可能性がある。
3. 予算メカニズム:
   • アルゴリズムは、特定の「安全な」行動 $L_{off}$（オフラインデータのみから計算されたLCB行動）の報酬の下限から導出される安全なベースライン報酬 $r_b$ を定義する。命題2は、$L_{off}$ が高確率で $\mu_{off}$ に近いことを保証している。
   • 探索予算 $B(t)$ が、ベースライン $r_b$ に対するアルゴリズムの超過累積報酬を表すものとして維持される。
   • 決定ルール: もし $B(t) > 0$ であれば、アルゴリズムは楽観的な行動 $U_t$ を選択する（探索）。もし $B(t) \le 0$ であれば、予算を蓄積するために悲観的な行動 $L_t$ を選択する（活用）。
   • このメカニズムにより、アルゴリズムはオフラインのベースラインに対して安全な状態を維持している間にのみ、「探索する権利」を得られるように制御される。

主な貢献

1. アルゴリズム設計: 本論文は、予算ベースの切り替えメカニズムを介して UCB と LCB 戦略を同時にバランスさせる、オフライン・ツー・オンライン線形バンディット用に特別に設計された最初のアルゴリズムである LinOtO を提示している。
2. 理論的保証: 著者らは、両方の指標に対して高確率の後悔界を確立している：
   • オンライン後悔 ($R_n$): 定理1は、LinOtO が最適な行動に対して劣線形な後悔を達成することを示している。この界は、ホライゾン $n$ に依存する項（LinUCBと同様）と、オフラインデータの質に依存する加算定数から構成される。オフラインデータが空間を十分にカバーしていれば、界は改善される。
   • オフライン後悔 ($R_n^{off}$): 定理2は、オフラインのリファレンスに対する後悔が $n$ に対して線形にスケールするが、オフラインサンプル数 $m$ に対して $O(1/\sqrt{m})$ で減少することを示す。これは純粋なオフライン（悲観的）な解の性能と一致する。
3. パレート・トレードオフ分析: 分析により、パラメータ $\alpha$ によって制御される調整可能なトレードオフが明らかになった。$\alpha$ を大きくするとオンラインの性能（LinUCBに近い）が優先され、$\alpha$ を小さくするとオフラインの性能（LinLCBに近い）が優先される。

実験結果
合成線形バンディットタスク（次元 $d=20$, $|A|=100$）を用いた実証的評価により、以下が示された：

• ホライゾンの感度: 短いホライゾンの場合、LinOtO は保守的な LinLCB ベースラインを追跡する。長いホライゾンの場合、探索へと移行し、LinUCB に匹敵する劣線形な後悔を達成する。
• オフラインデータの質:
  • オフラインデータセットに最適な行動が含まれていない場合、LinOtO はオフラインの劣った事前分布から逸脱して探索を行うことに成功し、最終的に LinLCB（線形な後悔を被る）を上回り、オフラインデータサイズ $m$ が増加するにつれて LinUCB の性能に近づく。
  • オフラインデータセットに最適な行動が含まれている場合、LinOtO は迅速に収束し、LinUCB および LinLCB と同等の性能を示す。
• 堅牢性: アルゴリズムは、純粋な探索（LinUCB）と純粋な活用（LinLCB）の両極端の間で一貫して動作し、問題のパラメータに適応する。

意義と主張
本論文は、LinOtO が構造化された環境における「理解が不十分な」オフライン・ツー・オンラインのトレードオフを効果的に解決することを主張している。MAB 設定（例：Sentenac et al., 2025）とは異なり、このアプローチは線形構造を活用して、後悔が行動数ではなく次元 $d$ にスケールすることを保証し、高次元の問題に対するスケーラビリティを実現している。

著者らは、現在のフレームワークが固定デザインのオフラインデータを想定しており、オフラインとオンラインの間の分布シフトや適応的なロギング・ポリシーを考慮していないことを控えめに述べている。これらの制限に対処すること、およびこのフレームワークを非線形設定に拡張することを、重要な今後の研究方向として特定している。本研究は、オンライン学習における探索と活用のトレードオフを導くための事前知識（ヒント、オフラインデータ）を活用するという、より広い文献に貢献するものである。