今回はMDP問題を動的計画法で解く方策反復方について紹介します。
方策反復法は方策の評価、改善を繰り返し（反復）最適な方策を獲得する手法です。
方策反復法とは
方策反復法では動的計画法によって、 最適方策\(\pi ^{\ast}(s, a)\) を求めます。
(MDP環境において)
つまり、繰り返し繰り返し細かく更新していって最適方策を求めていきます。
ちなみに、動的計画法はwikipediaを参考にすると
対象となる問題を帰納的に解く場合にくり返し出現する小さな問題例について、解を表に記録し表を埋めていく形で計算をすすめ、冗長な計算をはぶくアルゴリズムのことをいう。特定のアルゴリズムを指すのではなく、上記のような手法を使うアルゴリズムの総称である
出典 https://ja.wikipedia.org/wiki/%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95
方策反復法の手順はシンプルです。
- 方策\(\pi\)と状態価値\(V\)の初期化
- 方策\(\pi \)によって、\(V\)の更新(方策評価)
- 更新した\(V\)によって新たな方策\(\pi_{new}\)の計算(方策改善)
- 2.3を方策\(\pi \)が収束するまで繰り返す
方策反復法のイメージ図としては以下のようになります。
出典: Reinforcement Learning: An Introduction
アルゴリズムの全体像は以下のようになります。
出典: Reinforcement Learning: An Introduction
方策評価と方策改善について具体的にどのような操作を行うかを説明していきます。
方策評価
現在の方策\(\pi_t\)の評価を行います。
つまり、現在の方策によって状態価値\(V^{\pi}\)を計算してあげます。
すべての状態に対して、 現在の方策を用いて状態価値$V(s)$を更新していきます。
\begin{eqnarray}
V^{\pi}(s) &=& \sum_{a} \pi (a | s) \sum _{s’ \in S}P(s’ | s, a)[R(s, a)+\gamma V^{\pi}(s’)]
\end{eqnarray}
$$
ここで、
- \(P(s’ | s, a)\)：状態\(s\)において行動\(a\)を行った時に状態\(s’\)に遷移する確率
- \(R(s, a)\)：状態\(s\)において行動\(a\)を行った時に得られる報酬
\(V^{\pi}\)が収束するまで繰り返す。
シンプルな例で見てみます。
方策も状態遷移も決定論としてます。
上記の操作を全状態で行います。
つまり、全状態で、現在の方策\(\pi\)によって状態遷移し、
状態価値\(V\)を更新させます。
この状態価値\(V\)が収束した段階で、方策改善に移ります。
方策改善
更新した状態価値関数\(V^{\pi}\)によって、方策を更新します。
最もシンプルな更新方法は以下のようなgreedyに更新する方法です。
\begin{eqnarray}
\pi_{new}(s) = \underset{a}{\operatorname{argmax}} \sum_{s’} P(s’|s, a) [R(s, a)+\gamma V(s’)]
\end{eqnarray}
$$
上記の式によって最も期待報酬値が大きくなるように行動選択を行うことで、 \(V^{\pi _{new}}(s) \geq V^{\pi}(s)\)となる方策\(\pi_{new}\)を得ることができます。
つまり、より良い方策を得ることができます。
これは方策改善定理によって証明されています。
方策改善もシンプルな例で見てみます。
これも方策も状態遷移も決定論としてます。
全状態で、得られる利益\(R(s, a)+\gamma V(s’)\)が最大となる行動を 方策新しい方策\(\pi_{new}\)としていきます。
この方策がまったく変化しなくなった段階で方策反復によって最適方策が得られています。
実験
問題設定
シンプルなグリッドワールド問題を方策反復法で解いてみます。
非常にシンプルなグリッドワールドですので、決定論的な環境にします。
(つまり、状態\(s\)で行動\(a\)を選択したら必ず\(s’\)に変化する)
今回は決定論的な環境で、方策もgreedy方策ですので、
方策評価は、
\begin{eqnarray}
V(s) = R(s, \pi(s)) + \gamma V(s’)
\end{eqnarray}
$$
また、方策改善では、
\begin{eqnarray} \pi _{new}(s) = \underset{a}{\operatorname{argmax}} [R(s, a)+\gamma V(s’)]
\end{eqnarray}
$$
としています。
ソースコード
実験結果
動的計画法によって得られた方策\(\pi\)と状態価値\(V\)を確認してみます。
以下出力になります。
vが状態価値、piが方策になります。
[[0.99 1. inf] [0.9801 0.99 1. ] [0.970299 0.9801 0.99 ]] pi [[ 3. 3. inf] [ 0. 0. 0.] [ 0. 0. 0.]]
infはゴール地点です。
(とりあえずinfで表現しただけで深い意味はありません)
vは各状態の価値を表しています。
ゴール(inf)に近ければ近いほど高い値を得ることが出来ていることがわかります。
また方策は、 0が上、3が右を表しています。(その他はソースコードを参照していだければと思います)
適切な経路を得ることが出来ていることがわかります。
スタート地点(0, 2)から上、上、右、右でゴールに到着することがわかります。
コメント
[…] 方策反復法（動的計画法） […]