Stochastic Linear Bandits with Parameter Noise

技術的サマリー：パラメータノイズを伴う確率的線形バンディット

問題定義
本研究は、パラメータノイズを伴う確率的線形バンディットモデルを調査する。この設定において、学習者は時間 horizon $T$ にわたり環境と相互作用し、行動集合 $\mathcal{A} \subseteq \mathbb{R}^d$ から行動 $a_t$ を選択する。固定された $\theta^\star$ とノイズ $\eta_t$ を用いて報酬が $X_t = a_t^\top \theta^\star + \eta_t$ となる標準的な加法ノイズモデルとは異なり、パラメータノイズモデルでは、報酬が $X_t = a_t^\top \theta_t$ で与えられると仮定する。ここで、$\theta_t$ は平均 $\theta^\star$ と共分散行列 $\Sigma$ を持つ固定かつ未知の分布 $\nu$ から i.i.d. にサンプリングされる。

本論文は、重要な相違点を強調している。パラメータノイズモデルでは、学習者が報酬の分散に影響を与えることができる。具体的には、$\text{Var}(X_t) = a_t^\top \Sigma a_t$ であるのに対し、加法ノイズモデルでは分散は環境によってのみ決定される。著者らは、パラメータノイズモデルが（$\theta_t$ が敵によって選択される）敵対的線形バンディットモデルの緩和である一方で、特定の幾何学的設定において加法ノイズモデルよりもtighter な後悔 bound を可能にする独自の構造的性質を有していると指摘している。

手法とアルゴリズム
著者らは、異なる行動集合の幾何学に特化した 2 つのアルゴリズムを提案する。

1. VASE（分散感知最適設計逐次除去）:

   • 対象: 一般的な有限行動集合（およびカバリング議論による無限集合）。
   • メカニズム: 分散情報を活用する逐次除去アルゴリズム。各フェーズにおいて、行動を選択するための G-最適設計 $\pi_\ell$ を計算する。設計のサポート内の行動の分散を、停止則アルゴリズム（SR）を用いて明示的に推定する。
   • 主要な革新: 本アルゴリズムは、推定された分散を 2 つの用途で使用する。すなわち、探索に必要なサンプル数を削減するためと、重み付き最小二乗推定量における重みとしてである。この重み付けにより、サンプル数が少なくても推定量の共分散が制御されたまま保たれるため、分散依存の後悔 bound が導かれる。

2. VALEE（分散感知線形探索・活用）:

   • 対象: $p \in (1, 2]$ である $\ell_p$ 単位球（およびその双対ノルム $q \ge 2$）。
   • メカニズム: 単純な探索・活用アルゴリズム。
     • 探索: 標準基底ベクトル $e_i$ を実行する。Median-of-Means（MoM）法を用いて、座標ごとに平均ベクトル $\theta^\star$ を推定する。共分散行列 $\Sigma$ が未知の場合、まず基底ベクトルの分散を推定する。
     • 活用: 推定誤差が分散および時間 horizon に対して十分に小さくなった時点で、推定された平均 $\hat{\theta}$ から導出された行動 $\hat{a}$ にコミットする。具体的には、$\hat{a}_i = \text{sign}(\hat{\theta}_i)|\hat{\theta}_i|^{q-1} / \|\hat{\theta}\|_q^{q-1}$ である。
   • 主要な革新: 解析は、$\ell_p$ 球の幾何学とパラメータノイズの構造を利用する。著者らは、基底ベクトルを探索することで、加法ノイズモデルにおける標準的な $\epsilon$ bound よりも tight である $\sqrt{\sigma^2(e_i)}$ に比例する推定誤差が得られることを示す。これにより、報酬分布の分散構造に依存する最適な後悔 bound を達成できる。

主要な結果
本論文は上限と下限の両方を確立し、提案されたアルゴリズムが特定の設定において（対数因子を除いて）ミニマックス最適であることを示している。

• 一般的な有限行動集合（$K$ 個の行動）:

  • 上限: VASE は $\tilde{O}(d^2 + \sqrt{dT \log(K/\delta) M_\sigma})$ の後悔を達成する。ここで $M_\sigma$ は $\max_a \sigma^2(a)$ によって有界となる分散依存量である。
  • 下限: $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$ の下限が証明されており、$\log(K) \approx d$ の場合、上限が対数因子を除いて tight であることを示している。

• $\ell_p$ 単位球（$p \le 2$）:

  • 既知の共分散: VALEE は $\tilde{O}(d + \sqrt{dT \sigma^2_q})$ の後悔を達成する。ここで $\sigma^2_q = (\sum \Sigma_{ii}^{q/2})^{2/q}$ である。これは $\tilde{\Omega}(\sqrt{dT \sigma^2_q})$ という一致する下限によって最適であることが示されている。
  • 未知の共分散: VALEE は追加の加法項を負い、$\tilde{O}(\sqrt{dT \sigma^2_q} + d^{2/3 + 2/3q} T^{1/3})$ の後悔となる。著者らは、この加法項は分散推定フェーズに起因すると指摘している。

• $\ell_p$ 単位球（$p > 2$）:

  • 本論文は $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$ の下限を提供し、これらの幾何学における既知の敵対的設定の下限と一致する。

意義と主張
本論文は、$\ell_2$ 単位球のような特定の行動集合において、加法ノイズモデルが敵対的モデル（$\sqrt{dT}$）よりも悪い後悔 bound（$d\sqrt{T}$）をもたらすという「奇妙なケース」を解決すると主張している。著者らは、パラメータノイズモデルが、確率的モデルは敵対的モデルよりも容易であるという直観とより一致していることを実証している。

• tighter な bound: $p \le 2$ である $\ell_p$ 球の場合、パラメータノイズモデルは $\sqrt{dT \sigma^2_q}$ のオーダーの後悔 bound を可能にする。これは分散が小さい場合、加法ノイズモデルで典型的な $d\sqrt{T}$ の bound よりも著しく小さくなり得る。
• 構造的利点: 結果は、実現の線形性（期待値だけでなく）と、学習者が分散に影響を与える能力が、これらの改善された bound を達成するために重要であることを浮き彫りにしている。
• 単純性: 驚くべきことに、$\ell_p$ 球（$p \le 2$）の最適後悔は、加法ノイズ設定でしばしば必要とされる複雑な最適設計アルゴリズムとは対照的に、非常に単純な探索・活用アルゴリズム（VALEE）を用いて達成可能である。

著者らは、共分散が既知の場合、$p \le 2$ に対する結果が（対数因子を除いて）最適であると結論づけるが、共分散が未知の場合には $T^{1/3}$ 項という未解決のギャップが残っており、今後の研究で解決される可能性があるとしている。また、$p > 2$ に対する下限に一致するアルゴリズムの設計も未解決問題として残されている。