When and why randomised exploration works (in linear bandits)

技術要約：ランダム化された探索がいつ、なぜ機能するのか（線形バンディットにおいて）

問題設定
本論文は、エージェントが $\mathbb{R}^d$ の単位ユークリッド球の閉部分集合 $\mathcal{X}$ からアクション $X_t$ を選択する逐次的意思決定設定である、線形バンディット問題を取り扱っている。エージェントは、平均 $\langle X_t, \theta^\star \rangle$ を持つ報酬 $Y_t$ を受け取る。ここで $\theta^\star$ は未知のパラメータベクトルである。目的は、$n$ ステップのレグレット（最適アクションの報酬と実際に取られたアクションとの累積差）を最小化することである。

最適化アルゴリズム（例：Upper Confidence Bound）は、線形バンディットに対して $O(d\sqrt{n} \log n)$ という頻度論的なレグレット境界を確立している一方で、Thompson sampling のようなランダム化された探索アルゴリズムは、この設定における解析が歴史的に困難であった。ランダム化手法に対する従来の頻度論的解析では、「強制的な楽観性（forced optimism）」や「事後分布の膨張（posterior inflation）」、すなわち、高確率で楽観性を確保するために事後分布の分散を人工的に膨らませる手法に依存することが多かった。これらの修正は通常、最適化アルゴングよりも劣る $O((d \log n)^{3/2}\sqrt{n})$ といったレグレット境界をもたらし、最適化アルゴリズムと比較して余分な $\sqrt{d}$ の因子を導入してしまう。さらに、近年の下界（Hamidi and Bayati, 2023; Zhang, 2022）は、修正されていないThompson sampling が特定の病理的な設定において線形レグレットを招く可能性があることを示しており、ランダム化された探索は構造的な仮定なしには普遍的に最適ではないことを示唆している。

手法と仮定
著者らは、ランダム化されたアルゴリズムを修正することなく（すなわち、強制的な楽観性や事後分布の膨張を行わずに）、新しい解析フレームワークを提案している。代わりに、この解析はアクション集合 $\mathcal{X}$ の特定の幾何学的特性に依拠している。

1. アルゴリズムの枠組み: 本論文では、各ステップ $t$ において、パラメータ $\theta_t$ が $\theta_t = \hat{\theta}_{t-1} + V_{t-1}^{-1/2}\eta_t$ としてサンプリングされるクラスのランダム化アルゴリズムを検討している。ここで $\hat{\theta}_{t-1}$ は正則化最小二乗推定値、$V_{t-1}$ はデザイン行列、$\eta_t$ は回転不変な摂動である。アクションは $X_t = \arg\max_{x \in \mathcal{X}} \langle x, \theta_t \rangle$ として選択される。
2. 摂動の仮定: 摂動 $\eta_t$ は、有界な二次のモーメントと四次のモーメントを持つ、独立で回転不変なランダム変数（例：ガウス分布または球面上の一様分布）であると仮定されている。
3. アクション集合の仮定（滑らかさと強凸性）: 理論的な核心となる貢献は、仮定4.2に基づいている。これは、アクション集合 $\mathcal{X}$ が、その支持関数の二乗 $J_{\mathcal{X}}^2$ が特定のノルム $\|\cdot\|_*$ に関して $m$-強凸かつ $M$-滑らかであるような、単位球の閉じた吸収的な部分集合であることを要求している。
   • 強凸性: 支持関数が「平坦な」領域を持たないことを保証し、パラメータ空間の小さな変化がアクション空間の有意義な変化へと変換されることを保証する。
   • 滑らかさ: 支持関数の勾配（パラメータからアクションへの写像）がリプシッツ連続であることを保証し、パラメータの摂動によるレグレットの大きな跳ね上がりを防ぐ。
   • 例: このクラスには、スケーリングされた $\ell_q$-球（$q \in (1, \infty)$）が含まれる。

主要な貢献と解析
本論文は、「不確実性に直面した楽観性（optimism in the face of uncertainty）」の枠組みに依存しない、新しい頻度論的レグレット解析を提供している。代わりに、探索プロセスのダイナミクスと信頼集合の進化を直接解析している。

• レグレットの分解: 著者らは、期待レグレットを、アルゴリズムが「楽観的」であるステップ（サンプリングされたパラメータが真の最適値よりも高い値を示すステップ）と、そうでないステップの2つの成分に分解している。
• 非楽観的な探索: 重要な洞察は、サンプルが楽観的でない場合であっても、それは依然として信頼集合を縮小させる価値のある情報を提供するということである。著者らは、ステップごとのレグレットをBregemannダイバージェンス形式 $r_t = D_{J_{\mathcal{X}}}(\theta^\star, \theta_t)$ として扱い、$J_{\mathcal{X}}^2$ の強凸性と滑らかさを利用してこのダイバージェンスを抑え込む。
• 情報の成長: 証明では、期待情報利得 $\mathbb{E}_{t-1}[X_t X_t^\top]$ をデザイン行列 $V_t$ の成長に関連付けることで、デザイン行列 $V_t$ の成長の下界を確立している。これにより、パラメータ空間の「サイズ」（$V_t^{-1/2}$ で測定）と、実際に行われた探索を結びつけている。
• 膨張の回避: 以前の研究とは異 달리、この解析はサンプリング分布の分散を膨らませることを必要としない。アルゴリズムの自然なランダム性が、アクション集合の幾何学的特性と組み合わさることで、探索を促進しレグレットを制御するのに十分であることを示している。

主な結果
上述の仮定の下で、著者らは、指定された摂動条件を満たすあらゆるランダム化アルゴリズムが、以下の頻度論的レグレット境界を達成することを証明している：
$$R_n \lesssim O(d\sqrt{n} \log n)$$
具体的には、定理4.1は $O(d\sqrt{n} \log n)$ のオーダーの境界を提供している（$n$ および $\delta$ に関する対数因子は無視）。これは、線形バンディットの既知の下界（Rusmevichientong and Tsitsiklis, 2010）と対数因子を除いて一致している。

意義と主張
本論文は、線形バンディットにおけるThompson sampling の次元依存性に関する重要な未解決問題を解決したと主張している。

• 最適な次元依存性: 構造化された線形バンディットの設定（特にアクション空間が滑らかで強凸である場合）において、修正されていない（非膨張の）Thompson sampling が最適な次元依存性（$O(d)$）を達成できることを初めて示した。
• 成功のメカニズム: 本研究は、なぜランダム化された探索がこれらの設定で機能するのかを明らかにしている。すなわち、アクション集合の幾何学的特性により、人工的な楽観性を必要とせずに、パラメータ空間における摂動が効果的にアクション空間を探索できることが保証されている。
• 限界と範囲: 著者らは、滑らかでない、あるいは吸収的でないアクション空間（例：「罠」となる腕を持つ空間）におけるThompson sampling の線形レグレットを示す既存の下界と、本結果が矛盾しないことを認めている。手法の成功は、アクション集合が滑らかさと強凸性の仮定を満たしていることに依存している。本論文は、これらの条件が達成のために必要であることを主張しているのではなく、アルゴリズムの修正なしに最適なレートを達成するための十分条件であることを示している。

要約すると、本論文は、多くの性質の良いアクション集合（$\ell_q$-球を含む）において、ランダム化された探索アルゴリズムが自然に最適なレグレットレートを達成することを確立し、これまで理論的保証のために必要と考えられていたアドホックな分散膨張技術の必要性を排除している。