今日読んだ部分では研究を紹介しています．
２章 Stochastic Bandits: Fundamental Results
2.4 Refinements and Bibliographic Remarks
ここで，いくつかの細かな改善点を議論する． 以下では有界な報酬を考える（2.4.7を除いて）
2.4.1 Improved Constants
UCBの証明のリグレットバウンドは２つの方法で改善できる． １つは異なる時間ステップでのユニオンバウンドを“peeling” argumentに置き換えることだ． これにより，$\alpha>1$に対して，ログオーダーのリグレットを達成できる． ２つ目の改善はGarivier and Capp´eによって提案された式(2.5)–(2.7)を使うより曖昧な条件を使う方法だ． これにより，$\alpha$-UCBのリグレットのオーダが$\alpha>1$に対して，$\frac{\alpha}{2}\ln n$となる． $\alpha$が位置に近い値より改善できないのは下界からわかる．
2.4.2 Second-Order Bounds
$\alpha$-UCBは最適なリグレットオーダであるが，式 (2.4)と定理2.2はギャップがある． これに対して，いくつかの改善法が提案されている．
Audibertらによって提案されたUCB-Vはヘフディングの不等式の代わりにBernsteinの不等式を用いた． 他のやり方ではL2ノルムで距離を図るのではなく，KLダイバージェンスで測る方法だ． Honda and Takemuraは漸近的な結果を示し，Garivier and Capp´eやMaillardらはKL-UCBという手法を示した． このリグレットは$\alpha>1$にたいして，$$$\sum_{i:\Delta_i>0}\frac{\Delta_i}{kl(\mu_i,\mu^*)}\alpha\ln n+\mathcal{O}(1)$$である． KL-UCBはベルヌーイ分布に対して最適であり，どんな報酬分布に対しても$\alpha$-UCBより優れている．
メモ
機械学習プロフェッショナルシリーズのバンディット問題の本によると， KL-UCBは理論限界を達成できるもののKLダイバージェンスを含む式を$\mu^*$に関して解く必要があるけれど，閉形式で解けないためニュートン法を用いるなどの工夫が必要． しかし，バンディット問題はパフォーマンスが要求される環境で利用される場合があるため，そのような場合でも利用できる計算コストが低いかつ理論げんかいを達成できる戦略が必要． そこで，DMED(Deterministic Minimum Empirical Divergence)ポリシーという戦略が提案されている．
2.4.3 Distribution-Free Bounds
$\Delta_i$が0に近い値をとるとき、式(2.4)は非常に大きな値になりうる。 しかし、アーム$i$から引いたリグレットは$n\Delta_i$より大きくならない。 こうした点から、$\alpha$-UCBのリグレットは$\sqrt{\alpha nK\ln n}$より小さいリグレットになる（数値の定数を除いて）。 しかし、次の節で示すようにリグレットのminimaxな下界は$\sqrt{Kn}$である。 Audibert and Bubeckはこの余分なログオーダを取り除く修正版の$\alpha$-UCBを提案した。 $\Delta=\min_{i=i^*}\Delta_i$としたとき、MOSS (Minimax Optimal Strategy in the Stochastic case)は $$\min\left\{\sqrt{nK}, \frac{K}{\Delta}\ln\frac{n\Delta^2}{K}\right\}$$ より小さなリグレットを達成する（数値の定数を除いて）。
minimax最適とは？
問題設定
条件付き確率分布$P(x|\theta)$からのノイズの乗ったデータ(?)または破損したデータ(?)$x\in\mathcal{X}$から決定的な（ベイズではない）パラメータ$\theta\in\Theta$を推定する問題を考える。ゴールは与えられたリスク関数$R(\theta, \delta)$を最小化するパラメータ$\theta$を推定する良い推定器$\delta(x)$を見つけることだ。 ここで、リスク関数とは確率$P(x|\theta)$についての損失関数$L(\theta,\delta)$の期待値である。
定義
リスク関数$R(\theta,\delta)$に対して推定器$\delta^M:\mathcal{X}\mapsto\Theta$がminimaxであるとはその推定器が全ての推定器の中で最小のリスクをとるとるということである。つまり、$$\sup_{\theta\in\Theta}R(\theta,\delta^M)=\inf_{\delta}\sup_{\theta\in\Theta}R(\theta,\delta)$$ を満たすということである。
この結果の弱いところは最も小さなギャップ$\Delta$にのみ依存していることである． Auer and Ortnerはimproved UCBという$$\sum_{i:\Delta_i>0}\frac{1}{\Delta_i}\ln(n\Delta_i^2)$$を達成する戦略を作った． これはいくつかの設定でMOSSより優れているが$\sqrt{nK}$のminimax最適なレートを達成していない． すべての場合でMOSSとimproved UCBより優れてたリグレットを達成できる手法があるかはopen problemだ． 実現可能な予想としては $$\sum_{i:\Delta_i>0}\frac{1}{\Delta_i}\ln\frac{n}{H}~with~\sum_{i:\Delta_i>0}\frac{1}{\Delta_i^2}$$が達成できるとなっている．
2.4.4 High Probability Bounds
擬リグレット$\overline{R}_n$は重要だが，$\hat{R}_n=n\mu^*-\sum_{t=1}^n\mu_{I_t}$を高確率で保証したい場合もある． $\hat{R}_n$のばらつきが$\sqrt{n}$のオーダであり，$\overline{R}_n$のオーダは$\ln n$であるため，$\sqrt{n}$が優位になると考えられるので$\hat{R}_n$を$\overline{R}_n$に近づけるのは難しいことだと考えれる． AudibertらはUCBの$\hat{R}_n$のconcentrationの性質を解析した．それによると$\hat{R}_n$はその期待値の周りに集中しているが，nについて多項式オーダで$\hat{R}_n$はオーダ$n$になる． Salomon and Audibertは常時停止可能なアルゴリズムは基本的に指数部に色々乗っている古典的なconcentration inequalityではこの多項式のconcentrationを改善できないことを証明した． このことはHigh Probability Boundsに関しては常時停止可能なアルゴリズムは停止時間を用いるアルゴリズムより弱いことを示している．
2.4.5 $\epsilon$-Greedy
$\epsilon$-Greedyはシンプルな戦略である． パラメータ$0<\epsilon<1$を選び，$1-\epsilon$の確率で貪欲に経験的に最も高い報酬を得られるアームを引き，$\epsilon$の確率でランダムにアームを引く． Auerらは$\epsilon$をtに依存する関数$\epsilon_t=K/(d^2t)$としたとき，$0< d<\min_{i\not=i^*}\Delta_i$が与えられているもとで，擬リグレットは$(K\ln n)/d^2$のようになることを証明した． このアルゴリズムは実用上はうまく行くが，$\min_{i\not=i^*}\Delta_i$のタイトな下界を$d$として選ばないと，性能は劣化する．
2.4.6 Thompson Sampling
マルチアームバンディット問題に関する極めて初期の研究でThompsonは，ベルヌーイ分布の場合の戦略を提案した． トンプソンサンプリングと呼ばれる戦略は次のようなものだ．
パラメータ$\mu_{i}\in[0,1]$の一様な事前分布を考える．$t$ラウンドでの$\mu_i$に対する事後分布を$\pi_{i,t}$とする．また，$\theta_{i,t}\sim\pi_{i,t}$とする． 戦略は$I_t\in\rm arg\max_{i=1,d\dots,K}\theta_{i,t}$というものだ．
Agrawal and Goyalはトンプソンサンプリングがログオーダのレートを達成することを示した． Kaufmannらは式(2.4)とちょうど同じ擬リグレットを達成できることを示した．
2.4.7 Heavy-Tailed Distributions
2.2節ではモーメント母関数を通してUCB戦略を得た．また，定理2.1で示されるバウンドは分布のテールが重くなると悪化することがわかる． 特に，モーメント母関数が有限でない場合は結果が得られなくなる．
しかし，Bubeckらは分布の分散が有限であるならば式(2.4)と同じ擬リグレットを得られる戦略が存在することを示した． より正確に言うと基本的な経験平均より洗練されたよりロバストな平均のエスティメータを使うことで，1でバウンドされた$1+\epsilon$のモーメントを持つ分布に対するUCB戦略を構築することができる． その時のリグレットは $$R_{n}\le\sum_{i:\Delta_i>0}\left(8\left(\frac{4}{\Delta_i}\right)^{\frac{1}{\epsilon}}\ln n+5\Delta_i\right)$$ をみたす．（論文ではリグレットで表記されているが，文脈的には魏リグレットでは？）