技術要約：非定常コンテキスト・バンディットのためのフロー補正型トンプソン・サンプリング

問題設定

本論文は、コンテキスト、アクション、および報酬の関係性が時間の経過とともに進化する設定である、非定常線形コンテキスト・バンディットの課題に取り組んでいる。古典的なコンテキスト・バンディットでは、パラメータベクトル $w_t$ は定常であると仮定されている。しかし、現実世界のアプリケーション（レコメンデーションシステム、ダイナミック・プライシング、金融など）では、ユーザーの嗜好や市場条件がドリフト（変動）するため、過去のデータをそのまま使用すると系統的なバイアスが生じる。

核心となる困難は、過去のデータを保持して事後分散を減少させることと、古いデータを破棄して時代遅れのモデルによるバイアスを回避することの間のトレードオフにある。スライディングウィンドウ、指数減衰、定期的なリスタートといった既存のアプローチは、過去のデータを、一様に破棄または重み付けを減らすべき「負債」として主に扱っている。著者らは、非定常性が予測可能な構造（例：緩やかなドリフト、周期性、または回帰するレジーム）を持つ場合、過去の観測値には、介入した環境の変化に合わせて補正を行うことで活用できる価値ある情報が含まれていると主張している。

手法：フロー補正型トンプソン・サンプリング (FC-TS)

著者らは、過去の観測値を事後分布に組み込む前に「現在時刻の疑似観測値」へと変換するベイズ・フレームワークであるフロー補正型トンプソン・サンプリング (FC-TS) を提案している。この手法は、非定常性の処理を、トランスポート演算子（輸送演算子）と信頼性重み付けルールという2つの明確なコンポーネントに分離している。

1. コアメカニズム

各ラウンド $t$ において、すべての過去の観測値 $(x_s, a_s, r_s)$ に対して、FC-TSは輸送された報酬 $\hat{r}_{s \to t}$ を構築する：
$$\hat{r}_{s \to t} = r_s + \hat{\Delta}_{s \to t}(x_s, a_s)$$
ここで、$\hat{\Delta}_{s \to t}$ は時刻 $s$ から $t$ までの平均報酬のシフトを推定する。これにより、過去の報酬を現在の報酬モデルに適合するように「前方へ流す（フローさせる）」ことが可能になる。

ドリフト推定の不正確さによるノイズを防ぐため、各輸送された観測値には $[0, 1]$ の範囲の信頼性重み $\omega_{s,t}$ が割り当てられる。この重みは、補正が不確実な場合に、その観測値が事後分布に与える影響を制御し、実効的なノイズ分散を増大させる。

アクション $a$ の事後分布は、これらの重み付けされ輸送された観測値を用いて更新される：
$$\Lambda_t^{(a)} = \lambda I + \sigma^{-2} \sum_{s<t, a_s=a} \omega_{s,t} x_s x_s^\top$$
$$\eta_t^{(a)} = \lambda m_t^{(a)} + \sigma^{-2} \sum_{s<t, a_s=a} \omega_{s,t} \hat{r}_{s \to t} x_s$$
$$\mu_t^{(a)} = (\Lambda_t^{(a)})^{-1} \eta_t^{(a)}$$
アクション選択は、ガウス事後分布 $\mathcal{N}(\mu_t^{(a)}, (\Lambda_t^{(a)})^{-1})$ を用いた標準的なトンプソン・サンプリングに従って行われる。

2. 構造化されたインスタンス化

本フレームワークは、3つの一般的な非定常パターンに対して具体的なインスタンスを提供する統一されたテンプレートを提供している。

• 線形ドリフト (Linear Drift): パラメータが $w_t^{(a)} \approx \theta^{(a)} + t \delta^{(a)}$ として進化すると仮定する。トランスポート演算子は、オンライン・リッジ回帰の推定値 $\hat{\delta}_t^{(a)}$ を用いて報酬をシフトさせる：$\hat{r}_{s \to t} = r_s + (t-s)\langle \hat{\delta}_t^{(a)}, x_s \rangle$。外挿の不確実性を考慮するため、重みは指数関数的に減衰する（$\omega_{s,t} = \gamma^{t-s}$）。
• 周期的な変動 (Periodic Variation): パラメータが周期 $P$ で繰り返されると仮定する。トランスポート演算子は、同じフェーズ内にある観測値に対しては恒等写像（$\hat{r}_{s \to t} = r_s$）となる。重みはフェーズ間の円周距離によって決定され、アルゴリズムが以前のサイクルからのデータを再利用することを可能にする（$\omega_{s,t}$ はフェーズの近接性に依存する）。
• 回帰するレジーム (Recurring Regimes): 有限個のレジーム間を切り替わる環境を扱う。アルゴリズムはレジーム固有の事後分布のバンクを保持する。チェンジポイント（予測残差に対するCUSUMにより検出）を検知した際、ゼロから再開するのではなく、再出現したレジームの事後分布をロードする。

本フレームワークは**合成（コンポジション）**もサポートしており、それぞれのトランスポートおよび重み付けルールを組み合わせることで、線形ドリフトと周期性を同時に扱うことができる。

主な貢献

1. フロー補正型事後分布更新: 過去の報酬を現在時刻の疑似観測値へと補正し、一様に破棄するのではなく、信頼性で重み付けされたベイズ更新を通じて組み込むという、トランスポートに基づく非定常性の視点を導入した。
2. モジュール式アルゴリズム設計: FC-TSは、汎用的なトランスポート演算子と重み付けルールによって定義されており、線形ドリフト、周期変動、回帰レジーム向けにインスタンス化されている。これには、トレンドと複数の周期性を組み合わせた適応型バリアントも含まれる。
3. 実証的検証: 5つのケーススタディ（線形ドリフト、周期変動、回帰レジーム、複合非定常性、および半合成ポートフォリオ選択）における広範な評価により、FC-TSが忘却ベースの最先端のベースラインを上回ることを示した。

実験結果

著者らは、FC-TSを4つのベースライン（Standard TS (STD-TS)、Sliding Window TS (SW-TS)、Discounted TS (D-TS)、Restarting TS (R-TS)）と比較評価した。

• 性能向上: FC-TSは5つの設定すべてにおいて最も低い累積リグレットを達成し、各環境における最強のベースラインに対して 14.1% から 59.0% の改善を示した。

• ケース別の洞察:

  • 線形ドリフト: FC-TSはウォームアップ期間中、SW-TSと同等の性能を示したが、ドリフト推定が安定するにつれて徐々に差を広げ、10個のシードのうち8個で勝利した。
  • 周期的な変動: FC-TSは「フェーズ・メモリー」により、以前のサイクルからデータを蓄積できるため、合成的な利得が最大（50.0%）となった。リグレットはサイクルごとに約70から約4へと低下したが、ベースラインは横ばいであった。
  • 回帰するレジーム: FC-TSは、スイッチの検出時にレジーム固有の事後分布をロードすることで、リスタートに伴う「コールドスタート」のペナルティを回避し、59.0%の改善を達成した。
  • 複合非定常性: ドリフトと急激な変化が混在する環境において、FC-TSはドリフト補正（滑らかな進化のため）とレジームのリセット（急激な変化のため）を組み合わせることに成功し、29.5%の改善をもたらした。
  • 半合成ポートフォリオ: 月次/四半期サイクルと成長株からバリュー株へのドリフトが重なる金融タスクにおいて、適応型FC-TSバリアントは、最良のベースライン（D-TS）に対して28.1%のリグレット改善を実現した。アブレーション研究により、この利得の主因はドリフト補正であることが確認された。

• アブレーション研究の結果:

  • 有効サンプルサイズ: トランスポート補正なしでより多くのデータを保持した場合（「No-transport」アブレーション）、データを破棄する手法よりもリグレットが高くなった。これは、古いデータが系統的なバイアスを導入することを確認している。
  • トランスポートの価値: トランスポート演算子自体が、様々なドリフトスケールにおいて、No-transport バリアントと比較して47〜57%のリグレット削減に寄与しており、事後分布の再構築ではなく、補正メカニズムこそが性能を駆動していることが証明された。

意義と主張

本論文は、構造化された非定常性は、データを一様に破棄することよりも、経験を補正して再利用することによってより適切に対処できると主張している。

著者らは、環境のドリフトが予測可能（緩やか、周期的、または回帰的）である場合、過去のデータは負債ではなく資産であることを強調している。環境の報酬分布の「フロー」を明示的にモデル化することで、FC-TSは忘却ベースの手法よりもはるかに大きな有効サンプルサイズを維持できる。結果は、非定常バンディットにおけるサンプル効率の鍵は、単一の画一的な忘却ルールを適用することではなく、環境の特定の時間構造に基づいて過去の観測値を重み付けし、補正することにあることを示唆している。

論文は、今後の課題として、較正された不確実性を伴うドリフト構造のオンライン学習、一般化線形モデルやニューラルバンディットへのフレームワークの拡張、および未モデル化の分布シフトを伴う高リスクな設定における安全策の開発を挙げ、控えめに締めくくっている。