Abstract
クルバック・ライブラー（KL）正則化は、オフラインの意思決定に広く用いられており、いくつかの利点があります。そのため、KLで正則化されたパフォーマンス指標に関する、オフライン学習のサンプル計算量（sample complexity）に関する最近の研究が動機づけられています。それにもかかわらず、KLで正則化されたオフライン学習における正確なサンプル計算量は、十分に完全に特徴づけられているわけではありません。本論文では、この問題を多腕バンディット（MABs）の設定で調べます。大きな正則化 eta = O(epsilon^{-1}) のもとで、KL-PCB（Zhao et al., 2026）がサンプル計算量 O(eta SAC^{pi^*}/epsilon) を達成し、小さな正則化 eta = Omega(epsilon^{-1}) のもとでサンプル計算量 Omega(SAC^{pi^*}/epsilon^2) を持つことを示す、鋭い分析を与えます。ここで eta は正則化パラメータ、S はコンテキスト数、A は腕の数、pi^* が最適方策であるときの政策被覆係数 C^{pi^*}、epsilon は望ましいサブ最適性（desired sub-optimality）であり、O と Omega はすべての多項対数因子（poly-logarithmic factors）を隠します。さらに、正則化強度の全範囲にわたって上界と一致する、一対のより鋭いサンプル計算量の下界も提示します。全体として、我々の結果は、KL正則化を用いるオフライン多腕バンディットをほぼ完全に特徴づけるものです。
