強化学習について学んでみた。（その14）

久々に強化学習の話。

前回は、価値反復について説明し、プログラムを書いてみた。

今日からは、そもそも状態遷移のモデルが分からない場合に、どうすればいいのかを考えていく。

おさらい

まず、以下の記事で状態遷移のモデルとBellman方程式について説明した。

ここでは3つの課題を挙げているけど、もしモデル（状態遷移の確率、および、報酬の期待値）が分かっているなら、方策反復や価値反復を使って方策を改善していけることが分かった。

しかし、実際にはモデルが分かるということはあまりない。
例えば、将棋である局面から次の局面にどのように遷移するかの確率が分かるかといえば、まず分からない。
なので、最後の課題、そもそも状態遷移のモデルが分からない場合にはどうすればいいのか、を考える必要がある。

基本的な考え方

じゃあ、どうすればいいのかというと、基本的な考え方は簡単。
実際に何度もやってみればいいじゃん、と。

何度も何度も繰り返し実行すれば、そのときの状態遷移は「（知ることが出来ない）本当の状態遷移の確率」に従うので、得られる収益の平均は期待値ーーすなわち、状態価値や行動価値ーーに収束していく。

このように、実際に何度も繰り返して、そこで得られた経験から状態価値や行動価値を推定していく方法を、モンテカルロ法と呼ぶ。
（なお、これまでにやった、モデルから反復法でBellman方程式を解いていく方法を、動的計画法と呼ぶ）

モンテカルロ法による方策評価

さて、上記の考え方に従うと、方策 $\pi: \mathcal{S} \times \mathcal{A}(s) \rightarrow [0, 1$ ]での状態価値 $\boldsymbol{V}^{\pi} \in \mathbb{R}^{\mathcal{S}}$ を評価する、モンテカルロ法による方策評価は、以下のようになる：

すべてのに対して、以下のように初期化する：
- $V_s^{\pi} \leftarrow 0$
- $Returns(s) \leftarrow \mbox{空のリスト}$
以下を繰り返す：
1. 方策 $\pi$ に従ってエージェントを行動させ、状態の列 $s_0, s_1, s_2, \cdots , s_T$ と報酬の列 $r_1, r_2, \cdots , r_T$ を観測する。
2. 観測された各状態について、が初回訪問なら：
  1. $R \leftarrow \sum_{t' = t+1}^T r_{t'}$
  2. $R$ を $Returns(s_t)$ に追加する。
  3. $V_{s_t}^{\pi} \leftarrow \mbox{average}\left(Returns(s_t)\right)$

なお、途中で初回訪問ならという条件を入れているのは、観測された状態列の中に、同じ状態が複数回現れる可能性があるから。
そこで、初めて観測されたとき（これを初回訪問という）の状態の収益だけを扱う方法と、何度も観測された状態の収益を平均化して扱う方法が考えられる。
上記のアルゴリズムは前者の方法を使っていて、初回訪問モンテカルロ法と呼ばれる。
（一方、後者は逐一訪問モンテカルロ法と呼ばれる）

行動価値と開始点探査

ところで、上では状態価値を評価したけど、モデルがない場合、状態価値が分かるだけでは困ってしまうことがある。
というのも、ある行動 $a \in \mathcal{A}(s)$ をとったとき、状態がどのように遷移するかの確率が分からないので、その行動による収益の期待値を計算できないから。
これでは、状態価値が分かっても、どの行動をとるべきなのかを知ることが出来ない。

そこで、モデルがない場合は、状態価値ではなくて行動価値を評価しないといけない。
行動価値を評価してあれば、それぞれの行動による収益の期待値を知ることが出来るので、それが一番大きくなるように行動するのがいいと分かるからだ。

ただし、その場合、ちょっと考えておかないといけないことがある。
それは、評価しようとしている行動価値 $Q_{s, a}^{\pi}$ の状態行動対 $(s, a)$ が観測されないと、その行動価値を評価することが出来ない、という問題。
例えば、 $\pi(s, a) = 0$ の場合、エージェントが方策にしたがって行動をするだけだと、 $(s, a)$ という状態行動対は永遠に観測されないことになる。

そこで、開始点探査（Exploring Starts）の仮定というものを置く。
これは、任意の状態行動対 $(s, a)$ について、 $(s_0, a_0) = (s, a)$ となる確率が0ではない、とする仮定。
そうなっていれば、たとえ（開始点以外で）決定論的な方策（＝各状態で選ばれる行動は常に同じ）を使っていたとしても、 $(s, a)$ が観測されないということは起きない。

この開始点探査の仮定をいれたモンテカルロ法（モンテカルロ-ES法、ESはExploring Startsの略）による行動価値の評価は、以下のようになる：

すべてのに対して、以下のように初期化する：
- $Q_{s, a}^{\pi} \leftarrow 0$
- $Returns(s, a) \leftarrow \mbox{空のリスト}$
以下を繰り返す：
1. 任意の状態行動対 $(s, a)$ を、開始点として $(s_0, a_0) = (s, a)$ とする。
2. 方策 $\pi$ に従ってエージェントを行動させ、状態行動対の列 $(s_1, a_1), (s_2, a_2), \cdots, (s_{T-1}, a_{T-1})$ と報酬の列 $r_1, r_2, \cdots , r_T$ を観測する。
3. 観測された各状態行動対について、初回訪問なら：
  1. $R \leftarrow \sum_{t' = t+1}^T r_{t'}$
  2. $R$ を $Returns(s_t, a_t)$ に追加する。
  3. $Q_{s_t, a_t}^{\pi} \leftarrow \mbox{average}\left(Returns(s_t, a_t)\right)$

モンテカルロ-ES法と方策改善

さて、方策評価は上記のモンテカルロ-ES法で出来たとして、方策改善を行うにはどうすればいいか。

これは強化学習について学んでみた。（その11） - いものやま。と同様に考えればよくて、グリーディ方策をとればいい。

ところで、方策評価を行って、そのあと方策改善を行って、というのを繰り返すのだと、方策改善が行われるまでにかなりの時間を要することが考えられる。
そこで、価値反復と同様の考え方を取り入れる。
すなわち、方策評価が終わるまで待って方策改善を行うのではなく、方策評価の途中で方策改善も行っていく、という考え方だ。
モンテカルロ法の場合、一通りの状態行動列を観測して方策評価を行ったら、そこで評価された行動価値を使って方策改善を行うといい。

具体的には、以下のようなアルゴリズムになる：

すべてのに対して、以下のように初期化する：
- $Q_{s, a} \leftarrow 0$
- $Returns(s, a) \leftarrow \mbox{空のリスト}$
すべての $s \in \mathcal{S}について、決定論的な方策[tex: \pi(s)$ を $\mathcal{A}(s)$ の任意の行動で初期化する。
以下を繰り返す：
1. 任意の状態行動対 $(s, a)$ を、開始点として $(s_0, a_0) = (s, a)$ とする。
2. 決定論的な方策 $\pi$ に従ってエージェントを行動させ、状態行動対の列 $(s_1, a_1), (s_2, a_2), \cdots, (s_{T-1}, a_{T-1})$ と報酬の列 $r_1, r_2, \cdots , r_T$ を観測する。
3. 方策評価
  観測された各状態行動対について、初回訪問なら：
  1. $R \leftarrow \sum_{t' = t+1}^T r_{t'}$
  2. $R$ を $Returns(s_t, a_t)$ に追加する。
  3. $Q_{s_t, a_t} \leftarrow \mbox{average}\left(Returns(s_t, a_t)\right)$
4. 方策改善
  観測された各状態について、初回訪問なら：
  1. $\pi(s) \leftarrow \mathop{\mbox{arg max}}_{a \in \mathcal{A}(s_t)} Q_(s_t, a)$