走る作曲家のAIカフェ

目次

Overview

強化学習とは、エージェントが環境との相互作用を通じて、試行錯誤しながら最適な行動を学ぶ機械学習の一分野です。
このページでは、強化学習の基礎を学んでいきます。

Source

以下の講義・書籍を参考にしました。

Bandit Problem

強化学習の中で最もシンプルな問題の１つが「バンディット」である。「バンディット」とは「スロットマシン」のことであり、「多腕バンディット問題」とは、１本レバーのスロットマシンが複数台ある状況を指す。各マシンの当たりやすさは異なるが、どれが当たりやすいかは分からない。プレイヤーは決められた回数の中でプレイし、なるべく多く当てたいと考える。この状況では、スロットマシンは「環境」、プレイヤーは「エージェント」と呼ばれ、プレイは「行動」、当たったときにもらえるコインは「報酬」と呼ばれる。

スロットマシンである「環境」の状態は変化しない。プレイしたときにもらえるコインの枚数の期待値、すなわち「行動価値」が大きいスロットマシンを選んでプレイすればよい。行動 \(A\) に対する価値を \( q(A) = \mathbb{E}[R \mid A] \) で表す。真の行動価値を\(q(A)\)、行動価値の推定値を\(Q(A)\)とする。プレイヤーはスロットマシンの価値を事前に知ることはできないが、価値が最大のスロットマシンを選びたいと考える。しかし、実際にはプレイして、その結果から選択の善し悪しを推定する必要がある。

「実際に得られた報酬の平均値」をスロットマシンの価値の推定値として考えることができる。例えば、ある１台のスロットマシンを\(n\)回プレイし、実際に報酬\(R_1,R_2,...,R_n\)が得られたとき、行動価値の推定値は\(Q_n = \frac{R_1 + R_2 + \ldots + R_n}{n}\)となる。さらに、\(n\)回目の行動価値の推定値\(Q_n\)は、\(n\)個ある報酬の標本平均として求められ、\(Q_n = Q_{n-1} + \frac{1}{n}(R_n - Q_{n-1})\)と書き直すことができる。

プレイヤーの戦略として、これまでにプレイした結果をもとに一番良いスロットマシンを選ぶ、という方法が考えられる。各スロットマシンの価値の推定値の中で最も大きい値のスロットマシンを選ぶというのは、greedyな方法である。しかし、greedyな方法では、様々なスロットマシンを試すことなく、同一のスロットマシンが選ばれ続ける可能性がある。

これまでの経験を「活用」するだけでなく、「探索」も行うことでより良いスロットマシンを見つけようとする方法の代表例が、ε-greedy法である。ε-greedy法では、εの確率で探索（ランダムな行動）を行い、1-εの確率で活用（greedyな行動）を行う。

非定常問題、つまりスロットマシンの勝率がプレイする度に変動する場合、新しく得た報酬に対してより大きな重みを与える必要がある。標本平均を用いる場合、行動価値の推定値の更新式は\(Q_n = Q_{n-1} + \frac{1}{n}(R_n - Q_{n-1})\)であり、すべての報酬の重みは同じである。新しく得た報酬の重みを大きくするには、ステップサイズである\(1/n\)の代わりに、固定値\(α\)を使えばよい。このようにして、新しく得た報酬を重視する更新式は\(Q_n = Q_{n-1} + α(R_n - Q_{n-1})\)となる。

この更新式を用いると、各報酬に対する重みが過去になるにつれて指数関数的に減少する「指数移動平均」となる。

Markov Decision Process

エージェントの行動によって状況が変わる問題の一部はマルコフ決定過程（MDP）として定式化される。決定過程とは、エージェントが（環境と相互作用しながら）行動を決定する過程である。エージェントの行動によって変化する、エージェントが置かれる状況のことを「状態」と呼ぶ。エージェントは目先の報酬ではなく、将来を通して得られる報酬の総和を考える必要がある。

状態\(S_t\)に基づいてエージェントが行動\(A_t\)を行い、報酬\(R_t\)を得て、次の状態である\(S_{t+1}\)へと遷移する場合を考える。決定論的な状態遷移の場合、次の状態\(s'\)は、今の状態\(s\)と行動\(a\)によって一意に決まるため、\(s' = f(s, a)\)（状態遷移関数）という関数の形で表せる。

確率的な状態遷移の場合、状態\(s\)にいて行動\(a\)を行い、次の状態\(s'\)に移動する確率は\(p(s'|s, a)\)（状態遷移確率）と表せる。これまでにどのような状態にあって、どのような行動を行ってきたかという情報を必要としない性質をマルコフ性という。

エージェントが状態\(s\)にいて行動\(a\)を行い、次の状態が\(s'\)になったときに得られる報酬を\(r(s, a, s')\)という関数（報酬関数）で定義する。方策は、エージェントがどのように行動を決定するかを表す。決定論的な方策は、関数として\(a = \mu(s)\)のように定義できる。確率的な方策は、\(\pi(a|s)\)と表せる。

MDPの目標は、最適方策を見つけることである。MDPには、「終わり」のあるエピソードタスクと、「終わり」がない連続タスクがある。エージェントの目標は収益を最大にすることであり、収益は\(G_t=R_t+\gamma R_{t+1}+\gamma^2R_{t+2}+...\)として定義される。収益はエージェントが得る報酬の和であり、\(\gamma\)は「割引率」と呼ばれる。

収益の期待値は\(v_{\pi}(s)=\mathbb{E}[G_t|S_t=s,\pi]\)（状態価値関数）で表せる。方策\(\pi\)が変われば、エージェントが得る報酬も変わり、その総和である収益も変わる。状態価値関数は、\(v_{\pi}(s)=\mathbb{E_{\pi}}[G_t|S_t=s]\)として書くこともできる。\(v_{\pi}\)は真の状態価値関数であり、\(V_{\pi}\)は推定値としての状態価値関数を意味する。

最適方策\(\pi_*\)は、他のどの方策と比較しても、すべての状態において状態価値関数\(v_{\pi_*}(s)\)の値が大きい方策である。MDPでは、決定論的な最適方策が少なくとも一つ存在することが保証されている。最適方策における状態価値関数は、最適状態価値関数と呼ばれ、\(v_*\)で表す。

Bellman Equation

収益は\(G_t=R_t+\gamma R_{t+1}+\gamma^2R_{t+2}+...\)として定義され、以下のように式変形できる。

\[ \begin{align} G_t &= R_t+\gamma\{R_{t+1}(\gamma R_{t+2}+...)\} \\ &= R_t+\gamma G_{t+1} \end{align} \]

状態価値関数は\(v_{\pi}(s)=\mathbb{E_{\pi}}[G_t|S_t=s]\)と定義されるため、以下のように書ける。

\[ \begin{align} v_{\pi}(s) &= \mathbb{E_{\pi}}[R_t+\gamma G_{t+1}|S_t=s] \\ &= \mathbb{E_{\pi}}[R_t|S_t=s]+\gamma\mathbb{E_{\pi}}[G_{t+1}|S_t=s] \end{align} \]

状態が\(s\)で、エージェントが方策\(\pi(a|s)\)に従って行動し、状態遷移確率\(p(s'|s, a)\)に従って新しい状態\(s'\)に移行する場合を考える。

報酬関数が\(r(s, a, s')\)のとき、期待報酬は以下のように書ける。

\[ \begin{align} \mathbb{E_{\pi}}[R_t|S_t=s] &= \sum_{a}\sum_{s'}\pi(a|s)p(s'|s, a)r(s, a, s') \end{align} \]

また、以下の式が成り立つ。

\[ \begin{align} \mathbb{E}_{\pi}[G_{t+1}|S_t=s] &= \sum_{a}\sum_{s'}\pi(a|s)p(s'|s,a)\mathbb{E}_{\pi}[G_{t+1}|S_{t+1}=s'] \\ &= \sum_{a}\sum_{s'}\pi(a|s)p(s'|s,a)v_{\pi}(s') \end{align} \]

以上より、以下の式（ベルマン方程式）を導くことができる。

\[ \begin{align} v_{\pi}(s) &= \mathbb{E_{\pi}}[R_t|S_t=s] + \gamma\mathbb{E_{\pi}}[G_{t+1}|S_t=s] \\ &= \sum_{a}\sum_{s'}\pi(a|s)p(s'|s,a)r(s,a,s') + \gamma\sum_{a}\sum_{s'}\pi(a|s)p(s'|s,a)v_{\pi}(s') \\ &= \sum_{a}\sum_{s'}\pi(a|s)p(s'|s,a)\{r(s,a,s') + \gamma v_{\pi}(s')\} \end{align} \]

ベルマン方程式は、「状態\(s\)の価値関数」と「その次に取り得る状態\(s'\)の価値関数」との関係性を表した式である。

ベルマン方程式は、すべての状態\(s\)とすべての方策\(\pi\)について成り立つ。ベルマン方程式を使えば状態価値関数を求めることができる。

状態価値関数の２条件「状態」と「方策」に、「行動」を追加すると行動価値関数（Q関数）になる。Q関数を数式で表すと、\(q_{\pi}(s, a) = \mathbb{E_{\pi}}[G_t|S_t=s, A_t=a]\)となる。

Q関数は、時刻\(t\)の時に状態\(s\)で行動\(a\)を取り、時刻\(t+1\)以降では方策\(\pi\)に従った行動を取る。

その時に得られる収益の期待値が\(q_{\pi}(s, a)\)である。\(q_{\pi}(s, a)\)の行動\(a\)は方策\(\pi\)とは関係なく、自由に決めることができる。仮にQ関数の行動\(a\)を方策\(\pi\)に従って選ぶとすると、Q関数と状態価値関数は同じになる。

収益の期待値に関して、\(v_{\pi}(s)=\sum_{a}\pi(a|s)q_{\pi}(s, a)\)が成り立つ。

Q関数は以下のように展開でき、「Q関数を用いたベルマン方程式」を得る。

\[ \begin{align} q_{\pi}(s, a) &= \mathbb{E_{\pi}}[G_t|S_t=s, A_t=a] \\ &= \mathbb{E_{\pi}}[R_t+\gamma G_{t+1}|S_t=s, A_t=a] \\ &= \sum_{s'}p(s'|s, a)r(s, a, s')+\gamma\sum_{s'}p(s'|s, a)\mathbb{E_{\pi}}[G_{t+1}|S_{t+1}=s'] \\ &= \sum_{s'}p(s'|s, a)\{r(s, a, s')+\gamma v_{\pi}(s')\} \\ &= \sum_{s'}p(s'|s, a)\{r(s, a, s')+\gamma\sum_{a'}\pi(a'|s')q_{\pi}(s', a')\} \end{align} \]

ベルマン方程式は、ある方策\(\pi\)について成り立つ。

最適方策に関して成り立つ方程式をベルマン最適方程式と呼ぶ。

状態価値関数のベルマン方程式は次の式で表される。

\[ \begin{align} v_{\pi}(s) &= \sum_{a}\sum_{s'}\pi(a|s)p(s'|s,a)\{r(s,a,s') + \gamma v_{\pi}(s')\} \\ &= \sum_{a}\pi(a|s)\sum_{s'}p(s'|s,a)\{r(s,a,s') + \gamma v_{\pi}(s')\} \end{align} \]

最適方策を\(\pi_{*}(a|s)\)とした場合、次のようにベルマン方程式が成り立つ。

\[ \begin{align} v_{*}(s) &= \sum_{a}\pi_{*}(a|s)\sum_{s'}p(s'|s,a)\{r(s,a,s') + \gamma v_{*}(s')\} \end{align} \]

最適方策は\(\sum_{s'}p(s'|s,a)\{r(s,a,s') + \gamma v_{*}(s')\}\)の値が最大の行動を選び、その最大値がそのまま\(v_{*}\)になる。

これを数式で表すと、次のようになる。

\[ \begin{align} v_{*}(s) &= \max_{a}\sum_{s'}p(s'|s,a)\{r(s,a,s') + \gamma v_{*}(s')\} \end{align} \]

この式がベルマン最適方程式である。

行動価値関数（Q関数）についても同様にベルマン最適方程式を求めることができる。最適方策における行動価値関数は最適行動価値関数と呼ばれる。

Q関数のベルマン方程式は次のとおり。

\[ \begin{align} q_{\pi}(s, a) &= \sum_{s'}p(s'|s, a)\{r(s, a, s')+\gamma\sum_{a'}\pi(a'|s')q_{\pi}(s', a')\} \end{align} \]

この式に最適方策\(\pi_{*}\)を代入すると、以下のようになる。

\[ \begin{align} q_{*}(s, a) &= \sum_{s'}p(s'|s, a)\{r(s, a, s')+\gamma\sum_{a'} \pi_{*}(a'|s')q_{*}(s', a')\} \end{align} \]

状態価値関数のベルマン最適方程式と同様に展開すると、以下の式が得られる。

\[ \begin{align} q_{*}(s, a) &= \sum_{s'}p(s'|s, a)\{r(s, a, s')+\gamma\max_{a'}q_{*}(s', a')\} \end{align} \]

この式がQ関数に関するベルマン最適方程式である。

\(\pi\)を用いずに表せるのは、MDPでは決定論的な最適方策が少なくとも一つ存在するからである。

ここで、最適行動価値関数\(q_{*}(s, a)\)が分かっていると仮定すると、状態\(s\)における最適な行動は次のように求まる。

\[ \begin{align} \mu_{*}(s) &= arg\max_{a}q_{*}(s, a) \end{align} \]

行動価値関数におけるベルマン方程式をこの式に代入すると、以下の式が得られる。

\[ \begin{align} \mu_{*}(s) &= arg\max_{a}\sum_{s'}p(s'|s, a)\{r(s, a, s')+\gamma v_{*}(s')\} \end{align} \]

このように、最適状態価値関数\(v_{*}(s)\)を使って、最適方策\(\mu_{*}(s)\)を得ることができる。最適な行動価値関数を最大とするような行動であるため、「greedyな方策」といえる。

Dynamic Programming

動的計画法を使えば、状態と行動の数がある程度大きくなっても価値関数を評価することができる。

強化学習の問題は、多くの場合、方策評価と方策制御の２つのタスクに取り組むことになる。

方策評価とは、ある方策\(\pi\)が与えられたときに、その方策の価値関数\(v_{\pi}(s)\)や\(q_{\pi}(s, a)\)を求めることである。

方策制御とは、方策を制御して最適方策へと調整することである。

動的計画法では、方策評価を行う。

価値関数の定義は次のとおり。

\begin{align} v_{\pi}(s) &= \mathbb{E_{\pi}}[R_t+\gamma R_{t+1}+\gamma^2 R_{t+2}+...|S_t=s] \end{align}

無限を含む期待値の計算は不可能なので、次のベルマン方程式によって解決する。

\begin{align} v_{\pi}(s) &= \sum_{a}\sum_{s'}\pi(a|s)p(s'|s,a)\{r(s,a,s') + \gamma v_{\pi}(s')\} \end{align}

ベルマン方程式は、上式のように「現在の状態\(s\)の価値関数\(v_{\pi}(s)\)」と「次の状態\(s'\)の価値関数\(v_{\pi}(s')\)」との関係性を表す。

DPでは、ベルマン方程式を以下のように「更新式」へと変形する。

\begin{align} V_{k+1}(s) &= \sum_{a}\sum_{s'}\pi(a|s)p(s'|s,a)\{r(s,a,s') + \gamma V_{k}(s')\} \end{align}

\(V_{k}(s)\)は\(k\)回目に更新された価値関数、\(V_{k+1}(s)\)は\(k+1\)回目に更新された価値関数であり、共に「推定値」である。

この式の特徴は、「次に取り得る状態の価値関数\(V_{k}(s')\)」を使って、「今いる状態の価値関数\(V_{k+1}(s)\)」を更新することである。

ここで行っていることは「推定値\(V_{k}(s')\)」を使って「別の推定値\(V_{k+1}(s)\)」を改善することである。

推定値を使って推定値を改善するプロセスのことを、ブートストラッピングという。

DPでは、まず、\(V_{0}(s)\)の初期値を設定し、先に示した更新式によって\(V_{0}(s)\)から\(V_{1}(s)\)へと更新する。

この更新を繰り返し行うことで、最終的なゴールである\(V_{\pi}(s)\)へと近づけるアルゴリズムを、反復方策評価と呼ぶ。

反復方策評価では、\(V_{\pi}(s)\)への収束が証明されている。

DPのエッセンスは「同じ計算を二度しない」ことであり、その実現方法には、「トップダウン方式（メモ化）」と「ボトムアップ方式」がある。

今回の\(V_{0}(s), V_{1}(s), ...\)と1つずつ繰り上げながら価値関数を更新する手法は「ボトムアップ方式」である。

ゴールにおける価値関数の値は常に0である。

DPを使うことで、効率的に方策の評価を行うことができる。

目標の最適方策は、ベルマン最適方程式を満たす連立方程式を解くことで求められるが、計算量的に問題がある。

具体的には、状態のサイズを\(S\)、行動のサイズを\(A\)としたとき、解を求めるために\(A^S\)のオーダーの計算量が必要になる。

DPの反復方策評価によって方策を評価できたので、あとは方策の「改善」ができたらよい。

最適方策は以下の式で表される。

\begin{align} \mu_{*}(s) &= arg\max_{a}q_{*}(s, a) \\ &= arg\max_{a}\sum_{s'}p(s'|s, a)\{r(s, a, s')+\gamma v_{*}(s')\} \end{align}

最適方策は最大値をとる行動\(a\)によって決まるため、この式によって得られる方策は「greedyな方策」と呼ばれる。

最適価値関数\(v_{*}\)がわかれば、最適方策\(\mu_{*}\)が求まるが、\(v_{*}\)を知るには\(\mu_{*}\)が必要である。

「何らかの決定論的方策\(\mu\)」に対して上式を適用すると、以下のようになる。

\begin{align} \mu'(s) &= arg\max_{a}q_{\mu}(s, a) \\ &= arg\max_{a}\sum_{s'}p(s'|s, a)\{r(s, a, s')+\gamma v_{\mu}(s')\} \end{align}

ここでは、現状の方策を\(\mu(s)\)、方策\(\mu(s)\)における状態価値関数を\(v_{\mu}(s)\)、新たな方策を\(\mu'(s)\)とする。

もしすべての状態\(s\)において\(\mu(s)\)と\(\mu'(s)\)（greedy化された方策）が同じであれば、以下の式が成り立ち、方策\(\mu(s)\)は既に最適方策であるといえる。

\begin{align} \mu(s) &= arg\max_{a}q_{\mu}(s, a) \end{align}

逆に、greedy化によって方策が更新される場合、すべての状態\(s\)において\(v_{\mu'}(s) \geqq v_{\mu}(s)\)が成り立ち、方策は常に改善される。

したがって、最適方策を見つけるには、以下のようなフローを続ければよい。

greedy化によって方策が変更されない地点に到達したとき、その方策が最適方策であり、最適価値関数である。

評価と改善を繰り返すアルゴリズムを方策反復法と呼ぶ。

環境は状態遷移確率\(p(s'|s, a)\)と報酬関数\(r(s, a, s')\)によって表される。

強化学習の分野では、その2つを指して「環境のモデル」や単に「モデル」と呼ぶ。

環境のモデルが既知であれば、エージェントは何も行動することなく、価値関数を評価することができる。

方策反復法を使えば最適方策も見つけることができる。

エージェントが実際の行動を行わずに最適方策を見つける問題はプランニング問題と呼ばれる。

方策反復法のアイデアは、「評価」と「改善」という２つの過程を交互に繰り返すことである。

これを繰り返すことで、最適方策と最適価値関数に徐々に近づいていく。

方策反復法では「評価」と「改善」をそれぞれ"最大限"に行って、交互にフェーズを切り替える。

価値反復法では、「評価」と「改善」をそれぞれ"最小限"に行う。

改善フェーズで行うgreedy化は数式では次のように書ける。

\begin{align} \mu(s) &= arg\max_{a}\sum_{s'}p(s'|s, a)\{r(s, a, s')+\gamma V(s')\} \end{align}

argmaxによって行動は１つに決まるため、\(\mu(s)\)のように決定論的方策として表すことができる。

評価フェーズにおけるDPによる更新式は以下のように表される。

\begin{align} V'(s) &= \sum_{a}\sum_{s'}\pi(a|s)p(s'|s,a)\{r(s,a,s') + \gamma V(s')\} \end{align}

この式では、方策\(\pi(a|s)\)が確率的な方策として表記されているが、「改善」のフェーズを一度経由すれば、方策はgreedyな方策として表すことができる。

greedyな方策は、最大値を取る行動がただ１つ選ばれるため、決定論的な方策である。

そのため、上式における方策は、決定論的な方策\(\mu(s)\)として扱うことができ、\(a=\mu(s)\)として、以下のように簡略化できる。

\begin{align} V'(s) &= \sum_{s'}p(s'|s,a)\{r(s,a,s') + \gamma V(s')\} \end{align}

これが「評価」フェーズにおける価値関数の更新式である。

「改善」フェーズの式と「評価」フェーズの式を見比べると、計算に重複が生じることが分かる。

よって、以下のように１つの式にまとめることができる。

\begin{align} V'(s) &= \max_{a}\sum_{s'}p(s'|s,a)\{r(s,a,s') + \gamma V(s')\} \end{align}

この式のとおり、最大値をとるmax演算子によって、価値関数を直接更新する。

方策を使わずに価値関数を更新していることから、この式によって最適価値関数を得るアルゴリズムは「価値反復法」と呼ばれる。

価値反復法はこの１つの式によって、「評価」と「改善」を同時に行う。

ベルマン最適方程式は次の式で表される。

\begin{align} v_{*}(s) &= \max_{a}\sum_{s'}p(s'|s,a)\{r(s,a,s') + \gamma v_{*}(s')\} \end{align}

したがって、価値反復法における式はベルマン最適方程式を「更新式」にしたものといえる。

また、価値反復法における式は次のようにも書ける。

\begin{align} V_{k+1}(s) &= \max_{a}\sum_{s'}p(s'|s,a)\{r(s,a,s') + \gamma V_{k}(s')\} \end{align}

この式によって\(V_{*}(s)\)が得られれば、最適方策\(\mu_{*}(s)\)は次のように得られる。

\begin{align} \mu_{*}(s) &= arg\max_{a}\sum_{s'}p(s'|s,a)\{r(s,a,s') + \gamma V_{*}(s')\} \end{align}

つまり、greedyな方策を求めれば、それが最適方策となる。

Monte Carlo Method

動的計画法を使えば、状態と行動の数がある程度大きくなっても価値関数を評価することができる。強化学習の問題は、多くの場合、方策評価と方策制御の２つのタスクに取り組むことになる。方策評価とは、ある方策\(\pi\)が与えられたときに、その方策の価値関数\(v_{\pi}(s)\)や\(q_{\pi}(s, a)\)を求めることである。方策制御とは、方策を制御して最適方策へと調整することである。動的計画法では、方策評価を行う。

価値関数の定義は次のとおり。

\[ \begin{align} v_{\pi}(s) &= \mathbb{E_{\pi}}[R_t+\gamma R_{t+1}+\gamma^2 R_{t+2}+...|S_t=s] \end{align} \]

無限を含む期待値の計算は不可能なので、次のベルマン方程式によって解決する。

\[ \begin{align} v_{\pi}(s) &= \sum_{a}\sum_{s'}\pi(a|s)p(s'|s,a)\{r(s,a,s') + \gamma v_{\pi}(s')\} \end{align} \]

ベルマン方程式は、上式のように「現在の状態\(s\)の価値関数\(v_{\pi}(s)\)」と「次の状態\(s'\)の価値関数\(v_{\pi}(s')\)」との関係性を表す。

DPでは、ベルマン方程式を以下のように「更新式」へと変形する。

\[ \begin{align} V_{k+1}(s) &= \sum_{a}\sum_{s'}\pi(a|s)p(s'|s,a)\{r(s,a,s') + \gamma V_{k}(s')\} \end{align} \]

\(V_{k}(s)\)は\(k\)回目に更新された価値関数、\(V_{k+1}(s)\)は\(k+1\)回目に更新された価値関数であり、共に「推定値」である。

この式の特徴は、「次に取り得る状態の価値関数\(V_{k}(s')\)」を使って、「今いる状態の価値関数\(V_{k+1}(s)\)」を更新することである。ここで行っていることは「推定値\(V_{k}(s')\)」を使って「別の推定値\(V_{k+1}(s)\)」を改善することである。推定値を使って推定値を改善するプロセスのことを、ブートストラッピングという。

DPでは、まず、\(V_{0}(s)\)の初期値を設定し、先に示した更新式によって\(V_{0}(s)\)から\(V_{1}(s)\)へと更新する。この更新を繰り返し行うことで、最終的なゴールである\(V_{\pi}(s)\)へと近づけるアルゴリズムを、反復方策評価と呼ぶ。反復方策評価では、\(V_{\pi}(s)\)への収束が証明されている。

DPのエッセンスは「同じ計算を二度しない」ことであり、その実現方法には、「トップダウン方式（メモ化）」と「ボトムアップ方式」がある。今回の\(V_{0}(s), V_{1}(s), ...\)と1つずつ繰り上げながら価値関数を更新する手法は「ボトムアップ方式」である。ゴールにおける価値関数の値は常に0である。

DPを使うことで、効率的に方策の評価を行うことができる。目標の最適方策は、ベルマン最適方程式を満たす連立方程式を解くことで求められるが、計算量的に問題がある。具体的には、状態のサイズを\(S\)、行動のサイズを\(A\)としたとき、解を求めるために\(A^S\)のオーダーの計算量が必要になる。

DPの反復方策評価によって方策を評価できたので、あとは方策の「改善」ができたらよい。最適方策は次の式で表される。

\[ \begin{align} \mu_{*}(s) &= arg\max_{a}q_{*}(s, a) \\ &= arg\max_{a}\sum_{s'}p(s'|s, a)\{r(s, a, s')+\gamma v_{*}(s')\} \end{align} \]

最適方策は最大値をとる行動\(a\)によって決まるため、この式によって得られる方策は「greedyな方策」と呼ばれる。

最適価値関数\(v_{*}\)がわかれば、最適方策\(\mu_{*}\)が求まるが、\(v_{*}\)を知るには\(\mu_{*}\)が必要である。「何らかの決定論的方策\(\mu\)」に対して上式を適用すると、以下のようになる。

\[ \begin{align} \mu'(s) &= arg\max_{a}q_{\mu}(s, a) \\ &= arg\max_{a}\sum_{s'}p(s'|s, a)\{r(s, a, s')+\gamma v_{\mu}(s')\} \end{align} \]

ここでは、現状の方策を\(\mu(s)\)、方策\(\mu(s)\)における状態価値関数を\(v_{\mu}(s)\)、新たな方策を\(\mu'(s)\)とする。

もしすべての状態\(s\)において\(\mu(s)\)と\(\mu'(s)\)（greedy化された方策）が同じであれば、以下の式が成り立ち、方策\(\mu(s)\)は既に最適方策であるといえる。

\[ \begin{align} \mu(s) &= arg\max_{a}q_{\mu}(s, a) \end{align} \]

逆に、greedy化によって方策が更新される場合、すべての状態\(s\)において\(v_{\mu'}(s) \geqq v_{\mu}(s)\)が成り立ち、方策は常に改善される。

したがって、最適方策を見つけるには、以下のようなフローを続ければよい。

greedy化によって方策が変更されない地点に到達したとき、その方策が最適方策であり、最適価値関数である。評価と改善を繰り返すアルゴリズムを方策反復法と呼ぶ。

環境は状態遷移確率\(p(s'|s, a)\)と報酬関数\(r(s, a, s')\)によって表される。強化学習の分野では、その2つを指して「環境のモデル」や単に「モデル」と呼ぶ。環境のモデルが既知であれば、エージェントは何も行動することなく、価値関数を評価することができ る。方策反復法を使えば最適方策も見つけることができる。エージェントが実際の行動を行わずに最適方策を見つける問題はプランニング問題と呼ばれる。

方策反復法のアイデアは、「評価」と「改善」という２つの過程を交互に繰り返すことである。

これを繰り返すことで、最適方策と最適価値関数に徐々に近づいていく。方策反復法では「評価」と「改善」をそれぞれ"最大限"に行って、交互にフェーズを切り替える。価値反復法では、「評価」と「改善」をそれぞれ"最小限"に行う。

改善フェーズで行うgreedy化は数式では次のように書ける。

\[ \begin{align} \mu(s) &= arg\max_{a}\sum_{s'}p(s'|s, a)\{r(s, a, s')+\gamma V(s')\} \end{align} \]

argmaxによって行動は１つに決まるため、\(\mu(s)\)のように決定論的方策として表すことができる。

評価フェーズにおけるDPによる更新式は以下のように表される。

\[ \begin{align} V'(s) &= \sum_{a}\sum_{s'}\pi(a|s)p(s'|s,a)\{r(s,a,s') + \gamma V(s')\} \end{align} \]

この式では、方策\(\pi(a|s)\)が確率的な方策として表記されているが、「改善」のフェーズを一度経由すれば、方策はgreedyな方策として表すことができる。

greedyな方策は、最大値を取る行動がただ１つ選ばれるため、決定論的な方策である。そのため、上式における方策は、決定論的な方策\(\mu(s)\)として扱うことができ、\(a=\mu(s)\)として、以下のように簡略化できる。

\[ \begin{align} V'(s) &= \sum_{s'}p(s'|s,a)\{r(s,a,s') + \gamma V(s')\} \end{align} \]

これが「評価」フェーズにおける価値関数の更新式である。

「改善」フェーズの式と「評価」フェーズの式を見比べると、計算に重複が生じることが分かる。よって、以下のように１つの式にまとめることができる。

\[ \begin{align} V'(s) &= \max_{a}\sum_{s'}p(s'|s,a)\{r(s,a,s') + \gamma V(s')\} \end{align} \]

この式のとおり、最大値をとるmax演算子によって、価値関数を直接更新する。方策を使わずに価値関数を更新していることから、この式によって最適価値関数を得るアルゴリズムは「価値反復法」と呼ばれる。価値反復法はこの１つの式によって、「評価」と「改善」を同時に行う。

ベルマン最適方程式は次の式で表される。

\[ \begin{align} v_{*}(s) &= \max_{a}\sum_{s'}p(s'|s,a)\{r(s,a,s') + \gamma v_{*}(s')\} \end{align} \]

したがって、価値反復法における式はベルマン最適方程式を「更新式」にしたものといえる。また、価値反復法における式は次のようにも書ける。

\[ \begin{align} V_{k+1}(s) &= \max_{a}\sum_{s'}p(s'|s,a)\{r(s,a,s') + \gamma V_{k}(s')\} \end{align} \]

この式によって\(V_{*}(s)\)が得られれば、最適方策\(\mu_{*}(s)\)は次のように得られる。

\[ \begin{align} \mu_{*}(s) &= arg\max_{a}\sum_{s'}p(s'|s,a)\{r(s,a,s') + \gamma V_{*}(s')\} \end{align} \]

つまり、greedyな方策を求めれば、それが最適方策となる。

Temporal Difference

モンテカルロ法は、エピソードの「終わり」にたどり着いてからでないと、価値関数の更新ができない。なぜなら、エピソードの終わりになって初めて「収益」が確定するからである。連続タスクの場合、モンテカルロ法は使うことができない。また、エピソードタスクであっても、エピソードを終えるのに時間がかかる場合は、モンテカルロ法だと価値関数の更新に多くの時間を要する。特にエピソードの最初の段階では、エージェントの方策はランダムなことが多いため、さらに多くの時間を必要とする。

TD法では、環境のモデルを使わずに、行動を１つ行うたびに価値関数を更新する手法である。エピソードの終わりを待つのではなく、一定の時間が進むごとに方策の評価と改善を行う。TD法は、「モンテカルロ法」と「動的計画法」を合わせたような手法である。

収益は以下のように定義される。

\[ \begin{align} G_t &= R_t+\gamma\{R_{t+1}(\gamma R_{t+2}+...)\} \\ &= R_t+\gamma G_{t+1} \end{align} \]

この収益を用いて、価値関数は以下のように定義される。

\[ \begin{align} v_{\pi}(s) &= \mathbb{E_{\pi}}[G_{t}|S_t=s] & \text{(a)}\\ &= \mathbb{E_{\pi}}[R_t+\gamma G_{t+1}|S_t=s] & \text{(b)} \end{align} \]

MC法を使った手法は式(a)から、DP法を使った手法は式(b)から導くことができる。MC法では、期待値を計算する代わりに、実際に得られた収益のサンプルデータを平均することで、式(a)の期待値を近似する。平均には、標本平均と指数移動平均の２つがある。指数移動平均を実現するには、新しい収益が得られるたびに固定値\(\alpha\)で更新する。

これを数式で表すと次のようになる。

\[ \begin{align} V'_{\pi}(S_t)=V_{\pi}(S_t)+\alpha\{G_t-V_{\pi}(S_t)\} \end{align} \]

ここで、現状の価値関数を\(V_{\pi}\)、更新後の価値関数を\(V'_{\pi}\)とする。この式では、現状の価値関数\(V_{\pi}\)を\(G_t\)の方へと更新している。どのくらい\(G_t\)の方へ更新するかを\(\alpha\)で調整する。DP法は式(b)に基づいて期待値を計算する。MC法とは異なり、DP法では数式どおり期待値を計算する。

数式で表すと次のようになる。

\[ \begin{align} v_{\pi}(s) &= \sum_{a}\sum_{s'}\pi(a|s)p(s'|s,a)\{r(s,a,s') + \gamma v_{\pi}(s')\} \end{align} \]

上のように、状態遷移確率\(p(s'|s, a)\)と報酬関数\(r(s, a, s')\)を使って期待値を計算する。この式はベルマン方程式である。

つまり、DP法はベルマン方程式に基づいて以下のように価値関数を逐次更新する。

\[ \begin{align} V'_{\pi}(s) &= \sum_{a}\sum_{s'}\pi(a|s)p(s'|s,a)\{r(s,a,s') + \gamma V_{\pi}(s')\} \end{align} \]

この式で重要な点は、「今の状態における価値関数」を「次の状態における価値関数」を使って更新することである。このとき、すべての遷移を考慮している点が特徴である。DP法は、今の価値関数の推定値を、次の価値関数の推定値を使って更新する。この原理は「ブートストラップ」と呼ばれる。

一方、MC法は実際に得られた経験によって、今の価値関数を更新する。この２つの手法を融合させたのが、TD法である。TD法は、次の行動と価値関数だけを使って現在の価値関数を更新する。

重要な点は、次の２つである。

TD法を数式から導く。

\[ \begin{align} v_{\pi}(s) &= \sum_{a}\sum_{s'}\pi(a|s)p(s'|s,a)\{r(s,a,s') + \gamma v_{\pi}(s')\} & \text{(c)} \\ &= \mathbb{E_{\pi}}[R_t+\gamma v_{\pi}(S_{t+1})|S_t=s] & \text{(d)} \end{align} \]

式(c)はすべての候補に関して、\(r(s, a, s')+\gamma v_{\pi}(s')\)というように、報酬と次の価値関数を計算する。これを期待値の形で書き直すと式(d)になる。TD法では式(d)を用いて価値関数を更新するにあたり、\(R_t+\gamma v_{\pi}(S_{t+1})\)の部分をサンプルデータから近似する。

数式で表すと、TD法の更新式は以下のようになる。

\[ \begin{align} V'_{\pi}(S_t) &= V_{\pi}(S_t)+\alpha\{R_t+\gamma V_{\pi}(S_{t+1}) - V_{\pi}(S_t)\} \end{align} \]

ここで、\(V_{\pi}\)は価値関数の推定値であり、目的地が\(R_t+\gamma V_{\pi}(S_{t+1})\)になる。この目的地である\(R_t+\gamma V_{\pi}(S_{t+1})\)はTDターゲットと呼ばれる。TD法は、TDターゲットの方向へと\(V_{\pi}(S_t)\)を更新する。ここではTDターゲットとして１ステップ先の情報を使ったが、\(n\)ステップ先の情報を使うことも考えられる。これは「\(n\)ステップのTD法」と呼ばれる。

環境のモデルが未知の場合に使える道具として、MC法とTD法の２つがある。ここでの疑問は、MC法とTD法のどちらを使うべきか、もしくはどちらが優れているかということである。連続タスクではMC法を使えないため、TD法を使うことになる。しかし、エピソードタスクに関してはどちらが良いかわからない。実際、どちらが優れているかは理論的に証明されていない。

しかし現実の多くの問題では、TD法の方が速く学習できる（価値関数の更新が速く進む）。その理由は、それぞれが何をターゲットとしているかを見るとわかる。MC法は\(G_t\)をターゲットとし、その方向へと\(V_{\pi}\)を更新する。\(G_t\)はゴール にたどり着いてから得られる収益のサンプルデータである。

一方、TD法のターゲットは、１ステップ先の情報をもとに計算する。TD法の場合、時間が１ステップ進むごとに価値関数を更新することができるため、効率の良い学習が期待できる。また、MC法のターゲットは、多くの時間を積み重ねて得られた結果であるため、その値は分散が大きくなる。一方、TD法は１ステップ先のデータに基づくため、その変動は小さくなる。

TDターゲットの中には推定値\(V_{\pi}\)が使われている。TD法は「推定値で推定値を更新している」ブートストラッピングである。TDターゲットは推定値を含んでいるため、正確な値ではなく、「偏り（バイアス）がある」と呼ばれる。ただし、そのバイアスは更新を繰り返すごとに小さくなり、最終的には0になる。

一方、MC法のターゲットには推定値が含まれない。つまり、MC法のターゲットには「偏り（バイアス）がない」ということになる。

「方策オン型」の方策制御に、SARSAという手法がある。ここでも、評価と改善のプロセスを繰り返し行うことで最適方策へと近づけていく。改善フェーズでは方策をgreedy化する必要があり、\(V_{\pi}(s)\)の場合は環境のモデルが必要になる。

一方、\(Q_{\pi}(s, a)\)であれば以下のように計算でき、環境のモデルを必要としない。

\[ \begin{align} \mu(s) &= arg\max_{a}Q_{\pi}(s, a) \end{align} \]

TD法の更新式は以下のとおりである。

\[ \begin{align} V'_{\pi}(S_t) &= V_{\pi}(S_t)+\alpha\{R_t+\gamma V_{\pi}(S_{t+1}) - V_{\pi}(S_t)\} \end{align} \]

この式における状態価値関数\(V_{\pi}(S_t)\)を行動価値関数\(Q_{\pi}(S_t, A_t)\)に変更すると、以下の式が得られる。

\[ \begin{align} Q'_{\pi}(S_t, A_t) &= Q_{\pi}(S_t, A_t)+\alpha\{R_t+\gamma Q_{\pi}(S_{t+1}, A_{t+1}) - Q_{\pi}(S_t, A_t)\} \end{align} \]

これがQ関数を対象にしたTD法の更新式である。

方策オン型では、実際に行動を起こす方策（挙動方策）と評価・改善を行う方策（ターゲット方策）が一致する。方策オン型の手法の場合、挙動方策とターゲット方策が同じであるため、改善フェーズでは完全にgreedy化することはできない。もしそうしてしまうと、「探索」が行えなくなるため、ε-greedy法を使う。

エージェントが方策\(\pi\)に従って行動し、\((S_{t}, A_{t}, R_{t}, S_{t+1}, A_{t+1})\)というデータが得られた場合、先の更新式に従って、\(Q_{\pi}(S_t, A_t)\)を即座に更新することができる。そして、この更新が終わればすぐに「改善」フェーズへと進むことができる。この例では\(Q_{\pi}(S_t, A_t)\)が更新されるため、状態\(S_t\)における方策が変更される可能性がある。

具体的には、状態\(S_t\)における方策は以下のように更新できる。

\[ \begin{align} \pi'(a|S_t) &= \begin{cases} \arg\max_{a} Q_{\pi}(S_t, a) & \text{with probability } 1 - \epsilon \\ \text{random action} & \text{with probability } \epsilon \end{cases} \end{align} \]

このε-greedy法によって、状態\(S_t\)における行動の選び方が更新される。

方策オフ型の場合、エージェントは挙動方策とターゲット方策の２つの方策を持つ。挙動方策では、多様な行動を行って広くサンプルデータを集める。そしてサンプルデータを使って、ターゲット方策をgreedyに更新する。

このとき注意すべき点は次の２つである。

SARSAの更新式は次のようになる。

\[ \begin{align} Q'_{\pi}(S_t, A_t) &= Q_{\pi}(S_t, A_t)+\alpha\{R_t+\gamma Q_{\pi}(S_{t+1}, A_{t+1}) - Q_{\pi}(S_t, A_t)\} \end{align} \]

ペアデータ\((S_t, A_t)\)が更新される対象である。この\((S_t, A_t)\)という更新対象は任意に選ぶことができる。その選ばれたペアデータに対して次の時刻\(t+1\)の遷移を考える。このとき、次の状態\(S_{t+1}\)は、環境の状態遷移確率\(p'(s'|s, a)\)によってサンプリングされる。そして、状態\(S_{t+1}\)で選ばれる行動は、ターゲット方策\(\pi\)（もしくは挙動方策\(b\)）によってサンプリングされる。

そうして得られたサンプルデータを使い、先の更新式に従って\(Q_{\pi}(S_t, A_t)\)を更新する。このとき、方策\(\pi\)によって行動が選ばれることを明示すると、SARSAの更新式は次のように書ける。

\[ \begin{align} &\text{sampling: } A_{t+1} \sim \pi \\ &\ Q'_{\pi}(S_t, A_t) = Q_{\pi}(S_t, A_t)+\alpha\{R_t+\gamma Q_{\pi}(S_{t+1}, A_{t+1}) - Q_{\pi}(S_t, A_t)\} \end{align} \]

この\(R_t+\gamma Q_{\pi}(S_{t+1}, A_{t+1})\)は「TDターゲット」と呼ばれる。

行動\(A_{t+1}\)が方策\(b\)によってサンプリングされた場合を考える。その場合、重み\(\rho\)によってTDターゲットを補正する（重点サンプリング）。重み\(\rho\)は、「方策が\(\pi\)だったときにTDターゲットが得られる確率」と「方策が\(b\)だったときにTDターゲットが得られる確率」の比率である。

これを数式で表すと、次のようになる。

\[ \begin{align} \rho &= \frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})} \end {align} \]

よって、方策オフ型のSARSAの更新式は次のように表される。

\[ \begin{align} &\text{sampling: } A_{t+1} \sim \pi \\ &\ Q'_{\pi}(S_t, A_t) = Q_{\pi}(S_t, A_t)+\alpha\{\rho(R_t+\gamma Q_{\pi}(S_{t+1}, A_{t+1})) - Q_{\pi}(S_t, A_t)\} \end{align} \]

上式のとおり、行動は方策\(b\)によってサンプリングされ、重み\(\rho\)によってTDターゲットが補正される。方策オフ型のSARSAでは重点サンプリングを使う必要がある。

重点サンプリングは、結果が不安定になりやすいという問題があるため、使うのは避けたい。特に、２つの方策の確率分布が異なれば異なるほど、重点サンプリングで用いる重み\(\rho\)も大きく変動する。それによってSARSAの更新式にあるターゲットも変動するため、Q関数の更新が不安定になる。

これを解決するのが、Q学習である。Q学習は次の３つの特徴を持つ。

ベルマン方程式からSARSAが導出され、ベルマン最適方程式からQ学習が導出される。まずはベルマン方程式とSARSAの関係を見る。

方策\(\pi\)におけるQ関数を\(q_{\pi}(s, a)\)としたとき、ベルマン方程式は次の式で表される。

\[ \begin{align} q_{\pi}(s, a) &= \sum_{s'}p(s'|s, a)\{r(s, a, s')+\gamma\sum_{a'}\pi(a'|s')q_{\pi}(s', a')\} \end{align} \]

ベルマン方程式で重要な点は次の２つである。

つまり、ベルマン方程式は次の状態と次の行動のすべての候補を考慮する。

これを踏まえた上でSARSAを見ると、SARSAはベルマン方程式の「サンプリング版」とみなすことができる。「サンプリング版」というのは、すべての遷移ではなく、ある１つのサンプリングされたデータを使うということである。

SARSAでは、次の状態\(S_{t+1}\)は\(p(s'|s, a)\)に基づいてサンプリングする。そして、次の行動\(A_{t+1}\)は方策\(\pi(a|s)\)に基づいてサンプリングする。このときSARSAのTDターゲットは\(R_t+\gamma Q_{\pi}(S_{t+1}, A_{t+1})\)になる。このターゲットの方向へ少しだけQ関数を更新する。

このようにベルマン方程式とSARSAは対応していて、ベルマン最適方程式に対応するのがQ学習である。

価値反復法は、最適方策を得るための「評価」と「改善」という２つのプロセスを１つにまとめた手法である。価値反復法の重要な点は、ベルマン最適方程式に基づくただ１つの更新式を繰り返すことで最適方策が得られることである。

ここでは、ベルマン最適方程式による更新で、なおかつ、それを「サンプリング版」にした手法を考える。

Q関数のベルマン最適方程式は次のとおりである。

\[ \begin{align} q_{*}(s, a) &= \sum_{s'}p(s'|s, a)\{r(s, a, s')+\gamma\max_{a'}q_{*}(s', a')\} \end{align} \]

ここでは最適方策\(\pi_{*}\)におけるQ関数を\(q_{*}(s, a)\)で表す。ベルマン最適方程式は、ベルマン方程式とは異なり、max演算子が使われる。

Q学習では、推定値\(Q(S_t, A_t)\)のターゲットは、\(R_t+\gamma \max_{a}Q(S_{t+1}, a)\)になる。このターゲットの方向へとQ関数を更新する。

数式で表すと、以下のようになる。

\[ \begin{align} Q'(S_t, A_t) &= Q(S_t, A_t)+\alpha\{R_t+\gamma \max_{a}Q(S_{t+1}, a) - Q(S_t, A_t)\} \end{align} \]

この式に基づいてQ関数を繰り返し更新することで、最適方策におけるQ関数へと近づいていく。重要な点は、行動\(A_{t+1}\)がQ関数の最大値によって選ばれていることである。何らかの方策によってサンプリングされるのではなく、行動\(A_{t+1}\)はmax演算子によって選ばれる。そのため、方策オフ型の手法でありながら、重点サンプリングによる補正を行う必要がない。

Q学習はターゲット方策と挙動方策の２つを持ち、挙動方策\(b\)には「探索」を行わせる。よく用いられる挙動方策は、現在の推定値であるQ関数をε-greedy化した方策である。挙動方策が決まれば、それに従って行動を選びサンプルデータを集める。そして、エージェントが行動するたびに上式に従てQ関数を更新する。

エージェントの実装方法には、「分布モデル」と「サンプルモデル」がある。サンプルモデルの方がよりシンプルに実装できる。分布モデルとは、確率分布を明示的に保持するモデルである。サンプルモデルとは、サンプリングできることだけが条件のモデルである。