Evolution Strategyについて

いきなりまとめ

Evolution Strategyの概要

• Reinforcement Learningと同様の行動探索のためのアルゴルズム
• black-box stochastic optimization techniquesのこと
• ランダムに生成したパラメーターを元に探索を行う

Evolution Strategyの利点

• back-propagationが不要
• 高い並列性
• 高い頑健性
• long time scaleに向いている

Today I Learned

Evolution Strategies as a Scalable Alternative to Reinforcement Learning
を参考に。

Reinforcement Learning

ある環境（ゲーム）に置かれたagentがどうふるまうか(policy function)を決める。
policy functionとはたとえば、ゲームの状態をinputとして許された行動のそれぞれの確率を出力するneural networkのこと。
パラメーターの数は100万にもなり、ゲームをうまくプレイするための最適なパラメーターを見つけることがゴール。

Evolution Strategies

evolutionとついているがbiological evolutionとはほとんど関係ない。
black-box stochastic optimization techniquesのこと。
black-box stochastic optimizationでは100万のパラメーターが入力され、1つのtotal rewardが出力される。
数学的にはf(w)をwに関して最適化する。
ただしfについてはいかなる仮定も置かない。

最適化のアルゴリズムは“guess and check” process。
ランダムなパラメーターからスタートして、1:ランダムに少し調整、2:その結果を元に変更、を繰り返す。

具体的には、wに対してgaussian noiseを加え100個の少しずつ異なったパラメーターベクトルを生成。
それぞれ独立にpolicy networkを使用してシミュレーションを実施しrewadsの合計を取得。
アップデートするパラメーターベクトルはそれら100個のパラメーターをrewardsで重みづけした加重平均。

ESではパラメーターに直接ノイズを入れるが、RLではアクション選択にノイズを入れる。

Evolution Strategiesの利点

• バックプロパゲーションが不要
• 高い並列性
• 高い頑健性
• long time scaleに向いている

バックプロパゲーションが不要

これによって、

• コードが短い
• 2，3倍はやい
• メモリー消費が少ない
• gradients explodingの心配がない
• はるかに多くの関数の探索が可能

となる。

高い並列性

RLでは全パラメーターを同期させなければならない。
ESではノイズを入れたパラメーターに関するrewardを同期させるだけでよい。

高い頑健性

RLではハイパーパラメーターの値を変えると結果が大きく変わることがある。
たとえばframe-skip hyperparameterを変えるとRLでは結果が大きく異なる。
ESではどんな値でも同じくらいうまくいった。

long time scaleに向いている

1エピソードの時間が長い場合やアクションが長時間の影響を及ぼす場合などはESは望ましい。