![「状態の価値」とは？
特定の状態以降の収益の期待値を
「状態価値関数」と呼ぶ。
? ? = ?[??|?? = ?]
特定の状態で特定の行動をした後の
収益の期待値を「行動価値関数」と呼ぶ。
? ?, ? = ?[??|?? = ?, ? ? = ?]
18
このQがDQNのQ](https://image.slidesharecdn.com/2-170203040322/85/2-18-320.jpg)
![モンテカルロで状態価値を求める
状態価値
? ? = ?[??|?? = ?]
をどうすれば求められるか？
適当に試行錯誤して、得られた観測データの
平均値を取ればよい。*
…だけどこの方法は計算コストが大きい。
もっといい方法があるのでそれを見よう。
19
* ゲームの思考エンジンで「各局面からランダムにプレイして各手の勝率を求める」時
これは行動価値関数をこの方法で求めることに相当する。](https://image.slidesharecdn.com/2-170203040322/85/2-19-320.jpg)
![Vを変形
? ? = ? ?? ?? = ?
= ?[??+1 + ???+2 + ?2
??+3 + ? |?? = ?]
= ? ??+1 ?? = ? + ??[??+2 + ???+3 + ? |?? = ?]
? ??+1 ?? = ? = ?
?
?
?′
? ? ? ? ?′
?, ? ?(?, ?, ?′
)
? ??+2 + ???+3 + ? ?? = ?
= ?
?
?
?′
? ? ? ? ?′
?, ? ?(?′
)
20](https://image.slidesharecdn.com/2-170203040322/85/2-20-320.jpg)
![[DL輪読会]Control as Inferenceと発展](https://cdn.slidesharecdn.com/ss_thumbnails/20191004-191204055019-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会] マルチエージェント強化学習と心の理論](https://cdn.slidesharecdn.com/ss_thumbnails/0917imai-211210044729-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]近年のオフライン強化学習のまとめ —Offline Reinforcement Learning: Tutorial, Review, an...](https://cdn.slidesharecdn.com/ss_thumbnails/20200626journalclubpub-200630064755-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]Deep Learning 第2章 線形代数](https://cdn.slidesharecdn.com/ss_thumbnails/deeplearningchapter2-180601014406-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]`強化学習のための状態表現学習 －より良い「世界モデル」の獲得に向けて－](https://cdn.slidesharecdn.com/ss_thumbnails/20181026staterepresenration-181127055206-thumbnail.jpg?width=560&fit=bounds)
More Related Content
What's hot (20)
Viewers also liked (20)
More from nishio (20)
Recently uploaded (6)
强化学习その2
- 1. 強化学習 その2 2017-01-26 @ 機械学習勉強会 サイボウズ?ラボ 西尾泰和 関連スライド一覧 https://github.com/nishio/reinforcement_learning 2017-02-24 加筆
- 4. Sutton & Barto の新作 draftが読める。目次を一部紹介: 第1部: Tabular Solution Methods 6 Temporal-Difference Learning 8 Planning and Learning with Tabular Methods 第2部: Approximate Solution Methods 12 Eligibility Traces 13 Policy Gradient Methods 第3部: Looking Deeper 16 Applications and Case Studies 16.6 Human-Level Video Game Play 16.7 Mastering the Game of Go 16.8 Personalized Web Services 4 https://webdocs.cs.ualberta.ca/~sutton/book/the-book-2nd.html
- 5. 今後の予定 第1回(前回): 序章 1章 強化学習の基礎的理論 1節 強化学習とは 第2回: 2節 強化学習の構成要素 3節 価値反復に基づくアルゴリズム 第3回: 4節 方策勾配に基づくアルゴリズム 第4回: 5節 部分観测マルコフ决定过程 5
- 6. 今後の予定 第5回 2.1 統計学習の観点から見たTD学習 2.1.1 強化学習と教師付き学習の学習則 2.1.2~3 関数近似を(する/しない)価値関数推定 (ここまで28ページ) 第6回 2.1.4 セミパラメトリック統計学習に基づく定式 化(10ページ) 2.2 理論性能解析とベイズ (理論薄めでやる。13ページ) 6
- 7. 今後の予定 第7回 2.3 逆強化学習 第8回 2.4 経験強化型学習 2.5 群強化学習(飛ばします) 第9回 2.6 リスク考慮型強化学習 2.7 複利型強化学習(飛ばします) 第10回 3 強化学習の工学応用 3.3 対話処理における強化学習 7
- 8. 今後の予定 第11回 3.5 自然言語処理における逆強化学習と模 倣学習 第12回 3.7 深層学習を用いたQ関数の学習 (いわゆるDQN) 第13回 4 知能のモデルとしての強化学習 8
- 12. 環境をMDPで記述する 状態空間 ? = ?1, ?2, … , ? ? 行動空間 ?(?) = {?1, ?2, … , ? ?} 初期状態分布 ?0 状態遷移確率 ?(?′ |?, ?) 報酬関数 ?(?, ?, ?′) 時刻tの値 ??, ? ?, ?? 12
- 13. 環境をMDPで記述する 初期状態 ?0~?0 次の状態 ??+1~? ?′ ??, ? ? 報酬 ??+1 = ? ??, ? ?, ??+1 13 ??+1がtより前の状態や行動に依存していない ＝マルコフ性
- 14. 行動は？ 行動Aを決めるのは環境ではなくて エージェントなので上記枠組みにない。 方策 ? ? ? 行動 ? ?~? ? ?? 14 質疑Q: ? ?~? ? ??, ???1, ???2, … と考えてはダメか？ 現実的な実装は過去の全部の観測に依存するのでは？ A: 強化学習は学習によって?を更新していくので、 時刻tとt-1とで?が異なると考えればこの定式化でもその実装に矛盾しない。
- 15. 遅延報酬の扱い 報酬が即時でないので、 時刻tの報酬を個別に扱うのではなく、 まとめて「収益(return, income)」にする。 色々な方法がある。その1つが割引報酬和： ?? = ? ?=0 ∞ ? ? ??+1+? 15 ?は割引係数、0以上1未満の実数。ようは指数平滑平均。
- 18. 「状態の価値」とは？ 特定の状態以降の収益の期待値を 「状態価値関数」と呼ぶ。 ? ? = ?[??|?? = ?] 特定の状態で特定の行動をした後の 収益の期待値を「行動価値関数」と呼ぶ。 ? ?, ? = ?[??|?? = ?, ? ? = ?] 18 このQがDQNのQ
- 19. モンテカルロで状態価値を求める 状態価値 ? ? = ?[??|?? = ?] をどうすれば求められるか？ 適当に試行錯誤して、得られた観測データの 平均値を取ればよい。* …だけどこの方法は計算コストが大きい。 もっといい方法があるのでそれを見よう。 19 * ゲームの思考エンジンで「各局面からランダムにプレイして各手の勝率を求める」時 これは行動価値関数をこの方法で求めることに相当する。
- 20. Vを変形 ? ? = ? ?? ?? = ? = ?[??+1 + ???+2 + ?2 ??+3 + ? |?? = ?] = ? ??+1 ?? = ? + ??[??+2 + ???+3 + ? |?? = ?] ? ??+1 ?? = ? = ? ? ? ?′ ? ? ? ? ?′ ?, ? ?(?, ?, ?′ ) ? ??+2 + ???+3 + ? ?? = ? = ? ? ? ?′ ? ? ? ? ?′ ?, ? ?(?′ ) 20
- 21. ベルマン方程式 ? ? = ? ? ? ?′ ? ? ? ? ?′ ?, ? ? ?, ?, ?′ + ?? ?′ 同様に ? ?, ? = ? ?′ ? ?′ ? ?′ ?, ? ? ?, ?, ?′ + ?? ?′ ?′ ? ?′ , ?′ これをベルマン方程式と呼ぶ。 21
- 23. Sarsa SarsaはQを以下の式で更新する学習アルゴリズム： ? ??, ? ? ← ? ??, ? ? + ? ??+1 + ?? ??+1, ? ?+1 ? ? ??, ? ? ?は学習率(0以上1以下の実数) 下記ベルマン方程式ではs’やa’についてsumを取っているが、 それを「実際に出てきたもの」で置き換えて、 「Pやπは未知だけど、実際の観測をたくさん集めれば Pやπを掛けてsumしたのと同じところに収束するよね」 という発想。 ? ?, ? = ? ?′ ? ?′ ? ?′ ?, ? ? ?, ?, ?′ + ?? ?′ ?′ ? ?′, ?′ 23
- 24. On-policyとOff-policy 日本語だと「方策オン型/方策オフ型」と言う Sarsaの元になったベルマン方程式はπを含んでい る。つまり、方策πが変われば解も変わる。 (これを表現するために? ? (?, ?) と書いたりする) ? ?, ? = ? ?′ ? ?′ ? ?′ ?, ? ? ?, ?, ?′ + ?? ?′ ?′ ? ?′ , ?′ SarsaはOn-policy。 24
- 25. ベルマン最適方程式 価値Qがわかってるなら「価値が最大の行動をす る」という方策(greedy方策)が最適。じゃあベル マン方程式のπをその方策で置き換えたら？ ?? ?, ? = ? ?′ ? ?′ ? ?′ ?, ? ? ?, ?, ?′ + ?max ?′ ?? ?′ , ?′ これをベルマン最適方程式という。 25
- 26. Q学習(Q-learning) Q学習はQを以下の式で更新する学習アルゴ リズム： ? ??, ? ? ← ? ??, ? ? + ? ??+1 + ?max ?′ ? ??+1, ?′ ? ? ??, ? ? 要はSarsaのベルマン方程式をベルマン最適方程 式に変えたもの。Q学習は式に方策が入っていな いのでOff-policy。 26 解は方策の影響を受けないけど、探索範囲やどこを重点的に探索するかが 方策によって影響を受けるので、収束速度には影響があるよ。
- 27. 話のバックトラック Q: 何がしたかったんだっけ？ A: 最適な方策を見つけたい。そのためには大き く分けて2つ方法がある。 方法1：方策反復法 方策をモデル化して直接最適化する。 方法2：価値反復法 方策を「状態の価値」から計算できるものに 限定して、価値の推定を頑張る。 価値の推定方法(Sarsa, Q-learning)を2つ学んだ。 27
- 28. 理解の検証 自分が正しく理解できているかどうか 実装してみて検証したい。 今回学んだ範囲だと価値反復法だけだけど、 将来的に方策反復法や関数で近似する方法も 同じ問題設定で試してみたい。 28
- 30. 三目並べ 2人のプレイヤーが交互に○と×を書いて 先に3つ並んだ方が勝ちの有名なゲーム。 この片方のプレイヤーをエージェントとする。 環境： 盤面ともう片方のプレイヤー 行動： どこに書くか決めて、書く 報酬： 勝ったか負けたか 方策： 環境の状態と報酬を受け取って、行動を 決める関数 30
- 34. 実験 ランダム同士の対戦は1万回中 先手勝ち: 5785, 後手勝ち: 2918, 引き分け: 1297 だったので、0.578をベースラインとする。 Sarsa(先手)とランダム(後手)で10000試合し、 100試合ごとの勝率をプロットした。 Sarsaのパラメータ: π=greedy方策, α=0.5, γ=0.9 34
- 37. Qテーブルを観察 177147要素のQ巻数のテーブルのうち、 非ゼロの値が入っているのは450件だった。 17万要素は到達不能局面や非合法手を含む値 なので、実際の探索空間はもっと狭かった。 37
- 42. 話の流れの整理 話すことのキューが長くなってきたので整理 ? Sarsaを試したのでQ-learningを試して比較 ? Greedy方策を試したのでε-Greedy方策を 試して比較 ? その他 ? 状態を圧縮したら？ ? 指数平滑平均をやめたら？ 42
- 43. Q-LearningとSarsa+Greedy よしQ-Learningをためそう！と考えて： Sarsa: ? ??, ? ? ← ? ??, ? ? + ? ??+1 + ?? ??+1, ? ?+1 ? ? ??, ? ? Q-Learning: ? ??, ? ? ← ? ??, ? ? + ? ??+1 + ?max ?′ ? ??+1, ?′ ? ? ??, ? ? Sarsaにgreedy方策を組み合わせた場合、 同じ更新式になりそうに思うが、正しいか？ 43
- 53. 質疑 Q: なぜSarsaは崖から離れたのか？ A: 崖のそばが「確率εで-100食らう」低価値なマ ス目なので、価値の高い方に進んだ Q: 失敗時のダメージが大きい問題設定だとSarsa の方が常に良い？ A: とも言えない。問題設定次第。この狠狠撸の趣 旨は「Q学習が常に良いわけではない」 53
- 56. 付録: 状態とは何か？ 今までの実験では 「状態＝盤面」 としてきたがこれは正しいか？ 環境から観測できるすべての情報を元に 「情報が異なるなら、異なる状態である」 と考えるのは正しいか？ 56
- 63. 実験 (状態, 行動)対を圧縮する方法は3通り用意した。 まず行動で選ばれている場所を+3する。 回転?鏡映の8通りを全部6**9の整数にして 一番小さいものを取る(Sym) 3**9の盤面をまず各ラインに分解し((6**3) ** 8) ライン内をソート(6**3→18)、 各ラインもソートし、18**8のtupleにする(Line1) Line1の(6**3→18)の所で2色の駒が存在するor3を 含まないもの同一視(18→6)して6**8のtupleにす る(Line2) 63
- 64. 結果 Raw: 0.45+-0.16 Sym: 0.80+-0.19 Line1: 0.74+-0.14 Line2: 0.72+-0.12 どの圧縮手法も生の方法に比べて 2SD以上改善する Line*はもっと良くなると期待したのだが 意外とそうでもなかった。 64 (表記は「平均+-標準偏差*2」)
- 69. 付録: モンテカルロ木探索とは 原始的モンテカルロ(すべての手を同じ回数試行) は効率が悪い。 前回Multi-Armed Bandit問題で見たUCB1アルゴ リズムを用いて、有望そうな手を重点的に探索。 探索回数の多い手を1手先まで展開し minimaxな木探索と合体する →これがUCT(UCB applied to Trees) 69
- 71. 状態数の雑な見積もり 「16種類の駒+空欄」が16か所あるので 17^16 だから 4.6e+19。46エクサ個。 ……これはさすがにPythonのリストでは無理だ。 71 なおオセロが1e+28, チェスが1e+50, 将棋が1e+71, 囲碁が1e+160, という見積もりがあるので相対的にはかなりやさしい問題である
- 72. 少しマジメに見積もる マジメに考えるとn種類の識別される駒をmマス に置く、すべて置かなくてもよい置き方は ? ?, ? = ? ? + 1 … ? = 1 ?? ? ? 1, ? ? 1 + ? ?, ? ? 1 … else なので、 f(16, 16)=6199668952527617 f(15, 16)=1290434218669921 6e+13。4ケタ減ったけどまだペタ個オーダー。 72
- 73. scipy.sparse.dok_matrix たぶん到達不能局面が結構あると思うので 雑にdok_matrixにつっこむことにする。 dok_matrixはDictionary of Keys型スパース行列で ランダムアクセス性能がO(1)なので今回の目的に 適している。 <48661191875666868481x256 sparse matrix of type ‘<type ’numpy.float64‘>‘ with 0 stored elements in Dictionary Of Keys format> 無茶なサイズだが、問題なく動く。(see: 付録1) 73
- 74. 実験条件 Sarsa(後手)とランダムで100,000試合し、 Sarsaの1000試合ごとの勝率をプロットした。 ランダム同士の対戦は1万回中 先手勝ち: 5063, 後手勝ち: 4757, 引き分け: 180 だったので、0.475をベースラインとする。 Sarsaのパラメータ: π=greedy方策, α=0.5, γ=0.9 74
- 77. 結果 77
- 82. 参考文献 「コンピュータ囲碁における モンテカルロ法 ~ 理論編~」(2008年) http://minerva.cs.uec.ac.jp/~ito/entcog/contents/l ecture/date/20080614.html これからの強化学習 http://amzn.to/2josIJ1 Reinforcement Learning: An Introduction https://webdocs.cs.ualberta.ca/~sutton/book/ebo ok/the-book.html 82