Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

技術要約：劣ガウス報酬を持つリスク回避型バンディットにおける、トンプソン・サンプリングの漸近的最適性

問題設定
本論文は、リスク回避的な目的関数下でのマルチアームバンディット（MAB）問題を扱う。期待報酬を最大化する標準的なMAB設定とは異なり、リスク回避的な設定では、一般的なリスク汎関数 $\rho$（例：条件付き期待値（CVaR）、平均分散、シャープレシオ、または歪度リスク尺度）を最適化することを目的とする。本研究が取り組む具体的な課題は、$\rho$-NPTS（Chang and Tan [2022] によって提案された非パラメトリック・トンプソン・サンプリング・アルゴリズム）の理論的解析である。Chang and Tanは、パラメトリックな相伴アルゴリズムである $\rho$-MTS についてはインスタンス最適性を証明したが、非パラメトリックな $\rho$-NPTS の最適性は未解決問題として残していた。

根本的な障害は、$\rho$-NPTS が観測数 ($N_k$) と共に有効なアルファベットサイズが増大するディリクレ後験分布を構築することにある。既存のテール境界の結果を直接適用すると、$(N_k)^{N_k/2}$ という超指数関数的な前係数が発生するため、対数リグレットの証明が阻まれる。さらに、先行研究の多くは、「支配（dominance）」条件（パラメトリック手法に必要）や、UCB型のアルゴリズムに求められるリプシッツ連続性（リプシッツ連続なリスク汎関数を要求する）といった強い条件を必要としており、シャープレシオのような非リプシッツな汎関数を除外していた。

手法
著者らは、有界な密度と劣ガウスの裾（tails）を持つ分布 ($P(B, \sigma)$) を対象とした、アンカーフリーな非パラメトリック・トンプソン・サンプリング・アルゴリズムのバリアントである $\rho$-NPTSSG を導入する。核心となる技術的革新は、増大するアルファベットのディリクレ後験分布を固定されたグリッド上に投影する離散化レマ（discretisation lemma）（および劣ガウスの裾に対する切断型のレマ）である。

1. 離散化と集約:
   本論文では、サイズ $M$ の固定グリッド $G_M$ を定義する。任意の観測報酬シーケンスに対し、同一のグリッドビン内に落ちるディリクレ重みを集約することで、経験測度をこのグリッド上に投影する。

   • 重要な洞察: ディリクレ分布の集約特性により、投影されたビン上の重みは、サンプルサイズ $N_k$ に依存せず、固定された次元 ($M^+ \le M$) を持つディリクレ分布に従う。
   • 帰結: この投影により、テール境界における多項式的前係数が次数 $(M-1)/2$ に抑えられ、$N_k$ から独立したものとなる。これにより、先行研究の証明を阻んでいた超指数関数の障壁を打破できる。

2. アルゴリズムのバリアント:

   • $\rho$-NPTS (有界サポート): $[0, 1]$ 内にサポートを持ち、有界な密度を持つ分布を対象とする。固定アンカー（右端点）と一様グリッドを使用する。
   • $\rho$-NPTSSG (劣ガウス): 有界な密度と劣ガウスの裾を持つ $\mathbb{R}$ 上の分布を対象とする。固定アンカーを排除し（ラウンドロビン初期化を使用）、**切断型離散化（truncated discretisation）**レマを採用する。このレマは、サンプルサイズの増加に伴って幅が縮小する、経験平均を中心としたグリッドを使用し、オーバーフロー確率を制御するために裾を切断する。

3. リグレット解析:
   証明は、アルゴリズムが「高い」トンプソン・スコアを持つ劣最適アームを引く場合と、「低い」スコアを持つ場合へのリグレットの標準的な分解に従う。

   • 上界: 離散化レマを用いて、固定グリッド投影に対して Chang and Tan [2022] のテール境界を適用する。$\rho$ の連続性（具体的には $D_\infty$-連続性）により、投影された測度のリスクが真のリスクを近似することが保証される。
   • 下界: Chang and Tan [2022] によって確立された、カルバック・ライブラー（KL）ダイバージェンス最小化問題 $K^\rho_{\inf}$ に基づくインスタンス依存の下界と一致させる。

主な貢献

1. 未解決問題の解決: 本論文は、有界な密度と劣ガウスの裾を持つ分布のクラスに対する任意の連続なリスク汎関数 $\rho$ に対して、$\rho$-NPTSSG が $\sum_{k: \Delta^\rho_k > 0} \frac{\Delta^\rho_k \log n}{K^\rho_{\inf}(\nu_k, r^\rho_1)} + o(\log n)$ のインスタンス最適リグレットを達成することを証明した。
2. より弱い条件: 本結果は、リスク汎関数 $\rho$ の連続性（具体的にはレヴィ・プロホロフ距離に関する連続性）のみを要求する。これは以下よりも厳密に弱い条件である：
   • パラメトリックな $\rho$-MTS に必要な「支配」条件。
   • UCB型アルゴリズムに求められるリプシッツ条件。
     これにより、パラメトリックな報酬分布を仮定することなく、シャープレシオのような非リプシッツな汎関数に対して、初のインスタンス最適性の保証を提供できる。
3. 離散化レマ: 本論文は、増大するサポートを持つディリクレ過程を含むあらゆる問題において、潜在的に独立した関心事となり得る、固定解像度における増大アルファベットのディリクレ後験分布を制御する技術的レマを導入している。
4. 劣ガウスへの拡張: 著者らは、切断型離散化アプローチを通じて、有界サポートの結果をより広範な劣ガウス分布のクラス（ガウス分布のアームを含む）へと拡張し、事前指定されたサポート区間の必要性を排除した。

結果

• 定理 1 (有界サポート): 連続性のみを前提として、$P(B)$ における $\rho$-NPTS の漸近的最適性を確立する。
• 定理 2 (劣ガウス): $P(B, \sigma)$ における $\rho$-NPTSSG の漸近的最適性を確立する。
• 実験的検証: 本論文は、理論を検証する4つの実験を提示している：
  1. $\rho$-NPTS は、Beta分布のアームにおける CVaR のインスタンス最適下界を追跡し、Risk-LCB ベースライン（$\log^2 n$ の保証を持つ）を上回る性能を示す。
  2. $\rho$-NPTS は、切断正規分布のアームにおけるシャープレシオに対して $O(\log n)$ のリグレットを達成する。これは、非リプシッツ性ゆえに従来アルゴリズムでは保証が得られなかったケースである。
  3. $\rho$-NPTS は、修正なしで複合汎関数（例：$0.5 \text{CVaR} + 0.5 \text{Sharpe}$）を扱うことができる。
  4. $\rho$-NPTSSG は、ガウス分布のアームにおけるインスタンス最適下界に収束し、ガウス報酬を仮定しない専門的な Normal-Gamma Thompson Sampling アルゴリズム（Shah et al. [2025]）と同等の性能を示す。

意義と主張
本論文は、リスク回避型バンディットにおける非パラメトリック・トンプソン・サンプリングの理論的地位を確定させると主張している。これらのアルゴリズムは単なる経験的なヒューリスティックではなく、証明可能な漸近的最適性を持つことを示している。

その意義は、仮定の緩和にある：

• 実践者は、報酬グリッドを事前指定したり、アルファベットサイズをチューニングしたりすることなく、生の観測値をそのまま使用できる。
• 本手法は、従来の最適手法よりも、より広範なリスク汎関数（シャープレシオを含む）および分布クラス（劣ガウス）に適用可能である。
• 本結果は、共役事前分布やパラメトリックな仮定を必要とせずに、シャープレシオに対してより鋭いインスタンス最適定数を提供することで、Shah et al. [2022] の同時期の研究を包含するものである。

著者らは、有界密度仮定が証明で使用されるビン確率の境界に必要であり、点質量（例：ベルヌーイ分布）を持つ分布には当てはまらないことを注記している（それらに対しては、パラメトリックな $\rho$-MTS が補完的な解となる）。今後の研究方向として、コンテキスト付きバンディット、ヘビーテイル（重い裾）の報酬、および離散分布が挙げられている。