今日読んだ部分では確率的バンディット問題をより詳しく定義し，「不確実なときは楽観的に」というヒューリスティックの原則を紹介しています．
２章 Stochastic Bandits: Fundamental Results
確率的バンディット問題とは
各アームを$i=1,\dots,K$とし，アームに対応する未知の確率分布を$\nu_i$とする． 各ステップ$t=1,2,\dots$で，予測者はアーム$I_{t}\in{1,\dots,K}$を選び，$\nu_{I_t}$から（過去とは独立に）報酬$X_{I_t,t}$を受け取る． アーム$i$の平均を$\mu_i$とし，アームの平均の最大値と，最大値を取るアームのインデックスをそれぞれ$\mu^*=\max_{i=1,\dots,K}\mu_i$と$i^*\in\rm arg\max_{i=1,\dots,K}\mu_i$とする． 確率的設定では擬リグレットを主に考える． これは，確率的設定においては実際の報酬について最適な行動と比較するより，最適な行動の期待値と比較するほうが自然であるためだ．
以下のように擬リグレットを書き換えた定式化もリグレットとして用いる． 最初から$s$ラウンドまでのプレイヤーに選ばれたアーム$i$の回数を$T_i(s)=\sum_{t=1}^s\mathbb{1}_{I_t=i}$とする． アーム$i$のsuboptimalityパラメータを$\Delta_i=\mu^*-\mu_i$とする． 擬リグレットは$$\overline{R}_n=\left(\sum_{i=1}^K\mathbb{E}T_i(n)\right)\mu^*-\sum_{i=1}^K\mathbb{E}T_i(n)\mu_i=\sum_{i=1}^K\Delta_i\mathbb{E}T_i(n)$$と書くことができる．
2.1 Optimism in Face of Uncertainty
確率的バンディット問題の難しさは探索と活用のジレンマにある． この問題に対して良い戦略は探索と活用を同時に行うことだ．
これを行うためのかんたんなヒューリスティックの原則は「不確かなときは楽観的に(optimism in face of uncertainty)」と呼ばれるものだ. このアイディアはとても汎用的で，不確かな環境の中で多くの連続した意思決定を行っていく問題に用いられる． 予測者が環境から蓄積されたデータを持っていて，次にどのように行動するか決めなければならない場合を考える． はじめに，データに矛盾しない実際にあり得る環境の集合を構築する（一般に，concentration inequalitiesを用いて）． 次に，この集合の中から最も好ましい環境を特定する． 不確かなときは楽観的にの原則に基づき，最も好ましく，実現可能な環境の中で最適な決定を下す． 今後見ていくように，この原則によりシンプルでありながら，確率的バンディット問題に対してほとんど最適なアルゴリズムを作ることができる．