強化学習

統計・機械学習

一般メモ

  • 大枠は動学的最適化，つまり，目的関数がある関数の積分形式（または総和）で与えられ，目的関数を最大化する関数を求める問題の解法だと思われる．
  • 強化学習の特徴として試行性（試行をしながら学習すること．探索と利用のトレードオフの話など．）を挙げる記載が多いが，それは間違っていると思う．試行性は探索的アルゴリズム全般が持っていて，強化学習独特の特徴ではない．
  • 強化学習を他と際立たせているのは，最終状態まで良いか悪いかの判断が付かない（途中の状態での良し悪しが分からない）という問題設定への適用が可能である点だと思う．これを実現しているの（解法の特徴）が報酬の伝播だし，目的関数が和の形になっていることからも暗にそういう問題を想定していると思う．
  • 報酬の伝播というのは，結局各中間状態の良し悪しを最終状態からの推定値とするということだ．途中の状態を如何に評価するのかが肝であり，逆強化学習は人の動きから，最近流行りのDQNはそれを大量の試行から評価する．
  • つまり，教師あり学習はすべての状態ｘに対する答えｙが与えるが，それを与えることができない問題．一部の状態ｘ（多くはこれが最終状態や特異な状態）にのみｙが与えることができる場合，という問題設定への解法であると思う．
  • 教師ｙと報酬は別物だというのも分かるけど，報酬を推定しているという状況のほうが大きな特徴だ．
  • 探索する関数のxを状態として，出力をアクションと見れば，各状態（ｘ）での最適化なアクションは？という問題に答えていることになり，ロボットの行動学習にも応用される．
  • 特に状態が連続系じゃなく離散状態を取る例が良く見られるが，この場合はその手続をマルコフ決定過程(MDP)とみなして，MDPの最適化と捉えることもできる．この際，実環境でのロボットでは実際には全ての状態に関する情報を観測することは現実的には不可能である．よって，実際は部分観測MDP（POMDP）となる．
  • 最適化アルゴリズムはTD法と呼ばれるある時刻と別のある時刻の差分情報で逐次最適化していく方法，sarsa法とQ-learningが一般的．sarsa法とQ-learningの違いは，関数の更新式において，次状態の最適値を取るか，次状態での価値の分布までをみるかの違いだと思う．よって，Q学習のほうがよりグリーディに最適解に収束しようとするために収束は早いものの，局所解に陥る可能性が高い．sarsa法はその逆の性質だと思われる．
  • ↑と思っていたらSARSA法は，次状態で選ぶQ値を次状態の期待値とする，方法みたいだ．つまり，その選び方（方策）がすごく限定的な選択法ならSARSA法のほうが局所解に陥る可能性がある．逆に，Q学習は次の状態でどの行動を選ぶかは一般的にはεグリーディで選ぶから，必ずしもQが最大な行動を取るわけではない．この違いから，SARSA法は方策（SでのAの選択方法）依存，Q学習は方策非依存と言われるみたい．でもこれって，SARSAでどんな方策を使うかに依存する話だから，何か一般的な話してもしょうがないような気もする（SARSAがQに近いこともあれば，εがすごく小さくてQがSARSAに近いってことがある，みたいな）．方策依存，非依存，ってことと，実際には次状態のQを慎重に選んだり，εをどうするか？が局所解への陥りと収束性になる，と覚えておこう．
  • 他にはモンテカルロ法，動的計画法もある．動的計画法は問題がそのような形式に（サブ問題を逐次拡大しながら繰り返し最適化していくと大域最適解に到達できる形式）変換できるならそれで解くべき．モンテカルロ法はなんだろ？（ランダム試行で期待値で行動決定するってことかな？）
  • 報酬という形で徐々に徐々に望むべき姿に引き寄せて行く．本当に最終状態でしか報酬を与えないような場合には，一般的には学習に非常に多くの時間がかかる．そのため，内部にモデルを持ってモデル推定を併用したり，階層的に学習させたり，簡単な問題から段階的に学習させたり，という工夫が適用される．オセロのような最終局面にでどんでん返しが起こりやすい問題設定は序盤への報酬の伝搬に時間がかかると思われる．モンテカルロ木探索などは枝が指数的に手に負えない深さでモンテカルロで手を進めて報酬を推定したりする．
  • 絵画や音楽などでは，あるアクションに対する教示データが人によって異なる，それを利用して人の感性を学習させようと言うのが対話進化計算（IEC:Interactive evolutionary computatoin）という応用があるようだ．


Q学習/sarar法
・アルゴリズムの大枠は，Q(s,a)，但しsは状態，aは行動というテーブルを持っておいて，Qを逐次最適化していく．動学的最適化で考えるとQがまさに求める最適な関数．
・適時最適化では，状態sにあるときにある行動aをとった時に与えられる報酬と，次状態での得られうる報酬の期待値で逐次Qの中のどのaが良いのかを更新していく．ここで，ある行動に対しての直接的な報酬だけでなく，次状態を考慮して更新しているためゆっくり最適化すれば大域的最適解に行く．また，報酬に遅れがある場合にも順次その報酬がそれより以前の行動選択に影響を与える．但し，一般的には次状態の解の良さの期待は減衰させるのであんまり遅いと消えてしまう．
・sarsa法はQ学習よりも次状態の扱いが慎重．イメージではsarsa法のほうが石橋を叩いて渡るイメージ．慎重で遅いけど，ミスは少ない．
・現実問題としては状態が爆発する，または状態がそもそも直接記述できない時（部分観測って意味だと思う），QをNNで近似しようというのが最近流行りの強化学習＋NN系の話だと思う．

数式の意味
Q学習の説明を読むと更新式を目にするけれど，あの式の意味を直感的に理解しておくことが重要だ．更新式を理解するには，Qの意味を理解しておく必要がある．Qテーブルの各値Q(s,a)は状態sで行動aを取ることの価値であり，それは報酬の和である．無限の試行を繰返せば一定値に収束する．じゃあ，どんな値に収束するかというと，それ以降に獲得される報酬の最大値だ．それはどんな値？かと言うと，R(s,a)+R1(s',a')...Rn(s'',a'')，ここでRi(s',a')はそれ以降のi番目の行動の報酬だ．これは再帰的な定義になっていて，R1以降は状態s'で行動a'をとった時に，そして，それはその次の状態の...という風に続くことになる．これを最大化するんだから，R1以降は最大値を取るんだ．これがmax(...)の部分．それに値が発散しないように割引率γをつけたものを考える．つまり，Q(s,a)の最適値を下記で推定しているんだ．

Q(s,a) ≒ R(s,a) + γ*max(Q(s',a')) (1)

そう考えると，今のQ(s,a)の推定値と，式(1)の右辺の差が誤差の推定値となる（報酬自体も推定だ）．で，局所解に嵌らないように，ちょっとずつ誤差を埋めていこうとするとよく見る更新式になる．つまり，今の値Q(s,a)に誤差(R(s,a)+γ*max(Qs',a')-Q(s,a))をαで調整したものをちょっとずつ付け加えていこう，という意味になる．

Q(s,a) ← Q(s,a) + α{R(s,a) + γ*max(Q(s',a')- Q(s,a)} (2)

DQNでのNNへの教師信号って何？

  • NNはQテーブルを表現していることと，式(1)を理解していればおのずとわかる．
  • 式(1)の右辺はQ(s,a)の推定値なんだ．だから，NN（Q(s,a)を表現する）の教師信号のｙの推定値になる．よって，NNへの入力がs,aの時に式(1)の右辺の値がどうだったか？の履歴を入力と出力の組としてNNを学習させるんだ．
  • DQNはアクション毎にNNを持っているって認識であってるのかな？それとも，一つのNNで出力層だけアクション分あるのかな？


その他書き散らし
・行動は報酬に繋がるだけでなく，その後の報酬にも影響を与える．状態遷移による報酬体系
・探査を含むことが最大の特徴であり，探査と利用のジレンマをどうするか？が大きな問題になる．一般的にはεグリーディ法などが用いられる．
・報酬と価値，特に価値をどう表現してどう評価するか？は最重要な問題．最近の深層強化学習とかは，そこをNNなどで逐次最適化しようとしているんだと思う．
・GAなどの進化的手法との違いは進化の過程を直接的に使っているかどうか．
・手法は大きくは，１）行動価値評価法，２）強化比較法，に分類される．
　１）行動価値評価法
　　　各行動毎に評価値を持ち，その価値評価値にしたがってεグリーディ法やSoftMax法で行動を選択する．εグリーディ法は確率εで探索する方法．
　　しかし，εグリーディ法では行動の評価値に依らず一定の確率で選択する部分に改良の可能性がある．そこでSoftMax法は行動の評価値にしたがって，
　　ギブス分布またはボルツマン分布にしたがって行動を重みを付けて選択する．
　２）強化比較法
　　　ある行動をとった際の報酬を評価する際に，その値自身ではなく，リファレンス報酬値との差分を評価し，その値によってその行動の選択優先度を更新する．
　　リファレンス報酬値としては，これまでの報酬値の平均などが用いられる．
・評価値は絶対値ではなく相対的な値が重要である．
　　これを利用して，オプティミスティック初期値と呼ばれる方法は初期値を報酬よりも大きな値にしておくことで，試行の初期に局所解に落ちいいるのを避ける．また，非定常過程に対応するために，時系列にしたがって過去の報酬値を漸近的に減衰させていく方法がもある．これも相対的に過去を小さく評価していると言える．
・報酬関数に関して
・結局は報酬の与え方が全てだ．報酬であるべき姿を定義して，その実装は自動で生成してくれ，という問題設定だ．報酬の与え方次第で学習できるか否か，どういう学習になるのか？は異なる．その報酬の与え方は自明ではなく，そこに難しさがある．
・そこで，報酬定義を自動化しようという試みは古くからある．大きな流れの一つが人とインタラクションをさせて，報酬を推定しようというものだ．


＊終了時刻，トライアル回数が固定の場合とそうでない場合では当然解は異なる．
　現実問題は固定の場合が多いのかな