いま知っている情報で最善の選択をするか（活用）、それとも損を覚悟でもっと良い選択肢があるか調べるか（探索）？オンライン意思決定における最も根本的な葛藤だ。シルバーはこの講義で、一見ばらばらに見える探索戦略を五つの原理にまとめる。素朴な探索、楽観的初期化、不確実性下の楽観、確率一致、そして情報状態探索だ。以降のすべての節は、この五つの原理のどこかにぶら下がっている。
講義スライド: PDF
探索か活用か
活用とはいま知っていることで最善の決定を下すことであり、探索とはより多くの情報を集めることだ。核心は、長期的に最善の決定をするには短期的な犠牲が必要になりうる、という点にある。いま少し損をしてでも情報を十分に集めてこそ、旅路全体で最善の選択ができる。
シルバーが挙げる例が直観を築く。レストランを選ぶとき、活用はいつも通う行きつけの店に行くことで、探索は新しい店を一度試してみることだ。バナー広告では、活用は最もよく効いた広告を再び出すことで、探索は別の広告を試すことだ。石油掘削なら、活用はこれまで最もよく出た場所を掘ることで、探索は新しい場所に穴を開けてみることだ。囲碁なら、活用は最善だと信じる手を打つことで、探索は実験的な手を投げることだ。すべて同じ緊張である。いまの最善と未知の可能性のあいだで、どう時間を割り振るか。
五つの原理
この講義の骨格だ。シルバーは探索手法を次の五つの原理に整理する。
- 素朴な探索：貪欲方策にノイズを加える。$\epsilon$-貪欲が代表。
- 楽観的初期化：反証されるまではすべての選択肢が最良だと仮定する。
- 不確実性下の楽観：価値が不確実な行動を好む。
- 確率一致：各行動を、それが最適である確率だけ選ぶ。
- 情報状態探索：情報の価値まで計算に入れ、先を見越して計画する。
以下ではこれらの原理を、まず最も単純な舞台である多腕バンディットで立て、次に文脈付きバンディットとMDPへ引き上げる。
多腕バンディット
多腕バンディットはタプル $\langle \mathcal{A}, \mathcal{R} \rangle$ である。$\mathcal{A}$ は既知の $m$ 個の行動（腕）の集合であり、$\mathcal{R}^a(r) = \mathbb{P}[r \mid a]$ は未知の報酬分布だ。各ステップ $t$ でエージェントが腕 $a_t$ を引くと、環境が報酬 $r_t \sim \mathcal{R}^{a_t}$ を返す。目標は累積報酬 $\sum_{\tau=1}^t r_\tau$ を最大化することだ。状態も遷移もない。ただどの腕が良いかだけが残る、探索と活用の純粋な実験室である。
リグレット
成果を測る自然な尺度がリグレット（後悔）だ。行動の価値はその腕の平均報酬 $Q(a) = \mathbb{E}[r \mid a]$ であり、最適価値は
$$V^* = Q(a^*) = \max_{a \in \mathcal{A}} Q(a)$$1ステップのリグレットは、最適を差し置いて別の腕を引いたことで逃した機会損失だ。
$$l_t = \mathbb{E}[V^* - Q(a_t)]$$全体リグレットはこれをすべて足したものだ。
$$L_t = \mathbb{E}\Big[\sum_{\tau=1}^t V^* - Q(a_\tau)\Big]$$累積報酬を最大化することは、すなわち全体リグレットを最小化することと同じだ。以降はリグレットを減らすという観点で見る。
リグレットを数えてみる
リグレットをもう少し分解すると、何が問題なのかが見えてくる。$N_t(a)$ をステップ $t$ までに腕 $a$ を引いた期待回数とし、ギャップ $\Delta_a = V^* - Q(a)$ を最適腕と腕 $a$ の価値の差としよう。すると、リグレットはギャップと回数の関数へときれいに分かれる。
$$L_t = \mathbb{E}\Big[\sum_{\tau=1}^t V^* - Q(a_\tau)\Big] = \sum_{a \in \mathcal{A}} \mathbb{E}[N_t(a)]\,(V^* - Q(a)) = \sum_{a \in \mathcal{A}} \mathbb{E}[N_t(a)]\,\Delta_a$$読み方が重要だ。良いアルゴリズムは、ギャップが大きい腕（つまり大きく悪い腕）ほど引く回数を少なくすべきだ。ギャップが大きければ一度引くたびにそれだけリグレットが大きく積み上がるからだ。ところが落とし穴がある。私たちはギャップを知らない。ギャップを知っていたなら、そもそも最適腕が何かを知っていることであり、問題は終わってしまう。悪い腕をあまり引きたくないのに、どの腕がどれだけ悪いかを知らないこと、これがバンディット問題の本質だ。
線形リグレットか劣線形リグレットか
時間が経つにつれて全体リグレットがどう増えるかが、アルゴリズムの等級を分ける。二つの極端はどちらも失敗する。永遠に探索だけをすれば（ランダムに引き続ければ）悪い腕を引き続けるので、リグレットは時間に比例して線形に増える。永遠に探索をしなければ（一度決めた腕だけを引き続ければ）、外した場合その損が永遠に続き、やはり線形だ。問いはこれである。リグレットを線形より遅く、すなわち劣線形に減らせるか。
貪欲と $\epsilon$-貪欲
まず各腕の価値をモンテカルロで推定する。これまでその腕から受け取った報酬の平均だ。
$$\hat{Q}_t(a) = \frac{1}{N_t(a)} \sum_{t=1}^{T} r_t\,\mathbf{1}(a_t = a)$$貪欲アルゴリズムは推定価値が最も高い腕を選ぶ。$a_t^* = \arg\max_a \hat{Q}_t(a)$。問題は明白だ。序盤に運悪く真の最適腕から低い報酬を数回受け取ると、貪欲はその腕を永遠に無視して次善に居座りうる。一度はまり込むと抜け出せない。だから貪欲は線形リグレットを生む。
$\epsilon$-貪欲はこのはまり込みを防ぐためにノイズを混ぜる。確率 $1-\epsilon$ で $\arg\max_a \hat{Q}(a)$ を選び、確率 $\epsilon$ でどれかの腕をランダムに引く。おかげで永遠に探索を続けるので、最適腕をまったく見逃すことはない。しかし $\epsilon$ を定数に置くと、毎ステップ $\epsilon$ の確率で悪い腕を引く慣性が消えない。
$$l_t \geq \frac{\epsilon}{|\mathcal{A}|} \sum_{a \in \mathcal{A}} \Delta_a$$この最小リグレットが毎ステップ敷かれるので、定数 $\epsilon$-貪欲も結局は線形リグレットだ。これが素朴な探索の限界である。
楽観的初期化
二つめの原理だ。きわめて単純で実践的なアイデアで、すべての腕の初期価値 $Q(a)$ をわざと高く設定しておく。そして増分モンテカルロで更新するが、最初から $N(a) > 0$ で始める。
$$\hat{Q}_t(a_t) = \hat{Q}_{t-1} + \frac{1}{N_t(a_t)}(r_t - \hat{Q}_{t-1})$$効果はこうだ。すべての腕が最初は「自分こそ最良かもしれない」という膨らんだ期待を身にまとっているので、エージェントは自然と引いていない腕から一つずつ試していく。実際に引いてみると膨らんだ期待が現実の値へと削られ、そこで初めて楽観が晴れる。反証されるまでは最良だと仮定する、という原理の言葉どおりだ。序盤の探索を体系的に誘導する点で良いが、根本的な処方ではない。運悪く序盤に最適腕の楽観が早く削られてしまえば、依然として次善にはまり込みうる。だから貪欲に楽観的初期化を加えても、$\epsilon$-貪欲に加えても、依然として線形リグレットだ。
減衰する $\epsilon$-貪欲
$\epsilon$ を定数に置くのが問題なら、時間とともに減らしてはどうか。減衰スケジュール $\epsilon_1, \epsilon_2, \dots$ を取る。次のスケジュールを見よう。$c > 0$ かつ $d = \min_{a \mid \Delta_a > 0} \Delta_i$（最も小さい正のギャップ）のとき
$$\epsilon_t = \min\left\{1, \frac{c|\mathcal{A}|}{d^2 t}\right\}$$驚くべきことに、この減衰 $\epsilon$-貪欲は漸近的に対数リグレットを達成する。線形から対数へと下りてきたのだ。ところが決定的な但し書きが付く。このスケジュールはギャップ $d$ をあらかじめ知っている必要がある。先に見たとおり、ギャップは私たちが知らないまさにそれだ。だから目標を立て直さねばならない。報酬分布 $\mathcal{R}$ に関する事前知識なしに、任意の多腕バンディットに対して劣線形リグレットを出すアルゴリズムを見つけることだ。
下界：Lai-Robbins
ところが、どれほど賢くても越えられない壁がある。どんな問題が難しいかをまず見よう。問題の難しさは、最適腕と残りの腕がどれだけ似ているかで決まる。難しい問題は、見た目（分布）は似ているのに平均がわずかに異なる腕を持つ。二つの腕の報酬分布がほぼ重なると、どちらが少し良いかを見分けるのに非常に多くの標本が必要になるからだ。この類似はギャップ $\Delta_a$ と、分布間のKL情報量 $\mathrm{KL}(\mathcal{R}^a \Vert \mathcal{R}^{a^*})$ で形式化される。
定理（LaiとRobbins）。 漸近的な全体リグレットは、ステップ数の対数以上である。
$$\lim_{t \to \infty} L_t \geq \log t \sum_{a \mid \Delta_a > 0} \frac{\Delta_a}{\mathrm{KL}(\mathcal{R}^a \Vert \mathcal{R}^{a^*})}$$読み方はこうだ。どのアルゴリズムもリグレットを対数より速く減らすことはできない。対数リグレットが私たちの望みうる最善だ。そして分母のKLが小さいほど（腕が似ているほど）下界が大きくなる。似て見えるのに平均が異なる腕が最も難しい、という直観が式にそのまま刻まれている。あとは、この対数下界に実際に届くアルゴリズムを見つけることだけが残る。
不確実性下の楽観
三つめの原理だ。複数の腕の価値推定が、それぞれ異なる幅の不確実性（分布）を身にまとっているとしよう。どの腕を選ぶべきか。シルバーの答えがこの原理の核心だ。ある行動の価値について不確実であるほど、その行動を探索することがより重要になる。なぜなら、まさにその腕が実は最良かもしれないからだ。不確実だということは、上方向に大きく開いている可能性を含むという意味だ。
青い腕を引いてみると、その腕の価値についての不確実性が減り、するとまだより不確実な別の腕へと関心が移っていく。この過程を繰り返すと、やがて本当に最良の腕へ収束する。楽観をデータで一つずつ検証していくわけだ。
上側信頼限界
この原理を数値にしたのが上側信頼限界（UCB）だ。各行動に上側ボーナス $\hat{U}_t(a)$ を付け、高い確率で真値がその下にあるようにする。
$$Q(a) \leq \hat{Q}_t(a) + \hat{U}_t(a)$$このボーナスは、その腕を何回引いたか $N_t(a)$ に依存する。$N_t(a)$ が小さければ（あまり引いていなければ）$\hat{U}_t(a)$ が大きく（推定が不確実）、$N_t(a)$ が大きければ $\hat{U}_t(a)$ が小さい（推定が正確）。そしてこの上限が最も高い腕を選ぶ。
$$a_t = \arg\max_{a \in \mathcal{A}} \hat{Q}_t(a) + \hat{U}_t(a)$$推定値が良くて（価値が高くて）選ばれるか、あまり引いていなくて（不確実で）選ばれるか。活用と探索が一つの式に溶け込む。
Hoeffdingの不等式からボーナスを導く
ところがボーナス $\hat{U}_t(a)$ をどんな定数でも適当に決めてよいわけではない。これは統計的な信頼区間でなければならず、その幅はHoeffdingの不等式から出る。
定理（Hoeffdingの不等式）。 $X_1, \dots, X_t$ が $[0,1]$ 内の独立同分布の確率変数で、$\overline{X}_t = \frac{1}{t}\sum_{\tau=1}^t X_\tau$ が標本平均であれば、
$$\mathbb{P}\big[\mathbb{E}[X] > \overline{X}_t + u\big] \leq e^{-2tu^2}$$読み方が鍵だ。標本平均が真の平均から $u$ 以上ずれる確率は、$u$ が大きくなるほど指数的に小さくなる。これを腕 $a$ を選んだときの報酬に適用すると
$$\mathbb{P}\big[Q(a) > \hat{Q}_t(a) + U_t(a)\big] \leq e^{-2 N_t(a) U_t(a)^2}$$いま真値が上限を超える確率 $p$ を一つ決め、$U_t(a)$ について解けばよい。
$$e^{-2 N_t(a) U_t(a)^2} = p \quad\Longrightarrow\quad U_t(a) = \sqrt{\frac{-\log p}{2 N_t(a)}}$$観測が積み重なるほど、上限を超える事故をより厳しく防ぎたいので、$p$ を時間とともに減らす。たとえば $p = t^{-4}$ と置くと $t \to \infty$ で最適行動を確実に選ぶようになり、ボーナスが次のきれいな形になる。
$$U_t(a) = \sqrt{\frac{2 \log t}{N_t(a)}}$$この $\sqrt{2 \ln t / N(a)}$ が任意に選んだ魔法の定数ではない、というのが核心だ。これはHoeffdingが保証する信頼区間の幅そのものである。あまり引いていない腕ほど（$N$ が小さいほど）広く、時間が経つほど（$t$ が大きいほど確信を要求するので）少しずつ広く開く。
UCB1
これをそのままアルゴリズムに固めたのがUCB1だ。
$$a_t = \arg\max_{a \in \mathcal{A}} Q(a) + \sqrt{\frac{2 \log t}{N_t(a)}}$$定理。 UCBアルゴリズムは漸近的に対数の全体リグレットを達成する。
$$\lim_{t \to \infty} L_t \leq 8 \log t \sum_{a \mid \Delta_a > 0} \Delta_a$$ギャップをあらかじめ知る必要があった減衰 $\epsilon$-貪欲と違い、UCB1はギャップに関する事前知識なしに対数リグレットに届く。Lai-Robbins下界が対数だったので、UCBはその壁に定数倍以内で貼り付いたわけだ。シルバーは実際の10腕バンディット実験で、UCBが $\epsilon$-貪欲を安定して上回るという比較図を見せる。
確率一致とトンプソンサンプリング
ここまでは報酬分布について上限だけを仮定し、特別な事前知識を使ってこなかった。ベイズバンディットはここから一歩進む。報酬に対する事前分布 $p[\mathcal{R}]$ を仮定し、観測履歴 $h_t = a_1, r_1, \dots, a_{t-1}, r_{t-1}$ が与えられたときの事後分布 $p[\mathcal{R} \mid h_t]$ を計算して探索を導く。事前知識が正確なら性能が良くなる。この事後分布を使う道が二つあり、一つはベイズUCBで、もう一つがこれから見る確率一致（トンプソンサンプリング）だ。
ベイズUCBの例として報酬がガウシアンだと仮定すると、各腕の平均と分散に対するガウシアン事後をベイズ則で得て、平均に標準偏差を定数倍だけ乗せた腕を選ぶ。
$$a_t = \arg\max_a\; \mu_a + \frac{c\,\sigma_a}{\sqrt{N(a)}}$$先のUCBと同じ精神だ。不確実であるほど（$\sigma_a$ が大きいほど）上へより押し上げる。
確率一致
四つめの原理だ。確率一致は、各行動をその行動が最適である確率だけ選ぶ。
$$\pi(a \mid h_t) = \mathbb{P}\big[Q(a) > Q(a'),\ \forall a' \neq a \mid h_t\big]$$この方策がなぜ不確実性下の楽観と通じるかを見よう。不確実な行動ほど事後分布の上側の裾が厚く、他のすべての腕より値が大きい確率、すなわち最適である確率が自然に高くなる。だから不確実な腕がより頻繁に選ばれる。ただし、この確率を事後分布から解析的に計算するのが難しいのが難点だ。
トンプソンサンプリング
ここで驚くほど単純なトリックが登場する。トンプソンサンプリングは確率一致を標本一つで実装する。
$$\pi(a \mid h_t) = \mathbb{P}\big[Q(a) > Q(a'),\ \forall a' \neq a \mid h_t\big] = \mathbb{E}_{\mathcal{R} \mid h_t}\big[\mathbf{1}(a = \arg\max_a Q(a))\big]$$手順はこうだ。ベイズ則で事後分布 $p[\mathcal{R} \mid h_t]$ を得て、その事後から報酬分布 $\mathcal{R}$ を一つ標本抽出し、その標本で価値 $Q(a) = \mathbb{E}[\mathcal{R}^a]$ を計算したのち、その標本の上で最大値を与える腕を選ぶ。$a_t = \arg\max_a Q(a)$。毎回事後から引いた一つの標本のargmaxを取るこの単純な行為が、まさに「各腕を最適である確率だけ選ぶ」を実現する。不確実な腕は標本が大きく出ることが多く、頻繁に勝つ。
どんでん返しは歴史にある。この方法は1933年にトンプソンが提案した非常に古いアイデアなのだが、驚くべきことにトンプソンサンプリングはLai-Robbins下界を達成する。UCBと同様に理論的最善に届くのに、実装は事後から標本を一つ引くことで終わる。
10腕バンディットにおけるε-貪欲・UCB・トンプソンの累積リグレット。トンプソンがおおむね最も低い。「+5000」で長く回すと、ε-貪欲は定数探索のせいでリグレットが線形に急激に開いていく一方、UCBとトンプソンは劣線形（対数）に寝ていくのがはっきりする。εを大きくしたり、「新しいバンディット」で別の問題でも確かめてみよう。
情報の価値とベイズ適応
五つめの原理だ。探索はなぜ有用か。情報を得るからだ。ならば情報の価値を値付けできるだろうか。情報の価値とは、決定を下す前にその情報を持つために意思決定者が進んで支払う報酬の量である。情報を得た後の長期報酬から、当面の報酬を引いたものだ。不確実な状況ほど得られる情報が多いので、不確実な状況をより探索するのが理にかなう。情報の価値がわかれば、探索と活用を最適に天秤にかけられる。
情報状態空間
ここで観点が大きく変わる。ここまでバンディットを1ステップの決定問題として見てきたが、逐次的決定問題としても見られる。各ステップに情報状態 $\tilde{s}$ がある。$\tilde{s}$ は履歴の統計量 $\tilde{s}_t = f(h_t)$ で、これまでに積み上がったすべての情報を要約する。まだ何を知らないかを収めた状態というわけだ。そして各行動 $a$ は（情報を加えることで）新しい情報状態 $\tilde{s}'$ への遷移を、確率 $\tilde{\mathcal{P}}^a_{\tilde{s},\tilde{s}'}$ で引き起こす。これが拡張された情報状態空間の上のMDP $\tilde{\mathcal{M}} = \langle \tilde{\mathcal{S}}, \mathcal{A}, \tilde{\mathcal{P}}, \mathcal{R}, \gamma \rangle$ を定義する。探索がすなわち、この巨大なMDPの上の計画問題へと還元されるのだ。
例：ベルヌーイバンディット
具体的な例が絵を完成させる。ベルヌーイバンディットでは各腕が $\mathcal{R}^a = \mathcal{B}(\mu_a)$、すなわち確率 $\mu_a$ で勝ち負けするゲームだ。どの腕の $\mu_a$ が最も高いかを見つけたい。ここで情報状態は $\tilde{s} = \langle \alpha, \beta \rangle$ である。$\alpha_a$ は腕 $a$ を引いて報酬が0だった回数、$\beta_a$ は報酬が1だった回数だ。この $\langle \alpha, \beta \rangle$ が、その腕の報酬モデルに対する $\mathrm{Beta}(\alpha, \beta)$ 事後分布に対応する。
腕を引くたびに事後が更新されるのが、そのまま状態遷移になる。
$$\langle \alpha_a, \beta_a \rangle \to \begin{cases} \langle \alpha_a + 1, \beta_a \rangle & r = 0 \\ \langle \alpha_a, \beta_a + 1 \rangle & r = 1 \end{cases}$$$\mathrm{Beta}(\alpha_a, \beta_a)$ 事前から始めて、腕を引くたびに事後を更新するこの流れが、ベイズ適応MDPの遷移関数 $\tilde{\mathcal{P}}$ を定義する。各状態遷移が一つのベイズモデル更新に対応するのだ。
Gittins指数とシミュレーション探索
いまや私たちの手には情報状態の上の無限MDPがある。これは強化学習で解ける。モデルフリーへ行けばQ学習（Duff, 1994）のような方法であり、ベイズのモデルベースへ行けばGittins指数（Gittins, 1979）だ。このアプローチをベイズ適応強化学習と呼び、事前分布に対してベイズ最適な探索・活用の天秤を見つける。すなわちベイズ適応MDPを動的計画法で解けば厳密解が出て、その解がすなわちGittins指数だ。
問題は、この厳密解がたいてい扱いにくいことだ。情報状態空間が大きすぎる。だから実践では、最近のアイデアであるシミュレーションベース探索（Guez et al. 2012）を使う。現在の情報状態から複数のシミュレーションを回し、情報状態空間の前方を見越す方式だ。
文脈付きバンディット
バンディットに状態（文脈）を加えると、実践に一歩近づく。文脈付きバンディットはタプル $\langle \mathcal{A}, \mathcal{S}, \mathcal{R} \rangle$ である。$\mathcal{S} = \mathbb{P}[s]$ は未知の状態（文脈）分布であり、$\mathcal{R}^a_s(r) = \mathbb{P}[r \mid s, a]$ は状態と行動に条件付けられた報酬分布だ。各ステップで環境が状態 $s_t \sim \mathcal{S}$ を出し、エージェントが行動 $a_t$ を選ぶと、環境が報酬 $r_t \sim \mathcal{R}^{a_t}_{s_t}$ を与える。ニュースのトップ画面にどの記事を出すか、このユーザーにどの広告を見せるか、といった問題がここにぴたりと当てはまる。文脈（ユーザー、時間帯）に応じて最善の行動が変わる。
線形UCB
価値関数を線形近似器で推定する。$Q_\theta(s, a) = \phi(s, a)^\top \theta \approx Q(s, a)$。パラメータは最小二乗回帰で求める。
$$A_t = \sum_{\tau=1}^t \phi(s_\tau, a_\tau)\phi(s_\tau, a_\tau)^\top, \quad b_t = \sum_{\tau=1}^t \phi(s_\tau, a_\tau) r_\tau, \quad \theta_t = A_t^{-1} b_t$$ここで決定的な観察がある。最小二乗回帰は平均価値 $Q_\theta(s, a)$ だけを与えるのではなく、その価値の分散 $\sigma_\theta^2(s, a)$ まで与える。パラメータ推定の誤差から来る不確実性だ。だから不確実性の分だけボーナス $U_\theta(s, a) = c\sigma$ を乗せればよい。平均より $c$ 標準偏差上をUCBとするのだ。幾何で見ると、パラメータ $\theta_t$ のまわりに真のパラメータ $\theta^*$ を高い確率で含む信頼楕円体 $\mathcal{E}_t$ を描き、その中で価値を最大にするパラメータを選んで不確実性を反映する。
最小二乗ではパラメータの共分散が $A^{-1}$ であり、価値が特徴に線形なので、価値の分散は二次形式になる。$\sigma_\theta^2(s, a) = \phi(s, a)^\top A^{-1} \phi(s, a)$。したがって選択則は
$$a_t = \arg\max_{a \in \mathcal{A}} Q_\theta(s_t, a) + c\sqrt{\phi(s_t, a)^\top A_t^{-1} \phi(s_t, a)}$$バンディットの $\sqrt{2\log t / N(a)}$ が、文脈版では信頼楕円体の幅 $c\sqrt{\phi^\top A^{-1} \phi}$ へと育ったのだ。シルバーはこの線形UCBでニュースのトップ画面記事を選んだLi（李）らの事例を挙げる。
MDPへの拡張
バンディットで立てた五つの原理は、そのままMDPへ上がる。素朴な探索、楽観的初期化、不確実性下の楽観、確率一致、情報状態探索。それぞれをMDP版へ移してみよう。
楽観的初期化
モデルフリーでは行動価値を楽観的に初期化する。
$$Q(s, a) \leftarrow \frac{r_{\max}}{1 - \gamma}$$こうして到達可能な最大値へ膨らませておき、モンテカルロ制御でもSarsaでもQ学習でも好きなモデルフリーアルゴリズムを回せば、行っていない状態と行動を体系的に探索する。モデルベースでは楽観的MDPを立てる。まだ経験していない遷移は「天国へ行く」、すなわち $r_{\max}$ の報酬を与える終了状態へ行くと初期化する。そしてこの楽観的MDPを方策反復でも価値反復でも木探索でも解く。これがRMaxアルゴリズム（BrafmanとTennenholtz）だ。
不確実性下の楽観
モデルフリーUCBは行動価値の上限を最大化する。$a_t = \arg\max_a Q(s_t, a) + U(s_t, a)$。方策評価の不確実性を推定するのは簡単だが、方策改善から来る不確実性は無視する。これをきちんと反映して最適行動価値 $Q^*$ の上限を狙うには、$a_t = \arg\max_a Q(s_t, a) + U_1(s_t, a) + U_2(s_t, a)$ のように改善から来る不確実性 $U_2$ まで加えねばならず、この部分が厄介だ。
確率一致：モデルベースのトンプソン
ベイズのモデルベース強化学習は、MDPモデルそのものに対する事後分布 $p[\mathcal{P}, \mathcal{R} \mid h_t]$ を保持する。遷移と報酬を一緒に推定するのだ。この事後でトンプソンサンプリングをすると確率一致になる。
$$\pi(s, a \mid h_t) = \mathbb{E}_{\mathcal{P}, \mathcal{R} \mid h_t}\big[\mathbf{1}(a = \arg\max_a Q^*(s, a))\big]$$手順はバンディット版をそのまま似せている。事後 $p[\mathcal{P}, \mathcal{R} \mid h_t]$ を計算し、そこからMDP $\langle \mathcal{P}, \mathcal{R} \rangle$ を丸ごと一つ標本抽出し、その標本MDPを好きなプランニングアルゴリズムで解いて $Q^*$ を得て、その標本で最適行動を選ぶ。バンディットで報酬分布を一つ引いていたのが、MDPでは世界全体を一つ引いてその中で計画することへと大きくなる。
情報状態探索
MDPも情報状態を付けて拡張できる。拡張された状態は $\langle s, \tilde{s} \rangle$ で、$s$ は元のMDPの中の状態であり、$\tilde{s}$ は履歴の統計量（積み上がった情報）だ。各行動は新しい状態 $s'$ への遷移と、新しい情報状態 $\tilde{s}'$ への遷移を一緒に引き起こし、拡張された情報状態空間の上のMDP $\tilde{\mathcal{M}}$ を定義する。
とくにMDPモデルに対する事後分布 $\tilde{s}_t = \mathbb{P}[\mathcal{P}, \mathcal{R} \mid h_t]$ 自体が一つの情報状態となり、$\langle s, \tilde{s} \rangle$ の上の拡張MDPをベイズ適応MDPと呼ぶ。これを解けば（事前分布に対して）最適な探索・活用の天秤が出る。ただしバンディットと同様に、ベイズ適応MDPはたいてい途方もなく大きいので、シミュレーションベース探索（Guez et al.）が効果的だった。
おわりに
シルバーは探索と活用のいくつもの原理をたどった。$\epsilon$-貪欲のような素朴な方法、楽観的初期化、上側信頼限界、確率一致、情報状態探索。この五つはすべて最も単純なバンディットの舞台で生まれたが、まったく同じ原理がMDPにもそのまま適用される。一見ばらばらに見えた探索戦略が、実は一つの五叉の地図の上に置かれていたわけだ。