前書き

この記事では強化学習アルゴリズムの枠組みである 一般化方策反復 (General Policy Iteration, GPI) について説明します。名前は知らなくとも概念は知っているという方もおそらく多いと思いますし、それほど難しい話ではありません。が、このGPIの枠組みを理解しているかどうかは強化学習全体の理解度に大きく影響すると思っています。

記事の前半でGPIの枠組みを紹介し、記事の後半でQ学習やSARSAといった基本的な強化学習アルゴリズムをGPIの枠組みに従ってまとめていきたいと思います。

理論

方策反復法 (Policy Iteration)

GPIについて説明をする前に、方策反復法について確認しておきます。
方策反復法とは、次の2ステップを交互に繰り返すことで最適価値関数・最適方策を求める強化学習アルゴリズム (厳密にはプランニングアルゴリズム) です。

1. 方策評価 (policy evaluation) ベルマン作用素 ${\mathbf B}_{\pi}, {\mathbf \Upsilon}_{\pi}$ を繰り返し適用することで、現在の方策 $\pi$ の価値 $V^{\pi}, Q^{\pi}$ を推定する。

for _ in range(N):
    V = B_pi(V)
    Q = U_pi(Q)

1. 方策改善 (policy improvement) 現在の方策 $\pi$ の価値に基づいて、価値が最も高い行動を選択する方策 $\pi'$ に更新する。

pi[state, :] = argmax(Q[state, :])

この2ステップを十分な回数繰り返すことで、推定価値関数 $V, Q$ は最適価値関数 $V^{\ast}, Q^{\ast}$ に、推定方策 $\pi$ は最適方策 $\pi^{\ast}$ に収束していくことが知られています。

方策反復法についてより詳細に知りたいという方は、 過去の記事 を参照してもらうか、参考文献に挙げたような教科書を読んでもらえると良いかと思います。

一般化方策反復 (General Policy Iteration, GPI)

方策反復法は 方策評価 と 方策改善 の2ステップから構成されていました。現在の方策を評価して価値関数を更新し、現在の価値関数に基づいて方策を改善する、という流れで最適化が行われています。

他の強化学習アルゴリズムを眺めると、そのほとんどがこれと類似した構造を持っていることがわかると思います。つまり、強化学習アルゴリズムは基本的に「方策を評価し、その結果に基づいて方策を改善する」という流れに沿って進んでいきます。

GPIは名前こそ仰々しいものの、概念としては非常に単純なものです。次項では、方策評価・方策改善の具体的な内容をいくつか紹介したいと思います。

方策評価 (Policy Evaluation)

強化学習アルゴリズムの分類方法の1つとして「モデルベース vs. モデルフリー」というものがありますが、ここではその分類に従ってまとめていきます。「モデルベース vs. モデルフリー」の分類についてはここでは解説しませんが、これも強化学習を理解する上で重要なのでいくつか記事を読んでおくと良いと思います。

• 強化学習: プランニングと学習 (その1)
• 強化学習理論の基礎4

モデルベース

環境が既知であれば、方策反復法のようにベルマン作用素を利用して価値関数を求めることができます。 (これはプランニングの設定です。)
ただ、強化学習では環境が未知であるためこの方法を直接利用することはできません。

モデルベースなアプローチでは、環境情報 $p_T, R$ をモンテカルロ法などで推定した上でプランニングを実行することを考えます。具体的には、環境情報 $p_T, R$ を収集したデータ集合 ${\mathcal D}$ を用いて次のように推定します。¹

\begin{align}
\hat{p_T}(s' | s, a)
&= \frac{\sum_{t=0}^T {\mathbb I}_{\{ s_t = s \}} {\mathbb I}_{\{ a_t = a \}} {\mathbb I}_{\{ s_{t+1} = s' \}}}{\sum_{t=0}^T {\mathbb I}_{\{ s_t = s\}} {\mathbb I}_{\{ a_t = a \}}} \\
\hat{R}(s,a )
&= \frac{\sum_{t=0}^T R(s,a) {\mathbb I}_{\{ s_t = s \}} {\mathbb I}_{\{ a_t = a \}} }{\sum_{t=0}^T {\mathbb I}_{\{ s_t = s\}} {\mathbb I}_{\{ a_t = a \}}}
\end{align}

ここで ${\mathbb I}_{{ \cdot }}$ は指示関数で

\begin{align}
{\mathbb I}_{\{ P \}}
\equiv
\begin{cases}
1 & \text{ if } P \text{ is true } \\
0 & \text{ if } P \text{ is false }
\end{cases}
\end{align}

と定義されます。

モデルフリー (モンテカルロ法 / TD法)

前項ではモデルベースなアプローチを紹介しましたが、環境情報を推定することなく直接価値関数を求めるモデルフリーなアプローチも存在します。

モデルフリーなアプローチでは、価値関数をある目標に近づけるように更新することで真の目的関数を得る、という方法を採ります。式で書けば

\begin{align}
V(s)
&:= V(s) + \alpha (V_{\mathrm{target}}(s) - V(s)) \\
Q(s,a)
&:= Q(s,a) + \alpha (Q_{\mathrm{target}}(s,a) - Q(s,a))
\end{align}

というように、目標との誤差を小さくする方向に価値関数を更新していきます。なお、この目標はエージェントが自身で収集した状態行動の履歴を用いて設計することになります。目標設定の仕方によって、Q学習・SARSA・Expected SARSAというように異なるアルゴリズムが導出されます。

モンテカルロ法

価値関数は、ある状態 / 状態行動対から始めた場合の期待累積報酬を表すものでした。そこで素直に推定価値関数の目標を 実績リターン $c_t$ (実際に観測された報酬から計算された累積報酬) とすることが考えられます。すなわち

\begin{align}
V(s_t)
&:= V(s_t) + \alpha (c_t - V(s_t)) \\
Q(s_t,a_t)
&:= Q(s_t,a_t) + \alpha (c_t - Q(s_t,a_t))
\end{align} \\
\text{ where } c_t = \sum_{\tau=0}^t \gamma^{\tau} r_{\tau}

のように更新を行います。

モンテカルロ法によるアプローチでは、 (サンプル数を十分に大きくすれば) 推定価値関数 $V, Q$ は真の価値関数に収束することが知られています。しかし、ある状態 / 状態行動対における推定価値関数の値を更新するためにはそれを含むエピソードを最後まで見る必要があり、オンラインに更新することはできません。

時間的差分学習 (Temporal Difference learning, TD learning)

真の価値関数がベルマン方程式に従っていることを利用して、推定価値関数 $V$ の目標を「1ステップ先を観測した上での推定価値」$r_t + \gamma V(s_{t+1})$ とします。すなわち

\begin{align}
V(s_t)
:= V(s_t) + \alpha \left(r_t + \gamma V(s_{t+1}) - V(s_t) \right)
\end{align}

のように更新を行います。²

推定価値関数 $Q$ の目標としてはいくつか種類があります。というのは、1ステップ先の行動をどのように設定するかに選択の余地があるためです。

エージェントが環境と相互作用を行うとき、各ステップ $t$ で得られるのは現在の状態 $s_t$ 、選択した行動 $a_t$ 、その結果得られる報酬 $r_t$ と次の状態 $s_{t+1}$ の組 $(s_t, a_t, r_t, s_{t+1})$ で、次の行動 $a_{t+1}$ は含まれていません。 $a_{t+1}$ としてどのようなものを選択するかによって導出されるアルゴリズムが異なります。

1つ目は「1ステップ先の状態を観測した上で最適行動を選択した場合の推定価値」を利用する方法です。これは Q学習 の方策評価アルゴリズムです。

\begin{align}
Q(s_t,a_t)
:= Q(s_t,a_t) + \alpha \left( r_t + \gamma \max_{a}{Q(s_{t+1}, a)} - Q(s_t, a_t) \right)
\end{align}

2つ目は「1ステップ先の状態行動対を観測した上での推定価値」を利用する方法です。これは SARSA法 の方策評価アルゴリズムです。

\begin{align}
Q(s_t,a_t)
:= Q(s_t,a_t) + \alpha \left( r_t + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t) \right)
\end{align}

そして3つ目は「1ステップ先の状態を観測し、1ステップ先の行動に関してはすべての可能性を考えて期待値をとった場合の推定価値」を利用する方法です。これは Expected SARSA法 の方策評価アルゴリズムです。

\begin{align}
Q(s_t,a_t)
:= Q(s_t,a_t) + \alpha \left( r_t + \gamma {\mathbb E}_{a_{t+1} \sim \pi(s_{t+1})} \left[ Q(s_{t+1}, a_{t+1}) \right] - Q(s_t, a_t) \right)
\end{align}

方策改善 (Policy Improvement)

方策評価のステップで価値関数を更新したら、その価値関数に基づいて方策を更新します。このとき、基本的には価値が高い行動を高い確率で選択するような方策が望ましいと考えられます。ということで、ここでは 貪欲方策 と ソフトマックス方策 の2つを紹介したいと思います。

貪欲方策 (Greedy Policy)

単純な方策として、方策評価ステップで推定された価値関数 $V, Q$ に基づいて最善の選択をするものを考えることができます。

\begin{align}
\pi(a|s) := 
\begin{cases}
1 & \text{ if } a = \mathrm{argmax}_{b}{Q(s,b)} \\
0 & \text{ otherwise }
\end{cases}
\end{align}

ただ、決定的方策では環境の探索を十分に行うことができず、学習に失敗する可能性があります。これを修正する1つの方法は、小さな確率 $\epsilon$ で探索を行うようにするというものです。³

\begin{align}
\pi(a|s) := 
\begin{cases}
1 + \frac{\epsilon}{| {\mathcal A} |} - \epsilon & \text{ if } a = \mathrm{argmax}_{b}{Q(s,b)} \\
\frac{\epsilon}{| {\mathcal A} |} & \text{ otherwise }
\end{cases}
\end{align}

この方策を $\epsilon$-貪欲方策 ($\epsilon$-greedy policy) と呼びます。 $\epsilon$-貪欲方策は先ほど紹介したQ学習、SARSA、Expected SARSAで用いられています。

ソフトマックス方策 (Softmax Policy)

価値関数の値に即して確率値を割り振るようなモデルを考えることもできます。有名なものの1つが ソフトマックス方策 です。

\begin{align}
\pi(a|s)
= \text{softmax} \left( \frac{Q(s, a)}{\beta} \right)
= \frac{\exp{( Q(s,a) / \beta )}}{\sum_a \exp{( Q(s,a) / \beta )}}
\end{align}

ここで $\beta > 0$ は温度パラメータで、方策をどのくらい確率的にするかを制御します。$\beta$ を大きくすると一様分布、小さくすると貪欲方策に近づきます。

Q学習 / SARSA / Expected SARSA

最後に、GPIの枠組みで紹介したアルゴリズム (Q学習、SARSA、Expected SARSA) について簡単にまとめておきます。

Q学習

方策評価ではTD法を利用して価値関数 $Q$ を推定します。TD法では、あるエピソードの時刻 $t$ における情報 $(s_t, a_t, r_{t+1}, s_{t+1})$ とその次の時刻 $t+1$ における情報 $a_{t+1}$ を利用して価値関数を更新しますが、Q学習では次の時刻 $t+1$ における行動を $a_{t+1} \equiv \mathrm{argmax}_{a}{Q(s_{t+1}, a)}$ とします。方策改善の仕方は自由に決められますが、Q学習では $\epsilon$-貪欲方策を用いることが多いと思います。

Pythonライクな擬似コードを示します。Q学習では学習データをサンプルするたびに価値関数を更新することもできますが、ここでは学習データのサンプリングを独立させました。

for _ in range(N):

    # interaction
    history = environment.interact(pi)

    # policy evaluation
    for t in range(T):
        state, action, reward, state_next = history[t]
        td_error = (reward + gamma * max(Q[state_next, :])) - Q[state, action]
        Q[state, action] += alpha * td_error

    # policy improvement
    for state in S:
        action_opt = argmax(Q[state, :])
        pi[state, :] = eps
        pi[state, action_opt] = 1 - eps * (len(A) - 1)

強化学習における学習データのサンプリングについてこの記事では詳しくは述べませんが、サンプリングを工夫することで学習の安定性や効率を高めることができます。

例えば、深層学習を利用したQ学習アルゴリズム Deep Q-Network (DQN) ではリプレイバッファと呼ばれるバッファに学習データを蓄積しておき、学習する際にそこからランダムにサンプルを行います。これによって時系列の相関がなくなり、学習が安定するとされています。DQNについては解説記事がたくさんあるのでそちらを参照してください。

• DQN (Deep Q Network) を理解したので、Gopherくんの図を使って説明
• 深層強化学習DQN (Deep Q-Network) の解説

SARSA

方策評価ではTD法を利用して価値関数 $Q$ を推定します。SARSA法の方策評価では次の時刻 $t+1$ の行動 $a_{t+1}$ として、エージェントが同じエピソードで実際にとった行動を利用します。Q学習と同様に方策改善の仕方は自由に決められますが、ここではソフトマックス方策を用いたものを擬似コードに示すことにします。

for _ in range(N):

    # interaction
    history = environment.interact(pi)

    # policy evaluation
    for t in range(T-1):
        state, action, reward, state_next = history[t]
        _, action_next, _, _ = history[t+1]
        td_error = (reward + gamma * Q[state_next, action_next]) - Q[state, action]
        Q[state, action] += alpha * td_error

    # policy improvement
    for state in S:
        pi[state, :] = softmax(Q[state, :])

Expected SARSA

Expected SARSA法はSARSA法とほとんど同じですが、方策評価では次の時刻 $t+1$ の行動 $a_{t+1}$ として全ての可能性を考え、方策 $\pi$ に関する期待値をとります。

擬似コードは次のようになります。離散行動空間における期待値は内積 dot の形で書けることに注意してください。

for _ in range(N):

    # interaction
    history = environment.interact(pi)

    # policy evaluation
    for t in range(T):
        state, action, reward, state_next = history[t]
        Q_expt = dot(Q[state_next, :], pi[state_next, :])
        td_error = (reward + gamma * Q_expt) - Q[state, action]
        Q[state, action] += alpha * td_error

    # policy improvement
    for state in S:
        pi[state, :] = softmax(Q[state, :])

擬似コード上では探索を行う際に用いる方策 (行動方策) は最適化を行う方策 (目的方策) と同じとしましたが、目的方策とは異なる行動方策を考えることもできます。例えばExpected SARSA法の目的方策として貪欲方策、行動方策として $\epsilon$-貪欲方策を用いることにすれば、Q学習アルゴリズムに一致します。この意味でExpected SARSA法はQ学習を一般化したものになっています。

ちなみに、行動方策と目的方策が同じ強化学習アルゴリズムは 方策オン (on-policy) 、それらが異なる強化学習アルゴリズムは 方策オフ (off-policy) と呼ばれます。on-policy vs. off-policyを比較して議論することはしばしばあるので、少し勉強しておくといいかもしれません。

• 【強化学習】まとめてみた 第5回 (2) (Q学習だけじゃない！モンテカルロ法) 【方策ON、方策OFF】
• 今さら聞けない強化学習 (10): SarsaとQ学習の違い

後書き

強化学習の実装が完了次第、公開できればと思います。

参考

書籍

• Reinforcement Learning: An Introduction
• 強化学習 (強化学習プロフェッショナルシリーズ)