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

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

数学を厭わない強化学習（その1：Bellman方程式など）

機械学習 強化学習 数学を厭わない強化学習 
\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}

前回の続きです。

今回はValue-basedな手法の基礎となるBellman方程式など、状態価値 $\Vpis と行動価値 $\Qpisa が絡む式4つをメインに扱います。 イメージを掴みやすくするため、見やすい形で表現することにしたので、式の右辺が若干怪しい表現になってますけど、そこは許してください。 （期待値が絡むところなので式が見にくくなってしまうのと、説明が長くなってしまうためです。 正確なバージョンは次回扱います。）

割引報酬和が満たす漸化式

まず、後に証明で用いる重要な漸化式を証明します。 証明は簡単ですが、その意義は重要です。

C_t=r_{t+1}+\gamma C_{t+1} \label{eq:C}

イメージ

割引報酬和は「終端状態に到達するまでに得られた報酬たちを、それぞれに時間による重みをつけて総和を取る」という演算でした。 なので、総和のうち、最初にもらえる報酬を総和の外に出した、というだけです。 文章だと逆に分かりづらいですが、証明を見れば明らかです。

証明

C_t &=\sum_{t'=t+1}^T\gamma^{t'-t-1}r_{t'}\hs1\text{（定義）} \\
       &=r_{t+1}+\sum_{t'=t+2}^T\gamma^{t'-t-1}r_{t'} \\
       &=r_{t+1}+\gamma\sum_{t'=(t+1)+1}^T\gamma^{t'-(t+1)-1}r_{t'} \\
       &=r_{t+1}+\gamma C_{t+1}\hs1\text{（定義）}\hs1\QED

簡単な関係式でしたが、この考え方は以下で説明する4つの式全てに通じるものなので、重要です。 というか、Bellman方程式に関しては、形がこれとほぼ同じです。 まあ状態価値とか行動価値はそもそも（条件は色々ついているものの）割引報酬和そのものですから、当たり前と言えば当たり前なのですが。

状態価値に対するBellman方程式

状態価値 $\Vpis に対するBellman方程式は、以下の通りです。

\Vpis=\Rpis+\gamma\Vpisp\hs1\text{（$s'\onefollowPpis$）} \label{eq:V}

証明

\Vpis &=\expctpi[\cond{C_t}{s_t=s}]\hs1\text{（定義）} \\
         &=\expctpi\bigl[\cond{r_{t+1}+\gamma C_{t+1}}{r_{t+1}, s_{t+1}\twofollowPpis}\bigr]\hs1\text{（\eref{C}・$\pi$ に従う条件を明示）} \\
         &=\expctpi\bigl[\cond{r_{t+1}}{r_{t+1}\onefollowPpis}\bigr]+\gamma\expctpi\bigl[\cond{C_{t+1}}{s_{t+1}\onefollowPpis}\bigr]\hs1\text{（和の期待値は期待値の和）} \\
         &=\Rpis+\gamma\Vpisp\hs1\text{（$s'\onefollowPpis$）}\hs1\text{（定義）}\hs1\QED

状態価値と行動価値の関係式その1

状態価値と行動価値にも強い関係があります。 繰り返しになりますが、両方とも実質同じものを指してるので当たり前なのですが。

\Vpis=\Qpisa\hs1\text{（$a\followpis$）} \label{eq:VQ}

証明

\Vpis &=\expctpi[\cond{C_t}{s_t=s}]\hs1\text{（定義）} \\
         &=\expctpi\bigl[\cond{C_t}{s_t=s, a_t\followpis}\bigr]\hs1\text{（$\pi$ に従う条件を明示）} \\
         &=\Qpisa\hs1\text{（$a\followpis$）}\hs1\text{（定義）}\hs1\QED

状態価値と行動価値の関係式その2

先程とは逆に、$\Qpisa を変形していきます。

\Qpisa=\Rsa+\gamma\Vpisp\hs1\text{（$s'\onefollowPsa$）} \label{eq:QV}

証明

\Qpisa &=\expctpi[\cond{C_t}{s_t=s, a_t=a}]\hs1\text{（定義）} \\
            &=\expctpi\bigl[\cond{r_{t+1}+\gamma C_{t+1}}{r_{t+1}, s_{t+1}\twofollowPsa}\bigr]\hs1\text{（\eref{C}・$\pi$ に従う条件を明示）} \\
            &=\expctpi\bigl[\cond{r_{t+1}}{r_{t+1}\onefollowPsa}\bigr]+\gamma\expctpi\bigl[\cond{C_{t+1}}{s_{t+1}\onefollowPsa}\bigr]\hs1\text{（和の期待値は期待値の和）} \\
            &=\Rsa+\gamma\Vpisp\hs1\text{（$s'\onefollowPsa$）}\hs1\text{（定義）}\hs1\QED

行動価値に対するBellman方程式

状態価値 $\Qpisa に対するBellman方程式は、以下の通りです。

\Qpisa=\Rsa+\gamma\Qpispap\hs1\text{（$s'\onefollowPsa$、$a'\followpisp$）} \label{eq:Q}

証明

\Qpisa &=\Rsa+\gamma\Vpisp\hs1\text{（$s'\onefollowPsa$）}\hs1\text{（\eref{QV}）} \\
            &=\Rsa+\gamma\Qpispap\hs1\text{（$s'\onefollowPsa$、$a'\followpisp$）}\hs1\text{（\eref{VQ}）}\hs1\QED

まとめ

5本ほど式と証明を紹介しました。 下にまとめて再掲します。

C_t &=r_{t+1}+\gamma C_{t+1} \\
\Vpis &=\Rpis+\gamma\Vpisp & \text{（$s'\onefollowPpis$）} \\
\Vpis &=\Qpisa & \text{（$a\followpis$）} \\
\Qpisa &=\Rsa+\gamma\Vpisp & \text{（$s'\onefollowPsa$）} \\
\Qpisa &=\Rsa+\gamma\Qpispap & \text{（$s'\onefollowPsa$、$a'\followpisp$）}

まあ証明は割とどうでもよくて、イメージを掴むことが大事だと思います。 具体的には、

  • 割引報酬和の漸化式（$\eref{C} ）
  • 状態価値は（方策に従った時の）割引報酬和
  • 行動価値は（最初の行動以外は方策に従った時の）割引報酬和

この3つを抑えて適切に使えば、$\eref{C} 以外の4つの式は全て妥当なものに見えてくると思います。

それでは、今回はここまでです。 次回はサンプリングが入らないちゃんとした形のBellman方程式などを扱います。