確率ロボティクス2016第9回

Mon Nov 28 09:29:05 JST 2016 (modified: Fri Nov 29 17:22:47 JST 2019)
views: 792, keywords:

確率ロボティクス

第9回

上田 隆一

2016年11月30日@千葉工業大学

本日の内容

• 強化学習（古典的なもの）
• 参考: Sutton and Barto, 三上, 皆川訳: 強化学習, 森北出版, 2000.
  • ウェブ版 
  • そろそろ第2版が出るらしい

強化学習（reinforcement learning）

• 機械学習の一種
  • 起源: 動物の心理学研究から[宮崎2005]
    • 餌にありつけるような/危険を避けるような行動の学習
  • 最近ANN（人工ニューラルネットワーク）との組み合わせで脚光を浴びている

基本的な強化学習の問題

• 有限MDPでの行動決定の問題に一つ制限を与える
  • 状態遷移と報酬が、行動しないと分からない。
• 問題の定義
  • 時刻: [latex]\\mathcal{T} = \\{t | t = 0,1,2,\\dots,T \\}[/latex]
  • 状態: [latex]\\mathcal{S} = \\{s_i | i = 1,2,3,\\dots,N\\}[/latex]
    • うち、いくつかは終端状態の集合[latex]\\mathcal{S}_\\text{f}[/latex]に含まれる
  • 行動: [latex]\\mathcal{A} = \\{a_j | j = 1,2,3,\\dots,M\\}[/latex]
  • 状態遷移や報酬は時不変だが自明でない
    • ある確率分布に従って状態遷移する
    • ある法則に従って報酬が与えられる

何を求めたいのか

• （前回あんまり強調してませんでしたね・・・）
• 「最適方策」を求める
• 方策（二種類）
  • 決定論的方策: [latex]\\pi : \\mathcal{S} \\to \\mathcal{A}[/latex]
    • 状態が決まると行動が決まるもの
  • 確率的な方策: [latex]\\pi : \\mathcal{S}\\times \\mathcal{A} \\to \\Re[/latex]
    • 状態[latex]s[/latex]において行動[latex]a[/latex]を選択する確率
• 最適方策は決定論的になる（理由は次のページに）
  • [latex]\\pi^* : \\mathcal{S} \\to \\mathcal{A}[/latex]

問題を解く道具

• ベルマン方程式が成り立つ
  • [latex]V^*(s) = \\max_{a \\in \\mathcal{A} } \\sum_{s' \\in \\mathcal{S}}\\mathcal{P}_{ss'}^a [V^*(s') +\\mathcal{R}_{ss'}^a ][/latex]
    • [latex]V^*[/latex]: 最適状態価値関数
    • 左辺の「[latex]\\max_{a \\in \\mathcal{A} }[/latex]」を満たすものが最適方策[latex]\\pi^*[/latex]
• エージェントの「経験」
  • 状態遷移: ある状態[latex]s[/latex]で行動[latex]a[/latex]を選択したら状態[latex]s'[/latex]に遷移して報酬を得た
  • たくさん行動すれば統計的な性質が得られる
  • たくさん行動しなければ統計的な性質が得られない

問題の難しさ

• 価値関数に停留点が一つでもあると、エージェントがその場に留まってしまう
• 膨大な試行が必要

経験からの方策評価

• とりあえず決定論的な方策[latex]\\pi : \\mathcal{S} \\to \\mathcal{A}[/latex]に対して、 経験から価値関数を求めてみましょう
•  モンテカルロ法を利用
  • 効率はとりあえず気にしない
• 次のように計算
  • 次の試行・手続きを十分繰り返す
    • エージェントを[latex]\\pi[/latex]で終端状態まで動かす
    • 状態遷移・報酬を観測
    • この試行で通ったところの価値を求める
  • 各状態、各試行で求めた価値を平均

方策を求めるには

• 方策が与えられない場合
  • 何か適当な初期の方策を与えて価値関数がよくなるように方策を改善していけば良い
  • でもどうやって行動を選ぶのか？
• 価値をもう一種類考えるとやりやすい
  • 行動価値関数: [latex]Q^{\\pi}(s,a)[/latex]
    • 方策[latex]\\pi[/latex]の下、状態[latex]s[/latex]で行動[latex]a[/latex]を選択することの価値
    • [latex]V^{\\pi}(s) = \\max_a Q^{\\pi}(s,a)[/latex]

手順（方策オン型）

1. [latex]Q(s,a)[/latex]をnullで初期化
2. 初期状態を適当に選んでエージェントを動かす
3. [latex]Q(s,a)[/latex]が一番良い行動[latex]a[/latex]（グリーディな行動）を選ぶ
   • たまに違うのを選ぶ（[latex]\\epsilon[/latex]-グリーディ方策）
4. その試行における状態行動対の価値を計算
5. 各状態の価値を、これまでの全試行の価値の平均値で更新
   • 問題: [latex]\\epsilon[/latex]-グリーディー方策の価値が求まる

手順（方策オフ型）

• 各試行の非グリーディな行動が混ざっている部分を価値の更新に使わない
  • 終端状態から遡ってグリーディな行動だけとっていた部分だけ切り取って、そこの価値だけ更新
• 問題: 無駄が多い

ブートストラップの導入

• （強化学習での）ブートストラップ
  • 以前に計算した遷移後の状態の価値を使って遷移前の状態の価値を求める
• つまり価値反復で行った手続きの一部

TD（temporal difference）学習

• 行動した時に次の式で価値を更新
  • [latex]V(s) \\longleftarrow (1-\\alpha)V(s) + \\alpha[r + \\gamma V(s')][/latex]
    • [latex]\\alpha[/latex]: ステップサイズパラメータと呼ばれる
    • [latex]\\gamma[/latex]: 割引率
      • 移動等の問題の場合は1で考えておいて良い
• 行動するたびに上の式で価値を更新
• 方策オン型（Sarsa）とオフ型（Q学習）
• 今日はワンステップのものしか扱わないが、一度の行動でいくつかの状態を変更する効率の良い方法も（TD[latex](\\lambda[/latex])）

Sarsa

• 方策ON型TD学習
• 行動価値を学習
  • [latex]Q(s,a) ← (1-\\alpha )Q(s,a) + \\alpha[r + \\gamma Q(s',a')][/latex]
• 手順
  1. [latex]Q(s,a)[/latex]を初期化
  2. [latex]\\epsilon[/latex]-グリーディ方策等から行動[latex]a[/latex]を選択
  3. 行動[latex]a[/latex]をとり、[latex]s'[/latex]に移った後、次の行動[latex]a'[/latex]を選択
  4. 上の式で[latex]Q(s,a)[/latex]を更新

Q学習

• 方策オフ型TD学習
• 次の式を使う
  • [latex]Q(s,a) ← (1-\\alpha )Q(s,a) + \\alpha [r + \\gamma \\max_{a'} Q(s',a')][/latex]
• [latex]\\epsilon[/latex]-グリーディ方策を使っても非グリーディな行動が価値関数に影響を与えない

連続空間での強化学習

• 今までの話は離散状態が前提
• 連続空間も考えなければいけないことがある
  • ロボットは連続空間にいる
  • 離散状態の数が膨大になる
• 求める価値関数、方策
  • 連続状態空間[latex]\\mathcal{X}[/latex]に対して・・・
  • [latex]V^*: \\mathcal{X} \\to \\Re[/latex]
  • [latex]\\pi^*: \\mathcal{X} \\to \\mathcal{A}[/latex]

手法

• 近似（強化学習をこじらせると関数近似に流れ着く）
  • 動径基底関数
  • タイルコーディング
  • 人工ニューラルネットワーク（ディープニューラルネットワーク）
    • TD-Gammon, DQN, A3C
• アクター・クリティック（actor-critic）
  • 方策[latex]\\pi[/latex]の実装と価値関数[latex]V[/latex]の実装を分ける
  • [latex]Q(s,a)[/latex]を使ってしまうとメモリのサイズが大きく融通が利かない
  • A3Cはアクター・クリティック