強化学習1

強化学習1 藤⽥ ⼀寿

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

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

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

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

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

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

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

強化学習の⽬的は何か（ハンターの例から） • ハンターの⽬的は，最もよく獲物がとれる場所をなるべく早く探しだ すこと． • 最も報酬（獲物）を得られる⾏動を決める最適な⽅策を探す． • もしくは，最も効率良く，よく獲物がとれる場所を探し出すこと． • ⾏動の選択を通して得られる報酬の総和を最⼤化する．

探索と利⽤のトレードオフ • ハンターはいろいろな場所で何度も狩りを⾏い，獲物がよくとれる場 所を探す必要がある． • ハンターとしては効率良く獲物がよくとれる場所を探したい． • 探索する回数が少なければ少ないほどハンターは嬉しい． • しかし，少ない探索回数から得た情報から良い狩場を⾒つけたとして も，その狩場より良い狩場があるかもしれない．

探索と利⽤のトレードオフ • 探索回数が多ければ多いほど正確に良い⾏動が⾒つかるが，良い⾏動 をする回数は減り，探索を通して得られる報酬は少ないかもしれない ． • ⼀⽅，少ない探索回数から得られた情報を利⽤し良い⾏動を⾒つけて も，もっと良い⾏動があるため得られる報酬は少ないかもしれない． • これを探索と利⽤のトレードオフという．

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

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

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

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である．

AlphaZeroの概要 • 深層ニューラルネットワークとモンテカルロ⽊探索(MCTS)で構成構成され る． • 深層ニューラルネットワークは盤⾯から，出す⼿の確率と勝敗の結果を推 定する． • モンテカルロ⽊探索で出す⼿を決定する． 盤⾯St 盤⾯Stʼ MCTS DNN 出す⼿の確率p(Stʼ, a) 出す⼿a(St) 盤⾯の価値 v(Stʼ)

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

AlphaZeroのニューラルネットワーク Input • 価値と⽅策を出⼒するネットワーク Conv, 3x3, 256 Batch norm • Policy headとvalue headからなるヘッド部とボ ディー部で構成される． • Value headの出⼒が推定した結果 Conv, 3x3, 256 Batch norm Residual bloks • Policy headの出⼒が出す⼿の確率 ReLU • player1が勝てば１，負ければ-1 • ボディー部は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: • Q(s,a)+U(s,a)が最も⼤きい⼦ノードを選ぶ． • ⼦ノードが葉ノードでなければ，上に戻る．そうでなければ次へ． • Expand and evaluate • 葉ノードを展開し，次へ． • Backup • (推定した)結果を親ノードに 伝える．それをルートノードまで繰り返す． • selectをルートノードからやり直す． • N回上記の処理を⾏った後，ルートノードの⼦ノードのうち最も選んだ回 数が多かった⼦ノードの⼿を打つ． (Silver et al., 2017)

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

⼀般的な強化学習

MABと⼀般的な強化学習 • MABでは⾏動はスロットマシンを選ぶことなので，状態は⾏動は⼀体 となり，状態は考えない． • ⼀般的には，⾏動と状態は同じではない． MAB 平均報酬 𝑄! (𝑎) を参考に スロットマシン𝑎(𝑡)を選ぶ ⼀般的な強化学習 エージェ ント (Agent) ⽅策 (Policy) 報酬 𝑅(𝑡)を得る ⾏動(Action) 環境 報酬(Reward) 状態(State)

強化学習の要素 • 状態が𝑁種類あるとすると状態集合は𝑆 = {𝑠+ , 𝑠. , … , 𝑠$ }と表せる． • 時刻𝑡のとき状態は𝑆$ とし，𝑆の要素のうちのいずれかである． • 状態𝑠のとき，取りうる⾏動が𝑀種類あるとすると⾏動集合𝐴(𝑠) = {𝑎+ , 𝑎. , … , 𝑎/ }と表せる． • 時刻𝑡における⾏動𝐴$ は𝐴(𝑆$ )の要素のうちいずれかの値をとる • 時刻𝑡において状態𝑆! で⾏動𝐴(𝑆! )をし，状態が𝑆!(+ に変わったとき，環 境から受け取る報酬を𝑅!(+ とする．

狩りの例を思い出す 𝐴(𝑠) = {池に⾏く，草原に⾏く，森に⾏く，帰る} 𝑆 = {池, 草原, 森, 家} 𝑅 = {狩り成功10，失敗 − 5}

全ては確率で決まる • 時刻𝑡のとき状態が𝑠′，報酬が𝑟であるとすると，これらは次の確率で 決まる． • 𝑝 𝑠 0 , 𝑟 𝑠, 𝑎 = Pr{𝑆! = 𝑠 0 , 𝑅! = 𝑟 ∣ 𝑆!*+ = 𝑠, 𝐴!*+ = 𝑎} • これは以前の状態が𝑠′，その時とった⾏動が𝑎であるという条件のもと での 𝑠′， 𝑟の確率である． • 状態𝑠で⾏動𝑎を⾏ったとき，状態𝑠′ が起こる確率は，先の確率を報酬𝑟 で周辺化すれば良い． • 𝑝 𝑠 0 𝑠, 𝑎 = Pr 𝑆! = 𝑠 0 𝑆!*+ = 𝑠, 𝐴!*+ = 𝑎 = ∑1∈3 𝑝(𝑠 0 , 𝑟 ∣ 𝑠, 𝑎)

報酬の期待値 • 報酬の期待値（期待報酬）は状態と⾏動で決まるため，𝑠と𝑎の変数で ある． • 𝑟 𝑠, 𝑎 = 𝐸 𝑅! 𝑆!*+ = 𝑠, 𝐴!*+ = 𝑎 = ∑1∈3 𝑟 𝑝 𝑟 𝑠, 𝑎 = ∑1∈3 𝑟 ∑40 ∈5 𝑝 𝑠 0 , 𝑟 𝑠, 𝑎 周辺化 • また，状態𝑠のとき⾏動𝑎とったとき，状態が𝑠′になり報酬𝑟をもらうた め，報酬は𝑠, 𝑎, 𝑠′の3変数の関数で表現できる． • 𝑟 𝑠, 𝑎, 𝑠′ = 𝐸 𝑅! 𝑆!*+ = 𝑠, 𝐴!*+ = 𝑎, 𝑆! = 𝑠′ = ∑1∈3 𝑟 𝑝 𝑟 𝑠, 𝑎, 𝑠′ = 6 𝑟, 𝑠 0 𝑠, 𝑎 ∑1∈3 𝑟 6 𝑠′ 𝑠, 𝑎 ベイズ定理

未来の報酬 • 単純に未来に得られるすべての報酬の期待値，期待報酬は次のように 書ける． • 𝐺! = 𝑅!(+ + 𝑅!(+ + 𝑅!(+ + ⋯ + 𝑅7 • 𝑇は最終時間ステップである． • これは単純に同じ重みで未来のすべての報酬を⾜している．

割引報酬 • 未来になればなるほど予測は外れると考えると，遠い未来の報酬と近 い未来の報酬が同じ重みで⾜されるのではなく，遠い未来の報酬は少 なめに⾜したほうが良いだろう． • そこで，未来の報酬を割り引いた割引報酬を使う． 9 • 𝐺! = 𝑅!(+ + 𝛾𝑅!(. + 𝛾 . 𝑅!(8 + ⋯ = ∑; 9-: 𝛾 𝑅!(9(+ = 𝑅!(+ + 𝛾𝐺!(+ • 𝛾を割引率といい，0から1の間の値を取る．

価値関数 • エージェントはそもそも何が⽬的だろうか？ • 未来の報酬を最⼤化することが最⼤の⽬的だろう． • つまり，未来の報酬を最⼤化する状態にしたいとエージェントは考え る． • 状態𝑠で得られる割引報酬の期待値を価値関数といい次のように書く． 9 • 𝑣< 𝑠 = 𝐸< 𝐺! 𝑆! = 𝑠 = 𝐸< ∑; 9-: 𝛾 𝑅!(9(+ 𝑆! = 𝑠 • 𝜋は⽅策で，エージェントの⾏動のルールを表す．つまり，この価値 関数は⽅策 𝜋をとるエージェントが状態𝑠になったとき得られる割引報 酬の期待値である．

価値関数 𝑣% 𝑠 = 𝐸% 𝐺$ 𝑆$ = 𝑠 = 𝐸% 𝑅$ + 𝛾𝐺$&' 𝑆$ = 𝑠 = 𝐸% 𝑅$ 𝑆$ = 𝑠 + 𝛾𝐸% 𝐺$&' 𝑆$ = 𝑠 第1項は 𝐸% 𝑅$ 𝑆$ = 𝑠 = 5 𝑝 𝑟, 𝑠′ 𝑠, 𝑎 𝜋 𝑎 𝑠 𝑟 と書ける． • • • • ( ! ,*,+ 状態𝑠のときの価値関数は，その状態のときに将来得られる報酬 の期待値である． 状態𝑠から報酬を得るには⾏動𝑎をしなければならない．状態𝑠の とき得られる報酬の期待値を計算するには，状態𝑠のときに⾏え るすべての⾏動を考慮しなければならない． 状態𝑠から 状態𝑠のとき⾏動𝑎をする確率は𝜋(𝑎 ∣ 𝑠)である．𝜋は⾏動を決める のでエージェントの⽅策とみなせる． 𝑠′ 𝑠 池 𝑎 池 𝑟 成功 草 原 森 家 失敗

価値関数 𝐸% 𝐺$&' 𝑆$ = 𝑠 = 5 𝑝 𝑟, 𝑠′ 𝑠, 𝑎 𝜋 𝑎 𝑠 𝐸% [𝐺$&' ∣ 𝑆$&' = 𝑠′] ( ! ,*,+ = 5 𝜋 𝑎 𝑠 5 5 𝑝 𝑠 , , 𝑟 𝑠, 𝑎 𝐸% [𝐺$&' ∣ 𝑆$&' = 𝑠′] + (, 𝑠′ * 𝑣% 𝑠 = 𝐸% 𝐺$ 𝑆$ = 𝑠 だから 𝐸% 𝐺$&' 𝑆$ = 𝑠 = 5 𝜋 𝑎 𝑠 5 5 𝑝 𝑠 , , 𝑟 𝑠, 𝑎 𝑣% (𝑠 , ) + (, * よって 𝑣% 𝑠 = 𝐸% 𝐺$ 𝑆$ = 𝑠 = 𝐸% 𝑅$ + 𝛾𝐺$&' 𝑆$ = 𝑠 = 𝐸% 𝑅$ + 𝛾𝑣% (𝑠′) 𝑆$ = 𝑠 池 𝐸! [𝐺"#$ ∣ 池] 草 原 𝐸! [𝐺"#$ ∣ 草原] 森 𝐸! [𝐺"#$ ∣ 森] 家 𝐸! [𝐺"#$ ∣ 家] 𝑎 𝑠 池

⾏動価値に対するベルマン⽅程式 𝑣% 𝑠 = 𝐸% 𝑅$ + 𝛾𝑣% (𝑠′) 𝑆$ = 𝑠 = 5 𝜋 𝑎 𝑠 5 5 𝑝 𝑠 , , 𝑟 𝑠, 𝑎 (𝑟 + 𝛾𝑣% (𝑠 , )) + (, * これを⾏動価値に対するベルマン⽅程式という．

⾏動価値関数 • 状態𝑠になるためには⾏動しなければならない．そう考えれば，価値観 数は⾏動𝑎にも依存しているだろう． • ⾏動𝑎を考慮した価値関数を⾏動価値関数といい，次のように書く． • 𝑞! 𝑠, 𝑎 = 𝐸! 𝐺" 𝑆" = 𝑠, 𝐴" = 𝑎 決まっている 𝑠 池 𝑠′ 𝑎 𝑟 成功 草 原 失敗

⾏動価値関数 𝑞% 𝑠, 𝑎 = 𝐸% 𝐺$ 𝑆$ = 𝑠, 𝐴$ = 𝑎 = 𝐸% 𝑅$ + 𝛾𝐺$&' 𝑆$ = 𝑠, 𝐴$ = 𝑎 = = 𝐸% 𝑅$ 𝑆$ = 𝑠, 𝐴$ = 𝑎 + 𝛾𝐸% 𝐺$&' 𝑆$ = 𝑠, 𝐴$ = 𝑎 = 5 𝑝 𝑠 , , 𝑟 𝑠, 𝑎 𝑟 + 𝛾 5 𝑝 𝑠 , , 𝑟 𝑠, 𝑎 𝐸% [𝐺$&' ∣ 𝑆$ = 𝑠′, 𝐴$ = 𝑎′] (,,* (,,* = 5 𝑝 𝑠 , , 𝑟 𝑠, 𝑎 𝑟 + 𝛾 5 𝑝 𝑠 , , 𝑟 𝑠, 𝑎 𝑞% (𝑠 , , 𝑎′) (,,* = 𝐸% 𝑅$ + 𝛾𝑞(𝑠 , , 𝑎, ) (,,* 𝑆$ = 𝑠, 𝐴$ = 𝑎 これを⾏動価値に対するベルマン⽅程式という． 決まっている 𝑠 池 𝑠′ 𝑎 草 原 𝑎ʼ 𝐸! [𝐺"#$ ∣ 草原，𝑎′]

エージェントはどう⾏動すればよいか • エージェントの⽬的は報酬の最⼤化である． • 我々が知りたいのは，エージェントが⽬的を達するためにはどのよう な⾏動（⽅策）をとればよいかである． • 最も良い⽅策𝜋∗とすると，⽅策𝜋∗をとったときの価値関数は • 𝑣!∗ 𝑠 = max 𝑣! 𝑠 = max 𝐸! 𝐺" 𝑆" = 𝑠 ! ! • と書ける．これを最適状態価値関数と呼ぶ． • ⽅策𝜋∗をとったときの⾏動価値関数は • 𝑞!∗ 𝑠, 𝑎 = max 𝑞! 𝑠, 𝑎 = max 𝐸! 𝐺" 𝑆" = 𝑠, 𝐴" = 𝑎 ! ! • と書ける．これを最適⾏動価値関数と呼ぶ．

価値に対するベルマン最適⽅程式 • 最適な⽅策𝜋∗をとったときの価値関数は 𝑣∗ 𝑠 = max 𝑞%∗ 𝑠, 𝑎 = max 𝐸%∗ 𝐺$ 𝑆$ = 𝑠, 𝐴$ = 𝑎 +∈/ ( +∈/(() = max 𝐸%∗ 𝑅$ + 𝛾𝐺$&' 𝑆$ = 𝑠, 𝐴$ = 𝑎 +∈/(() = max 𝐸%∗ 𝑅$ + 𝛾𝑣%∗ 𝑆$&' +∈/(() = max 5 𝑝 𝑠 , , 𝑟 𝑠, 𝑎 +∈/(() 𝑆$ = 𝑠, 𝐴$ = 𝑎 𝑟 + 𝛾𝑣%∗ 𝑆$&' ( ! ,* • これを価値に対するベルマン最適⽅程式という． 決まっている 𝑠 池 𝑠′ 𝑎 草 原 最⼤値をとる𝑎 𝐸! [𝐺"#$ ∣ 草原]

⾏動価値に対するベルマン最適⽅程式 • 最適な⽅策𝜋∗をとったときの価値関数は 𝑞∗ 𝑠, 𝑎 = 𝐸 𝑅$ + 𝛾 max 𝑞%∗ 𝑆$ , 𝑎, ! + = 5 𝑝 𝑠 , , 𝑟 𝑠, 𝑎 ( ! ,* 𝑆$ = 𝑠, 𝐴$ = 𝑎 , , 𝑟 + 𝛾 max 𝑞 𝑠 ,𝑎 % ∗ ! + • これを，⾏動価値に対するベルマン最適⽅程式という． 𝑠 ( は𝑠, 𝑎に依存 決まっている 𝑠 池 𝑠′ 𝑎 草 原 𝑎′ 𝑞!∗ 𝑠′, 𝑎′ 最⼤値をとる𝑎(

エージェントはどうこうどうすればよいか • 価値関数や⾏動価値関数を計算してはみたが，エージェントがどうこ うどうすればよいのか分からない． • 最適価値関数𝑣∗が分かっていれば，エージェントは𝑣∗が最⼤の⾏動を 取れば良い． • しかし，実際は分からない． • エージェントは過去の試⾏錯誤から得た情報から最適価値関数もしく は最適⾏動価値関数を得なければならない．

動的計画法

動的計画法とは • 最適化⼿法およびプログラミング⼿法の⼀つ． • 1950年代Bellmanにより開発された． • 複雑な問題を部分的な簡単な問題に分割し，再帰計算により解く⼿法 である． • 強化学習では最適な⽅策を探すことが⽬的である．強化学習における 動的計画法では，状態ごとの価値を更新しながら最適な⽅策を探して いくことになる．

価値関数をどのように計算するか • 価値関数をどのように求めるか 𝑣) 𝑠 = 𝐸) 𝐺! 𝑆! = 𝑠 = 𝐸) 𝑅! + 𝛾𝐺!*# 𝑆! = 𝑠 = 𝐸) 𝑅! + 𝛾𝑣) (𝑆!*# ) 𝑆! = 𝑠 = + 𝜋 𝑎 𝑠 + 𝑝 𝑠 ( , 𝑟 𝑠, 𝑎 𝑟 + 𝛾𝑣) 𝑠 ( + , ! ,. • 価値関数が既知ならば価値関数から最適な⾏動を求められるが，実際 は価値関数は未知である． • エージェントは経験から得た価値関数を⽤い，状態の価値を評価しな ければならない． • 時刻𝑘 + 1のときの状態𝑠の価値は，⼀つ前の時刻𝑘の価値関数から次の ように求められる． 𝑣/*# 𝑠 = 𝐸) 𝑅!*# + 𝛾𝑣/ 𝑆!*# 𝑆! = 𝑠 = + 𝜋 𝑎 𝑠 + 𝑝 𝑠 ( , 𝑟 𝑠, 𝑎 𝑟 + 𝛾𝑣/ 𝑠 ( + , ! ,. • これをiterative policy evaluationと呼ぶ．

Iteretive policy evaluationのアルゴリズム • ⼊⼒：⽅策𝜋 • アルゴリズムパラメタ：閾値𝜃 • 初期化 • 任意の値ですべての状態の価値𝑉 𝑠 を初期化する．ただし，終端状態の𝑉(𝑠)は 0にする． • Loop: • Δ←0 • Loop for each 𝑠 ∈ S: • 𝑣 ← 𝑉(𝑠) • 𝑉 𝑠 ← ∑# 𝜋 𝑎 𝑠 ∑$% ,& 𝑝 𝑠 ' , 𝑟 𝑠, 𝑎 [𝑟 + 𝛾𝑉(𝑠 ' )] • Δ ← max(Δ, |𝑣 − 𝑉(𝑠)|) • unitil Δ < 𝜃 要約 古い𝑉(𝑠)を使って𝑉(𝑠)を再 計算する． 古い 𝑉(𝑠) と新しい 𝑉(𝑠) の 差が⼩さくなれば終了．

例：格⼦の世界 1 2 3 4 5 6 7 8 9 10 11 12 13 14 エージェントは格⼦内を移動する． 灰⾊は終端状態で，そこまで移動す るとエージェントは移動をやめる． 格⼦内の数値は，格⼦に割り振った 番号で，状態を表す． 𝑆 = {1,2, … , 14} エージェントは上下 左右に移動できる． 今回は等確率で移動 するとする． 格⼦の壁にぶつかっ た場合，その状態に 居続ける． どの状態になっても報酬 は−1 𝑅! = −1

例：格⼦の世界 初期状態𝑘 = 0 𝑘=1 0 0 0 0 0 -1 -1 -1 0 0 0 0 -1 -1 -1 -1 0 0 0 0 -1 -1 -1 -1 0 0 0 0 -1 -1 -1 0 すべての状態の価 値は０に初期化し た． 格⼦内の数値は状 態の価値𝑉(𝑠)であ る． 状態𝑠の価値𝑉/&# (1)を計算してみる． 更新式は 𝑉 𝑠 ← + 𝜋 𝑎 𝑠 + 𝑝 𝑠 ( , 𝑟 𝑠, 𝑎 [𝑟 + 𝛾𝑉(𝑠 ( )] + , ! ,. だから 𝑉/&# 1 1 1 1 = × −1 + 0 + × −1 + 0 + × −1 + 0 4 4 4 1 + × −1 + 0 = −1 4 すべての状態に対し同じ計算を⾏うと，図のよ うになる．上下左右等確率に移動するので， 1/4がかけてある．𝛾 = 1としている．

例：格⼦の世界 𝑘=1 𝑘=2 𝑘=3 0 -1 -1 -1 0 −1.7 −2 −2 0 −2.4 −2.9 −3 -1 -1 -1 -1 −1.7 −2 −2 −2 −2.4 −2.9 −3 −2 -1 -1 -1 -1 −2 −2 −2 −1.7 −2.9 −3 −2.9 −2.9 -1 -1 -1 0 −2 −2 −1.7 0 −3 −2.9 −2.4 0 状態𝑠の価値𝑉/&$ (1)を計算してみる． 𝑉/&$ 1 1 1 1 = × −1 + 0 + × −1 − 1 + × −1 − 1 4 4 4 1 + × −1 − 1 = −1.75 4 すべての状態に対し同じ計算を⾏うと，図のよ うになる． 状態𝑠の価値𝑉/&8 (1)を計算してみる． 𝑉/&8 1 1 1 1 = × −1 + 0 + × −1 − 1.7 + × −1 − 2 4 4 4 1 + × −1 − 2 = −2.425 4 すべての状態に対し同じ計算を⾏うと，図のよ うになる．

例：格⼦の世界 最終的に得られた 状態価値 0 −14 −20 −22 −14 −18 −20 −20 −20 −20 −18 −14 −22 −20 −14 0 ⽅策 何度か計算すると状態価値の値は収束する．この状態価値から⽅策を導い てみよう． エージェントは最も状態価値の⾼い⾏動を取る（greedy⽅策）とすると， 右図のような⽅策を取る．この⽅策は最適⽅策になっている．

Policy improvement
• 価値関数を求めたのは，より良い⽅策を⾒つけるためである．
• 現在の⽅策𝜋に従って⾏動するより，良い⾏動があるかどうか重要で
ある．ある場合は⽅策を更新しなければならない．
• 状態𝑠で⾏動𝑎をとり，その後⽅策𝜋に従い⾏動するとしたときの価値
は次のように書ける．
• 𝑞! 𝑠, 𝑎 = 𝐸 𝑅":; + 𝛾𝑣! 𝑆":;
𝛾𝑣! 𝑠 > ]

𝑆" = 𝑠, 𝐴" = 𝑎 = ∑<0 ,= 𝑝 𝑠 > , 𝑟 𝑠, 𝑎 [𝑟 +

• この値が𝑉 ! 𝑠 より⼤きい場合，状態sのとき⾏動aをとったあと⽅策𝜋
を取り続ける⽅が，状態𝑠のとき⽅策𝜋に従うより良いということにな
る．
• 𝑉 % 𝑠 は状態𝑠のとき⽅策𝜋に従い⾏動して得られる報酬の期待値である．
• ⽅策𝜋に従うより良い⾏動があるということは⽅策は改善の余地があるこ
とになる．

Policy improvement
• より良い⽅策𝜋 > (𝑠)は，状態𝑠で最も𝑞! 𝑠, 𝑎 が⾼い⾏動をするgreedyな
⽅策でだろう．
• 𝜋 > 𝑠 = arg max 𝑞! 𝑠, 𝑎 = arg max 𝐸 𝑟":; + 𝛾𝑉 ! 𝑠":; ∣ 𝑠" = 𝑠, 𝑎" = 𝑎 =
?

arg max ∑<0 ,= 𝑝
?

𝑠>, 𝑟

𝑠, 𝑎

?

𝑟":; + 𝛾𝑣! 𝑠":;

• このように，もとの⽅策の価値関数にもとづきgreedyな⾏動を選択す
ることで⽅策を改善する⽅法をpolicy improvementという．

Policy iteration（⽅策反復）
• 価値関数𝑉 ! を利⽤し，より良い⽅策𝜋′を導き，さらにその⽅策𝜋′を使
い価値関数を更新する，という⼿順で改善していくことで，最適⽅策
を⾒つける⽅法を⽅策反復という．
1. 初期化
すべての状態について𝑉 𝑠 ∈ 𝑅，𝜋(𝑠) ∈ 𝐴 𝑠
2. Policy evaluation
Loop:
Δ←0
Loop for each s ∈ S:
v←V s
V s ← ∑" π a s ∑#!,% p s& , r s, a [r + γV(s& )]
Δ ← max(Δ, |v − V(s)|)
unitil Δ < θ
3. Policy improvement
policy-stable← 𝑡𝑟𝑢𝑒
For each 𝑠 ∈ 𝑆:
old-action← 𝜋 𝑠
𝜋 𝑠 ← arg max ∑( !,) 𝑝 𝑠 & , 𝑟 𝑠, 𝑎 𝑟 + 𝛾𝑉 𝑠 &
'

If olde-action≠ 𝜋 𝑠 , then policy-stable← 𝑓𝑎𝑙𝑠𝑒
If policy-stable= 𝑡𝑟𝑢𝑒, then stop and return 𝑉 ≈ 𝑣∗ , 𝜋 = 𝜋∗ ; else go to 2

Value iteration
• Policy iterationは価値と⽅策両⽅を各ステップで更新する必要がある．
• Value iterationは各ステップで次式を更新する．
• 𝑉@:; 𝑠 = max 𝐸[𝑅":; + 𝛾𝑉 𝑆":; ∣ 𝑆" = 𝑠, 𝐴" = 𝑎] =
max ∑A0 ,B 𝑝
?

?
𝑠>, 𝑟

𝑠, 𝑎 [𝑟 + 𝛾𝑉(𝑠 > )]

• この式は次のような意味の計算を⾏っている．
• 最⼤の⾏動を取ることで⽅策評価を⾏っている．
• 現時点の最適⽅策に基づき状態価値に更新する．

パラメタ：閾値𝜃
初期化
すべての状態について𝑉 𝑠 ∈ 𝑅を任意の値
にする．ただし，終端状態のVは0．
Loop:
Δ←0
Loop for each 𝑠 ∈ 𝑆:
𝑣←𝑉 𝑠
𝑉 𝑠 ←
max ∑#!,% 𝑝 𝑠 & , 𝑟 𝑠, 𝑎 [𝑟 + 𝛾𝑉(𝑠 & )]
'
Δ ← max(Δ, |v − V(s)|)
unitil 𝛥 < 𝜃
次の決定論的⽅策𝜋 ≈ 𝜋∗ を出⼒．
𝜋 𝑠 = arg max i 𝑝 𝑠 & , 𝑟 𝑠, 𝑎 [𝑟 + 𝛾𝑉 𝑠 & ]
'

( ! ,)