バンディット問題の理論とアルゴリズム読書会 第5章
確率的バンディットとの違い
報酬に確率的な仮定を置かない（方策が決定的）
takkii.iconこのあと方策が確率的なもの出てくるが🤔
プレイヤーの方策を知っている（神のような能力を持つ）敵対者が報酬を選んでいると考えて方策の評価を行う
プレイヤーの方策が決定的である場合
（ここでは報酬の値の範囲を[0,1]と仮定（または正規化））
プレイヤーの方策を知っている敵対者は、プレイヤーが選ぶアームの報酬を全て0にすることが可能
takkii.icon神はプレイヤーの方策を知っていて、そこに確率的な要素もないので、次に選ぶアームを予測できる
僕たちのしたいこと
「良い方策」を考えたい
そのために
方策の評価指標を考えたい
評価指標案1：累積報酬での絶対評価
評価指標を累積報酬での「絶対評価」にすると、どの方策も累積報酬0となってしまい、方策の優劣はつけられない
評価指標案2：累積報酬での相対評価
プレイヤーが最適にアームを選んだ場合の累積報酬と、プレイヤーが選んだアームの累積報酬
神はプレイヤーが選ぶアームの報酬を0、選ばないアームの報酬を1に設定できる。T回プレイしたとすると
プレイヤーが選ぶアームの累積報酬は0
最適選択の累積報酬は$ 1 \times T = T
最適選択の累積報酬とプレイヤーの（決定的）方策での累積報酬の差はどんな方策でもTとなってしまう
方策の優劣の差がつけられない。
ここまでの結論
「最適選択の累積報酬」は強すぎる。
なので別のものを考えよう
リグレットを次のように定義
リグレット＝
「最適アームの累積報酬」
（ある最適なアームを1つ決めそれをT回選び続けた場合の累積報酬）
と「プレイヤーの累積報酬」
の差
https://gyazo.com/032827d8250f45576d32d22168123a26
takkii.iconアームを固定しているため、最適アームの累積報酬は、最適選択と異なり必ずしもTにならない
takkii.icon敵対者はこのリグレットを高めようと言う意志を持っているのか？🤔
例えば、神はできるだけ同じアームに報酬を集めようとするのか？
→そんな意志はないが、リグレットの最大値を考えるためにそのような場合を仮定する、と僕は読み取りました。
この定義だとどうなるか？
例えばプレイヤーが全てのアームを均等に選ぶ方策を取ると、リグレットは$ (K-1) T /K以下になる
https://gyazo.com/e60a067645a2f7f17e50afa17dbcd6d1
リグレットの最大値は$ Tよりは小さくなる
最適アームの累積報酬の最大値：$ (K-1)/K \times T
プレイヤーが選んだアームの累積報酬：$ 0
リグレットの最大値＝$ (K-1)/K \times T - 0
$ Tに関して線形オーダー
takkii.iconなのであまり良い方策ではない
ここまででやったこと
決定的な方策の評価指標について考えた
「最適選択の累積報酬」は強すぎたので、「最適アームの累積報酬」を考えた
リグレットを考えた。ただそのリグレットの最大値は決定的な方策だとどう頑張っても線形オーダーになってしまいそう（たぶん）
ここからやること
決定的な方策はオワコンなので確率的な方策を考えるぞっ
プレイヤー方策としてランダムな選択を許す
各時刻$ tにプレイヤーがアーム$ jを選ぶ確率を$ p_{j,t}とする。
敵対者はランダム選択の結果を知る前に時刻tの報酬を決めなければならないとする（確率だけわかった状態で決める）
敵対者は
$ p_{j,t}が最も低いアームjの報酬を1
それ以外のアームの報酬を0に設定する
プレイヤーは期待値として、最も低い$ p_{j,t} \times 1の報酬を得る
https://gyazo.com/1ebe1c27bab3f68dd849e8c05755037e
takkii.iconちなみにこの時プレイヤーとしては全てのアームを引く確率を$ 1/Kにするのが良い(ランダムにアームを選ぶだけ）
報酬を決める敵対者を適応型敵対者(プレイヤーの過去の選択に依存して次の報酬を決める)とする 敵対者はそれまでの報酬とプレイヤーの選択に依存して次の報酬を決めることができる
敵対者に確率的な方策を用いることも可能だが、「最悪ケース」を評価するためリグレットの最大値に影響なし。
敵対者は決定的な動きをするが、プレイヤーの選ぶアームは確率的。
プレイヤーがそれまで選んだアームによって、次にプレイヤーが引くアームの確率が変わる
そのため敵対者が設定する報酬$ X_j(t)も確率的な振る舞いをする。
確率的な方策に対する評価指標
プレイヤーの確率的な方策に対する評価は2つのやり方がある
1. 任意の小さい$ \sigma > 0に対して$ 1-\sigmaの確率で成り立つリグレット$ \rm{Regret}$ (T)の上界
takkii.icon定理5.6などで扱う
https://gyazo.com/45d815267e5d62c75150defcebcd16b2
右辺1つ目：敵対者が設定する報酬$ X_j(t)も確率的なため、各アームの期待値のmaxを用いる
右辺2つ目：$ i(t)は確率変数。$ T回アームを引いた時の期待値（＝各回で最も低い確率を足し合わせる）
適応型敵対者の場合、擬リグレットの右辺1つ目は「実際にプレイヤーが最適アームを選び続けた場合の累積報酬」ではない
takkii.iconこの場合、右辺1つ目はどのように計算すべきだろう？
プレイヤーが「常にアーム1」か「常にアーム2」かを選ぶことと、
リグレットの計算でアームを固定して考えることは別で考える必要がありそう。
具体例
https://gyazo.com/dc54e4d7b5cdbdf2f18c4a7c52aba9a1
https://gyazo.com/9a8a845bf243593e5475b74f97bb1b7d
takkii.icon$ \mathbb{E} \sum_{t=1}^T X_1(t)=0 \times \frac{1}{2} + (T-1) \times \frac{1}{2}
takkii.icon$ \mathbb{E} \sum_{t=1}^T X_2(t)=(T-1) \times \frac{1}{2} + 0 \times \frac{1}{2}
table:プレイヤーの選択（常に選ぶアーム）とリグレットの計算（アームの固定）
固定アーム1 固定アーム2
プレイヤー 常に1 0 （Tー1）/2
常に2 （Tー1）/2 0
擬リグレットの計算
式(5.2)の右辺の1つ目
https://gyazo.com/e85023ea558110c28e0bd7ca73e83aa9
は$ (T-1) \times \frac{1}{2}
式(5.2)の右辺の2つ目
https://gyazo.com/21bda2a02515c20a2b9a3a6e2cd5ec27
も、この場合は$ 0
なので擬リグレット＝$ (T-1) \times \frac{1}{2}
報酬を決める敵対者が忘却型の場合
敵対者の方策はプレイヤーの選択$ i(t)の影響を受けない
擬リグレットの最悪ケースの評価は、任意の報酬列に対する期待リグレットの最悪ケースの評価と同じになる
takkii.icon前述の、どちらをはじめに引くかでその後の報酬を変えるようなことはしてこないので
https://gyazo.com/089a8b77963d6bab7bee872e379b4463
記号の説明
https://gyazo.com/2f1858de78ed951a5cbfd08e7c3b580d
https://gyazo.com/73de9e60417c04d9e06d10efe4a6a519
ここまで
敵対的バンディットと
擬リグレットというものについて知りました
ここから
色々なアルゴリズムについて知る
Hedgeアルゴリズム(5.2)
Exp3方策(5.3)
Exp3.P方策(5.4)
各アルゴリズムの擬リグレットの上界が定まることを知る
ただ擬リグレットの上界を知っても評価しづらい。
擬リグレット下界（＝どのような方策に対しても生じてしまう擬リグレット）と比較して考える(5.5)
Exp3を一般化した方策のINF方策を知る
INF方策に含まれる、 Poly INF方策を用いると擬リグレット上界と擬リグレット下界の幅を狭めることができることを知る(5.6)
で、どうすりゃええんやという気持ちになる
5.2 オンライン学習理論とHedgeアルゴリズム
1980年代。PAC学習、質問学習、オンライン学習が主。
多腕バンディット問題はオンライン学習の枠組みにおける、「エキスパートを利用した予測」問題の特殊ケースと見ることができる
https://gyazo.com/5d5f23891c10544a11be24baebcf1df1
「エキスパートを利用した予測」の流れ
各時刻$ tに学習者は$ K人のエキスパートから1人のエキスパート$ i(t)を選ぶ
takkii.iconこの選び方について色々な研究がされていたようだ
学習者は自分が選んだエキスパート$ i(t)と同じ報酬$ X_{i(t)}(t)を得る
選ばなかった各エキスパート$ jの報酬$ X_j(t)が明かされる
takkii.icon多腕バンディットでは明かされれない
takkii.icon報酬が明かされる例としては、競馬や複数の天気予報士とかかな
これの繰り返し
上記について、最悪ケースにおいて
「学習者の累積報酬」と「最も報酬の多いエキスパートの累積報酬」との差
を小さくする学習者の方策について研究がされていた。
Hedgeアルゴリズム
「エキスパートを利用した予測」において注目すべきアルゴリズムの1つ
https://gyazo.com/ff3102979b0de7ccda7d7c2e7e45a2b7
はじめに各エキスパートの重みを$ 1/Kで初期化する
各エキスパートの重みを、重みの総和で割って、選ぶ確率にする
報酬が明かされる
各エキスパートの重みを更新する
$ w_{j,t+1} = w_{j,t}e^{\eta X_j(t)}
現在の重みに、$ e^{\eta X_j(t)}をかけている
例えば$ X_j(t)=1なら重みは$ e^{\eta}倍、$ X_j(t)=1なら$ 1倍になる（ただし報酬は0or1とは限らなそう）
重みが減ることはない
パラメータ $ \eta：学習レート。
値が大きいと、報酬によって大きく重みを更新する
上記を繰り返す
直接、ある時刻$ Tの各エキスパートの重みを求めることも可能
$ w_{j,t}=e^{\eta G_{j,t}}。累積報酬$ G_{j,t}($ t時点までのエキスパート$ jの累積報酬）
上記のアルゴリズムと同じ値にするなら$ 1/K（初期値）もかけるべきだが全てのエキスパートに同じ値をかけることになるので、エキスパートを選ぶ確率に影響を与えない
Hedgeアルゴリズムの特徴
takkii.iconどのエキスパートを選んでも、全ての報酬が明らかになる
takkii.iconどのエキスパートを選んだかは重みの更新に影響を与えない
takkii.iconどのエキスパートを選ぶかは確率的ではあるが、各時刻での重みは確率的でない
Hedgeの擬リグレットは上から抑えられる
https://gyazo.com/71136b2991408fa2a83abf95293d1081
解釈
$ \eta（学習レート）の調整でリグレットを抑えることができる
期待累積報酬が最大となるエキスパートの期待累積報酬 $ \overline{G}_*の上界$ gを知っていれば、以下の系5.2 より $ \etaを$ gに基づいて定めることで、期待リグレットを $ O(\sqrt{g \log{K}})に抑えることが可能
$ \overline{G}_*の明らかな上界は$ Tなので上のHedgeアルゴリズムの擬リグレットは$ O(\sqrt{T \log{K}})であることがわかる takkii.icon 事前に「$ \overline{G}_*の上界$ g」がわかることは他にあるのだろうか。過去の経験から推測するということだろうか
https://gyazo.com/7021208c57487940f8788f0bb1c2f833
証明
TODO
5.3 Exp3方策
報酬版Hedgeアルゴリズムのバンディット版がExp3方策
「エキスパートを利用した予測」との違い
自分が選んだアームの報酬しかプレイヤーが知ることができない(バンディット問題)
Hedgeでは累積報酬$ G_{j,t}を元に$ w_{j,t}=e^{\eta G_{j,t}}としていたが、Exp3ではわからない
https://gyazo.com/b9c84cdb043a12a0d3a7fe6bfc8c1a20
確率分布にしたがってアームを選ぶ
その確率分布がHedgeと異なる
https://gyazo.com/37a9521b53bd30a674e32107b4b0c294
重みを元に計算した確率を$ (1- \gamma)倍して減らし、一様分布$ \gamma / Kをプラスする
これは重みの比と一様分布を $ (1-\gamma) : \gammaの比で混ぜた分布を用いているということ
Exp3は引いたアームのみ重みが大きくなり、選ばなかったアームの選択確率は小さくなってしまう。そこで一様分布を加え小さくなりすぎるのを防ぐ
報酬$ X_{i(t)}(t)を得る
各アーム$ jの報酬の推定値$ \hat{X}_{j}(t)を下記のように計算する
https://gyazo.com/4dab0cf797e02d6df2a084292a8ee849
$ \hat{X}_j(t)は$ X_j(t)の不偏推定量 takkii.icon$ E(\hat{X}_j(t)) = p_{j,t} \times \frac{X_j(t)}{p_{j,t}} + (1-p_{j,t}) \times 0 = X_j(t)
takkii.icon不偏推定量になっていると、これを繰り返し行なっていれば報酬の推定値の合計もまた報酬の合計値になるから嬉しい、ということかな
各アーム$ jの重みを以下の式で更新する
$ w_{j,t+1}=w_{j,t}e^{\eta \hat{X}_{j}(t)}
選ばれたアームは重みが増える。選ばれなかったアームの重みは変わらない。確率分布を算出する際に微調整。
Exp3の擬リグレット上界は、Hedgeアルゴリズムと同様、最終的な重みの和を（推定）報酬との関係を用いて、
https://gyazo.com/c5881188d85605e848a979ce031a404e
証明
TODO
期待累積報酬$ \bar{G_*}の上界$ gがわかっていると下記のように$ \etaを最適化できる（takkii.icon$ \gammaも？）
系5.4から擬リグレットを$ O(\sqrt{TK\log{K}})であることがわかる
https://gyazo.com/a86e328a1cdd8d0cf0df8a2a9df05c45
5.4 Exp3.P方策
系5.4よりExp3方策で$ O(TK \log{K})の擬リグレットを達成する。
しかし$ \hat{X}_j(t)の分散は、二乗の平均から平均の二乗を引いて
$ \sigma^2 = \frac{1}{K}\sum_{j=1}^{K}{(\hat{X}_j(t))^2}- (E(\hat{X}_j(t)))^2 = (\frac{X_j(t)}{p_{j,t}})^2
リグレットは悪くなることが多い
Exp3.P方策だと、信頼区間の区間幅を$ O(\sqrt{T})にできると、$ \sqrt{T}のオーダーのリグレットを得ることができる
takkii.iconこの辺りからチルダかハットか見間違えやすいので注意
https://gyazo.com/f8d14e7899e6aafaab7cb042d5dd8ef3
Exp3方策を変更している
報酬の推定値と別に、「報酬の推定値の信頼区間の上限（信頼上界）」を用いている
赤枠
報酬の期待値に$ \frac{\beta}{p_{j,t}}を加える。
$ \betaは信頼性のパラメータ$ \deltaに依存して設定するパラメータ
与えられた$ \deltaに対して$ \betaをうまく設定すると、全てのアーム$ jに対し、$ 1-\deltaの確率で
$ G_j \leq \tilde{G}_j + \sqrt{TK\log{(K/\delta)}}
が成り立つ
takkii.icon例えば$ \delta=0.05にすれば、95％の確率で~以下になることを保証できる。
takkii.icon$ \deltaを小さくして確率を高めれば、その分右辺の$ \log{(K/\delta)}が大きくなり、範囲が広くなる。
これは次の補題により保証される。
https://gyazo.com/7d15c43af02720b93bda71238ea0f50f
擬リグレットではなく「リグレット」の上界を確率的に求めることができる
https://gyazo.com/bd21bf9dcc639199a7677685cfa295e5
証明
TODO
さらに、適切なパラメータを用いれば下記であることがわかる
https://gyazo.com/5be6c67dc5e3988398236f512f4638f1
証明
TODO
5.5 敵対的多腕バンディット問題のリグレット下界
パラメータをうまく定めたExp3方策の擬リグレット上界は$ O(\sqrt{TK\log{K}})であることがわかった（系5.4）
ではこの擬リグレットを達成する方策は良い方策なのか？どのように評価すべきか？
1つの方法として、擬リグレット下界（＝どのような方策に対しても生じてしまう擬リグレット）と比較する
この節では擬リグレット下界を求める
設定
敵対者が選ぶ報酬
$ \{0,1\}^{KT}上の以下の分布$ P_*を考える
takkii.iconこの表記は0 or 1がKT個存在しているということ？
まずK台のスロットのアームのうち、1つのアーム$ Jを無作為に選ぶ
その後、小さな値$ 0 < \epsilon \leq 1/2に対して、各時刻$ tごと独立に各アーム$ jの報酬$ X_j(t)を
ベルヌーイ分布$ \rm{Ber}(1/2 + \epsilon) $ (j = J)
ベルヌーイ分布$ \rm{Ber}(1/2) $ (j \neq J)
にしたがって発生させる
takkii.iconアーム$ Jは1が発生しやすく、それ以外は0と1が等しい確率
takkii.iconそのため最適なアームは$ Jになる。また敵対者はプレイヤーの方策を考慮に入れてないプレイをすることになりそう
https://gyazo.com/8577aea935e564b7d6afd2a4bab731d4
プレイヤー方策
敵対者が選んだアームが$ jの時の、$ P_*の分布を$ P_jとする
任意のプレイヤーAを固定
任意のプレイヤーがアーム$ jを選択する回数を$ N_jとする
報酬分布$ P_*の時のプレイヤーAの累積報酬$ G_Aについて考える
その期待値$ \mathbb{E}_{P_*}[G_A] は
$ T/2 + \epsilon \sum_{j=1}^{K} \mathbb{E}_{P_j}[N_j]/K
takkii.iconどのアームを選んでも報酬が出る確率は最低$ 1/2ある。それが$ T回あるので$ T/2。
takkii.icon敵対者がアーム$ jを選んだ時の報酬確率$ P_jを考える。その時プレイヤーがアーム$ jを選択する回数が$ N_j。その分だけ、$ \epsilon増える。敵対者が選んだアームが$ j=\{1...K\}それぞれの時について求め、それを$ Kで割って求めている
$ P_{\rm{unif}}は全てのアームが$ \rm{Ber}(1/2)の場合 （敵対者がアームを選ばなかった場合）
https://gyazo.com/cf5d3a9de5e25a215f4db3b21aa35a65
takkii.icon敵対者が選んだアーム（＝最も報酬の多いアーム）を引く回数の期待値の上界は、
全てのアームが$ \rm{Ber}(1/2)の時にアーム$ jを引く回数の期待値
$ Tと
$ \epsilonで表現できる
証明を読むために必要な定義
表記を簡単にするため新しい確率変数を用いる
$ Y_t = (i(t), X_{i(t)}(t))
takkii.icon時刻$ tに選んだアームと、その時の報酬
$ Y^t = (Y_1, Y_2, ..., Y_t)
takkii.iconそれらの時刻$ tまでのリスト
$ Y^tはプレイヤーが得られる情報全て
プレイヤーは$ Y^{T-1}（と乱数）だけに依存して$ i(t)を選択する
takkii.iconアームを確率的に選ぶ場合には乱数が入る
報酬分布$ P_*の時の$ Y_Tの分布を$ P_*(Y^T)で表す
定理5.9
https://gyazo.com/7c13aabcc7e2dce6021df26c2779772e
この式を元に、擬リグレット下界$ \Omega(\sqrt{KT})を導くことができる（系5.10）
系5.10
https://gyazo.com/8b575cde1f1d32aeda8fbb9055a49b43
擬リグレット下界$ \Omega(\sqrt{KT})を導くことができてうれしい
5.6 最適オーダーの方策
Exp3方策による擬リグレット上界$ O(\sqrt{TK\log K})（系5.4）
敵対的多腕バンディット問題に対する擬リグレット下界$ \Omega(\sqrt{KT})(系5.10)
表記法
https://gyazo.com/5156974f0d0be8a3523cbd94b0118b22
上界と下界は、オーダーで$ \sqrt{\log K}のギャップがある。
このギャップを埋める方策がINF方策
INF方策
前述のExp3方策を含む一般的な方策
用いる関数$ \psiがある式の時、Exp3方策と同じ
時刻$ tにおいてアーム$ iの選択確率$ p_{i,t}を下記のように表す
https://gyazo.com/adcf0bcaa7edb9ede9b967e67bbcf2c3
$ \hat{G}_{i,t} : アーム$ iにおける時刻$ t-1までの累積報酬推定値
$ \psi : 連続微分可能関数。下記の条件を満たす
https://gyazo.com/f0bc240f549f8da077149ed5119b886b
takkii.iconこんな感じの関数かな
https://gyazo.com/fb99a9eb810ebe7acc4a484d5795f1ed
takkii.icon関数$ \psi自体は正の値も取れると思うが、$ p_{i,t}において値として取ることはなさそう。
下記の(5.28)の条件より、$ C()の値の方が大きくなる
takkii.icon$ \psi' > 0は最大値に近い入力値ほど高い値を返してほしいためかな（累積報酬推定値が大きいほど確率$ pが大きくなってほしい）
takkii.icon$ \lim_{x \rightarrow -\infty} \psi < 1/Kはアームの腕の確率として$ 1/K未満が出力されないと初期値の全アーム$ 1/Kから学習が進まないからかな
takkii.icon$ \lim_{x \rightarrow 0} \psi(x) \geq 1はアームの確率として$ 1まで返してほしいからかな
$ C: 関数。$ [0,\infty)^Kを入力に、実数を返す。以下の条件を満たす連続微分可能関数。
https://gyazo.com/9348838fc762b7e939d07ace954ece8a
takkii.icon左の条件によって常に$ p_{i,t}の$ \psiの引数は負になる。
takkii.icon右の条件によって、例えば$ x_1,x_2,...,x_Kが等しい値の場合の時（より具体的にはゲーム開始時、各アームの累積報酬=0のとき）各アームの確率は$ 1/Kになる
https://gyazo.com/7385666603cafd11269fac7c2f129392
takkii.icon上記の$ p_{i,t}について、ある$ tの時の全アームを引く確率の合計が$ 1になっている必要があるため、かな
なお条件を満たす$ \psiに対して、$ Cが存在することが証明できる。
しかし閉形式で表現できるとは限らない
takkii.icon閉形式というのは
定数
一つの変数x
四則演算(+, -, ×, ÷)
n乗根
指数と対数(三角関数と逆関数も含む)
関数$ \psi として
https://gyazo.com/9c1eeb6e4e205c12c39ffa7ac1bd28e3
を用いたINF方策をPoly INF方策と呼ぶ。
パラメータ$ q,\eta, \gammaをうまく設定すると定理5.11のように$ O(\sqrt{KT})の擬リグレット上界を証明できる
ただ$ Cは一般の$ K,qに対して閉形式で表すことができない。
takkii.iconので定理5.11やアルゴリズム5.5などでは$ q=2と置いていることに注意
なお、$ \psiと$ Cをそれぞれ
https://gyazo.com/0e7027ca60eb32ae6ca9865c2234f391
https://gyazo.com/ff614bfe95ecf05ac30fccb145d8787c
とすることでExp3方策になる。
https://gyazo.com/9ab4dce446bd25f4b1aa100fcfc9d308
takkii.icon敵対的多腕バンディット問題に対する擬リグレット下界$ \Omega(\sqrt{KT})(系5.10)と合わせてみると、擬リグレットが敵対的バンディットのときにどの範囲に収まるかがわかる、かな
逐次的に進める場合
https://gyazo.com/0cd1b28bf613bd6b94d869ad056b97c3
takkii.iconExp3方策などにあった「重み$ w」はなくなった
その代わりに累積報酬の推定値と関数$ Cがある。
この関数は
入力として$ [0,\infty)を$ K個取る
出力は実数
連続
微分可能
https://gyazo.com/f74a6c79b004e904c368674bfd6cea22
takkii.icon関数の出力が、入力の最大値よりも大きく、入力の最大値にパラメータと腕の数に基づく値を加えたもの以下であること
https://gyazo.com/5d73fc64f8c5de8bad51d6c200638185
takkii.iconある時刻$ tの、全アームが引かれる確率の合計$ \sum_{i=1}^{K}p_{i,t}が$ 1になるための条件、かな
まとめ
この知見をどう活かせばいいのだ…？