前書き

この記事では、強化学習の枠組みについて説明します。様々な強化学習アルゴリズムを理解するのに必要十分な知識が得られるような記事を目指しました。

「強化学習の枠組みを形式的に理解したい」が「教科書1冊読むのは少しハードルが高い」という方に向けて書かれています。そのため、冗長な表現をできるだけなくして記事の分量を減らしています。

強化学習について全く触れたことがないという方には少し難しく感じる部分もあるかもしれません。その際には他の強化学習入門の記事と合わせて読むことをお勧めします。例えば

などを読むと雰囲気がよくわかると思います。

なお、記事のメイントピックから離れる話題 (e.g. 定理の証明) については見出しに $\ast$ をつけています。必要がなければ読み飛ばしてください。

導入

強化学習では、 エージェント (行動主体者)がある環境の下で行動し、その環境から報酬を受け取るようなプロセスを考えます。エージェントはこの報酬をできるだけ多く獲得できるように行動の戦略を立てることを目指します。こうした枠組みを 強化学習 (reinforcement learning) と呼んでいます。

例としてブロック崩しゲームを考えてみましょう。ブロック崩しは画面下部のバーを左右に操作することで動く球を打ち返し、画面上部のブロックを壊していくゲームです。ブロック崩しをプレイする人は高いスコアを目指して試行錯誤し、はじめは球を打ち返すので精一杯だった人も次第に戦略を考えられるようになっていきます。
これを強化学習の用語を使って言い換えれば、エージェントであるプレイヤーは、環境であるブロック崩しのゲームを報酬であるスコアが上がるように一生懸命プレイします。こう考えると、強化学習の枠組みは決して難しいものではないと感じてもらえると思います。

理論

マルコフ決定過程 (Markov Decision Process, MDP)

より形式的な問題設定を見ていきましょう。基本的に、強化学習における環境は マルコフ決定過程 (Markov Decision Process, MDP) ${\mathcal M} = ({\mathcal S}, {\mathcal A}, R, p_0, p_T)$ として定義されます。¹

\begin{align}
{\mathcal S}: & \text{状態集合} \\
{\mathcal A}: & \text{行動集合} \\
R: & {\mathcal S} \times {\mathcal A} \to [R_{min}, R_{max}]: \text{報酬関数} \\
p_0: & {\mathcal S} \to [0, 1]: \text{初期状態分布} \\
p_T: & {\mathcal S} \times {\mathcal A} \times {\mathcal S} \to [0, 1]: \text{遷移確率関数}
\end{align}

ここでは状態集合 ${\mathcal S}$ は離散的、行動集合 ${\mathcal A}$ は離散的であると考えています。また、文献によっては報酬関数の定義などが多少異なっているものもありますが、おおよそこのような形で定義されています。

MDP環境は状態 $s \in {\mathcal S}$ を保持しており、エージェントはそれを観測して次の行動 $a \in {\mathcal A}$ を選択することになります。エージェントが行動 $a$ をとると環境の状態が遷移確率関数 $p_T$ に従って変化するとともに、行動に対するフィードバックとして報酬 $r$ が与えられます。エージェントはこうした環境との相互作用を通して報酬を集めていきます。

この記事ではエージェントが時刻 $T$ までに経験した状態・行動・報酬の系列 (履歴) $h_T$ を

\begin{align*}
h_T
\equiv \{ (s_0, a_0, r_0, s_1), (s_1, a_1, r_1, s_2), \dots (s_{T-1}, a_{T-1}, r_{T-1}, s_T) \}
\end{align*}

と記すことにします。

なお、他の文献では「時刻 $t$ に状態行動対 $(s_t, a_t)$ を環境に入力すると時刻 $t+1$ に報酬と新しい状態 $(r_{t+1}, s_{t+1})$ が出力される」というイメージに基づいて

\begin{align*}
h_T
\equiv \{ (s_0, a_0, r_1, s_1), (s_1, a_1, r_2, s_2), \dots (s_{T-1}, a_{T-1}, r_T, s_T) \}
\end{align*}

という記法を用いていることがあります。 Reinforcement Learning: An Introduction いわくどちらの記法も広く使われているとのことですが、どちらかというと1番目の記法を使った文献の方が多いように感じます。
この記事では1番目の記法を使って説明をしていきたいと思います。²

環境とエージェントの相互作用をPythonライクな擬似コードで書くと以下のような流れになります。 (変数名や関数名などは雰囲気で汲み取ってください。)
sample 関数は第1引数で指定された集合から第2引数で指定された確率分布に従って要素を抽出する関数だと考えてください。 done は終了フラグで、ここでは環境の状態が終了状態集合 $T$ に含まれているときに done = False を設定しています。

# S: state set
# T: terminal state set

state = sample(S, environment.p_0())
while not done:
    action = agent.choose_action(state)
    reward = environment.R(state, action)
    state = sample(S, environment.p_T(state, action))
    done = state in T

ちなみに、MDPより一般的なモデルとして部分観測マルコフ決定過程 (Partially Observable MDP, POMDP) というものもあります。POMDP環境における強化学習は非常に難しいと言われています。POMDPについてはこの記事では説明しません。

方策 (Policy)

強化学習の目標は「できるだけ多く報酬を受け取る」ことでした。エージェントはそのように行動の戦略を立てていくことになりますが、この行動の戦略を 方策 (policy) と呼びます。ところによっては「政策」と呼んでいることもありますが、この記事では「方策」で統一表記します。

方策 $\pi$ は環境の状態 $s$ を入力とし、エージェントがとる行動 $a$ を選択するものです。例えば、状態 $s$ を観測したら行動 $a$ を決定的に選択する関数 $\pi: {\mathcal S} \to {\mathcal A}$ は方策と考えることができます。これを 決定的方策 (deterministic policy) と呼びます。

それに対し、状態 $s$ を観測したら行動 $a$ を確率分布 $\pi(\cdot | s)$ に従って選択するというモデルを考えることもできます。これを 確率的方策 (stochastic policy) と呼びます。確率的方策は、状態 $s$ を入力として行動 $a$ に関する確率分布を出力する関数 $\pi: {\mathcal S} \to ({\mathcal A} \to [0, 1])$ と考えることができます。

決定的方策は確率的方策の特別な場合と見ることもできますが、あえて区別すると都合が良いこともあります。この記事では、特に言及しない限り決定的方策を確率的方策と区別せず扱います。

目的関数

ここまで「エージェントはできるだけ多く報酬がもらえるように行動の戦略を立てる」³ と書いてきましたが、この「報酬」というのは 累積報酬 (cumulative Reward) を指しています。エージェントは行動の結果すぐに得られる 即時報酬 (immediate reward) を最大化するのではなく、将来的に得られる報酬も含めて最大化することを目指す、ということです。

強化学習の目的関数として用いられる累積報酬の1つは報酬和 (sum of rewards)で、以下のように定義されます。

\begin{align}
J(\pi) \equiv \sum_{t=0}^T R(s_t, a_t)
\end{align}

ここで $T \in {\mathbb N}$ は (有限) エピソード長を表しています。無限長のエピソードを考える場合には、累積報酬の値が発散しないように 割引率 (discount factor) $\gamma \in (0, 1]$ を導入した 割引累積報酬 (cumulative discounted reward) を利用します。

$$
J(\pi) \equiv \sum_{t=0}^T \gamma^t R(s_t, a_t)
$$

割引率 $\gamma$ は「エージェントがどのくらい長期的な視点で学習を行うか」を決めるハイパーパラメータとなります。 $\gamma$ を大きくするとエージェントは長期的な視点で学習を行うようになり、逆に $\gamma$ を小さくすると近視眼的になり、即時報酬をより重視するようになります。通常、$\gamma$ は大きな値 (e.g. 0.99) に設定されます。なお、 $\gamma = 1$ とすると割引累積報酬は報酬和に一致します。

以降は無限長のエピソードにおける割引累積報酬 ($\gamma \in (0, 1)$) を目的関数とする場合を想定して話を進めていきます。

価値関数 (Value Function)

累積報酬を最大化するような方策 $\pi$ を求めるには、方策の価値を評価する必要があります。方策の価値は 価値関数 (value function) として次のように定義されます。

\begin{align}
V^{\pi}(s) \equiv {\mathbb E}_{\pi} \left[\sum_{t=0}^{\infty} \gamma^t R(s_t, a_t) \middle| s_0 = s \right] \\
Q^{\pi}(s, a) \equiv {\mathbb E}_{\pi} \left[\sum_{t=0}^{\infty} \gamma^t R(s_t, a_t) \middle| s_0 = s, a_0 = a \right] \\
\end{align}

ここで ${\mathbb E}_{\pi}[\cdot]$ は

\begin{align}
{\mathbb E}_{s_0 \sim p_0(\cdot), s_{t+1} \sim p_T(\cdot|s_t,a_t), a_t \sim \pi(\cdot|s_t)}[\cdot]
\end{align}

の略記とします。${\mathbb E}$ は期待値演算を表します。

$V^{\pi}, Q^{\pi}$ はそれぞれ 状態価値関数 、 状態行動価値関数 (Q関数) と呼ばれています。
$V^{\pi}(s)$ は現在の状態 $s$ の価値、すなわち初期状態 $s$ で方策 $\pi$ に従って行動を選択していったときの累積報酬の期待値を表しています。
$Q^{\pi}(s,a)$ は現在の状態行動対 $(s,a)$ の価値、すなわち初期状態 $s$ で行動 $a$ を選択し、以降方策 $\pi$ に従って行動を選択したときの累積報酬の期待値を表しています。状態行動すべてに関して期待値をとっていることに注意してください。

ベルマン方程式 (Bellman Equation)

価値関数の定義から、次の関係式が成立することがすぐにわかります。

\begin{align}
V^{\pi}(s)
&= {\mathbb E}_{\pi} \left[\sum_{t=0}^{\infty} \gamma^t R(s_t, a_t) \middle| s_0 = s \right] \\
&= {\mathbb E}_{a \sim \pi(\cdot | s)} \left[ {\mathbb E}_{\pi} \left[ \sum_{t=0}^{\infty} \gamma^t R(s_t, a_t) \middle| s_0 = s, a_0 = a \right] \right] \\
&= {\mathbb E}_{a \sim \pi(\cdot | s)} \left[ Q^{\pi}(s,a) \right]
\end{align}

注意して計算すれば $Q^{\pi}$ を $V^{\pi}$ によって表すこともできます。

\begin{align}
Q^{\pi}(s,a)
&= {\mathbb E}_{\pi} \left[\sum_{t=0}^{\infty} \gamma^t R(s_t, a_t) \middle| s_0 = s, a_0 = a \right] \\
&= R(s,a) + {\mathbb E}_{\pi} \left[\sum_{t=1}^{\infty} \gamma^t R(s_t, a_t) \right] \\
&= R(s,a) + \gamma {\mathbb E}_{s' \sim p_T(\cdot | s,a)} \left[ {\mathbb E}_{\pi} \left[\sum_{t=0}^{\infty} \gamma^t R(s_{t+1}, a_{t+1}) \middle| s_1 = s' \right] \right] \\
&= R(s,a) + \gamma {\mathbb E}_{s' \sim p_T(\cdot | s,a)} \left[ V^{\pi}(s') \right]
\end{align}

最終行の変形は少し理解しづらいかもしれませんが、初期状態を $s_1 = s'$ と考えれば価値関数 $V^{\pi}(s')$ に等しいことがわかります。

こうして2つの価値関数は相互再帰的な関係にあることがわかりました。

\begin{align}
V^{\pi}(s) &= {\mathbb E}_{a \sim \pi(\cdot | s)} \left[ Q^{\pi}(s,a) \right] \\
Q^{\pi}(s,a) &= R(s,a) + \gamma {\mathbb E}_{s' \sim p_T(\cdot | s,a)} \left[ V^{\pi}(s') \right]
\end{align}

一方の式をもう一方に代入することで、自己再帰的に価値関数を表すこともできます。

\begin{align}
V^{\pi}(s) &= {\mathbb E}_{a \sim \pi(\cdot | s)} \left[ R(s,a) + \gamma {\mathbb E}_{s' \sim p_T(\cdot | s,a)} \left[ V^{\pi}(s) \right] \right] \\
Q^{\pi}(s,a) &= R(s,a) + \gamma {\mathbb E}_{s' \sim p_T(\cdot | s,a)} \left[ {\mathbb E}_{a' \sim \pi(\cdot | s')} \left[ Q^{\pi}(s',a') \right] \right]
\end{align}

これらを ベルマン方程式 (Bellman equation) と呼びます。ベルマン方程式は強化学習において最も基本的な式の1つです。

ベルマン作用素 (Bellman Operators)

ベルマン方程式に関連する話ということで、ここで ベルマン作用素 (Bellman operator) を導入したいと思います。

ベルマン作用素 ${\mathbf B}_{\pi}$ は関数 $V: {\mathcal S} \to {\mathbb R}$ を受け取って同じ型の関数を返す作用素で、${\mathbf \Upsilon}_{\pi}$ は関数 $Q: {\mathcal S} \times {\mathcal A} \to {\mathbb R}$ を受け取って同じ型の関数を返す作用素です。

\begin{align}
({\mathbf B}_{\pi} V)(s)
&\equiv {\mathbb E}_{a \sim \pi(\cdot | s)} \left[ R(s,a) + \gamma {\mathbb E}_{s' \sim p_T(\cdot | s,a)} \left[ V(s') \right] \right] \\
({\mathbf \Upsilon}_{\pi} Q)(s,a)
&\equiv R(s,a) + \gamma {\mathbb E}_{s' \sim p_T(\cdot | s,a)} \left[ {\mathbb E}_{a' \sim \pi(\cdot | s')} \left[ Q(s',a') \right] \right]
\end{align}

ベルマン方程式と照らし合わせてみると、価値関数 $V^{\pi}, Q^{\pi}$ に関して次の等式が成立することがわかります。

\begin{align}
\forall s \in {\mathcal S}. & ({\mathbf B}_{\pi} V^{\pi})(s) = V^{\pi}(s) \\
\forall s \in {\mathcal S}, a \in {\mathcal A}. & ({\mathbf \Upsilon}_{\pi} Q^{\pi})(s,a) = Q^{\pi}(s,a)
\end{align}

すなわち、価値関数 $V^{\pi} / Q^{\pi}$ はベルマン作用素 ${\mathbf B}_{\pi} / {\mathbf \Upsilon}_{\pi}$ の不動点です。⁴

\begin{align}
\forall n \in {\mathbb N}. & ({\mathbf B}^n_{\pi} V^{\pi})(s) = V^{\pi}(s) \\
\forall n \in {\mathbb N}. & ({\mathbf \Upsilon}^n_{\pi} Q^{\pi})(s,a) = Q^{\pi}(s,a)
\end{align}

価値関数の推定

ここまでの話を振り返ってみましょう。
強化学習の目標である「累積報酬の最大化」を達成する方策を見つけるためには、その方策の価値を見極める必要がありました。その価値を表す量として価値関数 $V^{\pi}, Q^{\pi}$ が定義され、それらがベルマン方程式と呼ばれる関係を満たすということを見ました。また、 (価値関数を不動点とするような) ベルマン作用素を導入すればベルマン方程式を簡潔に表現することができるということも確認しました。

さて、この項では価値関数 $V^{\pi}, Q^{\pi}$ を推定することを考えます。
価値関数の定義を見るとわかると思いますが、価値関数は状態行動系列 ${ (s_0, a_0), (s_1, a_1), \dots }$ ⁵ に関して期待値をとっているため、これを純粋に計算することは現実的ではありません。計算量が (エピソードの長さ $T$ に対して) 指数的に増大してしまうからです。

価値関数を効率よく推定するために利用するのが 動的計画法 (Dynamic Programming, DP) の考え方です。動的計画法というのは、それに含まれる帰納的な構造を利用することで問題をいくつかの部分問題に分割し、効率よく解を求めるアルゴリズムの枠組みです。⁶

ここでは価値関数 $V^{\pi}, Q^{\pi}$ を推定する問題を考えています。この問題に含まれる再帰的な構造はベルマン方程式に現れています。ベルマン作用素 ${\mathbf B}_{\pi}, {\mathbf \Upsilon}_{\pi}$ を用いた場合の式を再掲します。

\begin{align}
\forall s \in {\mathcal S}. & ({\mathbf B}_{\pi} V^{\pi})(s) = V^{\pi}(s) \\
\forall s \in {\mathcal S}, a \in {\mathcal A}. & ({\mathbf \Upsilon}_{\pi} Q^{\pi})(s,a) = Q^{\pi}(s,a)
\end{align}

実は、価値関数はこのベルマン作用素を用いた動的計画法によって求めることができます。この動的計画法に関する定理で重要なものを次に示します。

--
ベルマン作用素の収束性に関する定理

任意の関数 $V: {\mathcal S} \to {\mathbb R}, Q: {\mathcal S} \times {\mathcal A} \to {\mathbb R}$ に対して、

\begin{align}
\lim_{n \to \infty} ({\mathbf B}^n_{\pi} V)(s) &= V^{\pi}(s) \\
\lim_{n \to \infty} ({\mathbf \Upsilon}^n_{\pi} Q)(s,a) &= Q^{\pi}(s,a)
\end{align}

が成立する。

よって、任意の関数 $V: {\mathcal S} \to {\mathbb R} / Q: {\mathcal S} \times {\mathcal A} \to {\mathbb R}$ を初期値としてベルマン作用素 ${\mathbf B}_{\pi} / {\mathbf \Upsilon}_{\pi}$ を十分多くの回数適用すれば、真の価値関数 $V^{\pi} / Q^{\pi}$ を得ることができます。これは少し後で述べる 価値反復法 (value iteration) および 方策反復法 (policy iteration) の基礎になります。

方策の更新

ベルマン作用素を利用することで、現在の方策 $\pi$ の価値 $V^{\pi}, Q^{\pi}$ を求めることができそうです。では、この価値関数を利用することでより良い方策 $\pi'$ を見つけることを考えましょう。

単純には、新しい方策 $\pi'$ を価値 $Q^{\pi}$ に基づいて以下のように設定するのが良さそうです。

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

つまり、各状態 $s$ に対して最も行動価値 $Q^{\pi}(s,a)$ が高い行動 $a$ を決定的に選択するような方策に設定するということです。(このような方策は 貪欲方策 (greedy policy) と呼ばれることがあります。)

実際、このような方策は「より良い」方策になっています。詳しく言えば、方策 $\pi'$ の状態価値 $V^{\pi'}$ は (すべての状態 $s \in {\mathcal S}$ に対して) 方策 $\pi$ の状態価値 $V^{\pi}$ よりも高いことが示されています。

\begin{align}
\forall s \in {\mathcal S}. V^{\pi}(s) \le V^{\pi'}(s)
\end{align}

最適価値関数・最適方策

value iteration / policy iteration に進む前に、 最適価値関数 (optimal value function) と 最適方策 (optimal policy) について見ておきましょう。

最適価値関数 $V^{\ast}, Q^{\ast}$ は以下のように定義されます。

\begin{align}
V^{\ast}(s) &\equiv \max_{\pi}{V^{\pi}}(s) \\
Q^{\ast}(s,a) &\equiv \max_{\pi}{Q^{\pi}}(s,a)
\end{align}

そして最適方策 $\pi^{\ast}$ は以下のように定義されます。強化学習の目標はこの最適方策を求めることになります。

\begin{align}
\pi^{\ast} \equiv \mathrm{argmax}_{\pi} V^{\pi}(s)
\end{align}

割引累積報酬を目的関数とする場合には、最適方策が決定的な関数になることが知られています。

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

最適方策の定義から明らかに $V^{\ast} = V^{\pi^{\ast}}$ が成立します。同様に $Q^{\ast} = Q^{\pi^{\ast}}$ も成立します。

方策反復法 (Policy Iteration)

では、最適方策を求める強化学習アルゴリズムの1つである 方策反復法 (value iteration) を見ていきましょう。

方策反復法では、 方策評価 (policy evaluation) と 方策改善 (policy improvement) を交互に繰り返すことで最適価値関数ならびに最適方策を求めます。方策評価のステップでは、ベルマン作用素を用いることで現在の方策 $\pi$ に関する価値関数を求めます。方策改善のステップでは、より価値が高くなるように方策を更新します。アルゴリズムの概略は次の通りです。

while True:

    # policy evaluation (n-step)
    while (|V - V_old| >= eps):    
        V_old = V
        for s in S:
            V(s) = max(R(s,a) + gamma * expt(V_old, s_next, p_T), a)
    
    # policy improvement
    pi_old = pi
    for s in S:
        pi(s) = argmax(R(s,a) + gamma * expt(V, s_next, p_T), a)
    if (pi == pi_old):
        break

ここで max(f, x) は x に関する f(x) の最大値を、 expt(f, x, p) は x に関する f(x) の期待値を計算する関数だと考えてください。
上の擬似コードを見ると、価値関数の更新は更新幅が小さくなるまで何度も実行されることがわかりますが、その際にすべての状態 $s \in {\mathcal S}$ を同期的に更新するようにします。

方策反復法がうまく動作する背景にはベルマン作用素の収束性に関する定理および 方策改善定理 があります。こうした定理については価値反復法・方策反復法の後に載せました。価値反復法・方策反復法の理解に必須というわけではありませんが、余裕があれば見ておくと良いと思います。

価値反復法 (Value Iteration)

方策反復法では、方策評価のステップで正確に価値関数を求めるためにベルマン作用素を繰り返し適用していました。そのため、1回の方策改善を実行するまでの時間が非常に長くなってしまいます。

そこで、価値反復法では方策評価のステップを簡素にして高速化を図っています。アルゴリズムの概略は次のようになります。

while (|V - V_old| >= eps):

    # policy evaluation (1-step)
    V_old = V
    for s in S:
        V(s) = max(R(s,a) + gamma * expt(V_old, s_next, p_T), a)
      
    # policy improvement
    pi_old = pi
    for s in S:
        pi(s) = argmax(R(s,a) + gamma * expt(V, s_next, p_T), a)

ベルマン作用素に関する定理を思い出せば、価値反復法がうまく動作することがわかると思います。

* 方策評価に関する定理 (ベルマン作用素の収束性)

方策評価のステップではベルマン作用素を繰り返し適用することで方策 $\pi$ に関する価値関数 $V^{\pi}, Q^{\pi}$ を求めますが、このアルゴリズムによって価値関数を正確に推定できることは定理として示されています。

ベルマン作用素の収束性に関する定理

$V: {\mathcal S} \to {\mathbb R}$ を任意の関数とする。このとき、ベルマン作用素

\begin{align}
({\mathbf B}_{\pi} V)(s) \equiv {\mathbb E}_{a \sim \pi(\cdot | s)} \left[ R(s,a) + \gamma {\mathbb E}_{s' \sim p_T(\cdot | s,a)} \left[ V(s) \right] \right]
\end{align}

を繰り返し適用することで真の価値関数 $V^{\pi}$ を得ることができる。すなわち

\begin{align}
\forall s \in {\mathcal S}. \lim_{n \to \infty} ({\mathbf B}^n_{\pi} V)(s) = V^{\pi}(s)
\end{align}

が成立する。

証明としては、ベルマン作用素を $n$ 回適用した関数 $({\mathbf B}^n_{\pi} V)$ と価値関数 $V^{\pi}$ の差の上界・下界を示した上で、はさみうちの原理を適用することで示します。

ベルマン作用素の収束性に関する定理 - 証明

まず、ベルマン作用素

\begin{align}
({\mathbf B}_{\pi} V)(s)
\equiv {\mathbb E}_{a \sim \pi(\cdot | s), s' \sim p_T(\cdot | s,a)} \left[ R(s,a) + \gamma V(s') \right]
\end{align}

を関数 $V: {\mathcal S} \to {\mathbb R}$ に $n$ 回適用した結果を計算します。

\begin{align}
({\mathbf B}^n_{\pi} V)(s_0)
&= {\mathbf B}^{n-1}_{\pi} \left( {\mathbb E}_{a_0 \sim \pi(s_0), s_1 \sim p_T(s_0,a_0)} \left[ R(s_0,a_0) + \gamma V(s_1) \right] \right) \\
&= {\mathbf B}^{n-1}_{\pi} \left( {\mathbb E}_{a_0 \sim \pi(s_0)} \left[ R(s_0,a_0) \right] + \gamma {\mathbb E}_{a_0 \sim \pi(s_0), s_1 \sim p_T(s_0,a_0)} \left[ V(s_1) \right] \right) \\
&= {\mathbb E}_{a_0 \sim \pi(s_0)} \left[ R(s_0,a_0) \right] + \gamma {\mathbf B}^{n-1}_{\pi} \left( {\mathbb E}_{a_0 \sim \pi(s_0), s_1 \sim p_T(s_0,a_0)} \left[ V(s_1) \right] \right) \\
&\dots \sum_{t=0}^n \gamma^t {\mathbb E}_{\pi} \left[ R(s_t,a_t) \right] + \gamma^n {\mathbb E}_{\pi} \left[ V(s_n) \right]
\end{align}

価値関数 $V^{\pi}$ との差をとると

\begin{align}
({\mathbf B}^n_{\pi} V)(s_0) - V^{\pi}(s_0)
&= \left( \sum_{t=0}^{n-1} \gamma^t {\mathbb E}_{\pi} \left[ R(s_t,a_t) \right] - V^{\pi}(s_0) \right) + \gamma^n {\mathbb E}_{\pi} \left[ V(s_n) \right] \\
&= \left( \sum_{t=0}^{n-1} \gamma^t {\mathbb E}_{\pi} \left[ R(s_t,a_t) \right] - \sum_{t=0}^{\infty} \gamma^t {\mathbb E}_{\pi} \left[ R(s_t,a_t) \right] \right) + \gamma^n {\mathbb E}_{\pi} \left[ V(s_n) \right] \\
&= \sum_{t=n}^{\infty} \gamma^t {\mathbb E}_{\pi} \left[ R(s_t,a_t) \right] + \gamma^n {\mathbb E}_{\pi} \left[ V(s_n) \right]
\end{align}

となります。

第1項ついては、報酬関数が有界であることを利用して上界・下界を与えることができます。報酬関数の上界を $R_{\mathrm{max}}$ 、下界を $R_{\mathrm{min}}$ とすると

\begin{align}
&R_{\mathrm{min}} \le {\mathbb E}_{\pi} \left[ R(s_t,a_t) \right] \le R_{\mathrm{min}} \\
\Rightarrow&
\sum_{t=n}^{\infty} \gamma^t R_{\mathrm{min}}
\le \sum_{t=n}^{\infty} \gamma^t {\mathbb E}_{\pi} \left[ R(s_t,a_t) \right]
\le \sum_{t=n}^{\infty} \gamma^t R_{\mathrm{min}} \\
\Leftrightarrow&
\frac{\gamma^n}{1 - \gamma} R_{\mathrm{min}}
\le \sum_{t=n}^{\infty} \gamma^t {\mathbb E}_{\pi} \left[ R(s_t,a_t) \right]
\le \frac{\gamma^n}{1 - \gamma} R_{\mathrm{max}}
\end{align}

という形で上下からおさえることができます。

第2項については、価値関数が有界であることを利用します。

\begin{align}
\gamma^n \min_{s}{V(s)}
\le \gamma^n {\mathbb E}_{\pi} \left[ V(s_n) \right]
\le \gamma^n \max_{s}{V(s)}
\end{align}

よって、全体としては

\begin{align}
&\frac{\gamma^n}{1 - \gamma} R_{\mathrm{min}} + \gamma^n \min_{s}{V(s)}
\le ({\mathbf B}^n_{\pi} V)(s_0) - V^{\pi}(s_0)
\le \frac{\gamma^n}{1 - \gamma} R_{\mathrm{max}} + \gamma^n \max_{s}{V(s)} \\
\Leftrightarrow&
\gamma^n \left( \frac{R_{\mathrm{min}}}{1 - \gamma} + \min_{s}{V(s)} \right)
\le ({\mathbf B}^n_{\pi} V)(s_0) - V^{\pi}(s_0)
\le \gamma^n \left( \frac{R_{\mathrm{max}}}{1 - \gamma} + \max_{s}{V(s)} \right)
\end{align}

となります。したがって $n \to \infty$ の極限においては

\begin{align}
&\gamma^n \left( \frac{R_{\mathrm{min}}}{1 - \gamma} + \min_{s}{V(s)} \right) \to 0 \\
&\gamma^n \left( \frac{R_{\mathrm{max}}}{1 - \gamma} + \max_{s}{V(s)} \right) \to 0
\end{align}

となるため、はさみうちの原理より中辺も $({\mathbf B}^n_{\pi} V)(s_0) - V^{\pi}(s_0) \to 0$ が従います。

* 方策改善に関する定理 - 方策改善定理

方策改善のステップにおいて貪欲方策を選択すれば、対応する価値関数の値が大きくなることは方策改善定理で示されています。⁵

方策改善定理

$\pi: {\mathcal S} \to {\mathcal A}, \pi': {\mathcal S} \to {\mathcal A}$ を決定的方策とする。 $\pi, \pi'$ が

\begin{align}
\forall s \in {\mathcal S}. Q^{\pi}(s, \pi'(s)) \ge V^{\pi}(s)
\end{align}

を満たしているとき、

\begin{align}
\forall s \in {\mathcal S}. V^{\pi'}(s) \ge V^{\pi}(s)
\end{align}

が成立する。

方策改善定理は不等式 $Q^{\pi}(s, \pi'(s)) \ge V^{\pi}(s)$ を繰り返し適用することで証明することができます。

方策改善定理 - 証明

任意の状態 $s_0 \in {\mathcal S}$ に対して

\begin{align}
V^{\pi}(s_0)
&\le Q^{\pi}(s_0, \pi'(s_0)) \\
&= R(s_0,a_0) + \gamma {\mathbf E}_{s_1 \sim p(\cdot|s_0,a_0)} \left[ V^{\pi}(s_1) \right] \\
&\le R(s_0,a_0) + \gamma {\mathbf E}_{s_1 \sim p(\cdot|s_0,a_0)} \left[ Q^{\pi}(s_1, \pi'(s_1)) \right] \\
&= R(s_0,a_0) + \gamma {\mathbf E}_{s_1 \sim p(\cdot|s_0,a_0)} \left[ \left( R(s_1,a_1) + \gamma {\mathbf E}_{s_2 \sim p(\cdot|s_1,a_1)} \left[ V^{\pi}(s_2) \right] \right) \right] \\
\dots & \le \sum_{t=0}^{\infty} \gamma^t R(s_t, \pi'(s_t)) \\
&= V^{\pi'}(s_0)
\end{align}

が成立するため、主張の式が従います。

強化学習 vs. プランニング

ここまで方策反復法・価値反復法について紹介しましたが、これらのアルゴリズムは「環境が既知である」と仮定しています。つまり、2つのアルゴリズムは環境のダイナミクスや報酬の設計を知った上で最適な方策を求めていることになります。
(MDP環境に含まれる $p_T, R$ を利用して計算を実行しているためです。)

しかし、一般的な強化学習の問題では「環境が未知である」ことがほとんどです。エージェントは未知の環境下で試行錯誤を繰り返し、環境に関する情報を集めながら方策を最適化することが求められます。
(環境が既知である場合にはプランニング、環境が未知である場合には強化学習と区別するようです。)

未知の環境における強化学習アルゴリズムについてはこの記事では詳しくは説明しませんが、1つのアプローチとしては収集したデータから環境情報 $p_T, R$ を推定し、それを用いてプランニングのアルゴリズム (e.g. 方策反復法) を実行する、というものが考えられます。
(モデルベース強化学習 (model-based reinforcement learning) のアプローチです。)

もちろん、環境情報を推定することなく価値関数および方策を求めるというアプローチも多数存在します。
(モデルフリー強化学習 (model-free reinforcement learning) のアプローチです。)

モデルベース強化学習 vs. モデルフリー強化学習の分類に関しては例えば以下の記事が参考になります。

後書き

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

参考

書籍

記事

強化学習 (星の本棚)

MDPの基礎となる概念として マルコフ過程 (Markov process) というものがあります。これは状態集合 ${\mathcal S}$ と状態に関する遷移確率関数 $p_T$ から定義される系で、ここに行動や報酬の概念を加えるとMDPになります。 ↩
2番目の記法を使いたくない理由として $R_{t+1} = R(s_t, a_t)$ となるのが紛らわしいというのもあります。 ↩
なお、「できるだけ多く報酬を受け取る」ことを目指す代わりに「できるだけ罰則を受け取らない」ように学習するというプロセスも考えることができます。(実際そのように定式化されている文献もあります。) これらは本質的に同義であるため、ここではエージェントは「できるだけ多く報酬を受け取る」ことを目指すものとします。 ↩
関数 $f$ を適用しても変化しないような値 $x$ を (関数 $f$ の) 不動点と言います。すなわち、関数 $f$ の不動点は $x = f(x) = f(f(x)) = \dots$ を満たす $x$ となります。 ↩
動的計画法の考え方は強化学習以外の分野で使われることの方が圧倒的に多い気がしますが、提案したのはベルマン方程式にも名前が残っているBellmanです。 ↩ ↩²
価値関数の値が変化しないこともありますが、このとき価値関数は最適価値関数になっています。 ↩