強化学習とは#

強化学習(Reinforcement Learning; RL)，最適な意思決定のルールを求めることを目的とする分野であり，一般に「教師あり学習」や「教師なし学習」と並ぶ機械学習の一分野に分類される．

マルコフ決定過程#

マルコフ決定決定過程(Markov decision process; MDP)は，マルコフ連鎖に行動および報酬を組み入れた確率制御過程であり，５つの組

M\triangleq \{\mathcal{S},\mathcal{A},p_{s_0},p_T,g\}

で定義される．ここで，有限状態集合 $\mathcal{S}$ ．有限行動集合 $\mathcal{A}$ ，初期状態確率関数 $p_{s_0}$ ，状態遷移確率関数 $p_T$ ，報酬関数 $g$ は，

\begin{align*} \mathcal{S}\triangleq \{1,\cdots,|\mathcal{S}|\}&\\ \mathcal{A}\triangleq \{a^1,\cdots,a^{|\mathcal{A}|}\}&\\ p_{s_0}:\mathcal{S}\to [0,1]:p_{s_0}(s)\triangleq P(S_0=s)&\\ p_T:\mathcal{S}\times\mathcal{S}\times\mathcal{A}\to[0,1]:&\\ p_T(s'|s,a)\triangleq P(S_{t+1}=s'|S_t=s,A_t=a),\forall t\in \N_0&\\ g:\mathcal{S}\times \mathcal{A}\to \R& \end{align*}

報酬関数 $g$ は有限関数であり，

|g(s,a)|\leq R_\text{max},\forall (s,a)\in \mathcal{S}\times \mathcal{A}, R_\text{max}\in\R

であり，報酬の集合 $\mathcal{R}$ は，

\mathcal{R}\triangleq \{r\in\R:r=g(s,a),\exists(s,a)\in\mathcal{S}\times\mathcal{A}\}

である．定義上， $|\mathcal{R}|\leq |\mathcal{S}||\mathcal{A}|$ を満たす．

次に，方策と呼ばれる行動の選択ルールを規定する関数であるが，ここでは現時間ステップの状態 $s$ のみに依存して確率的に行動を選択する確率的方策 $\pi:\mathcal{A}\times\mathcal{S}\to[0,1]$

\pi(a|s)\triangleq P(A=a|S=s)

を用いることとする．方策 $\pi$ を含めたマルコフ決定過程 $M$ を

M(\pi)\triangleq \{\mathcal{S},\mathcal{A},p_{s_0},p_T,g,\pi\}

とし，任意の確率的方策 $\pi$ を含む方策集合を

\Pi\triangleq \left\{ \pi:\mathcal{A}\times\mathcal{S}\to[0,1]: \sum_{a\in\mathcal{A}}\pi(a|s)=1,\forall s\in\mathcal{S} \right\}

と定義する．

マルコフ決定過程の時間発展 $(s_0,a_0,r_0,\cdots,s_t,a_t,r_t)$ の具体的な手順は，

となる．

方策の最適化問題である逐次的意思決定問題は，一般に以下のような目的関数（期待割引累積報酬）を考える．

f(\pi)=\mathbb{E} \left[ \lim_{T\to\infty}\sum_{t=0}^T \gamma^t R_t |M(\pi) \right]

ここで， $\gamma\in[0,1)$ は割引率と呼ばれ，長期的な報酬和をどの程度考慮するかを調整するパラメータである．

定常なマルコフ方策は，

\pi^s\triangleq \{\pi,\pi,\cdots\}\in \Pi^S,\quad \pi\in\Pi

であり，特に，決定的方策 $\pi^d\in\Pi^d\sube\Pi$ の場合を，

\pi^{sd}\triangleq \{\pi,\pi,\cdots\}\in \Pi^{SD},\quad \pi\in\Pi

と定義する．一方で，一般のマルコフ方策は，

\pi^m\triangleq \{\pi_0\in\Pi,\pi_1\in\Pi,\cdots\}\in\Pi^M

とする．現在の状態だけではなくそれ以前の経験にも異存する非マルコフ方策は，

\pi^h\triangleq \{\pi_0^h,\pi_1^h,\cdots\}\in\Pi^H\triangleq (\Pi_t^h)_{t\in\N_0}

と定義する．なお，現在の時間ステップ $t$ までの全ての経験の履歴 $\{s_0,a_0,r_0,\cdots,s_{t-1},a_{t-1},r_{t-1},s_t\}\triangleq h_t\in \mathcal{H}_t$ に基づく，履歴依存の方策

\pi_t^h(a|h_t)\triangleq P(A=a|H_t=h_t)

の集合を

\Pi_t^h\triangleq \left\{ \pi_t^h:\mathcal{A}\times\mathcal{H}_t\to[0,1]:\sum_{a\in\mathcal{A}}\pi_t^h(a|h_t)=1 \right\}

としている．各方策系列の集合には，

\Pi^{SD}\sube \Pi^S\sube \Pi^M\sube \Pi^H

の包含関係があり，方策系列を引数とする任意の目的関数 $f$ に対して，

\max_{\pi\in\Pi^{SD}}f(\pi)\le \max_{\pi\in\Pi^{S}}f(\pi)\le \max_{\pi\in\Pi^{M}}f(\pi)\le \max_{\pi\in\Pi^{H}}f(\pi)

の関係にある．

割引累積報酬 $C\in\R$ は，

C_t\triangleq \sum_{k=0}^\infty\gamma^kR_{t+k}

と定義され， $\gamma\in[0,1)$ は割引率と呼ばれるハイパーパランメータである．定義式より，

C_t=R_t+ \sum_{k=1}^\infty\gamma^kR_{t+k} =R_t+\gamma C_{t+1}

のように再帰的な構造をもつ．また，報酬関数は定義より有限 $|R|\le R_\text{max}$ であるので，

|C_t|\le \sum_{k=1}^\infty\gamma^kR_\text{max} =\frac{R_\text{max}}{1-\gamma},\quad \forall t\in\N_0

より有限となる．

逐次的意思決定問題は一般に割引累積報酬に関する何かしらの統計量 $\mathcal{F}[C|M(\pi)]$ を目的関数 $f:\Pi\to\R$

f(\pi)\triangleq \mathcal{F}[C|M(\pi)]

や制約条件に用いて，方策についての最適化問題として定式化する．制約なしの逐次的意思決定問題は最適方策

\pi^\star\triangleq \argmax_{\pi\in\Pi}f(\pi)

の探索問題と解釈できる．