Q学習

機械学習および データマイニング
問題 分類 クラスタリング 回帰 異常検知 相関ルール（英語版） 強化学習 構造化予測（英語版） 特徴量設計（英語版） 表現学習（英語版） オンライン学習（英語版） 半教師あり学習（英語版） 教師なし学習 ランキング学習（英語版） 文法獲得（英語版）
教師あり学習（分類 • 回帰） 決定木（英語版） アンサンブル （バギング、ブースティング、 ランダムフォレスト） k-NN 線形回帰 単純ベイズ ニューラルネットワーク ロジスティック回帰 パーセプトロン 関連ベクトルマシン (RVM)（英語版） サポートベクトルマシン (SVM)
クラスタリング BIRCH（英語版） 階層的（英語版） k平均法 期待値最大化法 (EM) DBSCAN OPTICS（英語版） 平均値シフト（英語版）
次元削減 因子分析 CCA ICA LDA（英語版） NMF（英語版） PCA t-SNE
構造化予測（英語版） グラフィカルモデル ベイジアンネットワーク CRF HMM
異常検知 k-NN 局所外れ値因子法
ニューラルネットワーク オートエンコーダ ディープラーニング DeepDream 多層パーセプトロン RNN LSTM GRU 制約ボルツマンマシン（英語版） SOM CNN U-Net
強化学習 TD学習 Q学習 SARSA
理論 偏りと分散のトレードオフ 計算論的学習理論（英語版） 経験損失最小化（英語版） オッカム学習（英語版） PAC学習 統計的学習（英語版） VC理論（英語版）
学会・論文誌等 NIPS（英語版） ICML（英語版） ML（英語版） JMLR（英語版） ArXiv:cs.LG
全般 統計学および機械学習の評価指標
Category:機械学習 Category:データマイニング
表 話 編 歴

Q学習（Qがくしゅう、英: Q-learning）は、機械学習分野における強化学習の一種である。

概要[編集]

Q学習は強化学習の方策オフ型時間差分法の一つである。概念自体は古くから存在するが、Q学習（Q-learning）という名前で今日の手法がまとめられたのは、1989年のクリストファー・ワトキンズ（Christopher J.C.H. Watkins）の博士論文に端を発する。^[1]

TD学習は ${\displaystyle R_{t+1}+\gamma V(S_{t+1})}$ になるように学習させるが、Q学習はこれを ${\displaystyle R_{t+1}+\gamma \max _{a}Q(S_{t+1},a)}$ に置き換えたものである。状態価値関数 ${\displaystyle V(s)}$ の代わりに、行動価値関数 ${\displaystyle Q(s,a)}$ を使用する。

Q学習は有限マルコフ決定過程において全ての状態が十分にサンプリングできるようなエピソードを無限回試行した場合、最適な評価値に収束することが理論的に証明されている。実際の問題に対してこの条件を満たすことは困難ではあるが、この証明はQ学習の有効性を示す要素の一つとして挙げられる。

Q学習の内容[編集]

Q値[編集]

Q学習では実行するルールに対しそのルールの有効性を示す行動価値のQ値（Q-value）という値を持たせ、エージェントが行動するたびにその値を更新する。ここでいうルールとはある状態とその状態下においてエージェントが可能な行動を対にしたものである。例えばエージェントの現在の状態を${\displaystyle S_{t}}$とし、この状態で可能な行動が${\displaystyle A}$, ${\displaystyle B}$, ${\displaystyle C}$, ${\displaystyle D}$の4通りあるとする。このとき、エージェントは4つのQ値、 ${\displaystyle Q(S_{t},A)}$、${\displaystyle Q(S_{t},B)}$、${\displaystyle Q(S_{t},C)}$、${\displaystyle Q(S_{t},D)}$ を元に行う行動を決定する。

行動価値関数Qは、ある状態である行動を行った際、現在および将来に得られる報酬になるように学習させる。ただし、将来分の報酬は、経済学でも使われる割引率をかけた物を使用する。経済学と同じく、割引率をかけることで将来分の報酬が発散することを防ぎ、直近に得られる報酬に重きを置いている。

行動選択[編集]

行動の決定方法は理論上では無限回数試行するならランダムでも行動価値関数Qの収束は証明されているが、現実には収束を早めるため、なるべくQ値の大きな行動が高確率で選ばれるように行う。選択方法としては、ある小さな確率${\displaystyle \varepsilon }$でランダムに選択し、それ以外ではQ値の最大の行動を選択する${\displaystyle \varepsilon }$-グリーディ手法や、遺伝的アルゴリズムで使用されているルーレット選択、以下のようなボルツマン分布を利用したソフトマックス手法などが使用されている。

${\displaystyle \pi (S_{t},a)={\frac {\exp(Q(S_{t},a)/T)}{\sum _{a'\in {\mathcal {A}}}\exp(Q(S_{t},a')/T)}}}$

ここで ${\displaystyle T}$ は正の定数、${\displaystyle {\mathcal {A}}}$ は状態 ${\displaystyle S_{t}}$ でエージェントが可能な行動の集合である。

行動価値関数の更新[編集]

行動を決定した場合、次にその状態と行動の行動価値関数Qを更新する。状態 ${\displaystyle S_{t}}$ のエージェントが行動 ${\displaystyle A_{t}}$ を選び、報酬 ${\displaystyle R_{t+1}}$ を得て、状態が ${\displaystyle S_{t+1}}$ に遷移したとする。このとき行動価値関数 ${\displaystyle Q(S_{t},A_{t})}$ を次の式で更新する。^[2]

${\displaystyle Q(S_{t},A_{t})\leftarrow (1-\alpha )Q(S_{t},A_{t})+\alpha \left[R_{t+1}+\gamma \max _{a}Q(S_{t+1},a)\right]}$

ここで ${\displaystyle \alpha }$ は学習率といい、${\displaystyle 0<\alpha <1}$ とし、後述のように時間と共に減衰させても良い。${\displaystyle \gamma }$ は割引率といい、${\displaystyle 0<\gamma <1}$ な定数である。上記の更新式は現在の状態から次の状態に移ったとき、そのQ値を（報酬＋割引率×次の状態で最も高いQ値）に近づけることを意味している。このことにより、ある状態で高い報酬を得た場合はその状態に到達することが可能な状態にもその報酬が更新ごとに伝播することになる。これにより、最適な状態遷移の学習が行われる。

学習率[編集]

Q学習は報酬が有界で、学習率 ${\displaystyle \alpha _{t}}$ が以下の条件を満たすとき（つまりこの条件で時間と共に減衰させたとき）、全てのQ値は確率1で最適な値に収束することを1992年にChristopher J. C. H. Watkins等が証明した。（この条件を満たさないと収束しないという意味では無く、定数でも収束するときは収束する）^[3]

${\displaystyle 0\leq \alpha _{t}<1}$

${\displaystyle \sum _{t=0}^{\infty }\alpha _{t}\to \infty }$

${\displaystyle \sum _{t=0}^{\infty }\alpha _{t}^{2}<\infty }$

この収束性の良さのためQ学習に関する多くの研究がなされているが、いくつかの問題点も指摘されている。例えばQ学習による理論的保証は値の収束性のみであり、収束途中の値には具体的な合理性が認められないため、（価値反復法の）Q学習は方策勾配法と比べると学習途中の結果を近似解として用いにくい。また、パラメータの変化に敏感でありその調整に多くの手間が必要である、などがある。

参考文献[編集]

• Watkins, Christopher J.C.H. (1989). Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge, England. PDFダウンロード
• 松本啓之亮、黄瀬浩一、森 直樹、『知能システム工学入門』、コロナ社、2002年、ISBN 4-339-02392-2
• 大内 東、山本雅人、川村秀憲『マルチエージェントシステムの基礎と応用』、コロナ社、2002年、ISBN 4-339-02388-4

参照[編集]

関連項目[編集]

• 強化学習
• 時間差分学習（TD学習）
• SARSA法
• Deep Q-Network