Gymで強化学習⑧有限マルコフ決定過程

前回の記事では具体例を通して状態価値関数、行動価値関数、ベルマン方程式などを復習しました。その際に、1次元のグリッド・ワールドを使いました。グリッド・ワールドを使ったのは状態の数が有限になり理解しやすいからです。また、行動も有限にして取り扱いやすくしました。

状態と行動が有限なので状態価値関数や行動価値関数を配列や表にして表現することができます。このように表形式（Tabular）が使えるような環境におけるマルコフ決定過程を有限のマルコフ決定過程（Finite Markov Decision Process）と呼びます。

有限のマルコフ決定過程では、最適なポリシーを見つけるための代表的な手法として以下があります。

• 動的計画法

• モンテカルロ法

• TD法

• SARSA

• Q学習

Richard Suttonが書いた有名な強化学習の本「Reinforcement Learning, An Introduction」では、有限のマルコフ決定過程における強化学習を解説する際に、動的計画法から段階的にQ学習へと知識を積み上げています。

また、ディープマインドでアルファ碁などを研究開発したDavid Silverによる講義ビデオでも同様な順序に従っており、ほぼRichard Suttonの本の流れに従っています（彼の講義ビデオの中で上記の本を参照しています）。

よって、この記事では動的計画法からQ学習への大まかな流れを上記のリストに従って解説します。

動的計画法

動的計画法（Dynamic Programming)は、環境における状態、報酬、行動の関係が確率的に完全にわかっている場合に有用な手法です。動的計画法は一般に大きな問題をより小さな問題に分割して計算し、その結果をより多くな問題を解くために利用する方法です。

環境のモデルを完全に把握している場合、ある状態である行動をとったときにどのくらいの報酬が得られるのかがわかっています。しかし、ある状態の状態価値はわかっていません。これをベルマン方程式で解くことはできるでしょうか。

ベルマン方程式では状態価値関数$${v(s)}$$は状態$${s_t = s}$$から受け取る報酬$${r_t}$$とその後の状態$${s_{t+1}}$$の状態価値$${v(s_{t+1})}$$の合計の期待値を返します。

$$
v(s) \doteq \mathbb{E}[ r_t + \gamma v(s_{t+1}) | s_t = s]
$$

$${\doteq}$$は定義を意味します。

ここには大きな問題とより小さな問題が相互に関係しています。つまり、状態価値関数$${v(s)}$$の計算を大きな問題だとすると、それを分割して現在状態$${s_t = s}$$から受ける報酬$${r_t}$$と、その次の状態$${s_{t+1}}$$の状態価値$${v(s_{s+1})}$$との合計の期待値というより小さい問題になっています。

しかし、大きな問題とより小さな問題の両方で同じ状態価値関数を使っており、これではイタチごっこになってしまいます。なぜなら、環境のモデルを完全に把握していても状態価値関数はわかっておらず、状態価値関数を知るために状態価値関数そのものを知っていないとならないからです。

これでは状態価値関数を計算するのは不可能に見えますが解決方法があります。