【強化学習】Q-Learningの更新式から結果考察まで。ハイパーパラメータ依存性【Part1】

テクノロジー

2019.08.29 2019.08.26

みなさんこんにちは。

昔、こんな記事を書きました。

この記事では、Python+ChainerRLを用いて深層強化学習（DQN）を行いました。

記事中では、DQNの前段階として、普通の強化学習であるQ-Learnigのアルゴリズムも作ってみました。

今回は、そのQ-Learningについてまとめようと思います。

目次

Q-Learningとは
強化学習理論
1. マルコフ決定過程（MDP）によるモデル化
2. 強化学習における行動価値関数
Q-Learningの更新式
次回は、学習結果と考察

Q-Learningとは

強化学習についての説明は他に譲るとして、ここではQ-Learningについて説明します。

Q-Learningは、強化学習に使われるアルゴリズムの一つで、基本的なアルゴリズムといえます。強化学習に使われる基本的なアルゴリズムとしては、他にはSRASA、モンテカルロ法などがあります。

強化学習のアルゴリズムにおけるQ-Learningの立ち位置は、以下の図のような感じです。

Qiita：これから強化学習を勉強する人のための「強化学習アルゴリズム・マップ」と、実装例まとめ
https://qiita.com/sugulu/items/3c7d6cbe600d455e853b から引用

Q-Learningでは、「その状態 $s$ に、行動 $a$ をすることに、どれだけ価値があるか」を表した行動価値関数 $Q(s,a)$ を行動しながら更新していくことで、学習を行います。

強化学習理論

Q-Learningについて述べる前に、強化学習の理論について触れておきます。

マルコフ決定過程（MDP）によるモデル化

マルコフ決定過程によって、強化学習をモデル化していきます（マルコフ決定過程に関しては、Wikipediaなどを参照してください）。

以下では、時刻 $t$ における状態を $s_t$ 、行動を $a_t$ 、遷移確率を $P_{s,s'}^{a} = P(s'|s_t = s,a_t = a)$ とし、方策を $\pi(s,a) = P(a|s_t = s)$ とします。

ここで、方策 $\pi(s,a)$ とは、状態が $s$ のとき、どのように行動 $a$ をとるか、という意味を表します。

利得

利得 $R_(t )$ は、未来の報酬獲得にどの程度貢献したかを表し、割引率 $\gamma$ ( $\gamma$ は0から1の値をとり、よく大きな値（0.9~0.99）が使われる）を用いて、以下の式のように表します。

$R_(t )= r_{t+1}+\gamma r_{t+2}+\gamma^2 r_{t+3}+ \cdots =\sum_{k=0}^{\infty}{\gamma ^k r_{t+k+1}$

これは、現在に近いときに得られた利益ほど、利得に対する寄与が大きく、それ以降は割り引いて考えていることになります。

状態価値関数

「方策 $\pi$ をとったとき、その状態にどれだけ価値があるか？」を表す状態価値関数は、以下のようになります。

$V^{\pi}(s) = E\{R_t|s_t = s\} = \sum_{a} \pi(s,a) \sum_{s'} P_{s,s'}^{a}[ R_{s,s'}^{a}+\gamma V^{\pi}(s')]$

ここで、 $R_{s,s'}^{a} = E\{r_{t+1}|s_t = s, a_t= a, s_{t+1} = s'\}$ です。

この式の詳しい導出は、今さら聞けない強化学習（1）：状態価値関数とBellman方程式などをご覧ください。

行動価値関数

「方策 $\pi$ に従って、この状態でこの行動をとることにどれだけ価値があるか？」を表す行動価値関数は、以下のように表すことができます。

$Q^{\pi}(s, a) = \sum_{s'} P_{s,s'}^{a}[ R_{s,s'}^{a}+\gamma V^{\pi}(s')]$

一方で、状態価値関数は、

$V^{\pi}(s) = \sum_{a} \pi(s,a) Q^{\pi}(s, a)$

と表せるので、行動価値関数は、以下のように変形することができます。

$\therefore \quad Q^{\pi}(s, a) = \sum_{s'} P_{s,s'}^{a}[ R_{s,s'}^{a}+\gamma \sum_{a'} \pi(s',a') Q^{\pi}(s', a') ]$

これは、一種のBellman方程式となっています。

強化学習における行動価値関数

一般的には、強化学習で解きたい問題では、遷移確率 $P_{s,s'}^{a}$ が分りません。

それはそうですよね。次にどの状態に遷移するのか、わからない状況で学習するのが強化学習ですもんね。

ここで、方策について考えます。最も良い方策 $\pi^{\ast}(s)$ は、行動価値関数を最大にするような行動をすれば良いはずなので、

$\pi^{\ast}(s) =$ argmax $Q(s,a)$

と表せます。

また、このとき、状態価値関数は

$V^{\ast}(s) = \max_{a} Q(s,a)$

です。

これらより、最適（と思われる）行動価値関数は、以下のように変形することができます。

最適行動価値関数 $Q^{\ast}(s, a)$

$Q^{\ast}(s, a) = \sum_{s'} P_{s,s'}^{a}[ R_{s,s'}^{a}+\gamma V^{\ast}(s')] = r_{t+1} + \gamma\max_{a'}Q(s',a')$

ここで、 $r_{t+1} = r'$ と表記しています。

Q-Learningの更新式

Q-Learningでは、TD学習（時間差分学習）として、行動価値関数の更新式を考えます。

学習率を $\alpha$ とすると、TD学習の更新式は目標関数（ここでは、最適行動価値関数 $Q^{\ast}(s,a)$ ）と現在の関数の差を重みを付けて更新すればよいので、

$Q(s,a) \leftarrow Q(s,a)+\alpha[Q^{\ast}(s,a)-Q(s,a)]$

つまり、Q-Learningの更新式は、以下のようになります。

Q-Learningの更新式

$Q(s,a) \leftarrow Q(s,a)+\alpha[r'+\gamma \max _{}Q(s',a')-Q(s,a)]$

この関数は、状態 $s$ と行動 $a$ の関数となっているので、Q-Learningは二次元の表（テーブル）の値を更新して学習していくと考えることができます。この表を、Qテーブルといいます。

直感的に学習の様子を理解したい方は、 https://s3.amazonaws.com/ml-class/notes/MDPIntro.pdf をみると良いかと思います。

次回は、学習結果と考察

長くなりましたので、ハイパーパラメータをいじったときの学習結果の変化については、次の記事【Part2】で考察します。

コメント

タイトルとURLをコピーしました