$Q$学習やSARSA学習では，状態の価値を求めて，その価値から方策を決定していた．ここでは，方策そのものを学習する方法，方策勾配法を考える．

導出

難しそうな式が見えるが，今までの知識に加えて合成関数の微分さえわかっていれば理解はできると思う．

目的関数

　ニューラルネットワークの全ての重みのパラメータを$\theta$とする．方策$\pi_{\theta}(a\mid s)$を学習する．このとき，方策勾配法では，方策のパラメータ$\theta$を更新する．正解がわからないため，損失関数を用意することはできないが，目的関数を用意してこれを最大化するように学習する¹．

　目的関数を設定する．エピソードタスクで，方策$\pi_{\theta}$を実行したときの軌道(trajectory)が次の通りであったとする． $$ \tau = (S_0, A_0, R_0, S_1, A_1, R_1, \cdots, S_{T-1}, A_{T-1}, R_{T-1}, S_T) $$ この$\tau$から収益は決定するため，次の通りに関数$G(\tau)$が定義できる． $$ G(\tau) = R_0 + \gamma R_1 + \gamma^2 R_2 + \cdots + \gamma^{T-1} R_{T-1} + \gamma^T R_T $$

目的関数$J(\theta)$は次のように表される． $$ J(\theta) = \mathbb{E}_{\tau\sim\pi_{\theta}}[G(\tau)] $$ 波の記号$a\sim A$は，$A$によって$a$が抽出(サンプリング，あるいは生成)されることを表す． この式は$\pi_{\theta}$から生成された軌道$\tau$の収益の期待値を表す． あとは，目的関数の勾配がわかれば，勾配上昇法²でパラメータを更新することができる．

勾配の導出

では，目的関数の勾配$\nabla_{\theta} J(\theta)$を求める． 先に結果を示すと，次のようになる． $$ \nabla_{\theta} J(\theta) = \mathbb{E}_{\tau\sim\pi_{\theta}} \left[ \sum_{t=0}^{T} G(\tau) \nabla_{\theta} \log \pi_\theta (A_t | S_t) \right] $$

期待値の式からの変形によって導出する．

$$ \begin{align} \nabla_{\theta} J(\theta) &= \nabla_\theta \mathbb{E}_{\tau\sim\pi_{\theta}} \left[ G(\tau) \right] \\ &= \nabla_{\theta} \sum_r \mathrm{Pr}(\tau | \theta)G(\tau) \\ &= \sum_r \nabla_{\theta} \mathrm{Pr}(\tau | \theta)G(\tau) \\ &= \sum_r \left\{ G(\tau)\nabla_{\theta} \mathrm{Pr}(\tau | \theta) + \mathrm{Pr}(\tau | \theta)\nabla_{\theta} G(\tau) \right\} \\ &= \sum_r G(\tau)\nabla_{\theta} \mathrm{Pr}(\tau | \theta) \\ &= \sum _{r} G(\tau) \mathrm{Pr}(\tau | \theta) \frac{\nabla_{\theta} \mathrm{Pr}(\tau | \theta)}{\mathrm{Pr}(\tau | \theta)} \\ &= \sum _{r} G(\tau) \mathrm{Pr}(\tau | \theta) \nabla_{\theta} \log \mathrm{Pr}(\tau | \theta) \\ &= \mathbb{E}_{\tau\sim\pi_{\theta}} \left[ G(\tau) \nabla_{\theta} \log \mathrm{Pr}(\tau | \theta) \right] \\ &= \mathbb{E}_{\tau\sim\pi_{\theta}} \left[ \sum_{t=0}^{T} G(\tau) \nabla_{\theta} \log \pi_\theta (A_t | S_t) \right] \end{align} $$

• 式$(2)$: 期待値を確率$\times$収益の総和に変形
• 式$(3)$: $\nabla$を移動．足し算した後に微分しても，微分した後に足し算しても結果は変わらない．
• 式$(4)$: 積の微分の公式を用いる．
• 式$(5)$: $\nabla_\theta G(\tau)$は，$0$である．なぜなら，$G(\tau)$は$\theta$に依存しないからである．
  • いやいや，$\tau$は$\theta$によって決まるから，$G(\tau)$は$\theta$に依存するだろ，と思われるかもしれない(筆者は思った)．確かに，$\theta$から$\tau$を取り出したときに，その$\tau$は$\theta$に依存する．しかし，今見ているのはある一つの特定の$\tau$である．様々な$\theta$が考えられるが，どの$\theta$から取り出した$\tau$でも，その$\tau$自身はどれも同じであるから，$G(\tau)$はいつも同じ，つまり定数である．
• 式$(6)$: $\mathrm{Pr}(\tau | \theta)/\mathrm{Pr}(\tau | \theta) = 1$を掛け算した．
  • $\nabla$が掛かっているものは変わっていないことに注意
• 式$(7)$: $\log$の合成関数の微分の逆を行っている³． $$ (\log f(x))’ = \frac{f’(x)}{f(x)} $$
• 式$(8)$: 確率$\times$そのときの値の形をしていたので期待値として表す．

式$(9)$は，少し飛躍がある．$\mathrm{Pr}(\tau | \theta)$を展開する．なお，$p(S_0)$は，始めの状態が$S_0$である確率を表す． $$ \begin{align*} \mathrm{Pr}(\tau | \theta) = p(S_0) \prod_{t=0}^{T-1} \pi_\theta (A_t | S_t) p(S_{t+1} | S_t, A_t) \end{align*} $$ 対数をとると，積が和で表されるので，次のようになる． $$ \begin{align*} \log \mathrm{Pr}(\tau | \theta) = \log p(S_0) + \sum_{t=0}^{T-1} \log \pi_\theta (A_t | S_t) + \sum_{t=0}^{T-1} \log p(S_{t+1} | S_t, A_t) \end{align*} $$ よって，$\nabla_\theta \log \mathrm{Pr}(\tau | \theta)$は， $$ \begin{align*} \nabla_\theta \log \mathrm{Pr}(\tau | \theta) = \nabla_\theta \log p(S_0) + \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta (A_t | S_t) + \sum_{t=0}^{T-1} \nabla_\theta \log p(S_{t+1} | S_t, A_t) \end{align*} $$ このうち，$p(S_0)$と$p(S_{t+1} | S_t, A_t)$は$\theta$に依存しないので， $$ \begin{align*} \nabla_\theta \log \mathrm{Pr}(\tau | \theta) &= \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta (A_t | S_t) \\ &= \nabla_\theta \sum_{t=0}^{T-1} \log \pi_\theta (A_t | S_t) \end{align*} $$ となる．以上で，導出は終わりである．

勾配上昇法

最も簡単な更新式は次である．$\alpha$は学習率である． $$ \theta \leftarrow \theta + \alpha \nabla_{\theta} J(\theta) $$

$\nabla_\theta J(\theta)$を計算するために，モンテカルロ法を用いる．期待値の式が次であるため， $$ \begin{align*} \nabla_{\theta} J(\theta) &= \mathbb{E}_{\tau\sim\pi_{\theta}} \left[ \sum_{t=0}^{T} G(\tau) \nabla_{\theta} \log \pi_\theta (A_t | S_t) \right] \end{align*} $$ $\theta$に従い，$\tau$をサンプリングし，収益を計算をする． $$ \text{sampling:} \tau_i \sim \pi_\theta \quad (i = 1, \dots, N) \\ x^{(i)} = \sum_{t=0}^{T} G(\tau_i) \nabla_{\theta} \log \pi_\theta (A_t | S_t) \\ \nabla_{\theta} J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} x^{(i)} $$ サンプルが$N=1$つだけの場合，次の式になる．これを使う場合は，エピソードの各行動をするたびに，$\nabla_{\theta} \log \pi_\theta (A_t | S_t)$を計算し，その値$G(\tau)$を足していくような実装となる． $$ \begin{align*} \nabla_{\theta} J(\theta) \approx \sum_{t=0}^{T} G(\tau) \nabla_{\theta} \log \pi_\theta (A_t | S_t) \end{align*} $$

実装

例のポールを倒れないようにするやつを実装する．

ソフトマックス関数

$n$個の要素を持つベクトル$x$を入力すると，次のようなベクトルを返す関数である． $$ \begin{align*} \mathrm{softmax}(x) = \left( \frac{\exp(x_1)}{\sum_{i=1}^{n} \exp(x_i)}, \dots, \frac{\exp(x_n)}{\sum_{i=1}^{n} \exp(x_i)} \right) \end{align*} $$ $\exp(a)$は$e^a$を表し，これは各$e^{x_i}$を$\sum_{i=1}^{n} \exp(x_i)$でわっているので，全ての値を足すと1になる．また，$e^a$は正の値であるので，各要素は0から1の間に収まる．この値は確率として解釈できる．

モデル

ReLU関数とソフトマックス関数の$2$層のネットワークを用いる．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Policy(Model):
    def __init__(self, action_size):
        super().__init__()
        self.l1 = L.Linear(128)
        self.l2 = L.Linear(action_size)

    def forward(self, x):
        x = F.relu(self.l1(x))
        x = F.softmax(self.l2(x))
        return x

「行動の種類数」次元の出力をソフトマックス関数に通すことで，各行動の確率として解釈できるようにしている．

　各行動の報酬とその確率を保存しておき，勾配の式にしたがって目的関数を計算する．プログラムでは，目的関数を負にして，損失関数として扱っている．計算が終わったら最後にoptimizerのupdateメソッドを呼び出して，パラメータを更新する．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def update(self):
    self.pi.cleargrads()

    G, loss = 0, 0
    for reward, prob in reversed(self.memory):
        G = reward + self.gamma * G

    for reward, prob in self.memory:
        loss += -F.log(prob) * G

    loss.backward()
    self.optimizer.update()
    self.memory = []

全体のコードは本の作者様のGitHubに置いてあるので，そちらを参照してください．

ただし，この方法では効率が悪い．

REINFORCEアルゴリズム

概要

$$ \nabla_{\theta} J(\theta) = \mathbb{E}_{\tau\sim\pi_{\theta}} \left[ \sum_{t=0}^{T} G(\tau) \nabla_{\theta} \log \pi_\theta (A_t | S_t) \right] $$ 　さっきまで使っていたこの式の問題点を考えると，どの時刻$t$に対しても$G(\tau)$との積を取っている点が気になる．というのも，$t=T$のときにも$G(\tau)$が使われてしまっているのである．$t=T$は，最後の行動であり，その行動の重みとして，それまでのすべての行動$\tau$に関する収益$G(\tau)$を使っていることになる．つまり，$t=T$の行動をする前の情報が入ってきてしまっている．これは，他の$t$も同じで，それ以前どんな動きをしていたのかも知らないのに，それまでの行動込みの収益$G(\tau)$を使ってしまっている．そこで，$t$以降の行動のみを考慮するようにする． $$ \nabla_{\theta} J(\theta) = \mathbb{E}_{\tau\sim\pi_{\theta}} \left[ \sum_{t=0}^{T} G_t \nabla_{\theta} \log \pi_\theta (A_t | S_t) \right] \\ G_t = R_t + \gamma R_{t+1} + \dots + \gamma^{T-t} R_{T} $$

証明

勝手に$G_t$に変えていいのか疑問に思うが，これは証明ができる． 証明は本には載っておらず，証明はこちらに書いてある．

todo: 証明を理解する

ベースライン

ベースラインとは

todo: 書く

Actor-Critic

$G(\tau)$から$b(S_t)$(ベースライン)を引き算する．$b(S_t)$は$S_t$の関数であれば何でもいい． $$ \begin{align*} \nabla_\theta J(\pi_\theta) &= \mathbb{E}_{\tau\sim\pi_{\theta}} \left[ \sum_{t=0}^{T} G(\tau) \nabla_{\theta} \log \pi_\theta (A_t | S_t) \right] \\ \nabla_\theta J(\pi_\theta)&= \mathbb{E}_{\tau\sim\pi_{\theta}} \left[ \sum_{t=0}^{T} (G(\tau) - b(S_t))\nabla_{\theta} \log \pi_\theta (A_t | S_t) \right] \end{align*} $$ 予測の精度が高くなるため，分散が小さくなる．

さて，肝心の$b(S_t)$であるが，これは状態価値関数を使う．新たな変数として$w$を価値関数を表すニューラルネットワークのパラメータ，$V_w(S_t)$をそれに基づいた状態価値関数とする． $$ \nabla_\theta J(\pi_\theta) = \mathbb{E}_{\tau\sim\pi_{\theta}} \left[ \sum_{t=0}^{T} (G(\tau) - V_w(S_t))\nabla_{\theta} \log \pi_\theta (A_t | S_t) \right] $$ そして，これをTD法にする． $$ \nabla_\theta J(\pi_\theta) = \mathbb{E}_{\tau\sim\pi_{\theta}} \left[ \sum_{t=0}^{T} (G(\tau) + \gamma V_w(S_{t+1})-V_w(S_t))\nabla_{\theta} \log \pi_\theta (A_t | S_t) \right] $$

証明

いきなりだが，全事象の各確率の合計は$1$であるため次の式は成り立つ． $$ \sum_x P_\theta(x) = 1 $$ この式の勾配を求めると，$0$になる． $$ \nabla_\theta \sum_x P_\theta(x) = \nabla_\theta 1 = 0 $$ 値が$0$である式を変形すると，次のようになる(途中で$\log$の合成関数の微分の逆を行っている)． $$ \begin{align*} \nabla_\theta \sum_x P_\theta(x) &= \sum_x \nabla_\theta P_\theta(x) \\ &= \sum _{x} P_\theta(x) \frac{\nabla_{\theta} P_\theta (x)}{P_\theta (x)} \\ &= \sum_{x}P_\theta(x) \nabla_\theta \log P_\theta (x) \\ &= \mathbb{E}_{x\sim P_\theta} [\nabla_\theta \log P_\theta(x)] \end{align*} $$ これはつまり，次が成り立つということだ． $$ \mathbb{E}_{A_t\sim \pi_\theta} [\nabla_\theta \log \pi_(A_t|S_t)] = 0 $$ 好きな定数を掛け算しても$0$のままだ．定数である$S_t$の関数を掛け算しても問題ない(これは$A_t$に関する期待値だから)． $$ \mathbb{E}_{A_t\sim \pi_\theta} [b(S_t)\nabla_\theta \log \pi_\theta(A_t|S_t)] = 0 $$

実装

todo: 書く

Vの代わりにQ関数を使う

これも本には載っておらず，こちらに書いてある．

結論

$$ \nabla_\theta J(\pi_\theta) = \mathbb{E}_{\tau\sim\pi_{\theta}} \left[ \sum_{t=0}^{T} \left( \nabla_\theta \log \pi_\theta (a_t|s_t) \right) Q^{\pi_\theta}(s_t,a_t) \right] $$

証明

todo:書く

まとめ

方策勾配法は，基本的に次の式で表される． $$ \nabla_\theta J(\pi_\theta) = \mathbb{E}_{\tau\sim\pi_{\theta}} \left[ \sum_{t=0}^{T} \Phi_\tau\nabla_{\theta} \log \pi_\theta (A_t | S_t) \right] $$ $\Phi_\tau$は，手法によって異なる．

• $\Phi_\tau = G(\tau)$の場合
• $\Phi_\tau = G_t$の場合
• $\Phi_\tau = G(\tau) - V_w(S_t)$の場合
• $\Phi_\tau = G(\tau) + \gamma V_w(S_{t+1})-V_w(S_t)$の場合