強化学習「理論」入門

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

Transcript

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