強化学習1

強化学習1 公⽴⼩松⼤学 藤⽥ ⼀寿 Ver.20230911

強化学習とは • 数値化された報酬信号を最⼤にするために，何をすべきか（どのよう にして状況に基づく動作選択を⾏うか）を学習する．（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に負ける． (牧野ら，これからの強化学習)

式をいじって⾊々考察してみ る

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

単純なバンディットアルゴリズム • 先の式を使うと，多腕バンディット問題を解く単純なアルゴリズムは次の ようになる． • 腕はk本ある．それぞれの腕に対し平均報酬𝑄 𝑎 と選んだ回数𝑁(𝑎)がある ．⾏動を𝐴とする． • まず，𝑎 = 1から𝑘までについて次のように初期化する． • 𝑄 𝑎 ← 0, 𝑁 𝑎 ← 0 • 次の処理をループさせる． • • • • 1 − 𝜀の確率で𝑄(𝑎)が最⼤の⾏動𝐴を取る． 𝜀の確率でランダムに⾏動を選ぶ．選ばれた⾏動は𝐴とする． 実際に⾏動し報酬𝑅を得る． 𝑁 𝐴 ←𝑁 𝐴 +1 • 𝑄 𝐴 ←𝑄 𝐴 + ' ( ) 𝑅−𝑄 𝐴

⾮定常な問題のときの報酬の期待値 • 先の平均報酬の式から，報酬の期待値が次のように求まるとする． • 𝑄&(+ = 𝑄& + 𝛼 𝑅& − 𝑄& • 𝛼はステップサイズパラメタで０から１の値を取る． • 𝑄&(+ を式変形すると次のようになる． 𝑄*+' = 𝑄* + 𝛼 𝑅* − 𝑄* = 𝛼𝑅* + 1 − 𝛼 𝑄* = 𝛼𝑅* + 1 − 𝛼 𝛼𝑅*,' + 1 − 𝛼 𝑄*,' = 𝛼𝑅* + 1 − 𝛼 𝛼𝑅*,' + 1 − 𝛼 -𝑄*,' = 𝛼𝑅* + 1 − 𝛼 𝛼𝑅*,' + 1 − 𝛼 -𝛼𝑅*,- + ⋯ + 1 − 𝛼 *,'𝛼𝑅*,' + 1 − 𝛼 * 𝑄' * = 1 − 𝛼 * 𝑄' + . 𝛼 1 − 𝛼 ./' *,. 𝑅 .

⾮定常な問題のときの報酬の期待値 • 𝑄&(+ = 𝑄+ + ∑&,-+ 𝛼 1 − 𝛼 &*, 𝑅 , • この式は，過去に得た報酬の情報ほど使われない． • 過去に得た報酬 𝑅! は 1 − 𝛼 "#! がかけてある． • 1 − 𝛼 は1より⼩さいため， 𝑖が⼩さければ⼩さいほど（過去ほど） 1 − 𝛼 "#! が⼩さくなる． • つまり，より古い 𝑅! はあまり使われなくなる． • 最近の情報をより使うため，状況が変化しても対応可能となる． • 過去の間違った⾏動を忘れるとも解釈できる．

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

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 盤⾯𝑆! ′ 出す⼿の確率𝑝(𝑆! ! , 𝑎) 出す⼿𝑎(𝑆! ) 盤⾯の価値 𝑣(𝑆! ! ) DNN

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

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