数学を厭わない強化学習(その0:用語・文字定義)
\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{\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)}
新シリーズです。
数学から逃げるな
ということで、強化学習の数学的なところを適当にかいつまんで、できる限り明瞭に説明・証明していくシリーズになる予定です。
シリーズ最初の今回は、このシリーズで使っていく文字の定義とかを紹介していきます。 ものによってはここで定義とか定理とかイメージとかまで説明してしまいます。
なお、内容は随時追加・修正される可能性があります。
また、スマートフォンから見ると表示が崩れる現象が確認されているので、PCで見るか、スマホで見る場合はPCモードにして見るか気合で見るかしてください。
文字などの紹介・定義
数学的な操作・強化学習の基本的な文字
- $
\mathrm{Pr}\{X=x\}
:確率変数 $X
が値 $x
を取る確率。 - $
\expct[X]
:確率変数 $X
の期待値。- $
\expct[X]:=\sum_{x\in\mathcal{X}}\mathrm{Pr}\{X=x\}x
。- $
\mathcal{X}
は $x
が取り得る値全体の有限集合。
- $
- $
\expctpi[X]
:方策 $\pi
に従って行動した場合の、確率変数 $X
の期待値(詳しくは後述)。
- $
- $
\bm\nabla_{\bm\theta}
:ベクトル $\bm\theta
による偏微分の、偏微分作用素ベクトル - $
\gamma
:時間割引率。- 通常、定数のパラメータ。
- $
\gamma\in[0, 1]
。
- $
\Scal
:非終端状態集合(取り得る非終端状態全体の有限集合)。 - $
\Scalp
:状態集合(取り得る状態全体の有限集合)。 - $
\Acal
:行動集合(取り得る行動全体の有限集合)。- 行動集合が状態に依存する場合は、$
\Acal(s)
で状態 $s
における行動集合を表す。 - $
s
が終端状態である場合、$\Acal(s):=\emptyset
とする。
- 行動集合が状態に依存する場合は、$
- $
\Rcal
:報酬集合(取り得る報酬全体の有限集合)。- $
\Rcal\subset\Rset
。
- $
- $
s
:状態。- $
s\in\Scalp
。
- $
- $
a
:行動。- $
a\in\Acal
。
- $
- $
r
:報酬。- $
r\in\Rcal
。
- $
強化学習でよく出てくる演算のエイリアス
- $
\sums f(s):=\sum_{s\in\Scal}f(s)
。- $
\suma f(a)
や $\sumr f(r)
についても同様。
- $
- $
\sum_{s, a} f(s, a):=\sum_{s\in\Scal}\sum_{a\in\Acal(s)}f(s, a)
。- $
\sum_{a, r}f(a, r)
や $\sum_{s, r}f(s, r)
についても同様。
- $
- 同様に、走る範囲が書いていない総和計算については、$
\Scal
や $\Acal(s)
、$\Rcal
のうち適当なものを走る範囲として選択する。
実際に行動する際に出てくる文字
- $
t
:時刻。- $
t\in\Nset\cup\{\infty\}
。
- $
- $
T
:終端状態に到達した時刻。- $
T\in\Nset\cup\{\infty\}
。- $
T=\infty
の場合は、終端状態がない(永遠に行動し続けられる)ことを表す。 - $
T=\infty
となり得る場合は、時間割引率 $\gamma\in[0, 1)
とする。
- $
- $
- $
s_t
:時刻 $t
における状態。- $
s_t\in\Scalp
。
- $
- $
a_t
:時刻 $t
において取った行動。- $
a_t\in\Acal
。
- $
- $
r_t
:時刻 $t-1
において取った行動により得られた報酬。- $
r_t\in\Rcal
。
- $
- $
C_t
:時刻 $t
から終端状態に到達するまでに得られた報酬たちの割引報酬和。- $
C_t:=\sum_{t'=t+1}^T\gamma^{t'-t-1}r_{t'}
。 - ただし、時刻 $
t
における状態が終端状態であった場合には、$C_t:=0
とする。
- $
確率・確率分布
- $
\pi
:方策(取る行動を決定する規則)。- $
\pithetaas
:状態 $s
において行動 $a
を取る確率。計算に用いるパラメータとして $\bm\theta
を持つ。- $
s\in\Scal
、$a\in\Acal(s)
。
- $
- $
\pias
:$\pithetaas
の省略形。文字が多いと見にくくなるので、普通は $\bm\theta
は省略する。
- $
- $
\Psrsa
:状態 $s
において行動 $a
を取った場合に、次の状態が $s'
であり、かつ得られる報酬が $r
である確率。- $
\Psrsa:=\mathrm{Pr}\{\cond{s_{t+1}=s', r_{t+1}=r}{s_t=s, a_t=a}\}
。 - $
s\in\Scal
、$s'\in\Scalp
、$a\in\Acal
、$r\in\Rcal
。
- $
- $
\Pssa
:状態 $s
において行動 $a
を取った場合に、次の状態が $s'
である確率。- $
\Pssa:=\mathrm{Pr}\{\cond{s_{t+1}=s'}{s_t=s, a_t=a}\}
。 - $
s\in\Scal
、$s'\in\Scalp
、$a\in\Acal
。 - 任意の $
s\in\Scal
、任意の $s'\in\Scalp
、任意の $a\in\Acal
に対し、$\sumr\Psrsa=\Pssa
。 - $
\Prsa
も同様に定義する。もちろん成り立つ性質も同様に成り立つ。
- $
- $
\Ppisrs
:状態 $s
において方策 $\pi
に従って行動した場合に、次の状態が $s'
であり、かつ得られる報酬が $r
である確率。- $
\Ppisrs:=\suma\pias\Psrsa
。 - $
s\in\Scal
、$s'\in\Scalp
、$r\in\Rcal
。
- $
- $
\Ppiss
:状態 $s
において方策 $\pi
に従って行動した場合に、次の状態が $s'
である確率。- $
\Ppiss:=\suma\pias\Pssa
。 - $
s\in\Scal
、$s'\in\Scalp
。 - 任意の $
s\in\Scal
、任意の$s'\in\Scalp
に対し、$\sumr\Ppisrs=\Ppiss
。 - $
\Ppirs
も同様に定義する。もちろん成り立つ性質も同様に成り立つ。
- $
- $
\Ppinss
:状態 $s
において、方策 $\pi
に従って $n
回行動した後の状態が $s'
である確率。- $
\Ppinss:=\sum_{s_1, s_2, \ldots, s_{n-1}}\prod_{t=0}^{n-1}\Ppicond{s_{t+1}}{s_t}
。- 但し、$
s_0:=s
、$s_n:=s'
とする。
- 但し、$
- $
s\in\Scal
、$s'\in\Scalp
、$n\in\Nset
。 - $
s=s'
ならば $P_{\pi}^{~0}(\cond{s'}s):=1
、$s\neq s'
ならば $P_{\pi}^{~0}(\cond{s'}s):=0
とする。
- $
- $
\iota(s)
:状態 $s
が開始状態となる確率。- $
s\in\Scal
。
- $
- $
\Dpigamma(s)
:方策 $\pi
に従って開始状態から終端状態になるまで行動する場合の、状態 $s
の考慮度合い。- 「方策 $
\pi
に従って開始状態から終端状態になるまで行動する場合に、途中で状態が $s
となっている確率」に対し、時間割引率 $\gamma
を用いた時間の重みをつけたもの。 - $
\Dpigamma(s):=\sum_{s_0} \iota(s_0)\sum_{n=0}^{\infty}\gamma^n\Ppincond{s}{s_0}
。 - $
s\in\Scalp
。 - 確率分布に近い存在であり、同じような意味合いで用いられるが、厳密には確率分布ではない($
\gamma=1
なら確率分布)。
- 「方策 $
確率分布からのサンプリング
- 確率を表す文字の中に「$
\cdot
」が含まれている場合、そこに入っていた文字をサンプリングすることを表す。確率は、「$\cdot
」が含まれていない場合の確率とする。以下に例を示す。- $
a\followpis
:「任意の $a\in\Acal(s)
に対して、$a
に対応する($a
が選ばれる)確率が $\pias
であるような確率分布」から $a
をサンプリングすることを表す。 - $
s', r\twofollowPsa
:「任意の $s'\in\Scalp
、任意の $r\in\Rcal
に対して、$s', r
が(同時に)選ばれる確率が $\Psrsa
であるような確率分布」から $s', r
をサンプリングすることを表す。 - $
r\onefollowPpis
:「任意の $r\in\Rcal
に対して、$r
が選ばれる確率が $\Ppirs
であるような確率分布」から $r
をサンプリングすることを表す。
- $
期待値
- $
\Rsa
:状態 $s
において行動 $a
を取った際に得られる報酬の期待値。- $
\Rsa:=\expct[\cond{r_{t+1}}{s_t=s, a_t=a}]
。 - $
s\in\Scal
、$a\in\Acal(s)
。
- $
- $
\Rpis
:状態 $s
において、方策 $\pi
に従って行動した際に得られる報酬の期待値。- $
\Rpis:=\expctpi[\cond{r_{t+1}}{s_t=s}]
。 - $
s\in\Scal
。
- $
- $
\Vpis
:状態価値(状態 $s
の価値)。- $
s\in\Scalp
。 - 状態 $
s
から方策 $\pi
に従って終端状態になるまで行動を続けた場合に得られる割引報酬和の期待値と定義する。- $
\Vpis:=\expctpi[\cond{C_t}{s_t=s}]
。 - $
s
が終端状態である場合には、$\Vpis:=0
とする。
- $
- $
- $
\Qpisa
:行動価値(状態 $s
において行動 $a
を取ることの価値)。- $
s\in\Scalp
、$a\in\Acal(s)
。 - 状態 $
s
において行動 $a
を取り、その後は方策 $\pi
に従って終端状態になるまで行動を続けた場合に得られる割引報酬和の期待値と定義する。- $
\Qpisa:=\expctpi[\cond{C_t}{s_t=s, a_t=a}]
。 - $
s
が終端状態である場合には、$\Qpisa:=0
とする。
- $
- $
添字などの注意点
- 状態 $
s
などで、添字等がついてないものは現在の状態を、プライムがついた $s'
などは未来の状態を、上付き線がついた $\prds
などは過去の状態を表すことが多い。- ただし、総和を取る際の走る文字に用いられている場合はこの限りではない。単に文字の重複を避けるためにプライムを付けるなどしている。
- 方策 $
\pias
等に出てくる縦線は、条件付き確率を表す(この場合は、$s
が「条件」である)。 - このシリーズでは、$
\Nset
は非負整数全体の集合とする。 - 状態 $
s_t
において行動 $a_t
を取ることで、状態は $s_{t+1}
になり、同時に報酬 $r_{t+1}
を受け取った、というような時刻の付け方である。報酬の添字が間違えやすいので注意。 - なにかしらの文字にサーカムフレックスがついている場合(例:$
\Vpihats
)、それは(ニューラルネットワーク等による)近似値であることを表す。
$\expctpi
について
前述したように、$\expctpi
は「方策 $\pi
に従って行動した際の期待値」を表す。
これをより明確に定義する。
基本的に、$\expctpi
は $\expctpi[\cond{A}{B}]
の形で現れる。
このとき、$A
には、計算するために行動を要するものが入る(例:割引報酬和 $C_t
や報酬 $r_t
など)。
なお、割引報酬和が例に挙げられていることから分かるように、この行動は1回とは限らない。
計算できるようになるまで(例えば割引報酬和なら、状態が終端状態に到達するまで)行動することを考える。
この全ての行動を方策 $\pi
に従って行う、ということである。
注意点
- $
B
の部分に行動を指定する条件が入っていた場合は、当然それが優先される。 - 上で説明したことを視点を変えて表現すると、「条件である $
B
の部分に『方策 $\pi
に従って行動する』という条件が(暗に)課されている」となる。従って、この条件(方策 $\pi
に従う)の一部を明示しても支障はない。式変形の都合上、これを行うことがある。
まとめ
今回は文字定義とかなので特に面白いところもないですね。 次回から中身のある話になると思います。