【苦しみながら理解するReinforcement Learning】第4章 動的計画法

ここから遂に第2部具体的な解法に入る!

因みに第1部のタイトルは今更ながら強化学習問題だったw

本書では大きく3つの解法をみていく。(長所、短所も一緒に)

  • 動的計画法:数学的にうまく作られた方法。完全で正確な環境のモデルが必要。
  • モンテカルロ法:概念的に単純でモデルを必要としない。ステップ・バイ・ステップの斬新的な計算に適していない。
  • TD手法:モデル不要で、完全に斬新的。複雑で分析が難しい。

そして、第3部ではそれぞれの最も良い特徴を利用できる組み合わせに入る!

動的計算法(DP)は、完全なモデルが必要で、計算量が膨大なので、実用的ではないけど、理論的には重要で多くの解法の元となる考え方なので重要っぽい。
DPと強化学習では、価値関数を利用して良い方策の探索を計画し組み立てる考え方が中心となっている。(DPと強化学習とは異なるのかな?)

方策評価

方策評価(policy evaluation)とは、任意の方策πに対する状態価値関数 V^πを計算することである。
ここでは予測問題(prediction problem)と呼ぶ。

第3章で出てきた状態価値関数に対するBellman方程式を更新規則として用いることで、

【苦しみながら理解するReinforcement Learning】第3章 強化学習問題
https://twitter.com/kawashima2201_/status/1045687527246426112 さてと...気にせず進むか... これからとこうとしている問題の紹介...

連続した近似が次のように得られる。

\begin{align}
V_{k+1}(s) & = E_{\pi} [r_{t+1}+\gamma V_k ( s_{t+1} ) | s_t = s]
& = \sum_{\alpha}\pi( s, \alpha)\sum_{s’}P_{ss’}^{\alpha}[R_{ss’}^{\alpha}+\gamma V_k(s’)]
\end{align}
※ 何故かLatexが効かないので、{}を[]としている部分が、ここを含めいくつかあります…

V^πと同じ条件の下で、系列{Vk}が極限 k -> ∞ でV^πに収束することが一般的に示される。
このアルゴリズムは反復方策評価(iterative policy evaluation)と呼ばれる。

ここで、sの期待値(即時報酬と価値)を使って、新しいsの価値を計算していく。
反復方策評価は、すべての状態の価値に対して一度ずつバックアップを行い、新しい近似価値関数V_{k+1}を作り出す。(完全バックアップ:full backup)
DPアルゴリズムは、次状態の標本値ではなく、可能な次状態すべてを対象とするので、完全バックアップに相当する。

一方で、価値を全て保存せず、次々に更新していく(スイープ操作)手法を「その場更新型(in-place)」と呼ぶ。

このアルゴリズムは、更新を終える時が重要。
極限でのみ収束するが、実際には以下の式が十分に小さい正の値ならば終わる。

$$ max_{s∈S} [V_{k+1} (s) – V_k(s)] $$

また参考アルゴリズムは以下の通り。

方策評価_アルゴリズム

方策改善

方策に対して価値観数を計算することで、さらに良い方策を見いだす手がかりが得られる。
気になるのは、新しい方策に変えることがより良いのか、それとも以前より悪いのか、だ。

それを知る方法の1つは、状態sで行動aを選択し、その後は既存の方策πに従うことで、

\begin{align}
Q^{\pi} (s, a) & = E_{\pi} [ r_{t+1} + \gamma V^{\pi} (s_{t+1} ) | s_t = s, a_t = a ]
& = \sum_{s’} P_{ss’}^{\alpha} [R_{ss’}^{\alpha} + \gamma V^{\pi} (s’)]
\end{align}

もし、この値がV^π(s)より大きい場合、つまりsで一度aを選んで、その後πに従うことが、常にπに従う場合よりも良いならば、状態sに対してaを常に選ぶことが良いと判断できる。

これが成り立つのは一般的な定理の特別な場合に相当する。(方策改善定理: policy improvement theorem)
証明は本書がわかりやすいですよ!w

これを利用して全ての状態で、全ての可能な行動に関して、各状態でQ^π(s,a)が最良となる行動を選択するような変更が考えられる。(グリーディ方策 : greedy policy : 記号π’)

\begin{align}
\pi'(s) & = arg \max_{\alpha} Q^{\pi} (s, a)
& = arg \max_{\alpha} E [ r_{t+1} + \gamma V^{\pi} (s_{t+1} | s_t = s, a_t = a ]
& = arg \max_{\alpha} \sum_{s’} P_{ss’}^{\alpha} [ R_{ss’}^{\alpha} + \gamma V^{\pi} (s’) ]
\end{align}
※ 何故か改行できないが、前進あるのみw

argmax_aは、それに続く式を最大にするようなaの値を与える。
このグリーディ方策はV^πによって1ステップ先読みを行い、短期的に最良となるであろう行動を選択する。

これまでの議論では、決定論的な方策という特別な場合を扱ってきた。
確率的方策πでは、状態sで行動aを選択する確率π(s, a)を指定する。
ここでの考え方は、確率的方策に用意に拡張することができる。

方策反復

方策評価と法お作改善を繰り返して、最適価値関数に収束させる手法を方策反復(policy iteration)という。

参考プログラミング

4.3

価値反復

方策反復の欠点は、各繰り返しステップで方策評価を必要とすること。
価値反復は、方策改善と方策評価ステップを打ち切りを組み合わせた、極めて単純なバックアップ操作である。

価値反復は、方策評価と方策改善の2つのスイープ操作を、1回のスイープ操作の中に効果的に結合している。
方策改善のスイープ操作の間に、方策評価のスイープ操作を複数回行うことによって、収束がさらに早くなる場合が多い。

アルゴリズム例を次に示すが、方策評価のスイープ操作をいくつか行った結果に、最大値を求める操作が加わっている。

図4.5

非同期動的計画法

非同期DPアルゴリズムは、その場更新型の反復DPアルゴリズムである。
このアルゴリズムは状態集合全体の系統的なスイープ操作は行わず、状態を任意の順序で選んで価値のバックアップを行う。

非同期DPアルゴリズムは、バックアップ操作を適用する状態の選択に大きな自由度を与える。

与えられたMDP問題を解くために、エージェントが実際にMDPを経験するのに並行して、反復DPアルゴリズムを実行させることができる。
エージェントの経験を用いて、DPアルゴリズムがバックアップを適用する状態を決めることができる。

一般化方策反復

方策評価と方策改善の2つの過程の相互作用を一般的概念として、一般化方策反復(generalized policy iteration; GPI)と呼ぶ。

評価過程と改善過程

動的計画法の効率

DPは方策空間を直接探索するどのような手法よりも指数関数的に速い。
直接探索で最適方策の発見を保証するためには、すべての方策を余すところなく調べなければならないからである。
したがって、大規模問題群に対しては、DP手法のみが適用可能。

DP手法では、後続状態の価値の推定量に基づいて、状態の価値の推定量を更新する。
この手法は、別な推定量を基準にして当該推定量を更新する。
このような考え方をブートストラップ(bootstrap)と呼ぶ。
次章では、完全で正確なモデルを必要とせず、ブートストラップを行わない強化学習法について。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です