今日読んだ部分では，バンディット問題の確率的設定，敵対的設定，マルコフ性を持つ設定についてより詳しく紹介しています．
１章 導入
確率的バンディット問題の設定とは
それぞれのアームを$i=1,\dots,K$とする． 対応する$[0,1]$上の未知の確率分布を$\nu_i$とする． 選択したアームに対応するが確率分布$\nu_i$から独立にサンプリングされた報酬を$X_{i,t}$とする．
確率的バンディット問題
既知のパラメータ：アーム数$K$，取りうるラウンド数$n\ge K$
未知のパラメータ：$[0,1]$上の$K$個の確率分布$\nu_1,\nu_2,\dots,\nu_K$
各ラウンドに対して，
- 予測者はアーム$I_t\in\{1,\dots,K\}$を選ぶ
- 与えられた選択$I_t$に対して，過去に依存しない報酬$X_{I_t,t}\sim\nu_{I_t}$が環境から支払われ，予測者に明らかになる．
$i=1,\dots,K$に対して，$\nu_i$の平均（アーム$i$の報酬の平均）を$\mu_i$と記す． また，平均が最大のアームの平均値とそのアームのインデックスを$\mu^*=\max_{i=1,\dots,K}\mu_i$と$i^*=\rm arg\max_{i=1,\dots,K}\mu_i$とする． 擬リグレットは$$\overline{R}_n=n\mu^*-\sum_{t=1}^n\mathbb{E}[\mu_{I_t}]$$ とかける．
敵対的バンディット問題の設定とは
確率的バンディットの研究と並行して，探索と活用のトレードオフをゲームセオリーの視点からの定式化したものが研究された．
ゲームセオリー版のバンディット設定の動機づけをするために，不正をしているカジノにいることを考える．
そこでは，$i=1,\dots,K$のスロットマシンがあり，各時刻$t$にオーナーは自由な報酬（悪意を持って選ばれることがありうる）$g_{i,t}\in[0,1]$を$X_{i,t}$にセットする（誰もギャンブルにいかなくなるので，すべての報酬をゼロにする場合には興味がない）．
予測者は$t=1,2,\dots$において，アーム$I_{t}\in{1,\dots,K}$を選び，報酬$g_{I_t,t}$を観測する．
このとき，リグレットは最小できるだろうか？
このような設定を敵対的設定という．
敵対者が神だったりすると勝てないので，敵対者に仮定を置く．
- obvious adversary
各アームの報酬を設定するメカニズムが予測者の行動に依存しない - nonobvious adversary
各アームの報酬を設定するメカニズムが予測者の過去の行動に依存する．
明らかにこの２つの区別はプレイヤーが乱択する際に意味を持つ．もし，プレイヤーが決定的にアームを選ぶなら，敵対者はゲームのはじめにプレイヤーの行動をシミュレートして正しく報酬を決めることができてしまう．
nonobvious設定においてはリグレットの意味が曖昧になる． リグレットをプレイヤーの累積報酬と$n$ラウンドで最良の一つのアームを引き続けたときの報酬を比較したものとする． 報酬がプレイヤーの過去の行動に依存するため，プレイヤーが一つのアームを引き続けたとき，敵対的に決められた報酬とプレイヤーが実際に得られる報酬が異なることがある．
敵対的バンディット問題
既知のパラメータ：アーム数$K$，ラウンド数$n\ge K$
各ラウンド$t=1,2,\dots$に対して，
- 予測者は外部の乱数を利用して（しなくても良い），アーム$I_k\in\{1,\dots,K\}$を選ぶ．
- 同時に，敵対者は外部の乱数を利用して（しなくても良い），報酬ベクトル$\mathbf{g}_t=(g_{1,t},g_{2,t},\dots,g_{K,t})\in[0,1]^K$を選ぶ．
- 予測者は報酬$g_{I_t,t}$を受け取り，観測する．他のアームの報酬は観測しない．
この敵対的バンディット設定のゴールは高確率でのリグレットバウンドを得ることか，予測者と敵対者のランダム性に対しての期待リグレットバウンドを出すことである． nonobvious設定でこうしたリグレットを出すのは大変なので，擬リグレットから始める． $$\overline{R}_n=\max_{i=1,\dots,K}\mathbb{E}\left[\sum_{t=1}^ng_{i,t}-\sum_{t=1}^ng_{I_t,t}\right]$$
マルコフ性のあるバンディット設定
３つ目の基盤となるバンディット設定では各アームがそれぞれが状態空間を持つKこのマルコフ過程だと考える． 各時刻において，状態$s$においてアーム$i$が選ばれ，確率的な報酬が確率分布$\nu_{i,s}$からサンプリングされる．そして，アーム$i$の報酬過程の状態が確率的遷移行列$M_i$に基づいて，マルコフ過程のやり方で遷移する． 報酬と新しい状態はプレイヤーに明らかになっている． 一方で，選ばれなかったアームの状態は変わらない． これまでのバンディット設定はプレイヤーがリソースを投入するアーム$i$は変わらなかったが，マルコフ性のあるバンディット設定では変わりうる． また，確率的遷移行列$M_i$は既知であるとすることが多い． この場合，動的計画法により計算可能である． Gittinsは効率的に計算できる貪欲法を提案した．
マルコフ性のあるバンディット設定の有名な例はベイジアンバンディットだ． これらはパラメトリックな確率的バンディットである． 報酬分布のパラメータは既知の事前分布からサンプリングされ，リグレットは事前分布からサンプリングされたパラメータに対して平均を取ることで計算される． 選ばれたアームの状態遷移は新しい報酬を観測後，報酬の事後分布を更新することに対応する．