今日読んだ部分では，マルチアームバンディット問題とはどのような問題なのか？を紹介し，応用例を紹介しています． また，マルチアームバンディット問題の３つの設定と性能を図るための評価指標であるリグレットというものを３つ定義しています．
１章 導入
マルチアームバンディット問題とは
マルチアームバンディット問題は行動の候補からそのラウンドに行う行動を繰り返し割り当てる問題である． 各ラウンドで，１つの行動を割り当て，報酬を受け取る． このときのゴールは報酬の合計が最大になるように繰り返し行動を割り当てることである． バンディットという名前はアメリカのスロットマシンのスラングに由来している． カジノで，プレイヤーがたくさんのスロットマシンからアームを引くスロットマシンを次々に選んで，コインを入れていく問題がマルチアームバンディット問題となる．
バンディット問題は限られた情報の中で繰り返し意思決定していく問題である．そして，この問題は繰り返しの試行の中で，過去にうまく行ったアームを引き続けるのか，今後より高い報酬を返すかもしれないアームを探すのかという探索と活用のトレードオフに直面する．
応用
Thompsonによるもともとのバンディット問題の動機は医療における試行に由来するが，現代においては様々な産業分野で応用されている．
- 広告表示とWebページ最適化
Webページの来訪者にどの広告を表示するか，どのデザインを表示するか．このときの報酬はクリックスルーレートや他の望ましいユーザの行動となる． - ネットワークのデータ送信 ソース・ルーティングは，送信元から受信先へのパスを与えられたネットワークから選んで送信する通信方式である．このとき，パケットをどのパスを使って送るかがバンディット問題になる．
- コンピュータゲーム コンピュータゲームにおいては，ムーブのあとの取りうるゲームの続きをシミュレートして，評価することで，ムーブを選ぶ．このとき巨大な探索木から，期待できる部分木を効率的に探索するために使われている． Gellyらはバンディット問題のアルゴリズムを囲碁の木探索に用いるMoGoを実装することに成功した． MoGoはKocsis and Szepesv´ariによる階層型のバンディットのためのUCT(Upper Confidence bound applied to Trees)戦略を用いた．これは２章のUCB(Upper Confidence Bound)アルゴリズムから導かれる．
確率的バンディット設定と敵対的バンディット設定，マルコフ性をもつバンディット設定
報酬が支払われる過程に仮定されている性質によって，バンディット問題は３つの基盤となる定式化がある．その３種類とは確率的設定，敵対的設定，マルコフ性をもつ設定である． 本稿では確率的設定と敵対的設定を取り上げる．マルコフ性を持つバンディット設定については Mahajan and TeneketzisやGittinsらを参照．
リグレット
バンディット問題において，プレイヤーや予測者（バンディットアルゴリズムを実装した人）の振る舞いを解析するために，最適な戦略を取った人との性能の差を比較する． ここで，最適な戦略とは$n$ステップの間，一貫して最適なアームを引き続けることである． 言い換えれば，最適な戦略を取らなかったことに対する予測者のRegret（後悔）を調査する．
アーム数を$K\ge2$とする． 各アーム$i=1\dots K$に紐付いた未知の報酬を$X_{i,1},X_{i,2},\dots$とする． 予測者は各ステップ$t=1,2,\dots$でアーム$I_t$を選び，紐付いた報酬$X_{I_t,t}$を受け取る． nステップ後のリグレットは $$R_n=\max_{t=1,\dots,K}\sum_{t=1}^nX_{i,t}-\sum_{t=1}^nX_{I_t,t}$$ 期間nを前もって知らなくて良い場合，予測者はanytimeであるという． 予測者がanytimeであるとき，アルゴリズムをいつでも停止することができる．
一般に，報酬$X_{i,t}$と予測者の選択$I_t$がともに確率的であるため，以下の２種類の平均リグレットを考えられる．
- 期待リグレット(expected regret) $$\mathbb{E}R_n=\mathbb{E}\left[\max_{i=1,\dots,K}\sum_{t=1}^nX_{i,t}-\sum_{t=1}^nX_{I_t,t}\right]$$
- 擬リグレット(Pseudo Regret) $$\overline{R}_n=\max_{i=1,\dots,K}\mathbb{E}\left[\sum_{t=1}^nX_{i,t}-\sum_{t=1}^nX_{I_t,t}\right]$$
両方の定義で，報酬と予測者の行動の両方について期待値を取っている． 擬リグレットは期待値をとった最適な報酬と比較している．一方で，期待リグレットは実際の報酬に対して最適な行動を取ったときのリグレットの期待値である． このため，擬リグレットは常に期待リグレットより弱い． フォーマルに書くと$\overline{R}_n\le\mathbb{E}R_n$となる．
以下で疑リグレットは期待リグレットより弱いことを確認する．
$i=1,\dots,n$, $0\le\theta\le1$に対して，$$\theta x_i+(1-\theta)y_i\le\theta \max_jx_j+(1-\theta)\max_jy_j$$ が成り立つ．左辺の最大値を考えると，$$\max_i\theta x_i+(1-\theta)y_i\le\theta \max_jx_j+(1-\theta)\max_jy_j$$ が成り立つ．よって，$\max$は凸関数である． そこで，イェンゼンの不等式$f(\mathbb{E}[x])\le\mathbb{E}[f(x)]$($f$は凸関数)より，$\overline{R}_n\le\mathbb{E}R_n$となる．
以上より本当に擬リグレットは期待リグレットより弱かった．