この記事では，「報酬が平均・分散が未知の正規分布に従うと仮定したThompson Sampling」について解説をしたいと思います．

しかし，Thompson Samplingを理解するには，多腕バンディットやベイズ推定についてなど，いくつかの事前知識を必要とするため，４回に分けて以下のような流れで解説を行います．

1. 多腕バンディットについて
2. ベイズ推定について
3. Thompson Samplingについて
4. Thompson Samplingの実験的評価

第１回目となる今回は，強化学習の一分野である「多腕バンディット問題」という分野について軽く解説をしたいと思います．

TL;DR

• 多腕バンディット問題では，複数のスロットマシンの中から報酬の期待値が高い台をし続けるのが目標
  • あらかじめどの台が期待値が高いかはわかっていないので，実際にプレイしてみて情報を集めるしかない
  • プレイする台の選択には探索（exploration）と活用（exploitation）のトレードオフが存在
  • 如何にしてバランスを取りながらプレイする台を選択するかが重要
• 確率的バンディットは，最適な台をプレイできなかったために失う損失であるリグレットを最小化するのが目的

多腕バンディットとは

多腕バンディット問題について説明するときに，「複数のスロットマシンをプレイする」，というシチュエーションが用いられることがよくあります．

本記事でも，例に漏れず，「複数のスロットマシンをプレイする」というシチュエーションを元に説明をしたいと思います．

スロットマシンを用いた例

今，あなたの目の前に，$K$台のスロットマシンがあるとしましょう．

$K$台のスロットマシンにはそれぞれ適当な確率分布が割り当てられています． 各台をプレイすると，その確率分布に従って報酬がサンプルされます．

あなたは，一回ごとに好きな台を選んでプレイすることを合計$T$回繰り返すとします．

あなたは持ち金を増やすために，なるべく多くの報酬を得たいはずです． つまり，なるべく期待値の高い台のみをプレイし続けるというのが理想になります．

さて，あなたはどのようにしてプレイする台を選びますか？ ただし，あなたは各台に対してどのような確率分布が割り当てられているかを知らないものとします．

何が難しい？

期待値が高い台のみをプレイし続ける，という目標は，「各台の報酬がどのような確率分布に従っているのか」ということさえ分かっていれば簡単に達成することができます．

しかし，残念ながら各台に割り当てられた確率分布に関しては，はじめは何の情報もありません．

したがって，確率分布に関する情報を集めるために，各台を実際に何回かプレイしてみて，どの程度の報酬が得られるのかを観測する必要があります．

その一方で，期待値が低い台を何度もプレイしてしまうと，その分だけ損をすることになってしまうので，それまでに得た情報の中から期待値の高そうな台を推定し，その台を引く回数を増やす必要もあります．

前者は探索（exploration）と呼ばれ，後者は活用（exploitation）と呼ばれます． 探索と活用はお互いに相反する行為なので，どちらも同時に行うことができないので，トレードオフのような関係性を持ちます．

多腕バンディット問題では，この探索と活用のバランスを如何にしてとるか，ということが問題になります．

さて，多腕バンディット問題の概要と難しさを例を通じてなんとなく分かって頂いたところで，次は多腕バンディット問題を定式化してみましょう．

確率的バンディットと敵対的バンディット

多腕バンディット問題は，確率的バンディットと敵対的バンディットという２つに大別されます．

確率的バンディットでは，各台からの報酬が台に対して割り当てられた確率分布に従って決定されます．

一方で敵対的バンディットでは，各台からの報酬が敵対者と呼ばれるプレイヤーの台の選択方法を知っている最強の相手によって決定されます． 敵対的バンディットは各台からの報酬が何らかの確率分布に従っていることを仮定しなくても良いため，より広い範囲のケースを扱うことができますが，その分抽象的な枠組みになってしまいます．

察している方もいるかと思いますが，さきほどのスロットマシンの例は，実は確率的バンディットの一例でした．

今回の記事では，敵対的バンディットの説明は省き，確率的バンディットのみを対象としたいと思います（というより，敵対的バンディットについてそんなに詳しくありません）．

確率的バンディットの定式化

確率的バンディットの前提と目標

確率的バンディットでは，$K$台のスロットマシンが存在するとします．

プレイヤーは，各ステップ$t=1,\cdots,T$において，$K$台のスロットマシンから１つのマシンを選択してプレイします．

各台$i(i\leq i\leq K)$は，プレイされると，台$i$に割り当てられた期待値$\mu_i$である時不変の確率分布に従って，報酬を生成します．繰り返し台をプレイして得られる報酬はi.i.d，かつ，他の台とは独立して生成されるとします．

確率的バンディットでは，$t-1$までのプレイで得た報酬の履歴に基いて，ステップ$t$でどの台をプレイするかを決定する必要があります．

確率的バンディットでの目標は，ステップ$T$における報酬の合計値の期待値

$$E[\sum_{t=1}^{T}\mu_{i(t)}]$$

を最大化することです．

ここで，$i(t)$はステップ$t$においてプレイされる台のインデックスを表しており，期待値$E[\cdot]$はプレイする台を選択するアルゴリズムによる$i(t)$のランダム性に対する期待値を表しています．

リグレット最小化

前節で定義した確率的バンディットは，確率分布の期待値$\mu_i$のスケールに依存してしまうため，純粋に台選択アルゴリズムの良さを測るのには少し扱いづらさがあります．

そこで，リグレットと呼ばれる値の期待値を代わりの尺度とすることが一般的です．

$$E[Regret(T)]=E\left[\sum_{t=1}^{T}\left(\mu^{\ast}-\mu_{i(t)}\right)\right]=\sum_i\Delta_i\cdot E[k_i(T+1)]$$

ここで，$\mu^{\ast}=\max_i\mu_i$，$\Delta_i=(\mu^{\ast}-\mu_i)$であるとします． また，$k_i(t)$はステップ$t-1$までに台$i$がプレイされた回数とします．

この式は，各ステップ$t$において最適な台，すなわち，期待値が最大の台をプレイしなかったために失う損失の合計値の期待値，と捉えることができます．

報酬の合計値と違って，リグレットは小さければ小さいほど良い値（$0$が最小）になります．

なので，確率的バンディットの目標は，$E[Regret(T)]$を最小化すること，になります．