強化学習とは
強化学習(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)の具体的な手順は，
- 時間ステップt=0と初期化し，s_t\sim p_{s_0}を観測
- 行動a_t\sim \pi(\cdot|s_t)を選択
- 報酬r_t=g(s_t,a_t)，s_{t+1}\sim p_T(\cdot|s_t,a_t)を観測
-
t\leftarrow t+1とし，手順1.に遷移
となる．
逐次的意思決定の典型的問題設定
方策の最適化問題である逐次的意思決定問題は，一般に以下のような目的関数（期待割引累積報酬）を考える．
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)
の探索問題と解釈できる．具体的には，t=0からの割引累積報酬C_0の期待値を目的関数に用いることが多い．
f_0(\pi)\triangleq \mathbb{E}[C_0],\quad \forall \pi\in\Pi
この目的関数は価値関数V^\pi:\mathcal{S}\to\Rと呼ばれる状態の条件付き割引累積報酬
V^\pi(s)\triangleq \mathbb{E}^\pi[C_0\mid S_0=s]
の初期状態分布p_{s_0}による重み付き和
f_w(\pi)=\sum_{s\in \mathcal{S}}p_{s_0}(s)V^\pi
と解釈できる．ここで，重み関数w:\mathcal{S}\to \R_{\geq 0}による価値関数の重み付き和を
f_w(\pi;w)\triangleq \sum_{s\in\mathcal{S}}w(s)V^\pi(s)
と定義すれば
f_0(\pi; p_{s_0})=f_w(\pi;p_{s_0}),\quad \forall \pi\in\Pi
と書ける．
参考文献
Discussion