みなさんこんにちは。
昔、こんな記事を書きました。
この記事では、Python+ChainerRLを用いて深層強化学習(DQN)を行いました。
記事中では、DQNの前段階として、普通の強化学習であるQ-Learnigのアルゴリズムも作ってみました。
今回は、そのQ-Learningについてまとめようと思います。
Q-Learningとは
強化学習についての説明は他に譲るとして、ここではQ-Learningについて説明します。
Q-Learningは、強化学習に使われるアルゴリズムの一つで、基本的なアルゴリズムといえます。強化学習に使われる基本的なアルゴリズムとしては、他にはSRASA、モンテカルロ法などがあります。
強化学習のアルゴリズムにおけるQ-Learningの立ち位置は、以下の図のような感じです。

Qiita:これから強化学習を勉強する人のための「強化学習アルゴリズム・マップ」と、実装例まとめ
https://qiita.com/sugulu/items/3c7d6cbe600d455e853b から引用
Q-Learningでは、「その状態 に、行動
をすることに、どれだけ価値があるか」を表した行動価値関数
を行動しながら更新していくことで、学習を行います。
強化学習理論
Q-Learningについて述べる前に、強化学習の理論について触れておきます。
マルコフ決定過程(MDP)によるモデル化
マルコフ決定過程によって、強化学習をモデル化していきます(マルコフ決定過程に関しては、Wikipediaなどを参照してください)。
以下では、時刻 における状態を
、行動を
、遷移確率を
とし、方策を
とします。
ここで、方策 とは、状態が
のとき、どのように行動
をとるか、という意味を表します。
利得
利得 は、未来の報酬獲得にどの程度貢献したかを表し、割引率
(
は0から1の値をとり、よく大きな値(0.9~0.99)が使われる)を用いて、以下の式のように表します。
これは、現在に近いときに得られた利益ほど、利得に対する寄与が大きく、それ以降は割り引いて考えていることになります。
状態価値関数
「方策 をとったとき、その状態にどれだけ価値があるか?」を表す状態価値関数は、以下のようになります。
ここで、 です。
この式の詳しい導出は、今さら聞けない強化学習(1):状態価値関数とBellman方程式などをご覧ください。
行動価値関数
「方策 に従って、この状態でこの行動をとることにどれだけ価値があるか?」を表す行動価値関数は、以下のように表すことができます。
一方で、状態価値関数は、
と表せるので、行動価値関数は、以下のように変形することができます。
これは、一種のBellman方程式となっています。
強化学習における行動価値関数
一般的には、強化学習で解きたい問題では、遷移確率 が分りません。
それはそうですよね。次にどの状態に遷移するのか、わからない状況で学習するのが強化学習ですもんね。
ここで、方策について考えます。最も良い方策 は、行動価値関数を最大にするような行動をすれば良いはずなので、
argmax
と表せます。
また、このとき、状態価値関数は
です。
これらより、最適(と思われる)行動価値関数は、以下のように変形することができます。
最適行動価値関数
ここで、 と表記しています。
Q-Learningの更新式
Q-Learningでは、TD学習(時間差分学習)として、行動価値関数の更新式を考えます。
学習率を とすると、TD学習の更新式は目標関数(ここでは、最適行動価値関数
)と現在の関数の差を重みを付けて更新すればよいので、
つまり、Q-Learningの更新式は、以下のようになります。
Q-Learningの更新式
この関数は、 状態 と行動
の関数となっているので、Q-Learningは二次元の表(テーブル)の値を更新して学習していくと考えることができます。この表を、Qテーブルといいます。
直感的に学習の様子を理解したい方は、 https://s3.amazonaws.com/ml-class/notes/MDPIntro.pdfをみると良いかと思います。
次回は、学習結果と考察
長くなりましたので、ハイパーパラメータをいじったときの学習結果の変化については、次の記事【Part2】で考察します。
コメント