強化学習1 -強化学習の基本，多腕バンディット-

強化学習1 強化学習の基本，多腕バンディット問題 公⽴⼩松⼤学 藤⽥ ⼀寿 Ver.20240320

強化学習の基本的な考え⽅

強化学習とは • 数値化された報酬信号を最⼤にするために，何をすべきか（どのようにして状 況に基づく動作選択を⾏うか）を学習する．（Sutton and Barto (三上，皆川 訳) 強化学習） • 答えは与えられていない． • 報酬という⼿掛かりがある． • 試⾏錯誤で探す． • 環境に働きかけることで情報を得る．

強化学習の要素 ⾏動(Action) エージェント (Agent) 環境 (environment) 状態(State) ⽅策(Policy) 報酬(Reward) エージェントは⽅策に従い⾏動し，報酬を受け取る．そして状態が変わる．

ハンターの例 どこに行けば獲物がたく さんとれるだろうか？ 森 池 草原 ハンター ハンターは獲物をとりたい． しかし，どこで獲物がよくとれるかわからない． どこにいっても，とれることもあるし，とれないこともある． ハンターは最も獲物をとれる確率が⾼いところを探したい．

ハンターの例 どこで獲物がよくとれる かわからないから色々な ところで狩りをしよう． 森 池 草原 ハンター ハンターはどこで獲物がよくとれるかわからない． 全く⼿がかりがないので，ハンターはそれぞれの場所に⾏って狩 りをしてみる．

ハンターの例 それぞれの場所で何度も 狩りをしてみると，森が 一番獲物を取ることがで きた．今後，森で狩りを しよう． 森 池 草原 ハンター ハンターはそれぞれの場所何度もに⾏って狩りをしてみる． 何度も狩りをしていると，獲物がとれる確率が⾼い場所がわかってくる． 獲物とれる確率が最も⾼い場所が分かれば，ハンターはそこにだけ狩りに ⾏けばよい．

ハンターの例のまとめ • 初めは，ハンターは，どこで獲物がよくとれるか分からない． • ハンターは⼿がかりを得るために，それぞれの場所で狩りをする． • それぞれの場所で何度か狩りをして，よく獲物がとれる場所を⾒つける．

ハンターの⾏動を強化学習と考えれば • ハンターが狩りをすることは⾏動とみなせる． • 狩場は環境とみなせる． • 獲物は報酬とみなせる． • 様々な場所で狩りをして獲物がとれるかどうか試すことを探索という． • 試した結果を使うことを利⽤という． ⾏動(Action) 森 池 草原 ⽅策 環境 報酬(Reward)

強化学習の⽬的は何か（ハンターの例から） • ハンターの⽬的は，よく獲物がとれる場所を知ること． • 最も報酬を得られる⽅策（⾏動）を知りたい． • 欲を⾔えば，よく獲物がとれる場所をなるべく早く探したい． • 最も報酬を得られる⽅策をなるべく早く探す． • もしくは，なるべく損をせずに，よく獲物がとれる場所を探したい． • ⾏動を通して得られる報酬の総和を最⼤化する（なるべく最適⾏動を取りたい）．

探索と知識利⽤のトレードオフ • ハンターは獲物がよくとれる狩場を探したいので，いろいろな場所で何度も狩 りを⾏いたい（探索したい）． • ⼀⽅で，探索する回数が少なければ少ないほどハンターは嬉しい． • ハンターは獲物がよくとれる場所で早く狩りをしたい． • しかし，少ない探索回数から得た知識から良い狩場を⾒つけたとしても，その狩場 より良い狩場があるかもしれない． • ハンターは，良い場所を探さがしたい気持ちと早く良い場所で狩りをしたい気 持ちの板挟みになっている．

探索と知識利⽤のトレードオフ • エージェントは，今現在，最も良さそうな選択肢を選びたい． • しかし，他の選択肢も探索しないと他に良い選択肢があるかどうかわからない． • 探索ばかりでは，いつまでたっても良い選択肢を選べない． • 過去の知識を利⽤し最も報酬の⾼い⾏動をとろうとすると探索が減ってしまい， あるかもしれない更に良い⾏動を⾒つけられない．⼀⽅で，更に良い⾏動を探 そうとすると探索しなければならず，過去の知識から得た最も報酬の⾼い⾏動 を取れない． • これを，探索と知識利⽤のトレードオフという．

不確かなときは楽観的に • 探索しなければ正確に報酬を得られる確率を獲得できないが，正確に知るため には何回も探索しなければならない．（探索と利⽤のトレードオフ） • 「不確かなときは楽観的に」という考え⽅で探索と利⽤のトレードオフを回避 する． • 「不確かなときは楽観的に」とは • エージェントが⾒積もっている報酬が得られる期待（報酬の期待値）が真の期待値 より低いと探索されることが少なく修正されにくい． • ⾒積もりが真の期待値より⾼いと探索され，修正されることで⾒積もりが真の期待 値に近づく． • つまり，「どの⾏動をとっても報酬を得られるだろう」という楽観的な考え⽅によ り，探索が促され，期待報酬が修正される．

不確かなときは楽観的に： 悲観ハンターの場合1 森 期待値0 何処に行っても獲物は取 れないだろう． 池 期待値0 草原 期待値0 ハンターはどの狩場でも獲物は取れないと悲観的に思っている． ハンター

不確かなときは楽観的に： 悲観ハンターの場合2 森 期待値0 池に行ったら獲物が取れた．池は 良い狩場だ． 池 期待値1 草原 期待値0 ハンター たまたま池で獲物が取れるとハンターは池が良い狩場だと思い，他に あるもっと良い狩場を試さなくなる．他の狩場を試さないので，他の 場所の期待値が修正されない．

不確かなときは楽観的に： 楽観ハンターの場合1 森 期待値0.8 何処に行っても獲物は取 れるだろう． 池 期待値0.8 草原 期待値0.8 ハンターはどの狩場でも獲物は取れると楽観的に思っている． ハンター

不確かなときは楽観的に： 楽観ハンターの場合2 森 期待値0.8 池に行ったら獲物が取れた．他の 狩場も良さそうだから次は森に行 こう． 池 期待値1 草原 期待値0.8 ハンター たまたま池で獲物が取れたとしても，他の狩場も獲物が取れると思っ ているので他の狩場も試す．試す機会があるため，期待値が修正され る．

Multi armed bandit problem 多腕バンディット問題

Multi armed Bandit(MAB)問題 • 最も当たりを出す（最も期待値が⾼い）スロットマシンを探す問題 • 最もシンプルな強化学習の問題 当たる確率：0.3 どれを選べばよい のだろうか． 困った． 当たる確率：0.7 当たる確率：0.1 当たる確率：0.8 なぜmulti armed banditと呼ばれるのか？ Banditとは直訳すると盗賊の意味である．スロットマシ ンが⼈からお⾦を奪っていく様⼦を盗賊と⾔い表してい る．カジノでは1本の腕をスロットマシンがたくさん並 んでいるが，それをたくさんの腕を持った盗賊(multi armed bandit)と⽐喩している．

MAB問題は何が問題なのか • エージェントは事前にスロットマシンが当たる確率を知らない． • エージェントが当たる確率を知るためには実際に試すしかない． • 最も当たる確率が⾼いスロットマシンを早く⾒つけたい． • 探す過程での報酬を⾼くしたい． • なるべく損したくない． 当たる確率：0.3 当たる確率：0.7 当たる確率：0.1 当たる確率：0.8

MABでの⽂字の定義 • 𝑎(𝑡)：⾏動 • 𝑅(𝑡)：報酬 • 𝑄! (𝑎)：⾏動𝑎をしたときの平均報酬 • MABでは⾏動はスロットマシンを選ぶことなので，状態は⾏動は⼀体となり， 状態は考えない． 平均報酬 𝑄! (𝑎) を参考に スロットマシン𝑎(𝑡)を選ぶ スロットマシン𝑎の平均 報酬 𝑄! (𝑎)を覚えておく 報酬 𝑅(𝑡)を得る

MAB問題を解く代表的なアルゴリズム • greedyアルゴリズム • greedy（貪欲）に腕を選ぶ． • これまでの経験から最も報酬を得られる可能性が⾼い⾏動をする． • ε-greedyアルゴリズム • これまでの経験から最も報酬を得られる可能性が⾼い⾏動をするが，たまに違う腕 を選ぶ． • UCB1アルゴリズム • これまでの経験から最も報酬を得られる可能性が⾼い⾏動をするが，あまり選んで いない腕も優先して選ぶ．

greedy algorithm • まだ𝑛回選んだことがない腕がある場合，それを選ぶ． • それ以外の場合，すべての腕に対しこれまでの報酬の平均𝑄! 𝑎 を計算する． • 𝑄! 𝑎 が最⼤の腕を選ぶ． • 本当はあまり当たらない腕だが運良く当たりが多く出た場合，あまり当たらな い腕ばかり選んでしまう可能性がある．その逆もありうる．

greedyアルゴリズムは間違った選択をするかもしれない 腕1 当たる確率：0.3 腕2 当たる確率：0.7 腕1の⽅が当 たりそうだ ステップ 報酬 腕1 腕2 1 1 1 2 1 0 3 1 4 0 5 0 6 0 7 0 8 たまたま当たりが続いた たまたま当たっ たため，間違っ た選択をする． 腕1の情報が増える 1 腕1はハズレ のようだ．腕 2の⽅が良い かも

𝜺-greedy algorithm • まだ選んだことがない腕がある場合，その腕から⼀つ選ぶ． • εの確率ですべての腕からランダムに⼀つ選ぶ． • 1-εの確率で最も平均報酬𝑄! (𝑎)が⾼い腕を選択する． • ⼗分試⾏を繰り返せば最も当たる腕を探せる． • ⼀定の確率でランダムに⾏動を選択してしまうので，⼗分探索したあとでも最 も当たる腕を選び続けることができない．

UCB1 • まだ選んだことがない腕がある場合，その腕から⼀つ選ぶ． • 𝑈 = 𝑄! 𝑎 + 𝑐 "# ! $! % が⾼い腕を選択する．𝑡はステップ数，𝑁! 𝑎 は腕𝑎を選ん だ回数である． • 𝑄! 𝑎 が平均報酬が最も⾼い腕を選ばせようとし， "# ! $! % があまり選ばれてい ない腕を選ばせようとする． • 𝑁! 𝑎 が⼤きくなると "# ! $! % は⼩さくなる（ ln 𝑡 は対数なのであまり増加しな い）．つまり，それぞれの腕がそれなりに選ばれれば，平均報酬が最も⾼い腕 を選ぶことになる．

シミュレーション結果 • Greedyアルゴリズムはたまたま悪いスロットマシンを選びたまたま報酬が得 られてしまったため，最適な⾏動ができず報酬が低い． • UCB1もε-greedyアルゴリズムも報酬が⾼いが， ε-greedyアルゴリズムはラ ンダムに⾏動するため悪い⾏動もせざるを得ず平均報酬はUCB1に負ける． (牧野ら，これからの強化学習)

Thompson sampling

Thompson sampling • 𝐾個の腕があるとする．エージェントは腕𝑘 ∈ 1, … , 𝐾 を選ぶと，𝜃& ∈ 0, 1 の 確率で報酬が得られる．報酬は𝑟 ∈ {0,1}である．𝑟 = 1の時，報酬が得られた とする． • 腕𝑘から得られる報酬の期待値は𝜃& である． • 𝜃& はエージェントは知らず，時間変化もしない． • ⽬的は，報酬を得る回数を最⼤化することである．

Thompson sampling • 最初の試⾏で腕𝑥" を選んだときに報酬を得る確率は，𝑝 𝑟" = 1 𝑥" 𝑁回繰り返す． = 𝜃#! である．この試⾏を • エージェントは各𝜃$ に対する独⽴した事前信念を持っている状態から試⾏を開始するとする． • 開始するこれらの事前信念はパラメータ𝛼 = 𝛼" , … , 𝛼% および𝛽 = であるとする．共役特性があるため，ベータ分布を使⽤する． 𝛽" , … , 𝛽% のベータ分布 • よって，各腕𝑘について𝜃$ の事前信念は次のようなる． &('" +(" ) '" & (" • 𝑝$ 𝜃$ ∣ 𝛼$ , 𝛽$ = & ' )" 𝜃$ " 1 − 𝜃$ (" )" • 観測値が収集されると，分布はベイズ規則に従って更新される．各腕の事後信念も，単純なパ ラメータに従って更新できるベータ分布となる． • 𝛼$ , 𝛽$ ← 2 𝛼$ , 𝛽$ 𝑖𝑓 𝑥$ ≠ 𝑘 𝛼$ , 𝛽$ + 𝑟* , 1 − 𝑟* 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

更新式の導出 当たる確率が 𝜃 の腕があり，𝑁回の試⾏のうち報酬を得られた回数（ 𝑟 = 1 ）が𝑛，得られなかった回数（ 𝑟 = 0 ）が𝑁 − 𝑛だ とする．この事象が起こる確率は次のような⼆項分布で書ける． 𝑁 # 𝑝 𝑛, 𝑁 − 𝑛 𝜃 = 𝜃 1 − 𝜃 $%# 𝑛 これを尤度と⾒なすと，事後信念𝑝 𝜃 𝑛, 𝑁 − 𝑛, 𝛼, 𝛽 はベイズ定理から次のように書ける． Γ(𝛼+𝛽) &%' 𝑁 # 𝑝 𝜃 𝑛, 𝑁 − 𝑛, 𝛼, 𝛽 ∝ 𝑝 𝑛, 𝑁 − 𝑛 𝜃 𝑝 𝜃 𝛼, 𝛽 = 𝜃 1 − 𝜃 $%# 𝜃 1 − 𝜃 (%' 𝑛 Γ 𝛼 Γ 𝛽 𝑁 Γ(𝛼+𝛽) &)#%' = 𝜃 1 − 𝜃 ()$%#%' 𝑛 Γ 𝛼 Γ 𝛽 よって 𝑝 𝜃 𝑛, 𝑁 − 𝑛, 𝛼, 𝛽 = 𝐶𝜃 &)#%' 1 − 𝜃 ()$%#%' ここで𝐶は規格化定数である．つまり，事後信念はパラメータが 𝛼 + 𝑛と𝛽 + 𝑁 − 𝑛のベータ分布となる．⾯⽩いことに，パ ラメータ𝛼には報酬が得られた回数𝑛が加えられ，パラメータ𝛽には報酬が得られなかった回数𝑁 − 𝑛が加えられている． 𝑁 = 1でエージェントが報酬𝑟を受け取ったとすると，𝑛 = 𝑟，𝑁 − 𝑛 = 1 − 𝑟と書ける．以上から，次のベータ分布のパラメ ータの更新式が得られる． 𝛼, 𝛽 ← 𝛼, 𝛽 + 𝑟, 1 − 𝑟 また，事後信念の平均は 𝛼+𝑛 𝜃4 = 𝛼+𝛽+𝑁 となる． 𝛼と𝛽の初期値を⼩さな値にした場合，𝑁が⼗分⼤きければ 𝛼 → 𝑛，𝛼 + 𝛽 → 𝑁となり平均は報酬を得られる確率と なる．

Thompson sampling • エージェントは試⾏を繰り返し，先のスライドの更新式を⽤い，報酬がえられ るかどうかの各腕の信念を更新していく． • エージェントは各試⾏でどの腕を選べばよいのか． • Greedyに選ぶのであれば，報酬を得られる確率と⾒なせる𝜃:& = '+ '+ ()+ が最⼤の 腕を選べば良い． • ⼀⽅，信念 𝑝& 𝜃& ∣ 𝛼& , 𝛽& から報酬を得られる確率𝜃& をサンプリングし， 𝜃& が最⼤の腕を選ぶ⽅法もある．この⽅法をThompson samplingと呼ぶ．

多腕バンディット問題もう少 し詳細に考える

K-armed bandit problem • 𝑘個スロットマシンがあるとする． • つまり，どのスロットマシンを選ぶかという選択肢（⾏動）が𝑘種類ある． • 𝑘-armed bandit problemでは𝑘個の⾏動のそれぞれが，その⾏動が選択された 場合に期待される報酬または平均報酬を持つ． • これを⾏動の価値と呼ぶ． • タイムステップ𝑡で選択されたアクションを𝐴! として表し，対応する報酬を𝑅! として表す． • 任意の⾏動𝑎の価値𝑞∗ (𝑎)は，𝑎が選んだときに期待される報酬である． • 𝑞∗ 𝑎 =̇ 𝐸[𝑅! ∣ 𝐴! = 𝑎]

推定価値とサンプル平均法 • 各⾏動の価値がわかっていれば，k-armed Bandit 問題を解決するのは簡単である． • 常に最⾼の価値を持つ⾏動を選択すれば良い． • しかし，実際は価値の推定値はあるかもしれないが，⾏動の価値を確実に知ることはできない だろう． • タイムステップ𝑡における⾏動𝑎の推定価値を𝑄* 𝑎 とする． • 我々は𝑄! 𝑎 が𝑞∗ a に近いことを望む． • ⾏動価値を推定する⾃然な⽅法の1つは，実際に受け取った報酬を平均することである． • 𝑄* 𝑎 =̇ *以前に⾏動,をとったときに得られた報酬の合計 *以前に⾏動,をとった回数 = ∑+* .* ⋅", -. * + ∑* ", -. * • 1#! $% は𝐴& = 𝑎のとき1それ以外のとき0となる． • 分⺟が0の場合，𝑄* 𝑎 = 0 のように 𝑄* 𝑎 をあるデフォルト値にする． • 分⺟が無限⼤になると，⼤数の法則により𝑄* 𝑎 は𝑞∗ 𝑎 に収束する． • これは報酬のサンプルの平均であるため，サンプル平均法と呼ぶ．

Greedyな⾏動と𝜀 ‒greedy method • 最も単純な⾏動選択ルールは，推定価値が最も⾼い⾏動のうち⼀つを選ぶことである． • この⾏動をgreedyな⾏動と⾔う．数式で次のように表現する． • 𝐴* =̇ arg max 𝑄* 𝑎 , • 複数のgreedyな⾏動がある場合は，その中から任意の⽅法 （おそらくランダム）で⼀つ選ばれ る． • greedyな⾏動の選択は常に現在の知識を活⽤して⽬先の報酬を最⼤化する． • 明らかに劣っている⾏動をサンプリングして，現在のgreedyな⾏動が本当に優れているかどうか を確認することはしない（知識を利⽤するだけで，探索はしない）． • 簡単な代替⼿法は，ほとんどの場合はgreedyな⾏動を選ぶが，時々，たとえば⼩さな確率 𝜀 で， ⾏動価値の推定値とは関係なく，すべての⾏動の中から同じ確率でランダムに選択することで ある． • これを𝜀 ‒greedy methodと呼ぶ． • この⽅法の利点は，反復を無限回繰り返せば，すべての⾏動が無限回サンプリングされ，すべて の𝑄! 𝑎 が𝑞∗ 𝑎 に確実に収束する点である．

平均報酬 • ⾏動が１種類しかない場合，𝑛ステップ⽬の⾏動に使う平均報酬は次のように 書ける． • 𝑄+ = ,1(,2(⋯(,341 +./ • 𝑛 + 1ステップ⽬では ' '+) '+) 𝑅) + 𝑅* + ⋯ + 𝑅' 1 1 1 𝑛−1 𝑄'() = = . 𝑅& = 𝑅' + . 𝑅& = 𝑅' + . 𝑅& 𝑛 𝑛 𝑛 𝑛 𝑛−1 &$) &$) &$) 1 1 1 = 𝑅' + 𝑛 − 1 𝑄' = 𝑅' + 𝑛𝑄' − 𝑄' = 𝑄' + 𝑅' − 𝑄' 𝑛 𝑛 𝑛 • 平均報酬を報酬の推定値だとすると，この式は 新しい推定値 ← 古い推定値 + ステップサイズ 得られた報酬 − 古い推定値 • と⾒なせる．

単純なバンディットアルゴリズム • 先の式を使うIncremental Implementationによる多腕バンディット問題を解く 単純なアルゴリズムは次のようになる． • 腕は𝑘本ある．それぞれの腕に対し平均報酬𝑄 𝑎 と選んだ回数𝑁(𝑎)がある．⾏ 動を𝐴とする． Initialize, for 𝑎 = 1 𝑡𝑜 𝑘: 𝑄 𝑎 ←0 𝑁 𝑎 ←0 Loop forever: arg max 𝑄 𝑎 with probability 1 − 𝜀 % 𝐴←7 a random action with probabiliry 𝜀 𝑅 ← 𝑏𝑎𝑛𝑑𝑖𝑡 𝐴 𝑁 𝐴 ←𝑁 𝐴 +1 ) 𝑄(𝐴) ← 𝑄(𝐴) + , # 𝑅 − 𝑄 𝐴 (breaking ties randomly) 1 − 𝜀の確率で𝑄(𝑎)が最⼤の⾏動 を取る．同じ価値の⾏動がある 場合はランダムに選ぶ．

⾮定常な問題のときの報酬の期待値 • これまでに説明した平均化⽅法は定常的なバンディット問題，つまり報酬確率が時 間の経過とともに変化しないバンディット問題に適している． • ⾮定常である場合，過去の報酬よりも最近の報酬を重視するのが合理的である．こ れを⾏う最も⼀般的な⽅法の1つはconstant step-size parameterを使⽤である． • たとえば， 先の平均価値の逐次更新式から次の式が得られる． • 𝑄678 = 𝑄6 + 𝛼 𝑅6 − 𝑄6 • 𝛼はステップサイズパラメタで０から１の値を取る． • さらに式変形すると次のようになる． 𝑄'() = 𝑄' + 𝛼 𝑅' − 𝑄' = 𝛼𝑅' + 1 − 𝛼 𝑄' = 𝛼𝑅' + 1 − 𝛼 𝛼𝑅'+) + 1 − 𝛼 𝑄'+) = 𝛼𝑅' + 1 − 𝛼 𝛼𝑅'+) + 1 − 𝛼 * 𝑄'+) = 𝛼𝑅' + 1 − 𝛼 𝛼𝑅'+) + 1 − 𝛼 * 𝛼𝑅'+* + ⋯ + 1 − 𝛼 '+) 𝛼𝑅'+) + 1 − 𝛼 ' 𝑄) ' = 1 − 𝛼 ' 𝑄) + . 𝛼 1 − 𝛼 &$) '+& 𝑅&

⾮定常な問題のときの報酬の期待値 • 𝑄+(/ = 1 − 𝛼 + 𝑄/ + ∑+01/ 𝛼 1 − 𝛼 +.0 𝑅 0 • 𝑄678は𝑄8と過去の報酬の加重平均である． • この式は，過去に得た報酬の情報ほど使われない． • 過去に得た報酬 𝑅9 は 1 − 𝛼 6:9 がかけてある． • 1 − 𝛼 は1より⼩さいため， 𝑖が⼩さければ⼩さいほど（過去ほど） 1 − 𝛼 さくなる． 6:9 が⼩ • つまり，より古い 𝑅9 はあまり使われなくなる． • 新しい報酬を古い報酬より使うため，⾮定常な場合でも対応可能だろう．

楽観的な⾏動 • 𝑛 + 1ステップでの報酬の期待値は𝑄+(/ = 1 − 𝛼 + 𝑄/ + ∑+01/ 𝛼 1 − 𝛼 ける． +.0 𝑅 と書 0 • 𝑄/ はエージェントがはじめに想定している期待値と⾒なせる． • つまり，この値が⼤きければ楽観的で低ければ悲観的に思っているといえる． 𝑄) = 5と⾒積もったgreedy アルゴリズムは，はじめに 楽観的に期待値を⾒積もる ことで素早く良い⾏動を探 し当てている．Greedyな⾏ 動をしているにも関わらず である． (Sutton, Reinforcement Leaning)

Gradient bandit algorithm • 各アクション𝑎の数値的な好み(preference)を𝐻/ 𝑎 を学習することを検討してみる． • Preference 𝐻/ 𝑎 が⼤きい⾏動が実⾏される頻度は⾼いが，報酬の視点からpreferenceを解釈できない． • ただ，ある⾏動が他の⾏動よりも相対的に優先されるということが重要である． • Preferenceを使った⾏動確率は，次のようなソフトマックス分布 (つまり、ギブス分布またはボルツマン分 布) に従って決定される． • Pr 𝐴/ = 𝑎 =̇ #$ 0" #% ∑( %&' 0" =̇ 𝜋/ 𝑎 • 確率的勾配上昇の考え⽅に基づいたsoft-max action preferencesの⾃然学習アルゴリズムがある． • 各ステップで，⾏動𝐴/ を選択し報酬𝑅/ を受け取った後，⾏動のpreferencesを次のように更新する． • 𝐻/)' 𝐴/ =̇ 𝐻/ 𝐴/ + 𝛼 𝑅/ − 𝑅/ 1 − 𝜋/ 𝐴/ • 𝐻/)' 𝑎 =̇ 𝐻/ 𝑎 − 𝛼 𝑅/ − 𝑅/ 𝜋 𝑎 for all 𝑎 ≠ 𝐴/ • ここで，𝛼 > 0はステップサイズパラメータ、 𝑅B/ ∈ ℝ は時刻𝑡までのすべての報酬の平均である(ただし，時 刻𝑡は含まない)． • 𝑅B/ 項は報酬を⽐較するベースラインとして機能する．報酬がベースラインより⾼い場合，𝐴/ を選ぶ確率は増 加し，報酬がベースラインを下回る場合，確率は減少する．

多腕バンディットにおける確率的勾配法 勾配法より，𝐻! 𝑎 の更新式は 𝜕𝐸[𝑅! ] 𝜕𝜋! 𝑥 = ; 𝑞∗ 𝑥 = ; 𝑞∗ 𝑥 𝜋 𝑥 1)+$ − 𝜋 𝑎 𝜕𝐻! 𝑎 𝜕𝐻! 𝑎 𝜕𝐸[𝑅! ] 𝐻!"# 𝑎 = 𝐻! 𝑎 + 𝛼 𝜕𝐻! 𝑎 であ．𝑎は⾏動を表す変数である（つまり，すべての⾏動に対し，この更 新式は適⽤される）．⽬的関数(performance)は 𝐸 𝑅! = ; 𝜋! 𝑥 𝑞∗ 𝑥 $ とする．⽬的関数は時刻𝑡のときの報酬の期待値である． 𝜕𝐸[𝑅! ] 𝜕 𝜕𝜋! 𝑥 ＝ ; 𝜋! 𝑥 𝑞∗ 𝑥 = ; 𝑞∗ 𝑥 𝜕𝐻! 𝑎 𝜕𝐻! 𝑎 𝜕𝐻! 𝑎 $ $ & $ 𝑒! ∑(' 𝑒!& ' 𝜕𝜋! 𝑥 𝜕 = 𝜕𝐻! 𝑎 𝜕𝐻! 𝑎 𝑥 = 𝑎の時 𝜕 𝜕𝐻! 𝑎 & $ 𝑒! ∑(' 𝑒!& ∑(' 𝑒!& & $ = 𝑒! ∑(' 𝑒!& = ' ' ' 𝑒!& $ ∑(' 𝑒!& ' − 𝑒!& ∑(' 𝑒!& ' $ 𝑒!& * ∑(' 𝑒!& ' =𝜋 𝑥 1−𝜋 𝑎 * = ; 𝑞∗ 𝑥 − 𝐵! 𝜋 𝑥 1)+$ − 𝜋 𝑎 $ ここで，ベースライン𝐵! を導⼊した．更新は時刻𝑡の時，⾏動𝐴! を選択 したときに⾏われるから，確率変数𝑥は𝐴! である． 𝜕𝐸[𝑅! ] = ; 𝑞∗ 𝐴! − 𝐵! 𝜋 𝐴! 1)+,$ − 𝜋 𝑎 𝜕𝐻! 𝑎 ,$ = 𝐸- よって & $ ∑(' 𝑒!& ' = 1)+,$ − 𝜋 𝑎 −𝑒! & ) 𝑒! ∑(' 𝑒!& ' * = −𝜋 𝑥 𝜋 𝑎 𝜕𝜋! 𝑥 = 𝜋 𝑥 1)+$ − 𝜋 𝑎 𝜕𝐻! 𝑎 $ 𝐸- ,$ 𝑅! − 𝑅F 1)+,$ − 𝜋 𝑎 を求めるのは難しいし，これまで⾏って きた取得したサンプルに⽐例させた更新⼿法を⽤いたいので (𝑅! − 𝑅F ) 1)+,$ − 𝜋 𝑎 で置き換えると． 𝐻!"# 𝑎 = 𝐻! 𝑎 + 𝛼 𝑅! − 𝑅F & $ 𝑒! ,$ 𝑞∗ 𝐴! − 𝐵! = 𝐸- ,$ 𝑅! − 𝑅F 1)+,$ − 𝜋 𝑎 F 𝐵 = 𝑅とする． 𝑞∗ 𝐴! は⾏動𝐴! の価値なので𝑞∗ 𝐴! = 𝐸 𝑅! ∣ 𝐴! である． このことから 𝑞∗ 𝐴! を𝑅! に置き換えるする． 得られた⽬的関数の微分を⽤いると次の更新式が得られる． 𝐻!"# 𝑎 = 𝐻! 𝑎 + 𝛼𝐸- , 𝑅! − 𝑅F 1)+, − 𝜋 𝑎 𝑥 ≠ 𝑎の時 𝜕 𝜕𝐻! 𝑎 $ $ & ) − 𝑒! ) $ 1!"# は 𝑎 = 𝑥のとき1となり， それ以外の場合は０となる． 1)+,$ − 𝜋 𝑎

式展開 ; 𝑞∗ 𝑥 − 𝐵! 𝜋 𝑥 1)+$ − 𝜋 𝑎 $ = ; 𝑞∗ 𝑥 𝜋 𝑥 1)+$ − 𝜋 𝑎 $ = ; 𝑞∗ 𝑥 𝜋 𝑥 1)+$ − 𝜋 𝑎 $ − 𝐵! ; 𝜋 𝑥 1)+$ − 𝜋 𝑎 ;𝜋 𝑥 = 1 $ $ ;𝜋 𝑥 − 1 = 0 −𝐵 −;𝜋 𝑥 𝜋 𝑎 +𝜋 𝑎 1−𝜋 𝑎 $ $.) ;𝜋 𝑥 +𝜋 𝑎 −1=0 = ; 𝑞∗ 𝑥 𝜋 𝑥 1)+$ − 𝜋 𝑎 − 𝐵! 𝜋 𝑎 $ = ; 𝑞∗ 𝑥 𝜋 𝑥 1)+$ − 𝜋 𝑎 $ = ; 𝑞∗ 𝑥 𝜋 𝑥 1)+$ − 𝜋 𝑎 $ −;𝜋 𝑥 + 1−𝜋 𝑎 $.) − 𝐵! 𝜋 𝑎 − 1−𝜋 𝑎 + 1−𝜋 𝑎 $.)

MAB問題の応⽤事例

MAB問題の応⽤ • 配置問題 • モンテカルロ⽊探索 • 深層強化学習 • AlphaZero

配置問題

配置問題 • ウェブサイトのどこに，ボタンをおけば最もクリックされるのか？ • スロットマシンは，それぞれのボタン配置に対応する． • 報酬は，クリックに対応する． • MABアルゴリズムを⽤いそれぞれのボタン配置を試しながら，最適な配置を 探す． どれが⼀番ク リックされる か？ ボタンを左上に配置したサイ ト ボタンを右上に配置したサイ ト ボタンを左下に配置したサイ ト ボタンを右下に配置したサイ ト

配置問題 • ウェブサイトのボタンの⾔葉をどれにすれば最もクリックされるか？ • スロットマシンは，それぞれのボタンに表⽰する⾔葉に対応する． • 報酬は，クリックに対応する． • MABアルゴリズムを⽤いそれぞれのボタン配置を試しながら，最適な配置を 探す． どれが⼀番寄 付してくれる か？ ボタンをどの⾔葉にすれば寄付が増えるだろうか？ 訪問者に⾒せる⾔葉をバンディットアルゴリズムで決めれば最も良い⽂⾔が⾒つかるかも． 参加 寄付を 共に戦う ご協⼒を

モンテカルロ⽊探索

モンテカルロ⽊探索とは • ゲーム⽊を探索するためアルゴリズム． • 囲碁AIのアルゴリズムとして有名． • 多腕バンディットが活⽤されている． • モンテカルロ⽊探索（Monte Carlo Tree Search: MCTS）

マルバツゲームを解く 選べる盤⾯ 現在の盤⾯ 選べる盤⾯を⾒ても勝てる かどうか分からない． どの⼿を選べば良いかな？

マルバツゲームを解く 選べる盤⾯ 勝ち 現在の盤⾯ どの⼿を選べば良いかな？ 選べる盤⾯を⾒ても勝て るかどうか分からない． 1⼿先を考えてみ るか． 1⼿読んでみると，1番上の 盤⾯に勝ち⽬があることが 分かる．

マルバツゲームのゲーム⽊の例 現在の状態 マルが選べる盤⾯ バツが選べる盤 ⾯ 起こりうる盤⾯の⼀覧．起こりうる盤⾯を⽊構造で書いたものをゲーム⽊という．

モンテカルロ⽊探索のアルゴリズム • モンテカルロ⽊探索は先程のゲーム⽊を探索するアルゴリズムである． • ゲーム⽊を構成するノードは次の変数を持つ． • 平均報酬，訪問回数，盤⾯ • モンテカルロ⽊探索は次の4つの処理で構成される． • Selection: • Expansion • Simulation • Backpropagation (Browne et al., 2012)

モンテカルロ⽊探索のアルゴリズム • Selection: • ランダム，greedy，ε-greedy，UCB1などのバンディットアルゴリズムを⽤い⼦ ノードを選ぶ． • Greedyアルゴリズムなら，平均報酬が最も⼤きいノードを選ぶ． • 葉ノードまで続ける． • Expansion • N回葉ノードを訪れたら，その葉ノードを展開する． (Browne et al., 2012)

モンテカルロ⽊探索のアルゴリズム • Simulation • 葉ノードから終局までランダムに⼿を選ぶ． • Backpropagation • 勝敗の結果を報酬として親ノードに伝える．それをルートノードまで繰り返す． • selectをルートノードからやり直す． • T回，Selection，Expansion，Simulation，Backupを⾏った後，ルートノード の⼦ノードのうち最も選んだ回数が多かった⼦ノードの⼿を打つ． (Browne et al., 2012)

モンテカルロ⽊探索の例 現在の状態 起こりうる盤⾯を列挙し，⽊に追加する．

モンテカルロ⽊探索の例 現在の状態 選んだ マルが選べる盤⾯ 平均報酬：𝑄(𝑎) = 0 選ばれた回数：選ばれたので 𝑁 𝑎 =1 Selection: MABアルゴリズムで盤⾯を選ぶ．各盤⾯は平均報酬 と選ばれた数を保存している． Expantion: 選んだ盤⾯がN回選ばれていれば盤⾯を追加する． 今回は1度⽬なので追加しない．

モンテカルロ⽊探索の例 現在の状態 マルが選べる盤⾯ バツが選べる盤 ⾯ Simulation: 起こりうるランダム盤⾯をランダ ムに終局まで選び続ける．

モンテカルロ⽊探索の例 現在の状態 報酬の平均を更新 1 𝑄 𝑎 = =1 1 マルが選べる盤⾯ 勝った（報酬1） バツが選べる盤 ⾯ Backpropagation: 終局の結果を報酬として上 の盤⾯に送る．送られた報酬から報酬の平均 を更新する．

AlphaZero

モンテカルロ⽊探索の⽋点 • モンテカルロ⽊探索は探索回数が多ければ多いほど正確な結果を導ける． • しかし，⼿数が多いゲームでは，計算時間の制限から探索しきれないため正確 な結果を出せないかもしれない． • ゲーム⽊が幅広く深い場合は，探索空間が広く探索回数を増やさないと良い⾏動を 導けない． • 計算時間が制限されているため探索回数は限られている．その条件下でより正 確な結果を導く必要がある． • この問題を深層ニューラルネットワーク（DNN）で解決したのがAlphaZeroで ある．

⼈がマルバツゲームを解くとき 現在の盤⾯ 次の⼿ どうし よう この盤⾯なら相⼿が 悪い⼿を打てばマル が3つ並ぶから良い 盤⾯だ． 起こる可能性が ある盤⾯ 次の⼿を打った結果 起こる可能性が ある盤⾯ この盤⾯は必ず引き 分けになる． 勝つ可能性 がある⼿を 打とう！！

機械がマルバツゲームを解くには 可能性のあ る盤⾯を列 挙しよう． 現在の盤⾯ この盤⾯は5点 起こる可能性が ある盤⾯ 次の⼿を打った結果 この盤⾯は0点． 起こる可能性が ある盤⾯ 最も点が⾼ い盤⾯を選 ぶ．

機械がマルバツゲームを解くには • 機械は盤⾯を評価しなければならない • 盤⾯と評価の関係を学習しなければならない． • 回帰問題 • 機械は良い⼿（盤⾯）を選ばなければならない． • プレイしながら様々な盤⾯を評価する． • 強化学習（モンテカルロ⽊探索） 教師あり学習（回帰）＋強化学習（モンテカルロ⽊探索） ＝AlphaZero

AlphaZeroの概要 • 深層ニューラルネットワークとモンテカルロ⽊探索(MCTS)で構成構成され る． • 深層ニューラルネットワークは盤⾯から，出す⼿の確率と勝敗の結果を予 測する． • 盤⾯と勝敗の結果，盤⾯と出す⼿の確率の回帰問題を解く． • モンテカルロ⽊探索で出す⼿を決定する． 盤⾯𝑆* MCTS 盤⾯𝑆* ′ 出す⼿の確率𝑝(𝑆* 2 , 𝑎) 出す⼿𝑎(𝑆* ) 盤⾯の価値 𝑣(𝑆* 2 ) DNN

Deep neural networkの学習 • 学習データは，各盤⾯と最終的な勝ち負け，各盤⾯での出す⼿の確率を⽤いる． • 出す⼿の確率は各盤⾯において可能な次の⼿をモンテカルロ⽊探索が選んだ回 数から計算する． • 学習データはAlphaZero同⼠の対戦（⾃⼰対戦 ：self-play）の結果のみ⽤いる． • 事前に学習データを⽤意する必要はない．

AlphaZeroのニューラルネットワーク Input • 価値と⽅策を出⼒するネットワーク Conv, 3x3, 256 Batch norm • 価値は，⼊⼒された盤⾯で勝つ可能性を表す． ReLU • ⽅策は，⼊⼒された盤⾯で可能な⼿の選ぶ確率を表す． Batch norm Residual bloks • Policy headとvalue headからなるヘッド部とボディー部 で構成される． Conv, 3x3, 256 • Policy headが出す⼿の確率を出⼒する． ReLU body Conv, 3x3, 256 Batch norm ReLU • Value headの勝つ可能性を出⼒する． • AlphaZeroが先⼿が勝つと思っていれば１，負けると思って いるなら-1を出⼒する． • Body部はn個のresidual blocksで構成される． • ⼊⼒はk⼿分の盤⾯+現在のプレーヤ．盤⾯はプレーヤご とに⽤意する．それぞれ0，1で表される． Conv, 3x3, 256 Conv, 3x3, 256 Batch norm Batch norm ReLU ReLU full connect full connect ReLU softmax full connect tanh Value Policy head

AlphaZeroのモンテカルロ⽊探索 • Select: • 𝑄(𝑠, 𝑎) + 𝑈(𝑠, 𝑎)が最も⼤きい⼦ノードを選ぶ． • ⼦ノードが葉ノードでなければ，上に戻る．そうでなければ次へ． • Expand and evaluate • 葉ノードを展開し，次へ． • Backup • (推定した)結果を親ノードに 伝える．それをルートノードまで繰り返す． • selectをルートノードからやり直す． • N回上記の処理を⾏った後，ルートノードの⼦ノードのうち最も選んだ回数が多かった⼦ノー ドの⼿を打つ． (Silver et al., 2017)

モンテカルロ⽊探索との違い • AlphaZeroはモンテカルロ⽊探索の⼀種である． • モンテカルロ⽊探索との違いは，Simulationにおいて終局までゲーム⽊を探索 しない点である． • AlphaZeroは終局までゲーム⽊を探索しない代わりに，報酬を深層ニューラル ネットワークで計算する． • モンテカルロ⽊探索の場合，盤⾯から得られる報酬は終局での勝ち負けで算出 したが，AlphaZeroではvalue headの出⼒を報酬とする．