強化学習「理論」入門

2022年度 TopSE「機械学習概論」コースの一部として使用した講義資料です。
https://www.topse.jp/ja/curriculum-lectures.html

Transcript

1. Copyright (C) 2022 National Institute of Informatics, All rights reserved. 強化学習「理論」入門 中井悦司 / Etsuji Nakai 2022/05/28 ver2.4
2. 目次 第１部：強化学習のゴールと課題 ◦ 強化学習の考え方 ◦ バンディットアルゴリズム（基本編） ◦ バンディットアルゴリズム（応用編） 第２部：環境モデルを用いた枠組み ◦ マルコフ決定過程による環境のモデル化 ◦ 状態価値関数による行動ポリシーの比較 ◦ 動的計画法による状態価値関数の計算 第３部：行動ポリシーの改善アルゴリズム ◦ ポリシー反復法 ◦ 価値反復法 第４部：サンプリングデータによる学習 ◦ モンテカルロ法 ◦ TD 法（Q-Learning） ◦ TD 法（SARSA） 第５部：ニューラルネットワークによる関数近似 ◦ 状態価値関数の近似計算 ◦ DQN（Deep Q Network）
3. 参考書籍 3
4. サンプルコードの入手について • 新しく開いたノートブック上で次のコマンドを実行すると、本講義のサンプルノートブックがダウンロー ドできます。 ◦ 次のコマンドを実行すると、ユーザー認証が行われて、Colab の実行環境に該当ユーザーの Google Drive がマウントされます。 ◦ 次のコマンドを実行すると、サンプルノートブックが Google Drive に保存されます。 from google.colab import drive drive.mount('/content/gdrive') %%bash cd '/content/gdrive/My Drive/Colab Notebooks' git clone https://github.com/enakai00/colab_rlbook 4
5. 第１部　強化学習のゴールと課題
6. 強化学習の考え方
7. 教師あり／教師なし学習との違い • 教師あり学習（例：分類アルゴリズム） ◦ 「入力データと正解ラベル」の組を教師データとして学習 ◦ 予測時に100%の正解率を達成することはできない 7
8. 教師あり／教師なし学習との違い • 教師なし学習（例：クラスタリング） ◦ 類似性が高いデータのグループを発 見する ◦ データに対する知見を得ることが主 な目的で、「正解」の定義はない 8
9. 強化学習の考え方 • 「環境」内を行動するエージェントが、最善の「行動ポリシー」を発見することが目的 ◦ 行動ポリシー ⇨ 場面ごとにエージェントの行動を選択するルール • 数学的には、「マルコフ決定過程」として環境と報酬を定義する ◦ 行動によって得られる「総報酬」を最大化することがゴール（確率的な要素を含む環境 においては、「総報酬の期待値」が最大になる行動ポリシーを発見することを目指す） ◦ 環境のすべての情報が事前に分かっている場合、理論上は「ベルマン方程式に基づく動 的計画法」で厳密解を求めることが可能 9
10. 強化学習の課題 • 現実の問題では、次のような理由で厳密解を得ることは困難になる ◦ 環境のすべての情報が事前に分かっていない場合は、エージェントが収集した部分的な データによる学習が必要 ⇨ モンテカルロ法、TD法（Q-Learning、SARSA） ◦ 環境が複雑な場合は、必要となるメモリー容量や計算時間の観点で厳密解を求めるのは 困難 ⇨ ニューラルネットワークによる関数近似（DQN : Deep Q Network） • 厳密解を求める理論（ベルマン方程式に基づく動的計画法）が上記の近似手法を理解する基 礎となる 10 厳密解を求める理論を理解した上で、それを近似的に再現する手法を学ぶ
11. バンディットアルゴリズム（基本編）
12. 多腕バンディット問題 ※ 「マルコフ決定過程」を説明する前に、より単純な問題で「強化学習の基本概念」を押さえる • 10台のスロットマシン（ボタンを押すとランダムな得点が得られるマシン）があり、それぞ れが与える得点は、平均　　　　 、標準偏差 1 の正規分布に従う • 「100回ボタンを押した時の総得点を競う」というゲームに勝つ（総得点の期待値を最大化 する）にはどうすればよいか？ マシンごとの 得点の確率分布 12 ・・・
13. 不完全な環境情報と計算リソースの制限から来る困難 • 　　　　 が事前に分かっていれば答えは自明：　が最大のマシンを選び続ければよい • 事前のデータ収集が無限に行えるのであればやはり簡単：各マシンのボタンを（例えば） 10,000回ずつ押して、得られた点数の標本平均で　　　　 を推定 • これらが許されない場合、100回のプレイ中にデータ収集（μ の推定）と点数稼ぎ（μ が最大 と思われるマシンの選択）を組み合わせる必要がある 13 真の平均値 これまでの結果 標本平均で推定 マシンごとに 個別に蓄積
14. Exploration（探索）と Exploitation（活用）の組み合わせ • ε-greedy ポリシー：確率 ε でランダムなマシンを選択、それ以外は μ の推定値（これまでに 得られた点数の標本平均）が最大のマシンを選択 ◦ ε をハイパーパラメーターとして、ハイパーパラメーター・チューニングを実施 14
15. 平均値計算の実装テクニック • 愚直に実装するなら、過去データ　　　　　　をすべて記憶しておいて下記で計算 • 次の公式で「新しいデータを得るごとに平均値を更新する」ことも可能 ◦ 『これまでの平均値と新しく得たデータの「誤差」を 1 / n の重みで加えて修正するルール』と考え ることができる 15 n - 1 個目までの データの平均値 n 個目までの データの平均値
16. コードによる確認 • ノートブック「Chapter01/01_Bandit_Algorithm_1.ipynb」を参照 16 def get_action(qs, epsilon): if np.random.random() < epsilon: # Explore: choose randomly. return np.random.randint(len(qs)) else: # Exploit: choose the arm with the max average. return np.argmax(qs) def episode(bandit, epsilon, steps): total_rewards = [0] qs = [0] * bandit.arms count = [0] * bandit.arms for _ in range(steps): arm = get_action(qs, epsilon) reward = bandit.select(arm) # Append total rewards total_rewards.append(total_rewards[-1] + reward) # Update an average of rewards. count[arm] += 1 qs[arm] += (reward - qs[arm]) / count[arm] return total_rewards ε-greedyポリシーの実装 平均値の逐次計算 ハイパーパラメーター・チューニング （グリッドサーチ）の結果
17. バンディットアルゴリズム（応用編）
18. 非定常状態への対応 • 各スロットマシンが出力する得点の平均値 μ がプレイ中に徐々に変動する場合、古い過去 データで推定するのは危険 • 過去データの平均値　 の代わりに、一定の重み α で更新される推定値　 を利用 確率分布が徐々に 変化すると仮定 18 平均値の場合は新しい データほど重みが減少 一定の重みで更新する ことで直近のデータを 重視する
19. コードによる確認 • ノートブック「Chapter01/　 02_Bandit_Algorithm_2.ipynb」を参照 19 def episode(bandit, alpha, steps): total_rewards = [0] qs = [0] * bandit.arms count = [0] * bandit.arms for _ in range(steps): arm = get_action(qs, epsilon=0.1) reward = bandit.select(arm) # Append total rewards total_rewards.append(total_rewards[-1] + reward) # Update an estimate of the mean. if alpha == 0: # Use an average to estimate the mean. count[arm] += 1 qs[arm] += (reward - qs[arm]) / count[arm] else: # Update an estimate with a constant weight. qs[arm] += alpha * (reward - qs[arm]) return total_rewards 一定の重み α による更新 ハイパーパラメーター・チューニング （グリッドサーチ）の結果
20. 平均値を用いた推定値との比較 • 「定常状態」の問題については、平均値を用いた方が理論的にはより正確な推定が可能 • ただし、「真の平均値が最大のマシンを選ぶ」という意味では厳密な推定は不要で、一定 の重み α による更新でも（α を適切にチューニングすれば）得られる結果は同等になる 20 一定の重みによる更新の場合 推定値は変動を続ける 推定値は真の 平均値に収束 μ は -2 〜 1.5 の 範囲で均等に分布
21. 初期値を用いた探索のトリック • 推定値 q の初期値を 0 とした際に、最初に 選んだマシンがたまたま高得点を返すと、そ の後しばらくは、そのマシンが高確率で選ば れる • 推定値 q の初期値を意図的に大きくしておく と、データが得られるごとに推定値が下がる ので、ゲームの初期では、すべてのマシンが まんべんなく選ばれる 21 平均値 μ が 最大のマシン 平均値 μ が 最大のマシン
22. まとめ • 環境情報が事前に分かっている場合、最適なアクションを厳密に決定することができる ◦ 第２部、第３部で、マルコフ決定過程を用いたより一般的な枠組みを解説 • 環境情報が事前に分かっていない場合、「環境情報の収集」と「これまでに収集した情報 によるベストなアクションの選択」を並列に実行する必要がある ◦ 第 4 部で詳しく解説 ◦ 多くの場合、ε-greedy ポリシーを利用してこれらを並列に実行する ◦ 新しいデータで環境情報をアップデートする際は、（定常状態、非定常状態に関わらず）「一定の 重み α で推定値を更新する」という方法を用いる事が多い ※ ランダムなアクションを混ぜないポリシー（「これまでに収集した情報による 　ベストなアクション」を常に選択するポリシー）を Greedy ポリシーと呼ぶ 22 モデルベース アルゴリズム モデルフリー アルゴリズム
23. 演習 & 休憩 • 余裕のある方は、「コードによる確認」の説明を参考にしながら、以下のノートブックを 見て、コードの実装を理解してみてください。 ◦ Chapter01/02_Bandit_Algorithm_1.ipynb → 定常状態（標本平均を用いた「真の平均値」の推定） ◦ Chapter01/02_Bandit_Algorithm_2.ipynb → 非定常状態（一定の重みで推定値を更新） 23
24. 第２部　環境モデルを用いた枠組み
25. マルコフ決定過程による環境のモデル化
26. マルコフ決定仮定とは？ • マルコフ決定過程 ⇨ 有限個の「状態」と「アクション」を組み合わせた状態遷移図で表さ れるプロセス 26 行動ポリシー ◦ 状態遷移には「報酬」が付随 ◦ アクションの結果は、今の状態 のみに依存して決まる • 状態ごとに選択するアクションを決 定する「行動ポリシー」の中で、総 報酬を最大化するものを発見するこ とがゴール この例では無限の報酬が得られる （最大値が定義できない）ので、 問題設定の修正が必要 環境 エージェント
27. エピソード的タスク • 「商品を出来るだけ早く１つ購入する」ことを目的にして、図のような状態遷移を定義す ると、前ページの行動ポリシーが明らかに最善のポリシーとなる ◦ エージェントが終了状態に到達するタスクを「エピソード的タスク」と言う 27 ※ 前ページの状態遷移の場合、下記の 　行動ポリシーでも総報酬は無限大になる
28. 非エピソード的タスク • 前々ページのように終了状態がないタスクを「非エピソード的タスク」と言う • このような場合は、「報酬の割引率 γ」を導入すると行動ポリシーを適切に比較することが できる ◦ 具体的には、次のような状態遷移（S：状態、A：アクション、R：報酬）に対して、 次式で総報酬を定義する（γ は 0.9 程度の 1 より小さい値） 28
29. 報酬の割引率による効果 • 報酬の割引率 γ を導入した場合、行 動ポリシー A の総報酬は次になる • 行動ポリシー B のように余計な行動 が加わると総報酬は小さくなる 行動ポリシー A 行動ポリシー B 29
30. 確率的な状態変化 30 • マルコフ決定過程では、確率的な状態変 化も許される ◦ 状態 s でアクション a を選択した時 に報酬 r を得て次の状態が s' になる 条件付き確率を　　　　　　と表す • 右図の例を条件付き確率で表すと次になる このような1次元、もしくは、2次元のマスを 移動する題材を「グリッドワールド」と呼ぶ
31. バックアップ図による状態変化の表現 31 • マルコフ決定過程の状態変化のプロセスは、右 図のような「バックアップ図」でもれなく表現 できる ◦ 点線矢印部分は、同じツリーが再帰的に 現れる ◦ 「バックアップ図」という名前の由来は この後で説明
32. 状態価値関数による行動ポリシーの比較
33. 状態価値関数の定義 33 • 状態価値関数　　　は、行動ポリシー π に従って、 状態 s から行動を続けた際の総報酬の期待値を表す （終了状態に対する値は必ず 0 と定義する） • 「常に右に進む」行動ポリシーを　 とすると、右の バックアップ図より、次の値が得られる R （+5） S M G 1 1 R • 次の関係が成り立っており、原理的には、終了状態から逆にたどることで順に値が決定し ていく（バックアップ図という名前の由来） 直後の報酬 その後の報酬 ⇦ 状態 s から、報酬 r が得られて、状態 s' に遷移したとする
34. 状態価値関数（直接計算の例） 34 • 「常に左に進む」行動ポリシー　 に対するバック アップ図は、右図になる • 期待値計算の問題として愚直に解くと、　　　は次 のように計算できる 1回目でゴールに到達 2回目でゴールに到達 3回目でゴールに到達
35. 状態価値関数の再帰的関係 35 • バックアップ図の再帰構造を考えると、　　　に対 して次が成り立つことがわかる ◦ 　　　　　より、先ほどと同じ結果が得られる • この結果から、　　　 は次のように決まる 直後の報酬 + その後の報酬 直後の報酬 + その後の報酬
36. 状態価値関数が満たす関係式 36 • 前ページの議論を一般化すると、次のように公式化することができる（行動ポリシー π が状 態 s で選択するアクションを a とする） • 状態 s でアクション a を選択した場合、確率　　　　　　 で報酬 r が得られて、状態 s' に 移行する。s' 以降に得られる総報酬の期待値は　　　なので、s から見た総報酬の期待値は （割引率 γ を考慮して）上式で与えられる ※ これを（確率的な行動ポリシーに対応するように）さらに一般化したものが後で説明する 　「状態価値関数に対するベルマン方程式」になる 直後の報酬 + その後の報酬
37. • （状態、および、アクションの数が有限個のマルコ フ決定過程では）他のすべての行動ポリシーよりも 優れた「最善の行動ポリシー　 」が必ず存在する ◦ これを発見することを強化学習のゴールとする　　　　　 行動ポリシーの優劣比較 37 • 「すべての状態 s について　　　　　　　 」となる時、行動ポリシー　　は、行動ポリシー 　　よりも優れていると定義する ◦ 状態 s によって大小関係が変わり、優劣が定まらない場合もある この例における最善の行動ポリシーは どのようになるでしょうか？
38. 行動ポリシーの優劣比較 38 • 先ほどのグリッドワールドの場合、最善 の行動ポリシー　 は次に決まる ◦ 　　　の時は ◦ 　　　の時は ◦ 　　　　 の時は次の行動ポリシー
39. 動的計画法による状態価値関数の計算
40. 確率的な行動ポリシー 40 • 行動ポリシー π は、確率的にアクション を選択するものでも構わない ◦ この場合、状態 s でアクション a を選択する条件付き確率を　　　 と表す ◦ 確率を伴わない行動ポリシー π の 場合は、状態 s で（確率 1 で）選 択するアクションを　　 で表す C R B その他の確率は すべて 0 確率的 行動ポリシー 決定的 行動ポリシー
41. 状態価値関数に対するベルマン方程式 41 • 決定的行動ポリシーの場合は、状態 s で選択するアクションを a として、次の関係が成り 立っていた • 確率的行動ポリシーの場合、アクション a は確率　　　　で選択されるので、あ らゆるアクションの可能性を考慮した期 待値は次になる 状態価値関数に対するベルマン方程式 　　 を使って 　 を計算
42. 動的計画法による状態価値関数の計算 42 • バックアップ図において終了状態から逆向きに ベルマン方程式を適用すると、状態価値関数の 値が順番に決まっていくと想像される • 実際には、順番を気にせずに「すべての状態 s について、ベルマン方程式の右辺で　　　を更 新する」という処理を無限に繰り返すと、正し い状態価値関数の値が得られる 状態価値関数に対する ベルマン方程式と 本質的に同じもの ◦ この手続きを「（ベルマン方程式に基づく）動的計画法」と呼ぶ 実装時は、「すべてのアクション a につ いてのループ」と「起こり得るすべての 結果 (r, s') についてのループ」が必要
43. コードによる確認 43 • ノートブック「Chapter02/　 01_Policy_Evaluation_1.ipynb」を参照 • 次の環境で動的計画法を適用 ◦ 右端（s = 7）に到達すると +1 の報酬 ◦ 常に右に移動する行動ポリシー ◦ 状態価値関数の初期値は 0 ◦ s = 0, 1, 2, …, 6 の順にベルマン方程式 を適用 1回目の Iteration 2回目の Iteration
44. 44 1回目の Iteration 2回目の Iteration 「終了状態」では任意の アクションに対して 「報酬 0 で同じ状態に留 まる」ものと定義する
45. コードによる確認 45 • ノートブック「Chapter02/　 02_Policy_Evaluation_2.ipynb」を参照 • 次の環境で動的計画法を適用 ◦ 右下が終了状態 ◦ 移動ごとに -1 の報酬 ◦ 「落とし穴」に落ちると左上に戻る ◦ 確率 1/2 で右、もしくは、下に移動す る行動ポリシー 実装上は、すべての状態 s をベル マン方程式で更新した際に、変化 の最大値が 0.01 未満になった所 で処理を打ち切る
46. コードによる確認 46 class Gridworld: def __init__(self, size=6, traps=[]): self.size = size self.traps = traps self.start = (0, 0) self.goal = (size-1, size-1) self.states = [(x, y) for x in range(size) for y in range(size)] self.actions = [(-1, 0), (0, -1), (1, 0), (0, 1)] self.policy = {} for s in self.states: self.policy[(s, (-1, 0))] = 0 self.policy[(s, (0, -1))] = 0 self.policy[(s, (1, 0))] = 1/2 self.policy[(s, (0, 1))] = 1/2 self.value = {} for s in self.states: self.value[s] = 0 def move(self, s, a): if s == self.goal: return 0, s # Reward, Next state s_new = (s[0] + a[0], s[1] + a[1]) if s_new not in self.states: return 0, s # Reward, Next state if s_new in self.traps: return -1, self.start # Reward, Next state return -1, s_new # Reward, Next state 行動ポリシー　　　　を Python のディクショナリーとして定義 状態価値関数　　　を Python のディクショナリーとして定義 今の場合は、確率的な状態変化を伴わない 環境なので、（確率 1 で得られる） 報酬 r と次の状態 s' を返却 終了状態は任意のアクションに対 して、報酬 0 と同じ状態を返す 環境を表すクラス 条件付き確率　　　　　　 に基づいて 報酬 r と次の状態 s' を返却
47. コードによる確認 47 def policy_eval(world, gamma=1, delta=0.01): while True: delta_max = 0 for s in world.states: v_new = 0 for a in world.actions: r, s_new = world.move(s, a) v_new += world.policy[(s, a)] * (r + gamma * world.value[s_new]) delta_max = max(delta_max, abs(world.value[s] - v_new)) world.value[s] = v_new if delta_max < delta: break 確率的な状態変化を伴わないので、 「起こり得るすべての結果 (r, s') に ついてのループ」は不要 状態価値関数の変化（の最大値）が 0.01 未満になったら処理を打ち切る 動的計画法を実装した関数 • この実装における「状態価値関数」は、何らかの数式で表現される「関数」ではなく、それぞれの状態 s に対する値　　　を個別に保存した「テーブル」に過ぎない点に注意 • 同様に、行動ポリシー π もそれぞれの状態 s に対するアクションを個別に保存した「テーブル」であり、 強化学習における学習処理は、本質的にはこのテーブルを書き換えていく作業に他ならない 状態価値関数の値を更新 すべてのアクション a についてのループ すべての状態 s についてのループ
48. まとめ 48 • 状態価値関数 ◦ 行動ポリシー π に従って、状態 s から行動を続けた際の総報酬の期待値 ⇨ 行動ポリシー π を決めると、対応する状態価値関数　　　が決まる ◦ 状態価値関数は、ベルマン方程式を用いた「動的計画法による繰り返しアルゴリズム」 で計算できる • 状態価値関数は何の役に立つのか？ ◦ 状態価値関数を比較することで、行動ポリシーの優劣が判断できる ◦ 状態価値関数を用いて、より優れた行動ポリシーを作ることができる → 第3部で解説 行動ポリシー π 環境モデル 直後の報酬 + その後の報酬
49. 演習 & 休憩 • 余裕のある方は、「コードによる確認」の説明を参 考にしながら、以下のノートブックを見て、コード の実装を理解してみてください。 ◦ Chapter02/01_Policy_Evaluation_1.ipynb ◦ 「コードによる確認」で説明した例に加えて、「一歩 進むごとに -1 の報酬が加わる」場合の例が後半にあ ります。 49 常に右に進む 行動ポリシー
50. 第３部　行動ポリシーの改善アルゴリズム
51. ポリシー反復法
52. 行動-状態価値関数の定義 52 • 行動-状態価値関数　　　　は、現在の状態 s において、 「アクション a を選択して、その後は行動ポリシー π に 従って行動を続けた場合」に得られる総報酬の期待値を表す ◦ 右のバックアップ図より、次で計算される ◦ ベルマン方程式でアクションについての期待値計算を特定のアクション a に置き換えた ものと考えてもよく、次が成り立つ 直後の報酬 + その後の報酬
53. 「一手先読み」による行動ポリシーの改善 • 行動ポリシー π が与えられた時、次の方法で新しい行動ポリシー π' を定義する。 ◦ 状態 s でアクション a を選択する際に、取り得るすべての a について　　　　を計算 して、これが最大になるものを選択する ⇨ 次の一手について、あらゆる手を比較して一番よいものを選ぼうという発想。ただし、すべての手を 正確に比較するには、一手先を見るだけではだめで、さらに先の手を読んで、ツリー状に展開されるあ らゆる手筋を比較する必要がある。そこまでするのは大変なので、二手目以降については既存の行動ポ リシー π に従うものと仮定して、次の一手の良さを測ろうという作戦 ◦ この π' は、必ず、π よりも優れた行動ポリシーになることが数学的に証明される 53 「　　　 に基づく Greedy ポリシー」と呼ぶ ⇔
54. （参考）π' が π よりも優れていることの（直感的な）証明 54 • 　　　 を最大にするアクション a が　　 であるという π' の定義より、次の関係が成り立つ • 上式の右辺は、1手目だけ π' に従った場合（2手目以降は π に従う）の総報酬なので、少なくとも1手目に ついては、π よりも π' に従う方が有利である（総報酬が大きくなる）ことを意味する • 2手目についても同じ議論から π' に従った方が有利と言える。3手目以降についても同様なので、帰納的 に考えて、2手目以降もすべて π' に従った方が1手目だけ π' に従った場合よりも総報酬は大きくなり、次 が得られる 最大値は平均値 よりも必ず大きい すべて π' に従った 場合の総報酬 1手目だけ π' に 従った場合の総報酬 ※ 厳密な証明は「ITエンジニアのための強化学習 　理論入門（3.1 ポリシー反復法）」を参照
55. ポリシー反復法のアルゴリズム • 次の手続きを繰り返す事で、最善の行動ポリシー　 に到達する 1. 適当な行動ポリシー π を用意する 2. 動的計画法で状態価値関数　　 を求める 3. 行動-状態価値関数に変換する： 4. 行動ポリシー π を　　　　に基づく Greedy ポリシー π' に置き換える → 2. に戻る ※ このアルゴリズムで得られる最善の行動ポリシー　 は、確率的なアクションを含まない 　「決定的行動ポリシー」になる。ただし、一般には、最善の行動ポリシーは複数存在する 　可能性があり、そこには確率的行動ポリシーも含まれることがある 55
56. コードによる確認 56 • ノートブック「Chapter03/02_Policy_Iteration_2.ipynb」を参照 ◦ 右下が終状態、移動ごとに報酬 -1 が得られる（最短で右下に移動することが目標） ◦ 行動ポリシーが変化しなくなるまでアップデートを実行 落とし穴に落ちると 確率 α=1 で左上に戻る
57. コードによる確認 57 確率 α = 0.5 で左上に戻る 1- α = 0.5 で右下に行く 確率 α = 0 で左上に戻る 1- α = 1 で右下に行く • 落とし穴に落ちた際の動作 を変えると、対応する行動 ポリシーも適切に変化する ことが分かる
58. コードによる確認 58 def policy_update(world, gamma=1): update = False for s in world.states: q_max = -10**10 a_best = None for a in world.actions: results = world.move(s, a) q = 0 for p, r, s_new in results: q += p * (r + gamma * world.value[s_new]) if q > q_max: q_max = q a_best = a if world.policy[(s, a_best)] != 1: update = True for a in world.actions: world.policy[(s, a)] = 0 world.policy[(s, a_best)] = 1 return update 行動ポリシーのアップデート を実装した関数 すべてのアクション a につ いて　　　　を比較して最 大となるアクションを選択 確率 1 で選択されたアクションを実行する ように行動ポリシーをアップデート
59. 価値反復法
60. 価値反復法 • 動的計画法で状態価値関数を計算するコードを実装する際は、値の変化が小さくなった所 で処理を打ち切った • ポリシー反復法では、行動ポリシーを更新するごとに（以前の計算結果を捨てて）状態価 値関数を再計算するので、早めに処理を打ち切って先に進んだ方が効率的かもしれない • 打ち切るタイミングを極限まで早めて、状態価値関数の更新と行動ポリシーのアップデー トを並列に実行するのが「価値反復法」のアルゴリズム 60
61. ポリシー反復法と価値反復法の比較 61
62. 価値反復法のアルゴリズム 62 • より具体的には、次の更新処理をすべての状態 s について適用する処理を（行動ポリシー が変化しなくなるまで）繰り返す 次ページの説明を参照
63. 価値反復法における状態価値関数の更新 63 • 一般に、決定的ポリシー　　 では、状態価値関数に対するベルマン方程式は次のように変 形される • さらに、今の場合は、　　　 に基づくGreedy ポリシーを構成しているので、　　は 　　　 を最大にするアクション a に一致する 確率 1 で　　　　 を選択
64. コードによる確認 64 • ノートブック「Chapter03/03_Value_Iteration_1.ipynb」を参照
65. def policy_update(world, s, gamma=1): q_max = -10**10 a_best = None for a in world.actions: results = world.move(s, a) q = 0 for p, r, s_new in results: q += p * (r + gamma * world.value[s_new]) if q > q_max: q_max = q a_best = a for a in world.actions: world.policy[(s, a)] = 0 world.policy[(s, a_best)] = 1 return q_max アップデート後の行動ポリシーが選択する a に対する　　　　の値　　　　　　 を返却 コードによる確認 65 これはアップデート後の行動ポリシー に対する状態価値関数　　　に一致 def value_iteration(world, delta=0.01): while True: delta_max = 0 print('.', end='') for s in world.states: v_new = policy_update(world, s) # Policy update delta_max = max(delta_max, abs(world.value[s] - v_new)) world.value[s] = v_new # Value update if delta_max < delta: print('\n') break 行動ポリシーのアップデート を実装した関数 価値反復法を実装した関数 行動ポリシーのアップデートと 状態価値関数のアップデートを 並列に実行
66. まとめ 66 ◦ 状態価値関数　　　から計算できる ⇨ ベルマン方程式でアクションに 　ついての期待値計算を省いた形 • 行動-状態価値関数は何の役に立つのか？ ◦ 行動-状態価値関数の値でアクション を比較することで、より優れた行動 ポリシーが構成できる • 行動-状態価値関数 ◦ 現在の状態 s において、「アクション a を選択して、その後は行動ポリシー π に従っ て行動を続けた場合」に得られる総報酬の期待値 行動ポリシー π で アクションを選択 特定のアクション a を選択
67. 三目並べエージェントの実装 67 • ノートブック「Chapter03/04_Tic_Tac_Toe.ipynb」を参照 ◦ 先手用のエージェントと後手用のエージェントが相互に学習を繰り返す方法で実装 先手・後手共に学習済みの エージェント（必ず引き分ける） 先手はランダムな手を打つ エージェント
68. 三目並べエージェントの実装 68 • 先手用エージェントの構成 ◦ 状態：先手の手番のあらゆる盤面 ◦ 行動ポリシー（初期状態）：自分が打てる位置をランダムに選択 ◦ 状態変化：「先手の手番の盤面」でどこかに手を打つと、後手用エージェントが打ち 返してきて、再び「先手の手番の盤面」になる ◦ 報酬：「先手の勝ち状態」になると +1、「先手の負け状態」になると -1 • 後手用エージェントも同様に構成 • 先手用エージェントと後手用エージェントを交互に学習（以下を繰り返す） ◦ 後手用エージェントを固定して、先手用エージェントにポリシー反復法を適用 ◦ 先手用エージェントを固定して、後手用エージェントにポリシー反復法を適用
69. 報酬設計による学習結果の違い 69 • 前ページの例では、「勝つと +1、負けると -1、引き分けは 0」という報酬設計を用いた ◦ 三目並べは互いに最善手を打つと必ず引き分けるので、結果として、引き分けばかり になる • 「勝つと +1、それ以外（負け、もしくは、引き分け）は 0」と いう報酬設計に変更すると学習結果が変わる ◦ 負けも引き分けも同等の価値なので、エージェントは、引き 分けに持ち込むよりは、（相手のミスによって）勝つことを 狙った手を打つようになる
70. 演習 & 休憩 • 余裕のある方は、「コードによる確認」の説明を参考にしながら、以下のノートブックを 見て、コードの実装を理解してみてください。 ◦ Chapter03/02_Policy_Iteration_2.ipynb →　ポリシー反復法による実装 ◦ Chapter03/03_Value_Iteration_1.ipynb →　価値反復法による実装 70 落とし穴に落ちると確率 α で左上に戻る（確率 1-α でゴールに到達する） という環境で、さまざまな α の値に対する結果があります。結果の違いを 比較してください。
71. 第４部　サンプリングデータによる学習
72. モンテカルロ法
73. 状態遷移確率が未知の場合 73 • ベルマン方程式に基づく動的計画法は、状態遷移確率　　　　　　 が事前に分かっている という前提 • たとえば、ビデオゲームをプレイするエージェントを学習する場 合、ビデオゲームのコードを見なければ、状態遷移確率を知るこ とはできない ⇨ 厳密に計算するのではなく、実際にプレイしたデータから 　推定する手法が必要
74. 状態価値関数の推定（問題例） 74 • 次のゲームを考える ◦ プレイヤーは 1 〜 99 の手持ちのポイントがあり、任意のポイントを賭ける ◦ 確率 0.4 で賭けに成功すると、賭けたポイントが倍になって戻る ◦ 確率 0.6 で賭けに失敗すると、賭けたポイントは没収される ◦ 手持ちのポイントが 100 以上になると勝ち（報酬 +1 を得る） ◦ 手持ちのポイントが 0 になると負け（報酬 -1 を得る） • 手持ちのポイント s に対して、賭けるポイントの値 a を決定する行動ポリシー π を決め て、これに対する状態価値関数　　　を推定する
75. エピソードの結果を用いた推定 75 • 手持ちポイント　 からスタートして、実際にゲームをプレイした結果が次になったとする ◦ 最終的に総報酬 +1 を得ており、　　　 に対するサンプルの1つとなる ◦ 　からスタートした時の同様のデータを集めて平均値をとれば　　　 の推定値になる • 上記のエピソードは、途中に含まれる状態　　　　　 についても、総報酬 +1 のサンプル とみなすことができる ◦ このように、総報酬が確定したエピソードをサンプルとして推定する手法を（狭義 の）モンテカルロ法と呼ぶ このような「終了状態」に至るまでの 状態遷移データを「エピソード」と呼ぶ
76. モンテカルロ法の一般的な手続き 76 • ゲームをプレイしながら、それぞれのステップで　　　　 の3つ組データを集取する ◦ エピソードと対応する3つ組みデータの例 • 3つ組データを後ろから前にスキャンしていく と、各ステップに対する総報酬を計算しながら、 それぞれの状態に対する平均値の更新が行える(*) 　 からスタート した時の総報酬 　 からスタート した時の総報酬 (*) 平均値更新の公式（データ数 n は 　状態ごとに個別にカウントする）
77. コードによる確認 77 • ノートブック「Chapter04/　 02_Gambler's_Problem_Value_E stimation.ipynb」を参照 • 状態価値関数のグラフから、ポリ シーの優劣が比較できる ◦ 上段と中段は優劣が決まらない例 になっている ◦ 下段は上の2つよりも優れている （実は、これが最善のポリシー） 後半は無駄に 賭け過ぎ ちょうど100ポイントに なるように賭けている 状態 s（手持ちのポイント） 状態 s（手持ちのポイント） 賭けるポイント v(s) の値 「成功」or「失敗」 のどちらかで終了
78. コードによる確認 78 def get_episode(gambler): episode = [] s = np.random.randint(1, gambler.goal) while True: a = gambler.policy[s] r, s_new = gambler.play(s, a) episode.append((s, a, r)) if s_new == 0 or s_new == gambler.goal: break s = s_new return episode １回分のエピソードを シミュレーションする関数 3つ組データ　　　　を収集 def train(gambler, num): c = 0 while c < num: episode = get_episode(gambler) episode.reverse() total_r = 0 for (s, a, r) in episode: total_r += r gambler.cnt[s] += 1 gambler.values[s] += (total_r - gambler.values[s]) / gambler.cnt[s] c += len(episode) 状態価値関数を推定する関数 収集データの順序を反転 ポイントの初期値を乱数で設定（つまり、 エピソードの開始状態 s はランダムに選択） ・・・ 逆順に報酬 r を加えることで、 「その時点以降の総報酬 total_r」 を更新
79. 行動-状態価値関数の推定 79 • ポリシー反復法、もしくは、価値反復法で行動ポリシーを更新する際は、行動-状態価値関 数　　　　の計算が必要 ◦ 状態価値関数から求める場合は、状態遷移確率　　　　　　 が必要なので、今の場 合、この方法は使えない • そこで、エピソードのサンプルから直接に行動-状態価値関数　　　　を推定する ◦ 行動-状態価値関数は、「現在の状態 s において、アクション a を選択して、その後は 行動ポリシー π に従って行動を続けた場合に得られる総報酬の期待値」なので、実際 に得られた総報酬の値をたくさん集めて平均値を計算すればよい
80. 行動-状態価値関数の推定 80 • 状態　 において、最初のアクション　 は任意に選んで、その後は行動ポリシー π に従っ て行動した結果、次のエピソードが得られたとする ◦ この時の総報酬　　　 　　　　　　は　　　　　 を推定するサンプルになる • 上記のエピソードで、　以降のデータを取り出す ◦ この時の総報酬　　　　　　　は　　　　　を推定するサンプルになる（アクション 　 がたまたま行動ポリシー π による選択と一致していたと考える） 行動ポリシー π に従ったアクション
81. モンテカルロ法による価値反復法の実装 81 • つまり、状態価値関数の推定と同様に、3つ組データを後ろからスキャンする方法で行動- 状態価値関数の推定（サンプルデータによる推定値の更新）が可能 ◦ ただし、エピソードの最初のアクションは、ランダムに選択することが必要（さもなくば、行動ポ リシー π に従うアクションのデータしか集まらなくなる） • エピソードのデータを収集するごとに、次を実施することで価値反復法が実現できる ◦ エピソードに含まれるペア　　　 に対する行動-状態価値関数　　　　を更新 ◦ 状態 S の行動ポリシーを更新
82. 価値反復法のアルゴリズム（復習） 82 • 今の場合は、行動-状態価値関数の計算をサンプルデータによる更新に置き換える 不要 サンプルデータ による更新 エピソードの開始状態 s を ランダムに選択すること 繰り返す サンプル データ収集 サンプルデータ（エピソード） に含まれる状態 s について実施
83. コードによる確認 83 • ノートブック「Chapter04/　 03_Gambler's_Problem_Value_Iteration.ipynb」 を参照 ※ 得られる行動ポリシーが乱雑に見えるのは、 　最善の行動ポリシーが一意でないことによる さまざまな最善の行動ポリシーの例 07_Gambler's_Problem_Optimal_Policies.ipynb 前半は50ポイントを 得る最善のポリシー
84. コードによる確認 84 def policy_update(gambler, s): q_max = -10**10 a_best = None for a in range(1, s+1): if gambler.q[(s, a)] > q_max: q_max = gambler.q[(s, a)] a_best = a gambler.policy[s] = a_best 行動ポリシーを アップデートする関数 def train(gambler, num): c = 0 while c < num: episode = get_episode(gambler) episode.reverse() total_r = 0 for (s, a, r) in episode: total_r += r gambler.cnt[(s, a)] += 1 gambler.q[(s, a)] += (total_r - gambler.q[(s, a)]) / gambler.cnt[(s, a)] policy_update(gambler, s) c += len(episode) 収集データの順序を反転 Greedy ポリシー　　 を Python ディクショナリーとして実装 モンテカルロ法による 価値反復法を実装した関数 行動-状態価値関数　　　　を更新すると 同時に行動ポリシーをアップデート
85. モンテカルロ法による価値反復法の課題 85 • （最初のアクションを除いて）Greedy ポリシー　　　　　　　　　　　に従ってエピソー ドを収集する場合、問題によってはエピソードが完了しない可能性がある ◦ 実物の迷路をロボットを走行させてデータを集める場合を考える（迷路の任意の位置 からはスタートできず、必ず迷路の入り口からエピソードを始める） ◦ 初期の行動ポリシー（特に確率的要素を含まない Greedy ポリシー）では、永遠に出 口に到達できず（総報酬が確定しないので）学習処理ができない • 一般には ε-greedy ポリシーでランダムなアクションを混ぜるべきで、これにより（偶然 に）ゴールできる可能性が生まれる。 ◦ しかしながら、この場合、得られた総報酬は　　　　　 の推定には使えない・・・ 次ページで紹介する、後半の一部のデータ だけを学習に使うワークアラウンドを用いる
86. 行動ポリシー　　 に一致 オフポリシーデータの部分的な利用 86 • ε-greedy ポリシーで行動した結果、次のエピソードが得られたとする ◦ この場合、　 以降の次のエピソードは、学習に使用できる ◦ つまり、終了状態から前に向かってスキャンしていき、行動ポリシーに一致しないア クションを発見した時点で処理を終える（それより前のデータは捨てる） ※ 学習対象の行動ポリシー π と異なる行動ポリシーで収集したデータを一般に「オフポリシーデータ」 　と言う ⇨ モンテカルロ法では、最初のアクション以外はオンポリシーデータを使う必要がある 行動ポリシー　　 に一致 行動ポリシー　　 に不一致
87. オフポリシーデータの部分的な利用 87 • 行動ポリシーに一致しないアクションより前のデータは捨てるので、一般には、終状態に近 い部分しか学習できない恐れがある • 学習の進捗に応じて ε を徐々に小さ くすることで、ある程度は長距離に 渡る学習にも対応できる
88. →（中略）→ epsilon=0.899 　　epsilon=0.897 　　epsilon=0.896 　　epsilon=0.890 ############　　　############　　　############　　　############ #S #　　　#S #　　　#S #　　　#S # # #　　　# #　　　# #　　　# # ####### #　　　####### #　　　####### #　　　####### # # #　　　# #　　　# #　　　# # # #　　　# #　　　# #　　　# # # #######　　　# #######　　　# #######　　　# ####### # #　　　# #　　　# #　　　# # # +G#　　　# ++G#　　　# ++G#　　　# +++G# ############　　　############　　　############　　　############ 　　epsilon=0.885 　　epsilon=0.873 　　epsilon=0.806 　　epsilon=0.670 　　############　　　############　　　############　　　############ 　　#S #　　　#S #　　　#S #　　　#S # 　　# #　　　# #　　　# #　　　# # 　　####### #　　　####### #　　　####### #　　　####### # 　　# #　　　# #　　　# #　　　# # 　　# #　　　# #　　　# #　　　# # 　　# #######　　　# #######　　　# #######　　　# ####### 　　# ++ #　　　# ++ #　　　# #　　　# + # 　　# +++G#　　　# +++G#　　　# +++++++G#　　　# ++++++G# 　　############　　　############　　　############　　　############ 　　　　　　　epsilon=0.264 　　epsilon=0.241 　　epsilon=0.226 　　　　　　　############　　　############　　　############ 　　　　　　　#S #　　　#S #　　　#S++ # 　　　　　　　# +++ #　　　# +++++ #　　　# +++++ # 　　　　　　　#######+++ #　　　#######+++ #　　　#######+++ # 　　　　　　　# + #　　　# + #　　　# + # 　　　　　　　# ++++++ #　　　# ++++++ #　　　# ++++++ # 　　　　　　　# +#######　　　# +#######　　　# +####### 　　　　　　　# +++++++#　　　# +++++++#　　　# +++++++# 　　　　　　　# G#　　　# G#　　　# G# 　　　　　　　############　　　############　　　############ → → → → → → → → → コードによる確認 • ノートブック「Chapter04/　 04_Maze_Solver_Monte_Carlo.ipynb」を参照 学習の初期は、エピソードが非常に長い （ゴールに到達するのに時間がかかる） 1ステップごとに -1 の報酬を与えて 最短経路を学習させる 88
89. コードによる確認 89 def get_episode(agent, epsilon): episode = [] s = (1, 1) # Start while True: if np.random.random() < epsilon: a = agent.actions[np.random.randint(len(agent.actions))] else: a = agent.policy[s] r, s_new = agent.move(s, a) episode.append((s, a, r)) x, y = s_new if agent.maze[y][x] == 'G': break s = s_new return episode def train(agent, epsilon, min_epsilon): episode_lengths = [] max_data_length = 0 while True: episode = get_episode(agent, epsilon) episode_lengths.append(len(episode)) episode.reverse() total_r = 0 last = False data_length = 0 for (s, a, r) in episode: data_length += 1 if a != agent.policy[s]: last = True total_r += r agent.cnt[(s, a)] += 1 agent.q[(s, a)] += (total_r - agent.q[(s, a)]) / agent.cnt[(s, a)] policy_update(agent, s) if last: break モンテカルロ法による 価値反復法を実装した関数 １回分のエピソードを シミュレーションする関数 3つ組データ　　　　を収集 ε-greedy ポリシーで行動 収集データの順序を反転 行動ポリシーと異なるアクション を処理したら、そこでこのエピ ソードに関する処理を打ち切り
90. 演習 & 休憩 • 余裕のある方は、「コードによる確認」の説明を参考にしながら、以下のノートブックを 見て、コードの実装を理解してみてください。 ◦ Chapter04/02_Gambler's_Problem_Value_Estimation.ipynb →　サンプリングによる状態価値関数の推定 ◦ Chapter04/03_Gambler's_Problem_Value_Iteration.ipynb →　モンテカルロ法による価値反復法 　（サンプリングによる行動-状態価値関数の推定と行動ポリシーのアップデート） ◦ Chapter04/04_Maze_Solver_Monte_Carlo.ipynb →　ε-greedy ポリシーを用いたモンテカルロ法（オフポリシー学習） 90
91. TD 法（Q-Learning）
92. モンテカルロ法の根本課題と対応策 92 • モンテカルロ法は、エピソードが完了するまで、学習処理（行動-状態価値関数　　　　の 更新）が実行できない ◦ これは、サンプリング固有の問題ではない。状態遷移確率　　　　　　が分かってい ても、原理的にはバックアップ図を終了状態までたどらなければ総報酬は確定しない ◦ 動的計画法では、状態価値関数に対するベルマン方程式を用いることで、「状態 s の 状態価値関数　　　を次のステップ s' の状態価値関数　　　で計算」できた • 同様にして「行動-状態価値関数に対するベルマン方程式」を用いると、エピソードの完了 を待たずに行動-状態価値関数　　　　の更新ができるようになる TD（Temporal Difference）法
93. （復習）行動-状態価値関数の定義 93 • 行動-状態価値関数　　　　は、現在の状態 s におい て、「アクション a を選択して、その後は行動ポリ シー π に従って行動を続けた場合」に得られる総報 酬の期待値を表す ◦ 右のバックアップ図より、次で計算される ◦ 次はベルマン方程式と同じ関係式 特定のアクション a を選択した 際の総報酬　　　　 をさまざまな アクションについて平均化
94. 行動-状態価値関数に対するベルマン方程式 94 • 決定的ポリシー　　 を前提とする場合、状態価値関数のベルマン方程式は次のように変形 できる（Q-Learning は Greedy ポリシー　　　　　　　　　　　を学習するのでこの前提 は成り立つ） • これを次の関係に代入 行動-状態価値関数に 対するベルマン方程式 確率 1 で　　　　 を選択
95. Q-Learning の考え方 95 • 「行動-状態価値関数に対するベルマン方程式」は　　　　　 　　　の期待値計算と見る ことができる • 今は状態遷移確率　　　　　　 が分からないので、厳密な期待値の代わりにサンプリング で収集したデータによる平均値で推定する • より簡単に、一定の重み α で更新する手法を採用すると次の更新ルールが得られる ⇨ 1回のアクションで　　　　　の4つ組データを得ると、　　　 が上式で更新できる 本質的には、この部分の 「期待値」を計算している
96. （参考）サンプリングによる期待値の近似計算 (1/2) 96 • 確率分布 p(x) に従う確率変数 X について、実際に発生した X の値を集めたサンプルを 　　　　 　　とする • この時、X から計算される関数 f (X) の期待値は次のように近似できる • サンプルを収集しながら近似値（推定値）を更新するのであれば、つぎの手順になる 　　　　　　　　　　　　 n - 1 個目までのデータ による推定値 n 個目のデータ　 を加えた推定値
97. （参考）サンプリングによる期待値の近似計算 (2/2) 97 • （非定常状態にも対応できるように）一定の重み α で更新する方法を採用すると次になる • 行動-状態価値関数について、次の近似計算を考える ※ 左辺の　　 は定数で、右辺の　　　 は実際に観測されたサンプルである点に注意 • サンプルを収集しながら右辺の推定値を更新するなら次のルールになる
98. Q-Learning の手続き 98 • ランダムなアクションを混ぜた ε-greedy ポリシーで行動した結果、次の状態変化が得られ たとする • 最初のステップの4つ組　　　　　　 　 を用いて次の更新ができる ◦ アクション　 は学習対象の行動ポリシーに一致していなくても構わない点に注意 • 次のステップの4つ組　　　　　　 　 でも同様の更新が可能 ◦ 結局の所、すべてのステップについて行動-状態価値関数の更新が行える
99. Q-Learning の実装 99 • ε-greedy ポリシーでエージェントを行動させながら、次の処理を継続する ◦ 状態 s でアクション a を選択した結果、報酬 r を得て次の状態が s' に変化 ◦ 行動-状態価値関数の値を更新する ◦ 状態 s に対する行動ポリシーを更新する • 学習対象の行動ポリシー（Greedy ポリシー）に対して、さらにランダムなアクションを混ぜた ε-greedy ポリシーで学習データを収集している点に注意（オフポリシーデータによる学習） ⇨ ランダムなアクションを混ぜないと特定経路の学習しかできない恐れがある
100. （参考）Q-Learning とモンテカルロ法の比較 100 • モンテカルロ法における行動-状態価値関数の更新：オンポリシーデータによる学習 • Q-Learning における行動-状態価値関数の更新：オフポリシーデータによる学習 ・・・ 実際に得られた総報酬 直後の報酬 + その後の報酬（の推定値） エピソードが完了する ごとにまとめて更新 1回のアクション ごとに更新が可能 ランダムなアクションより 前のデータは捨てる必要がある ε-greedy ポリシーで集めた すべてのデータが利用できる
101. コードによる確認 101 • ノートブック「Chapter04/05_Maze_Solver_Q_Learning.ipynb」を参照 ◦ 1ステップごとに -1 の報酬が入るので、同じ場所をウロウロしていると、その付近 の行動-状態価値関数の値はどんどん小さくなる ◦ 結果として、初期段階から、まだ訪れていない場所に積極的に移動する（行動-状態 価値関数の値が初期値 0 のアクションを選択する）ようになり、モンテカルロ法 （初期段階ではランダムな行動だけでゴールを目指す）より早くゴールに到達できる エピソードの長さが急速に減少する ############ #++++++ # # ++ # #######+ # # ++ # # +++ # # +####### # ++ # # +++++G# ############
102. 102 def get_episode(agent, epsilon, train): episode = [] s = (1, 1) # Start while True: if np.random.random() < epsilon: a = agent.actions[np.random.randint(len(agent.actions))] else: a = agent.policy[s] r, s_new = agent.move(s, a) episode.append((s, a, r)) if train: agent.q[(s, a)] += 0.2 * (r + agent.q[(s_new, agent.policy[s_new])] - agent.q[(s, a)]) policy_update(agent, s) x, y = s_new if agent.maze[y][x] == 'G': break s = s_new return episode １回分のエピソードを シミュレーションする関数 エピソードの収集と同時に 行動-状態価値関数　　　　、 および、行動ポリシーを更新 ε-greedy ポリシーで行動 コードによる確認
103. コードによる確認 103 • まだ訪れていない場所を積極的に探索する効果により、Q-Learning では、モンテカルロ 法では困難な「長距離の学習」が可能になる
104. TD 法（SARSA）
105. 行動-状態価値関数に対するベルマン方程式（一般形） 105 • 先ほど導いた行動-状態価値関数に対するベルマン方程式は、　　　 に基づいた Greedy ポリシー　　 が前提 • 一般の行動ポリシー　　　　の場合は、「行動-状態価値関数の定義」で示した次の関係 式を組み合わせる
106. 行動-状態価値関数に対するベルマン方程式（一般形） 106 • Q-Learning で用いたベルマン方程式と比較すると、次のアクション a に加えて、さらに その次のアクション a' が方程式に含まれていることがわかる ◦ SALSA で用いるベルマン方程式 ◦ Q-Learning で用いるベルマン方程式 その次のアクション a' は、 Greedy ポリシーで決まる その次のアクション a' についての期待値を計算
107. SARSA の考え方 107 • SARSA では、Greedy ポリシーを前提とせず、「一般形の行動-状態価値関数に対するベ ルマン方程式」で行動-状態価値関数　　　　を更新する • 一般の行動ポリシー π で次の状態変化が得られたとする ◦ 冒頭の5つ組のデータ　　　　　　　　　 は、上記のベルマン方程式に含まれる 　　　　　　に対応すると考えて、次の更新を行う 次のアクション A 0 に加えて、さらに 次のアクション A 1 も計算に使用する
108. SARSA の考え方 108 • 後に続くすべての5つ組で同様の更新ができるので、結局、エピソードを収集しながら、5 つ組　　　　　　 による更新を継続することができる ※ Q-Learning では最後の a' を使用せずに行動-状態価値関数を更新していた点に注意 • 上記の更新と並行して、状態 s に対する行動ポリシーを Greedy ポリシーで更新すれば、 （価値反復法と同様に）行動ポリシーが改善されていく Greedy ポリシーで決まる アクションを指定
109. SARSA の問題点（致命的な課題） 109 • SARSA が前提とするベルマン方程式では、最後のアクション a' は、行動ポリシー　　　 に従って確率的に選ばれたアクションになっている ◦ つまり、学習対象の行動ポリシー π で集めたデータでなければ、得られた5つ組みは （ベルマン方程式が前提とする確率を反映した）適切なサンプルにはならない ◦ 一方、実際の学習対象の行動ポリシー π は（ランダムなアクションを含まない） Greedy ポリシーなので、これでは、収集されるエピソードに偏りが生じて学習が進 まなくなる。どうしよう・・・
110. SARSA の実装方法 110 • SARSA を実装する際は、理論的な厳密性は犠牲にして、確率 ε でランダムな行動をまぜた ε-greedy ポリシーでデータを収集する ◦ これを学習対象の Greedy ポリシーによるデータと勘違いした状態で学習を進める ◦ 結果として、厳密に最善の行動ポリシーを達成することはできなくなるが、実用上、 十分に有用な結果が得られればそれでよしとする ※ 歴史的には、SARSA の後に、その改善版として Q-Learning が考案されており、 　実用上は、Q-Learning を用いた方がよい
111. コードによる確認 111 • ノートブック「Chapter04/06_Maze_Solver_SARSA.ipynb」を参照 学習の効率はそれほど悪くない ############ #++++++ # # ++ # #######+ # # ++++ # # + # # +####### # +++++++# # G# ############ 最短経路の学習に成功 （より複雑な問題では最適解 　を得られるとは限らない）
112. 112 def get_episode(agent, epsilon, train): episode = [] s = (1, 1) # Start if np.random.random() < epsilon: a = agent.actions[np.random.randint(len(agent.actions))] else: a = agent.policy[s] while True: r, s_new = agent.move(s, a) episode.append((s, a, r)) if np.random.random() < epsilon: a_new = agent.actions[np.random.randint(len(agent.actions))] else: a_new = agent.policy[s_new] if train: agent.q[(s, a)] += 0.2 * (r + agent.q[(s_new, a_new)] - agent.q[(s, a)]) policy_update(agent, s) x, y = s_new if agent.maze[y][x] == 'G': break a = a_new s = s_new return episode １回分のエピソードを シミュレーションする関数 その次アクション a' をε-greedy ポリシーで選んでおいて… コードによる確認 アクション a' に対する 行動-状態価値関数の値を用いる 事前に選んであった 次のアクション a' を 次のループで使用する
113. SARSA が失敗する例 113 • ノートブック「Chapter04/　 08_Maze_Solver_Q_Learning_vs_SARSA.ipynb」を参照 ◦ 上部の「----------」は「崖」になっており、ここに落ちると -100 の 報酬と共にスタート地点に戻る ◦ ε-greedy ポリシーで最短経路付近のパスを通ると頻繁に崖に落ちる ◦ SARSA はこれを「学習対象の行動ポリシーの結果」とみなして、崖を 大きく避けるパスを学習する ◦ Q-Learning は収集データの内容と学習対象の行動ポリシーを区別する ので、正しく最短経路を学習する #----------# #+++++++++G# # #### # # #### # # # # # # # ############ #----------# #+ G# #+ #### +# #+ ####+++# #++++++++ # # # # # ############ Q-Learning の結果 SARSA の結果
114. SARSA が失敗する理由（詳細） 114 • 例えば、ε-greedy ポリシーでデータを収集した際に次のデータが得られたとする ◦ 現在の状態 s：崖の横（最短経路上） ◦ 次のアクション a：右に移動（最短経路上） ◦ その次のアクション a'：上に移動（崖に落ちる） • SARSA の場合、その次のアクション a' を含めて評価する • Q-Learning の場合、その次は最適なアクション　　 を選択したと仮定して評価する 崖に落ちるので負の値になる 　　　　　　 に一致する #----------# #++ G# # #### # # #### # # # # # # # ############ a a' →↑
115. 演習 & 休憩 • 余裕のある方は、「コードによる確認」の説明を参考にしながら、以下のノートブックを 見て、コードの実装を理解してみてください。 ◦ Chapter04/05_Maze_Solver_Q_Learning.ipynb →　Q-Learning による迷路の学習（迷路データを自由に変更して試してください） ◦ Chapter04/06_Maze_Solver_SARSA.ipynb →　SARSA による迷路の学習 115
116. 第５部 ニューラルネットワークによる関数近似
117. 状態価値関数の近似計算
118. 状態価値関数の実装方法（Tabular 方式） 118 • これまでのコードでは、Python のディクショナリーで状態価値関数を定義した ◦ 状態 s ごとに、対応する値　　　を個別に記憶する方式 ◦ 状態数が爆発的に増えるとメモリー不足で対応不可（たとえば、囲碁の盤面はおよそ 10172 通りあると言われる） class Gridworld: def __init__(self, size=8, goals=[7], penalty=0): … self.value = {} for s in self.states: self.value[s] = 0 状態価値関数を ディクショナリーで実装
119. 状態価値関数の実装方法（関数近似） 119 • 図の状態価値関数では、終了状態（s = 7）を除いて直線的に変化しているので、一次関数 　　　　　　　で表現できる ◦ 学習データを用いて w と b をチューニングすれば同じ結果が得られるはず class StateValue: def __init__(self, w, b): self.w = w self.b = b def get_value(self, s): w = self.w b = self.b return w*s+b 0 報酬：+1 1 2 3 4 5 6 7 終了状態 移動ごとに -1 の報酬 常に右に移動する行動ポリシー に対する状態価値関数 状態価値関数を 一次関数で実装
120. 状態価値関数の実装方法（関数近似） 120 • 一般には、一次関数で表現できるとは限らな いが、多数のパラメーターを持つニューラル ネットワークを用いれば、複雑な状態価値関 数も高い精度で近似できると期待される 活性化関数 ReLU
121. ニューラルネットワークの学習方法 121 • ニューラルネットワークは、正解ラベル付きのトレーニングデータを用いた「教師あり学 習」でチューニングを行うが、今の場合、状態価値関数の値そのものは用意できない 常に右に移動する行動ポリシーに対して 得られるデータ対応する正解ラベル • ベルマン方程式を見ると、　　　　　 の期待値とし て状態価値関数が計算できることがわかる ⇨ 収集データから計算した　　　　　 を正解ラベル 　として学習すればよい 正解ラベル ※ 同じ入力値 s に対して正解ラベルの値が複数ある場合、ニューラルネットワークは、 　それらの平均値を出力するように学習されると期待できる
122. ニューラルネットワークの学習方法 122 • 正解ラベルの値は、現時点でのニューラルネットワークの出力を用いて計算するので、学 習が進むと正解ラベルの値も変化する 常に右に移動する行動ポリシーに対して 得られるデータ対応する正解ラベル ◦ データ収集後に「正解ラベルの計算 → 学習」の ループを繰り返すと、学習初期は正解ラベルの 値はほとんどが不正確だが、少なくとも終了状 態の直前（s = 6）に対しては正しい値をとる ◦ その結果、　　 は正しい値を出力するように学 習されて、その手前の状態（s = 5）に対する正解 ラベルも正しい値に近づく ◦ この繰り返しで全体的に正しい値に近づく
123. ニューラルネットワークで状態価値関数を学習する手順 123 • 行動ポリシー π でエージェントを行動させながら、次の処理を繰り返す ◦ 　　　 の3つ組データを一定量収集する ◦ それぞれの3つ組から、状態 s と正解ラベル　　　　　 のペア（学習データ）を用意 する ◦ 上記の学習データでニューラルネットワークの教師あり学習（バッチ処理）を行う ※ ここでは、非定常状態にも対応できるように、データ収集と学習を並列に行っている • 教師あり学習（バッチ処理）を行うと状態価値関数の出力　　 が変わるので、正解ラベル の再計算が必要な点に注意
124. コードによる確認 124 • ノートブック「Chapter05/01_Neural_Network_Policy_Estimation_1.ipynb」を参照 Iteration 1: [ -0.0 0.9 1.9 2.9 3.9 4.9 5.9 0.0 ] Iteration 2: [ 0.1 0.7 1.2 1.8 2.4 3.0 3.5 0.0 ] Iteration 3: [ 0.2 0.5 0.8 1.1 1.4 1.7 2.0 0.0 ] Iteration 4: [ -0.4 -0.1 0.1 0.4 0.6 0.9 1.1 0.0 ] Iteration 5: [ -1.1 -0.8 -0.5 -0.2 0.1 0.4 0.7 0.0 ] Iteration 6: [ -1.9 -1.5 -1.1 -0.7 -0.3 0.1 0.4 0.0 ] Iteration 7: [ -2.4 -2.0 -1.5 -1.0 -0.5 -0.1 0.4 0.0 ] Iteration 8: [ -3.1 -2.5 -1.9 -1.3 -0.7 -0.1 0.4 0.0 ] Iteration 9: [ -3.7 -3.0 -2.3 -1.6 -0.9 -0.2 0.5 0.0 ] Iteration 10: [ -4.2 -3.4 -2.6 -1.8 -1.0 -0.1 0.7 0.0 ] Iteration 11: [ -4.6 -3.7 -2.8 -1.9 -1.0 -0.1 0.8 0.0 ] Iteration 12: [ -4.8 -3.9 -2.9 -2.0 -1.0 -0.1 0.8 0.0 ] Iteration 13: [ -5.0 -4.0 -3.0 -2.0 -1.1 -0.1 0.9 0.0 ] Iteration 14: [ -5.0 -4.0 -3.0 -2.0 -1.0 -0.0 1.0 0.0 ] Iteration 15: [ -5.1 -4.1 -3.0 -2.0 -1.0 -0.0 1.0 0.0 ] Iteration 16: [ -5.1 -4.1 -3.0 -2.0 -1.0 -0.0 1.0 0.0 ] Iteration 17: [ -5.1 -4.0 -3.0 -2.0 -1.0 -0.0 1.0 0.0 ] Iteration 18: [ -5.0 -4.0 -3.0 -2.0 -1.0 -0.0 1.0 0.0 ] Iteration 19: [ -5.0 -4.0 -3.0 -2.0 -1.0 -0.0 1.0 0.0 ] Iteration 20: [ -5.0 -4.0 -3.0 -2.0 -1.0 0.0 1.0 0.0 ] def build_model(self): state = layers.Input(shape=(1,)) value = layers.Dense(1)(state) model = models.Model(inputs=[state], outputs=[value]) model.compile(loss='mse') return model ◦ 一次関数をニューラルネットワーク として定義して学習を実施 正しい状態価値関数 　　　 の値を達成 ニューラルネットワークの定義
125. コードによる確認 125 def train(world, state_value, num): for c in range(num): print('Iteration {:2d}: '.format(c+1), end='') examples = [] for _ in range(100): episode = get_episode(world) examples += get_episode(world) np.random.shuffle(examples) states = [] labels = [] for s, r, s_new in examples: states.append(np.array([s])) v_new = state_value.get_value(s_new) labels.append(np.array(r + v_new)) state_value.model.fit([np.array(states)], np.array(labels), batch_size=50, epochs=100, verbose=0) show_values(world, state_value) class StateValue: def __init__(self, goals): self.goals = goals self.model = self.build_model() def build_model(self): state = layers.Input(shape=(1,)) value = layers.Dense(1)(state) model = models.Model(inputs=[state], outputs=[value]) model.compile(loss='mse') return model def get_value(self, s): if s in self.goals: return 0 input_states = [np.array([s])] output_values = self.model.predict([input_states]) value = output_values[0][0] return value 状態価値関数　　 をニューラル ネットワークで計算するクラス 状態価値関数の値を返すメソッド モデルの predict メソッドで予測処理 100 エピソード分のデータを 集めて、結果をシャッフル 正解ラベル　　　　　　を計算 ミニバッチで学習処理を実施 学習処理を実行する関数
126. コードによる確認 126 • ノートブック「Chapter05/　 02_Neural_Network_Policy_Estimation_2.ipynb」を参照 ◦ 「16ノード＋8ノード」の隠れ層を持つ多層ニューラル ネットワークで右上のグリッドワールドを学習 Iteration 50: [ -15.0 -15.7 -16.7 -16.9 -4.2 ] [ -12.0 -12.9 -14.4 -16.0 -3.6 ] [ -9.6 -10.1 -11.9 -14.6 -2.9 ] [ -7.5 -8.0 -9.0 -11.6 -2.2 ] [ -6.2 -5.2 -4.2 -3.1 -2.5 -1.5 ] [ -5.2 -4.2 -3.2 -2.2 -1.3 0.0 ] def build_model(self): state = layers.Input(shape=(2,)) hidden1 = layers.Dense(16, activation='relu')(state) hidden2 = layers.Dense(8, activation='relu')(hidden1) value = layers.Dense(1)(hidden2) model = models.Model(inputs=[state], outputs=[value]) model.compile(loss='mse') return model ニューラルネットワークの定義
127. （参考）ニューラルネットワークの特徴 127 • ニューラルネットワークは、入力値の領域を一定 の区画に分けて、区画ごとの特性を表現するのに 適している • したがって、状態数が増加しても区画ごとの特性 が変わらなければ、同じサイズのニューラルネッ トワークで適切な近似が可能 ◦ 右図は前ページと同じサイズのニューラル ネットワークでより大きなグリッドワールド を学習した結果
128. DQN（Deep Q Network）
129. ニューラルネットワークによる行動-状態価値関数の学習 129 • ニューラルネットワークで行動-状態価値関数　　　　を近似して、Q-Learning を適用す ることを考える • 行動-状態価値関数に対するベルマン方程式を見ると、　　　　　　　　を正解ラベルとし て学習すればよいことがわかる 正解ラベル
130. ニューラルネットワークで行動-状態価値関数を学習する手順 130 • 具体的には、入力　　　から　　　　の推定値を出力するニューラルネットワークを用意し て、次の処理を繰り返す ◦ ε-greedy ポリシーでエージェントを行動させて　　　 の4つ組データを一定量収 集する ◦ それぞれの4つ組から、入力　　　と対応する正解ラベル　　　　　 　　 のペア （学習データ）を用意する ◦ 上記の学習データでニューラルネットワークの教師あり学習（バッチ処理）を行う • 行動ポリシーはディクショナリーとして保存するのではなく、毎回、行動-状態価値関数　　　 の出力 を計算して、これが最大になるアクション a を選択する ⇨ 教師あり学習（バッチ処理）を行うと行動-状態価値関数の出力が変わるので、それに伴って行動結果 　も変わり、より広い範囲の学習データが収集できるようになる
131. 「あるけあるけゲーム」 131 • 次のようなゲームの自動プレイエージェントを学習する ◦ 14 × 14 の画面上に壁（#）と障害物（X）を配置 ◦ プレイヤー（*）は上下左右に移動 ◦ 移動した場所には新たな障害物（+）が配置される ◦ 障害物に当たらずに長く移動を続けることを目指す
132. 状態の定義 132 • 障害物の配置が固定的であれば、プレイヤーの 座標 (x, y) を状態 s とすればよい • 今の場合、障害物の配置が動的に変化するの で、障害物を含めた「画面全体」を状態 s とみ なす必要がある ◦ 右図のように2レイヤーからなる数値デー タに変換して、ニューラルネットワークに 入力する
133. ニューラルネットワークの構造 133 • 行動-状態価値関数　　　　を表現するために、アクション a と結合して入力する One-hot 表現
134. 畳み込みフィルターの仕組み 134 • 畳み込みフィルターを用いて、プレイヤーに隣接する障害物の情報を特徴量として抽出
135. 畳み込みフィルターの仕組み 135 • 複数レイヤー画像に畳み込みフィル ターを適用すると、レイヤー間の相関 関係も抽出できる
136. データ収集と学習の流れ 136 • ε-greedy ポリシーによるデータ収集と、「正解 ラベルの計算＋学習処理」を繰り返す ◦ 4つ組データ　　　　　 から、入力値と正 解ラベルのペア　　　　　　　　　　　　 を生成 • 過去データを保存して再利用する ◦ 過去のデータと直近のデータを適切に混ぜ ることで、Explore と Exploitation のバラ ンスを取る（Experience Replay）
137. コードによる確認 137 • ノートブック「Chapter05/03_Walk_Game_Training.ipynb」を参照 ◦ 平均して20ステップ程度進めるエージェントが学習される def build_model(self): cnn_input = layers.Input(shape=(14, 14, 2)) cnn = layers.Conv2D(8, (5, 5), padding='same', use_bias=True, activation='relu')(cnn_input) cnn_flatten = layers.Flatten()(cnn) action_input = layers.Input(shape=(4,)) combined = layers.concatenate([cnn_flatten, action_input]) hidden1 = layers.Dense(2048, activation='relu')(combined) hidden2 = layers.Dense(1024, activation='relu')(hidden1) q_value = layers.Dense(1)(hidden2) model = models.Model(inputs=[cnn_input, action_input], outputs=q_value) model.compile(loss='mse') return model ############## # # # x # #x x # # x x x# # *++ x# # +++# # ++ +++# # ++x + # # +++++++ # # # # x # # x # ############## Length: 21 ニューラルネットワークの定義
138. コードによる確認 138 def train(environ, q_value, num): experience = [] for c in range(num): for n in range(50): if n % 10 == 0: epsilon = 0 else: epsilon = 0.2 episode, _ = get_episode(environ, q_value, epsilon) experience += episode if len(experience) > 10000: experience = experience[-10000:] examples = experience[-200:] + random.sample(experience[:-200], 400) np.random.shuffle(examples) states, actions, labels = [], [], [] for state, a, r, state_new in examples: states.append(np.array(state)) action_onehot = np.zeros(len(environ.action_map)) action_onehot[a] = 1 actions.append(action_onehot) if not state_new: # Terminal state q_new = 0 else: _, q_new = q_value.get_action(state_new) labels.append(np.array(r + q_new)) q_value.model.fit([np.array(states), np.array(actions)], np.array(labels), batch_size=50, epochs=100, verbose=0) ※ 主要部分のみ抜粋 学習処理を実行する関数 50 エピソード分のデータを追加して、 過去10,000 個のデータを保存 10 回に 1 回は Greedy ポリシーを用いる 正解ラベルを作成して ミニバッチで学習を実施 直近のデータ 200 個と、それ以 前のデータからランダムに選んだ 400 個を集めてシャッフル
139. （参考）モンテカルロ・ツリーサーチによる実行時の先読み 139 • 実行時に（学習済みのモデルを用いて）複数のパスを選択した上で、ゲーム終了まで再シ ミュレーションすることで、精度を向上するテクニック • シミュレーション結果から 行動-状態価値関数（の予 測値）を更新した上で最適 なアクションを選択 ※ ニューラルネットワークそのものを追加学習する 　わけではなく、選択したパスに対する行動-状態価 　値関数の予測値をメモリー上に保存して、モンテ 　カルロ法で一時的にアップデートする
140. コードによる確認 140 ############## #x x x # # +++x x # # x + ++ # # +++++ + # # +++++++++ # # ++ x+ + # # +++++ ++++ # # + ++ + + # # + +++++ + # # ++++ ++# # x x*# # # ############## Length: 53 • ノートブック「Chapter05/04_Walk_Game_with_Search.ipynb」を参照 ◦ 実行時に「もう一歩だけ追加で先を読む」処理を追加 ◦ 現在の状態 s からすべてのアクション a に対して、報酬 r と次の状 態 s' をシミュレーションで取得して、　　　　　　　　が最大に なるアクションを選択 ◦ これは、行動-状態価値関数に対するベルマン方程式を用いた更新 を1回だけ追加で行っていると考えられる 通常の Greedy ポリシーではこれが 最大になるアクションを選択 ここでは、これが最大になる アクションを選択
141. 演習 & 休憩 • 余裕のある方は、「コードによる確認」の説明を参考にしながら、以下のノートブックを 見て、コードの実装を理解してみてください。 ◦ Chapter05/01_Neural_Network_Policy_Estimation_1.ipynb →　単純な一次関数で表される行動-状態価値関数を学習 ◦ Chapter05/03_Walk_Game_Training.ipynb →　「あるけあるけゲーム」の学習（最後に学習済みのモデルを保存します） ◦ Chapter05/04_Walk_Game_with_Search.ipynb →　先に保存した学習済みのモデルを用いて「一手だけ先を読む」処理を追加 141
142. Copyright (C) 2022 National Institute of Informatics, All rights reserved.