強化学習の基礎　マルコフ決定過程とQ-Learningについて

この記事では、強化学習を理解するための基本的な知識であるマルコフ決定過程によるモデル化とQ-Learningアルゴリズムについての解説を行います。

マルコフ決定過程(Markov Decision Process, MDP)

確率論におけるマルコフ性とは、「現在の状態が直前の状態にのみ依存して定まる性質」のことでした。今回考えるマルコフ決定過程もこのマルコフ性を持っています。

マルコフ決定過程の構成要素は、状態空間$S$、行動空間$A(s)$、状態遷移確率$P(s’|s,a)$、そして報酬関数$r(s,a,s’)$です。

現在の状態$s\in S$に依存して次に選択できる行動$a\in A(s)$が決まり、現在の状態と選択した行動によって状態遷移確率$P(s’|s,a)$が定まります。
選択した行動に対する報酬$r(s, a, s’)$は、現在の状態$s$、選択した行動$a$、行動の遷移先にあたる状態$s’$に依存して定まります。

強化学習とは、状態$s$の時に行動$a$が選択される確率$\pi(a|s)$を最終的に得られる報酬が最大となるように推定するアルゴリズムの総称です。

この$\pi$のことをpolicy(方策 / 政策)と呼びます。

Policy（方策）の良し悪しを定義する

それでは、報酬を最大化するようなpolicyを数学的に定義していきましょう。
まず、収益と価値という概念を導入します。

収益とは、「ある期間内で得られた累積の報酬」と定義し、$G_t$と表記します。収益の例は以下のものが考えられます。($R_t$はステップ$t$における報酬を表します)

1. $$G_t=\sum_{\tau=0}^{T-1}R_{t+1+\tau}$$
2. (収益が発散しないように平均を取ったもの)
   $$G_t=\lim_{T\to\infty}\frac{1}{T}\sum_{\tau=0}^{T-1}R_{t+1+\tau}$$
3. (割引報酬和, $\gamma$は割引率を表し、1に近いほど長期的な判断を意味する)
   $$G_t=\sum_{\tau=0}^\infty\gamma^\tau R_{t+1+\tau}$$

次に価値を、「状態を条件としたときの収益の期待値」と定義します。
具体的には、$V^\pi(s)=E^\pi[G_{t+1}|S_t=s]$のように表記します。

これらを使って最適なpolicyを定義しましょう。
以下の両方が成り立つとき、policy$\pi_1$はpolicy$\pi_2$よりも良いと呼びます。

• $\forall s\in S,\space V^{\pi_1}(s)\geq V^{\pi_2}(s)$
• $\exists s_0,\space s.t. \space V^{\pi_1}(s_0)>V^{\pi_2}(s_0)$

状態$s$によって価値の大小関係が変化する場合は比較不能だとします。

最適なpolicy$\pi^*$を、全てのpolicyの中で上記関係における最大のもの、すなわち
$$\pi^*=\text{argmax}_{\pi}V^\pi(s)\quad(\forall s\in S)$$
と定めます。

今後の議論を簡潔にするため、行動価値関数$Q$を次のように定義します。
$$Q^\pi(s,a)=E^\pi[G_{t+1}|S_t=s,A_t=a]$$

この$Q$が既知の場合には具体的なpolicyを用いて考えることができますが、通常$Q$は未知です。この場合には、

1. $Q$を推定したのちにpolicyを推定する（価値反復法）
2. 直接policy$\pi$を推定する（方策勾配法）

といった方針が考えられます。
今回は価値反復法の中でもQ-learningと呼ばれるアルゴリズムについて解説します。

Q-learning

一般的な価値反復法の具体的な手順は以下のようになります。

Q-learningでは各ステップにおいて最適な行動を選択するように学習を進めるため、以下の更新式を満たすように行動価値関数を推定することで最適なpolicyを推定することができます。
行動価値関数の更新は以下のように行います。

$$Q(S_t,A_t)\leftarrow (1-\alpha)Q(S_t, A_t)+\alpha(R_{t+1}+\gamma\max_{a’}Q(S_{t+1},a’))$$

$\alpha$は学習率と呼ばれるハイパーパラメーターで、アルゴリズム実行前に指定する必要があります。上記更新式の右辺を変形すると、
$$Q(S_t,A_t)+\alpha(R_{t+1}+\gamma\max_{a’}Q(S_{t+1},a’)-Q(S_t,A_t))$$
のようになります。

学習が収束していれば行動価値関数は変化しないはずだということから、学習が収束していれば第二項$\alpha(R_{t+1}+\gamma\max_{a’}Q(S_{t+1},a’)-Q(S_t,A_t))$は0になります。

また、更新式がpolicyに依存しないため、どんなpolicyを選択したとしても同じ行動価値関数に収束します。

参考書籍
これからの強化学習