Weighted Sequential Bayesian Inference for Non-Stationary Linear Contextual Bandits

技術要約：非定常線形コンテキスト・バンディットのための重み付き逐次ベイズ推論

問題の定式化

本論文は、非定常線形コンテキスト・バンディット問題を取り扱う。この設定において、学習者は$T$ラウンドにわたって環境と相互作用する。各ラウンド$t$において、学習者はコンテキスト依存のアクションの集合$X_t \subseteq \mathbb{R}^d$を観測し、アクション$x_t$を選択し、ノイズを含む報酬$r_t = \langle x_t, \theta^*_t \rangle + \epsilon_t$を受け取る。核心となる課題は、報酬パラメータ$\theta^*_t \in \mathbb{R}^d$が未知であり、かつ時間とともに変化することである。非定常性の度合いは、全変動予算$B_T = \sum_{t=1}^{T-1} \|\theta^*_t - \theta^*_{t+1}\|_2$によって定量化される。目的は、最適アクションの報酬と選択されたアクションの報酬との累積差である動的後悔（dynamic regret）を最小化することである。

既存の効率的な手法は、通常、**重み付き正規化最小二乗法（WRLS）**推定器に依存している。WRLSは再帰的な更新を通じて$O(d^2)$の計算複雑性を実現できるが、点推定しか提供しない。ランダム化された探索（例：トンプソン・サンプリングやランダム化UCB）を行うために、従来の手法は、頻度論的な共分散行列を用いて人工的なガウスノイズを注入することで、「代理」事後分布を構築しなければならなかった。このアプローチは、本質的なベイズ的根拠を欠いており、局所ノルムのような複雑な解析的構成物に依存することが多い。

手法：重み付き逐次ベイズ（WSB）推論

著者らは、WRLSの計算効率を維持しつつ、非定常線形バンディットのための原理的なベイズ的枠組みを確立するために、**重み付き逐次ベイズ（WSB）**推論を提案する。

1. 一般化された事後分布の構築:
   点推定の代わりに、WSBは時間変化するパラメータに対するガウス事後分布の列 $\rho_t(\theta) = \mathcal{N}(\theta | \mu_t, \Sigma_t)$ を保持する。この手法は、過去の観測値を減衰させるための一連の重み $\{w_{s,t}\}$（通常は指数減衰 $w_{s,t} = \gamma^{t-s}$）を用いる。事後平均 $\mu_t$ と逆共分散 $\Sigma_t^{-1}$ は以下のように再帰的に更新される：
   $$\Sigma_t^{-1} = \gamma \Sigma_{t-1}^{-1} + \sigma^{-2} x_t x_t^\top + (1-\gamma)\Sigma_0^{-1}$$
   $$\mu_t = \Sigma_t \left( \gamma \Sigma_{t-1}^{-1} \mu_{t-1} + \sigma^{-2} x_t r_t + (1-\gamma)\Sigma_0^{-1} \mu_0 \right)$$
   無情報事前分布の下では、WSBの平均 $\mu_t$ は代数的にWRLSの点推定値 $\hat{\theta}_t$ と一致するが、WSBは不確実性定量化に必要な完全な事後共分散 $\Sigma_t$ を本質的に提供する。

2. 集中解析と動的事前分布ペナルティ:
   著者らは、WSB事後分布の時一様信頼限界を導出している。推定誤差 $\|\mu_{t-1} - \theta^*_t\|$ は、以下の3つの成分に分解される：

   • ドリフト項 ($\alpha^{WSB}_t$): パラメータの変化によって誘発されるバイアスを捉える。
   • ノイズ項 ($\beta^{WSB}_t$): 報酬からの確率的ノイズを捉える。
   • 動的事前分布項 ($\Pi_t$): 初期事前分布の影響を表す新しい項。WRLSの解析では初期化ペナルティが固定された最悪ケースの定数（$\sqrt{\lambda}S$）によって抑えられるのに対し、WSBのペナルティ $\Pi_t$ は、時間とともに変化する事後共分散 $\Sigma_t$ を通じて評価される。$\Sigma_t$ が時間の経過とともに収縮するにつれ、$\Pi_t$ も減衰し、データ依存のよりタイトな境界をもたらす。

3. 簡略化されたマルチンゲール証明:
   集中境界を確立するために、本論文はベクトル値マルチンゲールの時一様集中に関する簡略化された証明を提供している。非負の超マルチンゲールに対する**ヴィルの不等式（Ville's inequality）**を活用することで、著者らはバンディットの文献で伝統的に使用されている複雑な停止時刻の構成を回避し、自己正規化境界のためのより明快な導出を実現している。

主な貢献

本論文は主に3つの貢献を行っている：

1. WSBフレームワーク: 非定常線形バンディットのためのパラメトリックなベイズ推論手法の導入。これはWRLSの$O(d^2)$の効率性と一致しつつ、ランダム化された探索のための本質的な事後分布を提供する。
2. 洗練された後悔保証: 3つのWSBベースのアルゴリズム（WSB-LinUCB、WSB-RandLinUCB、WSB-LinTS）に対する頻度論的な後悔境界の確立。以前のランダム化戦略（D-RandLinUCB、D-LinTSなど）で見られた $d^{7/8}$ の次元依存性を改善し、洗練されたドリフト解析（以前はUCBにのみ適用されていた）をランダム化戦略へと拡張することで、$\tilde{O}(d^{3/4} B_T^{1/4} T^{3/4})$ の後悔境界を達成した。
3. 動的事前分布ペナルティ: 事後共分散が縮小するにつれて減少する動的項 $\Pi_t$ によって、事前分布の影響を分離できることを示した。これにより、固定された初期化ペナルティを使用する手法と比較して、過度な保守性を軽減できる。

実験結果

著者らは、急激な変化と緩やかなドリフトの両方を含む合成的な非定常シナリオにおいて、提案されたアルゴリズムを評価した。

• 決定論的 vs ランダム化: ランダム化された探索戦略（WSB-RandLinUCB および WSB-LinTS）は、すべての次元とシナリオにおいて、決定論的なUCBベースの手法を一貫して上回った。
• ベースラインとの比較:
  • WSB-RandLinUCB は、テストされたすべての次元（$d=2$ から $32$）において、頻度論的な対応物である D-RandLinUCB よりも低い累積後悔を達成した。
  • WSB-LinTS は、D-LinTS を大幅に上回った。
  • 決定論的な設定では、WSB-LinUCB は LB-WeightUCB（最先端のWRLS UCB）と同等の性能を示したが、高次元においてより複雑な局所ノルムを使用する D-LinUCB を一貫して上回ることはなかった。
• アブレーション研究: 事前分布の誤設定に関する実験では、アルゴリズムは中程度の事前分布誤差に対して頑健である一方、深刻な誤設定（事前分布の平均が真のパラメータスケールから遠い場合）は性能を低下させることが示され、パラメータ境界と互換性のある事前分布のスケールを選択することの重要性が浮き彫りになった。

意義と主張

本論文は、WSBが非定常バンディットにおける不確実性定量化のためのより原理的な基礎を提供すると主張している。人工的な代理分布や局所ノルムを回避することで、WSBベースのアルゴリズムは以下を実現する：

• 理論的最適性: 滑らかな重み付き戦略に対して、最先端の $\tilde{O}(d^{3/4} B_T^{1/4} T^{3/4})$ に一致する後悔境界を達成し、以前のランダム化手法よりも次元依存性を改善した。
• 実用的効率性: $O(d^2)$ の計算複雑性を維持し、非パラメトリックなガウス過程アプローチの $O(t^3)$ のコストを回避する。
• 保守性の低減: 動的な事前分布ペナルティにより、データが集まるにつれて探索がより保守的でなくなるため、ランダム化設定において経験的に優れた性能が得られる。

著者らは、自分たちの境界が競争力はあるものの、依然として理論的な下限 $\Omega(d^{2/3} B_T^{1/3} T^{2/3})$ をわずかに上回っていることを指摘しており、このギャップは、周期的なリセットなしに滑らかで連続的な適応のみを用いてミニマックス最適性を達成することの難しさに起因するとしている。しかし、WSBフレームワークは、理論的な厳密さと連続的な適応能力のバランスが取れた、非常に実用的な代替案として提示されている。