強化学習・メタヒューリスティクス

機械学習の枠組み

• 教師あり学習
  • SVD
  • ナイーブベイズ
• 教師なし学習: データにラベル付けがされておらず、エラーも報酬もない。
  • クラスタリング
    • 階層型クラスタリング
      • 最短距離法
      • 最長距離法
    • 非階層型クラスタリング
      • K-means
• 強化学習 (日本の wikipedia では教師なし学習の一種という位置づけ)
  • 動的計画法
  • モンテカルロ法
  • TD (Temporal Difference: 時間差分) 学習
    • 方策 ON: sarsa
    • 方策 OFF: Q-learning

参考文献

• http://www.eb.waseda.ac.jp/murata/ryotaro.nishino/openhouse/reinforce.php
• http://www.eb.waseda.ac.jp/murata/mituhiro.seki/openhouse/RL_abs.php
• http://www.eb.waseda.ac.jp/murata/mituhiro.seki/openhouse/RL_algorithm.php

強化学習とは

参考: http://sysplan.nams.kyushu-u.ac.jp/gen/edu/RL_intro.html
エージェントと環境のやりとり（試行錯誤）によって、環境に適応する方法を学習する枠組み。

1. エージェントは時刻 t における状態観測 s(t) に応じて意思決定を行い、行動 a(t) を出力する
2. エージェントの行動により、環境は状態 s(t+1) へ遷移する。環境はその遷移に応じた報酬 r(t) をエージェントに与える
3. 時刻を t+1 に進める。

上記のプロセスを通じて、利得最大化を目的として状態観測から行動出力へのマッピング(=方策、Policy、π)を獲得する。

マルコフ決定過程とはなにか

強化学習の枠組みでは、エージェントが存在する環境をマルコフ決定過程によってモデル化し、アルゴリズムの解析を行う。

マルコフ過程

未来の挙動が現在の値のみで決定される性質をもつ確率過程のこと。過去の挙動とは無関係

• 単純マルコフ過程: ただひとつの状態から次に起こる事象が決定されるマルコフ過程。単純に「マルコフ過程」といった場合はこれ。
• N 階マルコフ過程: N 個の状態系列から次の事象が決定されるマルコフ過程。

マルコフ決定過程

マルコフ過程に意思決定のプロセスが加わったもの。

Ｑ学習とはなにか

• 状態 State: s = {s_1, s_2, …, s_n}
• 行動 Action: a = {a_1, a_2, …, a_m}
• 遷移確率 Probability: P^a(s, s') = P(s_{t+1}=s'|s_{t}=s, a_{t}=a)
• この時に与えられる報酬 Return: r_t
• 報酬の期待値 Expected Return: R^a(s, s') = E(r_{t}|s_{t}=s, a_{t}=a, s_{t+1}=s')
• エージェントの各時刻 t における意思決定 Poilcy: \pi(s, a) = P(a_{t}=a|s_{t}=s)
• 利得（エージェントが将来にわたって受け取る報酬の時系列評価） Value: V_t = r_t + \gamma r_{t+1} + …

ここで、もし \pi が時間に関わらず不変（定常政策という）であれば、行動はその時の状態によってのみ選択される。したがって、利得も状態 s の関数になるので、State-Value 関数 V^{\pi}(s) となる。

探索戦略

メタヒューリスティクスとはなにか

実装してみよう！

このタスクについて

下記のことをアピールするためのものである。その目的を達成する過程で、自分自身の理解を深める。

• メタヒューリスティクスについてひと通り理解している
• 強化学習についてひと通り枠組みを理解している
• 簡単なエージェントなら実装可能