『Pythonで学ぶ強化学習 入門から実践まで』を読んでみた 第二章

前回のおさらい

強化学習が学習するもの
1、行動の評価方法→期待報酬(価値)$G_{t}$で行う、また価値を算出することを価値評価という。
2、(評価に基づく)行動の選び方＝戦略 $\pi$

簡潔にいうと、
強化学習が学習するもの
1、価値評価の学習
2、戦略の学習

価値の定義と算出：Bellman Equation

第一章では以下のように「価値」を定義した。

行動選択の段階(時刻$t$)で「報酬の総和」を「見積もった」値で、将来の即時報酬については「割引率」を適用している。

$G_{t}:=r_{t+1}+\gamma r_{t+2}+\gamma ^{2}r_{t+3}+\cdots + \gamma ^{T-t-1}r_{T}$
$\;\;$ $\quad =\sum\limits_{k=0}^{T-t-1}\gamma^{k}r_{t+k+1}$

だが、この「価値」には2つの問題があり、そのまま計算するのは困難である。

• 問題1：将来の即時報酬の値($r_{t+1},r_{t+2},\ldots$)が判明している必要がある点。

• 問題2：将来の即時報酬が必ず得られる点。
  一方、実際行動しなければ即時報酬は分からない、また報酬の候補も複数あり、どれになるか確率的である。

• 解決1：式を再帰的に定義することで解決する。第一章で再帰的な式に変化したわけはここにある。

  $G_{t}:=r_{t+1}+\gamma G_{t+1}$
  再帰的な式を定義することで、将来の即時報酬$G_{t+1}$の計算を持ち越すことができる。$G_{t+1}$にいったん適当な値を入れて、$G_{t}$を計算することが可能。

つまり、計算時点将来の即時報酬が分からなくても大丈夫ということだ。

※また、後で詳しく説明するが、

動的計画法DPでは将来の即時報酬$G_{t+1}$について過去の計算値(キャッシュ)を使うことで計算する。これはメモ化という。

• 解決2：期待値を導入することで解決する。つまり、即時報酬に確率をかけること。

• 行動確率を定義できれば、行動の結果得られる報酬(即時報酬)に行動確率をかけることで期待値が計算できる。
• 戦略$\pi$に基づいて行動する場合、状態$s$で行動$a$をとる確率は$\pi(a|s)$となる。
• 発生しうる即時報酬の候補はいくつかあり、どれになるかは確率的になる。
• そのため、報酬の値は期待値(確率x値)で表すようにする(行動確率 x 即時報酬)。

この2つの問題を解決した式がBellman Equationです。
詳しくは戦略(Policy)ベース、価値(Value)ベースの部分で説明します。

※ところで、行動確率って何？初めて出てきたよって思うよね？
行動確率$\pi(a|s)$だそう、だが詳しい説明はされていない、、、

だが、この2つとはなんとなく違う
遷移確率$P_{a}\left( s,s'\right)$：右へ移動として実際に右へ移動できる確率
戦略$\pi$：状態を受け取り、行動を出力する関数

個人的に理解したところ、
行動確率$\pi(a|s)$：
戦略に基づいて行動する→　状態$s$を受け取り、行動$a$を出力する
状態$s$で行動$a$をとる確率→　ある状態(セル)から上下左右どの方向に行けるか確率が違う、それを行動確率$\pi(a|s)$と呼ぶ。だから4つあるかも、どうやって決まるか知らんけど。

入力：状態$s$
戦略$\pi$
出力：行動$a$
状態と行動のペアの確率：行動確率$\pi(a|s)$

• 要は確率であるということで、その確率と報酬をかけて期待値を計算できることが分かればよいではないか？

エージェントの行動を定義する2つの方法

エージェントの行動を定義する方法は2つある。
方法1：(エージェントは)保持している戦略に基づき行動する
方法2：(エージェントは)常に「価値」が最大になる行動を選択する

戦略$\pi$に基づいて行動する場合、状態$s$で行動$a$をとる確率は$\pi(a|s)$となる。
そして、遷移先$s'$へは遷移関数から導かれる確率$T(s'|s,a)$で遷移する。($s'$は遷移先を意味する、つまり$s_{t}$の$s'$は$s_{t+1}$、$s_{t+1}$の$s'$は$s_{t+2}$)

※あれ？遷移確率$P_{a}\left( s,s'\right)$とは違うのかな？？？
→遷移確率$T(s'|s,a)$という表し方もあるようだ

方法1：戦略(Policy)ベース

状態$s$から戦略$\pi$に基づいて行動することで得られる価値$V_{\pi}(s)$
この$V_{\pi}(s)$は価値$G_{t}$と同様再帰的に定義できる

$V_{\pi }\left( s_{t}\right) =E_{\pi }\left[ r_{t+1}+\gamma V\pi \left( s_{t+1}\right) \right]$

※$E$は期待値という意味

報酬を報酬関数$R(s,s')$で書き直す
価値$r_{t+1}+\gamma V\pi\left( s_{t+1}\right) $・行動価値${\pi}(a|s)$・遷移確率$T(s'|s,a)$を掛けると期待値$V_{\pi }(s_{t})$は以下のようになる

$V _{\pi}(s) =\sum _{a}\pi \left( a|s\right) \sum _{s'}T\left( s'|s,a\right) \left( R(s,s')+\gamma V\pi \left( s'\right) \right)$

価値を再帰的かつ期待値で表現することで2つの問題点をクリアした、この式をBellman Equationと呼ぶ。

※解決1と解決2を適応したした式がBellman Equationだと考えてよい。
なおこの式にはPolicyベースとValueベースの2方法がある。

この方法1のように、戦略に基づき行動する方法をPolicyベースと呼ぶ
特徴：行動の評価方法のみ学習し、評価単体行動を決定する。

方法2：価値(Value)ベース

「価値が最大になる行動」を常に選択する場合は、この式を少し変換する。
→戦略$\pi$がmaxに置き換わる(価値＝戦略)

$V(s) =max_{a}\sum _{s'}T\left( s'|s,a\right) \left( R(s,s')+\gamma V\pi \left( s'\right) \right)$

特に報酬が状態のみで決まる場合、つまり$R(s)$のは以下のように書ける。
迷路にような環境、場所に応じて状態が決まる。
$V\left( s\right) =R\left( s\right) +\gamma \max _{a}\sum _{s'}T\left( s'|s,a\right) V\left( s'\right) $

この方法2、価値が最大になるよう行動する方法をValueベースと呼ぶ。
特徴：戦略で行動を決定し、その評価/更新に行動評価が使われる。
→つまり、戦略と価値評価が相互的に影響し合う。

補足

ValueベースのBellman Equationをでは価値を計算するのに、「価値が計算済み」である必要がある。
感覚的に行動は「価値が最大」なものを選ぶから、計算済みでない困ることは理解できるだろう。

$V\left( s\right) =R\left( s\right) +\gamma \max _{a}\sum _{s'}T\left( s'|s,a\right) V\left( s'\right) $

※「価値」とは上の式の$V(s')$のこと

• 問題：すべての行動で$V$を計算し値が最大になる行動を選ぶ、だが状態数が多いと計算は難しい。
• 解決：動的計画法(Dynamic Programming：DP)では$V(s')$を適当な値に設定し、複数回計算を繰り返すことで値の精度が上がり、最適解に近づく。 再帰的に式を定義したおかげらしい。 証明可能であるという、証明は割愛するけど。

動的計画法(Dynamic Programming：DP)

学習方法の例として、動的計画法(Dynamic Programming：DP)がある
迷路環境のような遷移関数と報酬関数が明らかな場合は使える。

遷移関数→出力：遷移先、遷移確率
報酬関数→出力：即時報酬

• 遷移先(次のセル)と遷移確率(右へ行こうとして右へ行ける確率)及び報酬(どのセルで何ポイント)が決まっている(というか決めているのが迷路？)

• モデル
  ＝環境
  ＝環境の動作を決定する遷移関数・報酬関数

• 遷移関数・報酬関数をベースに行動を学習する手法「モデルベース」の学習手法という。

• 強化学習限らず広く使われている。以下の解説は強化学習に限定した狭義の動的計画法である。

動的計画法による価値評価の学習：Value Iteration

基本的な考え：各状態の価値を算出し、値が最も高い状態に遷移するような行動をする。
価値反復法(Value Iteration)：動的計画法によって各状態の価値を算出する(価値評価を学習する)方法。
$V_{i+1}\left( s\right)$$ :=\max _{a}$

$\sum _{s}T\left( s'|s,a\right)$

$( R\left( s\right) +\gamma V_{i}\left( s'\right))$

※なぜかつなげるとバグってしまうため、上下に並べています、、、順番は合っています。

• $V_{i+1}$は、前回($i$回目の計算結果($V_{i}$)を利用して算出される。

• 具体的には遷移先の価値を$V_{i}$から取得している($V_{i}(s')$)

• 正確な値に近づいたかは更新前後の差異$(|V_{i+1}(s)-V_{i}(s)|)$1が一定値(閾値)より低い＝更新の必要ない

動的計画法による戦略の学習：Policy Iteration

基本的な考え：エージェントは保持している戦略に基づき行動する。

• 戦略は状態での行動確率$\pi(a|s)$を出力する。
• 行動確率$\pi(a|s)$から価値(期待値)の計算が可能になる。
• 戦略により価値を計算、価値を最大化するような戦略を更新する、というプロセスを繰り返して。価値の値(価値評価)、戦略双方の精度を高める。このプロセスを戦略(方策)反復法(Policy Iteration)と呼ぶ。
• 計算された価値は戦略の評価に使用される、戦略による価値評価を戦略評価(Policy Evaluation)と呼ぶ。
• 価値の更新と戦略の更新が繰り返す相互更新がPolicy Iterationの中核である。これで価値評価と戦略両方が学習される。

$V_{\pi }\left( s\right) $

$=\sum _{a}\pi \left( a|s\right)$

$\sum _{s'}T\left( s'|s,a\right) $

$\left( R\left( s,s'\right) +\gamma V_{\pi} \left( s'\right) \right)$

※なぜかつなげるとバグってしまうため、上下に並べています、、、順番は合っています。

Value IterationとPolicy Iterationの比較

• Value Iterationは価値が最大の行動を必ず選ぶ
• Policy Iterationは戦略に基づき、各行動は確率的に選ばれる

Policy Iteration　
メリット：全状態の価値を計算しない
デメリット：戦略が更新されるたび価値を計算し直さなければならない
どっちが良いかケースバイケースである。

モデルベースとモデルフリー

モデル
＝環境
＝環境の動作を決定する遷移関数・報酬関数

遷移関数・報酬関数をベースに行動を学習する手法「モデルベース」の学習手法という。

モデルベース特徴：

• エージェントを一歩も動かさず環境の情報のみから、シュミレートし最適な計画(戦略)を得る。
• 遷移関数と報酬関数が明らかかつ適切である必要がある。
• 例：エージェントを動かすコストが高い、ノイズが入りやすい(屋外でのドローン操作など)の環境に適している。

モデルフリー特徴：

• 遷移関数と報酬関数が不明な環境でも適用可能。
• 現実では遷移関数と報酬関数がが既知で、かつモデル化可能な場合は少ない。
• 現在では主流だけど、DNNでモデル可能になったものが増えているのでモデルベースも良き。

※モデルフリーは第三章で説明する。
※また、両方を組み合わせることでメリットを享受することも可能。

まとめ

• 強化学習が学習するもの：

  • 1、価値評価の学習
  • 2、戦略の学習

• 価値の定義：行動選択の段階(時刻$t$)で「報酬の総和」を「見積もった」値で、将来の即時報酬については「割引率」を適用している。

  • 問題1：将来の即時報酬の値($r_{t+1},r_{t+2},\ldots$)が判明している必要がある点。
  • 問題2：将来の即時報酬が必ず得られる点。

• 解決法：価値を再帰的かつ期待値で表現することで2つの問題点をクリアした、この式をBellman Equationと呼ぶ。

• エージェントの行動を定義する方法は2つある。

  • 方法1：(エージェントは)保持している戦略に基づき行動する→Policyベース
  • 方法2：(エージェントは)常に「価値」が最大になる行動を選択する→Valueベース

• 学習方法の例として、動的計画法(Dynamic Programming：DP)がある。

  • 迷路環境のような遷移関数と報酬関数が明らかな場合は使える。
  • 動的計画法DPでは将来の即時報酬$G_{t+1}$について過去の計算値(キャッシュ)を使うことで計算する。これはメモ化という。

• 動的計画法による価値評価の学習：Value Iteration
  基本的な考え：各状態の価値を算出し、値が最も高い状態に遷移するような行動をする。

• 動的計画法による戦略の学習：Policy Iteration
  基本的な考え：エージェントは保持している戦略に基づき行動する。
  価値の更新と戦略の更新が繰り返す相互更新がPolicy Iterationの中核である。これで価値評価と戦略両方が学習される。

• モデルベースとモデルフリーの特徴

参考資料

• 機械学習スタートアップシリーズ-Pythonで学ぶ強化学習-入門から実践まで
• Math Webmemo手書きの公式をLaTex変換してくれます！マジおすすめ！
• https://github.com/icoxfog417/baby-steps-of-rl-ja ※上記の本の公式アカウントです。コードや概要が見れます。
• DQN（Deep Q Network）を理解したので、Gopherくんの図を使って説明