\usepackage{amsmath,amssymb}
\usepackage{pifont}

\usepackage{bigints}
\usepackage{bm}
\usepackage{siunitx}

\newcommand{\hs}[1]{\hspace{#1zw}}
\newcommand{\vs}[1]{\vspace{#1zh}}
\newcommand{\hsh}{\hs{0.5}}
\newcommand{\vsh}{\vs{0.5}}

\newcommand{\eref}[1]{\text{式\eqref{eq:#1}}}

\newcommand{\Nset}{\mathbf{N}}
\newcommand{\Zset}{\mathbf{Z}}
\newcommand{\Qset}{\mathbf{Q}}
\newcommand{\Rset}{\mathbf{R}}
\newcommand{\Cset}{\mathbf{C}}

\DeclareMathOperator*{\argmax}{\mathrm{arg\,max}}
\DeclareMathOperator*{\argmin}{\mathrm{arg\,min}}

\mathchardef\ordinarycolon\mathcode`\:
\mathcode`\:=\string"8000
\begingroup \catcode`\:=\active
  \gdef:{\mathrel{\mathop\ordinarycolon}}
\endgroup

\newcommand{\cond}[2]{#1\,|\,#2}

\newcommand{\expct}{\mathbb{E}}
\newcommand{\expctpi}{\mathbb{E}_{\pi}}

\newcommand{\Scal}{\mathcal{S}}
\newcommand{\Scalp}{\mathcal{S}^+}
\newcommand{\Acal}{\mathcal{A}}
\newcommand{\Rcal}{\mathcal{R}}

\newcommand{\sums}{\sum_s}
\newcommand{\sumsp}{\sum_{s'}}
\newcommand{\suma}{\sum_a}
\newcommand{\sumap}{\sum_{a'}}
\newcommand{\sumr}{\sum_r}

\newcommand{\pias}{\pi(\cond{a}s)}
\newcommand{\piapsp}{\pi(\cond{a'}{s'})}
\newcommand{\pitheta}{\pi_{\bm\theta}}
\newcommand{\pithetaas}{\pi_{\bm\theta}(\cond{a}s)}
\newcommand{\Ppi}{P_{\pi}}
\newcommand{\Ppin}{P_{\pi}^{~n}}
\newcommand{\Pcond}[2]{P(\cond{#1}{#2})}
\newcommand{\Ppicond}[2]{\Ppi(\cond{#1}{#2})}
\newcommand{\Ppincond}[2]{\Ppin(\cond{#1}{#2})}
\newcommand{\Psrsa}{\Pcond{s', r}{s, a}}
\newcommand{\Pssa}{\Pcond{s'}{s, a}}
\newcommand{\Prsa}{\Pcond{r}{s, a}}
\newcommand{\Ppisrs}{\Ppicond{s', r}s}
\newcommand{\Ppiss}{\Ppicond{s'}s}
\newcommand{\Ppirs}{\Ppicond{r}s}
\newcommand{\Ppinss}{\Ppincond{s'}s}
\newcommand{\Dpigamma}{D_{\pi}^{\,\gamma}}

\newcommand{\follow}{\sim}
\newcommand{\followpis}{\follow\pi(\cond{\cdot}s)}
\newcommand{\followpisp}{\follow\pi(\cond{\cdot}s')}
\newcommand{\twofollowPsa}{\follow\Pcond{\cdot, \cdot}{s, a}}
\newcommand{\onefollowPsa}{\follow\Pcond{\cdot}{s, a}}
\newcommand{\twofollowPpis}{\follow\Ppicond{\cdot, \cdot}s}
\newcommand{\onefollowPpis}{\follow\Ppicond{\cdot}s}

\newcommand{\Rsa}{R(s, a)}
\newcommand{\Rpis}{R_{\pi}(s)}

\newcommand{\prd}[1]{\bar{#1}}
\newcommand{\prds}{\prd{s}}
\newcommand{\prda}{\prd{a}}

\newcommand{\Vpi}{V_{\pi}}
\newcommand{\Vpis}{\Vpi(s)}
\newcommand{\Vpisp}{\Vpi(s')}
\newcommand{\Qpi}{Q_{\pi}}
\newcommand{\Qpisa}{\Qpi(s, a)}
\newcommand{\Qpispap}{\Qpi(s', a')}

\newcommand{\Vpihat}{\hat{V}_{\pi}}
\newcommand{\Vpihats}{\hat{V}_{\pi}(s)}
\newcommand{\Qpihat}{\hat{Q}_{\pi}}
\newcommand{\Qpihatsa}{\hat{Q}_{\pi}(s, a)}

\newcommand{\QED}{\blacksquare}

\newcommand{\Jtheta}{J_{\bm\theta}}
\newcommand{\df}{\bm\nabla}
\newcommand{\gpi}{g_{\pi}}
\newcommand{\gpisa}{\gpi(s, a)}
\newcommand{\gpispap}{\gpi(s', a')}

前回の続きです。

前回まではValue-basedな手法の基礎を扱ったので、今回はPolicy-basedな手法の基礎である、方策勾配定理の証明をしていきます。

方策勾配定理

準備

方策 $\pitheta の「良さ」 $\Jtheta を、

\Jtheta:=\expct\bigl[\cond{\Vpi(s_0)}{s_0\follow\iota(\cdot)}\bigr]=\sum_{s_0}\iota(s_0)\Vpi(s_0) \label{eq:J}

で定義します。式から分かるように、$s_0\in\Scal は開始状態です。状態価値は（方策に従った際の）割引報酬和の期待値なので、開始状態における状態価値を最大化する（ような方策を獲得する）のが強化学習の目的と言えるからです。

さて、方策勾配定理は、$\bm\nabla_{\bm\theta}\Jtheta を与える定理です。これが分かれば、勾配法によって方策を改善することができるため、重要な定理です。

なお、以下では $\bm\nabla_{\bm\theta} は単に $\df と表記します。また、新たな記号 $\gpisa を、

\gpisa:=\Qpisa\df\pias \label{eq:g}

と定義します。

さらに、微分操作が入っているので、ここでは $\Vpis や $\Qpisa、$\Jtheta 等は全て $\bm\theta で微分可能であるとしておきます。

定理の主張

\df\Jtheta=\sums\Dpigamma(s)\suma\gpisa \label{eq:thm}

証明

補題

まず、補題

\df\Vpis=\sumsp\sum_{n=0}^{\infty}\gamma^n\Ppinss\suma\gpi(s', a) \label{eq:lem}

を示します。

まず、$\df\Vpis を以下のように変形していきます。

\df\Vpis &=\df\suma\pias\Qpisa\hs1\text{（状態価値と行動価値の関係式その1）} \\
              &=\suma\bigl\{\Qpisa\df\pias+\pias\df\Qpisa\bigr\}\hs1\text{（積の微分）} \\
              &=\suma\gpisa+\suma\pias\df\Qpisa\hs1\text{（$\eref{g}$）} \\
              &=\suma\gpisa+\suma\pias\df\left\{\Rsa+\gamma\sumsp\Pssa\Vpisp\right\}\hs1\text{（状態価値と行動価値の関係式その2）} \\
              &=\suma\gpisa+\suma\pias\sumsp\gamma\Pssa\df\Vpisp\hs1\text{（$\Rsa$、$\Pssa$ は $\bm\theta$ に依存しない）} \\
              &=\suma\gpisa+\sumsp\gamma\suma\pias\Pssa\df\Vpisp\hs1\text{（総和を取る順序を交換）} \\
              &=\suma\gpisa+\sumsp\gamma\Ppiss\df\Vpisp\hs1\text{（定義）}

結局、得られた式は

\df\Vpis=\suma\gpisa+\sumsp\gamma\Ppiss\df\Vpisp \label{eq:rec-1}

となりますが、これは、$\df\Vpis の漸化式であると見なすことができます。そこで、この式の右辺の $\df\Vpisp に対して同様の変形を行い、さらに変形していきます。

\df\Vpis &=\suma\gpisa+\sumsp\gamma\Ppiss\left\{\sumap\gpispap+\sum_{s''}\gamma\Ppi(\cond{s''}{s'})\df\Vpi(s'')\right\} \\
              &=\suma\gpisa+\sumsp\gamma\Ppiss\sumap\gpispap+\sum_{s''}\gamma^2\sumsp\Ppi(\cond{s''}{s'})\Ppiss\df\Vpi(s'')\hs1\text{（総和を取る順序を交換）} \\
              &=\sumsp\gamma^0P_{\pi}^{~0}(\cond{s'}s)\suma\gpi(s', a)+\sumsp\gamma^1P_{\pi}^{~1}(\cond{s'}s)\suma\gpi(s', a)+\sum_{s''}\gamma^2P_{\pi}^{~2}(\cond{s''}s)\df\Vpi(s'')\hs1\text{（定義・走る文字変更）}

以上の変形の過程と結果の形から、「『$\df\Vpis』に対して $\eref{rec-1} を $n 回適用した式の最右辺は、以下に示す $\eref{rec-n} となる」という予想を立てることができます（最後の項の走る文字も変更しました）。これは数学的帰納法を用いれば簡単に証明できるので、ここでは正しいということにします。数式を書くの結構辛いので許してください。

\df\Vpis=\sum_{k=0}^{n-1}\sumsp\gamma^kP_{\pi}^{~k}(\cond{s'}s)\suma\gpi(s', a)+\sumsp\gamma^n\Ppinss\df\Vpisp \label{eq:rec-n}

この式の右辺の最初の2種類の総和（走る文字が $k と $s'）を交換してから $n\to\infty の極限を取ることで、補題 $\eref{lem}$ が証明されます。但し、以下に注意します。

$\gamma\in[0, 1]（定義）
$\Ppinss\in[0, 1]（確率なので）
$\df\Vpisp は有限値（$\Vpisp が微分可能であるという仮定）
十分大きな $n に対し、$\Ppinss は $s'\in\Scal ならば十分小さな値を取る
- これが満たされない（永遠に行動し続けられ得る）場合は、$T の定義の部分で述べたように、$\gamma\in[0, 1) となっている

証明本体

ここまで来れば簡単です。 $\eref{lem} を $\eref{J} に適用して、$\df\Jtheta を計算します。

\df\Jtheta &=\sum_{s_0}\iota(s_0)\df\Vpi(s_0)\hs1\text{（$\iota(s_0)$ は $\bm\theta$ に依存しない）} \\
                &=\sum_{s_0}\iota(s_0)\sums\sum_{n=0}^{\infty}\gamma^n\Ppin(\cond{s}{s_0})\suma\gpi(s, a)\hs1\text{（$\eref{lem}$）} \\
                &=\sums\left\{\sum_{s_0}\iota(s_0)\sum_{n=0}^{\infty}\gamma^n\Ppin(\cond{s}{s_0})\right\}\suma\gpi(s, a)\hs1\text{（総和を取る順序を交換）} \\
                &=\sums\Dpigamma(s)\suma\gpisa\hs1\text{（定義）}\hs1\QED

補足

$\df\pias=\pias\df\ln\pias を利用して、さらに変形を続ける場合もあります。

\df\Jtheta &=\sums\Dpigamma(s)\suma\Qpisa\df\pias \\
                 &=\sums\Dpigamma(s)\suma\Qpisa\pias\df\ln\pias \\
                 &=\sums\Dpigamma(s)\expct\bigl[\cond{\Qpisa\df\ln\pias}{a\followpis}\bigr]

さらに $\gamma=1 の場合には、$\Dpigamma(s) は確率分布となるので、上の変形の2行目から以下のように変形できます。

\df\Jtheta &=\sums\Dpigamma(s)\suma\Qpisa\pias\df\ln\pias \\
                 &=\expct\bigl[\cond{\Qpisa\df\ln\pias}{s\follow\Dpigamma(\cdot), a\followpis}\bigr]

まとめ

今回は方策勾配定理の証明をしました。次回扱う内容は未定です。

読むとGPAが上がるブログ(仮)

GPA芸人が気の赴くままに何かを書くブログ

数学を厭わない強化学習（その3：方策勾配定理）

方策勾配定理

準備

定理の主張

証明

補題

証明本体

補足

まとめ