強化学習アルゴリズムの選び方

## 主旨

強化学習アルゴリズムは多すぎて，結局どういう条件でどのアルゴリズムを使ったらよいかわからなかったので，調べてみました．

## 系図

![image.png](https://qiita-image-store.s3.amazonaws.com/0/107399/85dac776-927d-2b23-ff98-58f5c4f117e7.png)
図: 主要なアルゴリズム(左上の数字は誕生年)

![image.png](https://qiita-image-store.s3.amazonaws.com/0/107399/7ef94016-0c36-ba66-408d-278e359d3053.png)
図: DQN誕生以降版([Deep Learning for Video Game Playing](https://arxiv.org/pdf/1708.07902.pdf)より引用)


## アルゴリズムの選択基準

- 問題の空間(離散/連続)と手法，工夫によってアルゴリズム名が変わる．
- 手法は行動価値関数$Q(s,a)$を更新するために利用

| アルゴリズム      | 状態空間 | 行動空間 |
| ---------------| ------- | ------ |
| DQN            | 離散/連続 | 離散   |
| DDPG           | 離散/連続 | 連続   |
| NAF[^1]        | 離散/連続 | 連続   |
| CEM            | 離散/連続 | 離散   |
| Sarsa          | 離散     | 離散   |
| Q学習           | 離散     | 離散   |
| Deep Sarsa     | 離散/連続 | 離散   |

## 問題例

| 状態空間 | 行動空間 | 例　　　　　                     |
| ------ | ------ | ------------------------- |
| 離散    | 離散    | 三目並べ, 迷路, テトリス, 囲碁 | 
| 離散    | 連続    | ダーツ                   　　　　|
| 連続    | 離散    | 倒立振子                 　　　　|
| 連続    | 連続    | ブロック崩し, インベーダー    　　　　|

## サンプルコード

OpenAI Gymの倒立振子は，
- 状態空間: 連続(座標と傾き)
- 行動空間: 離散(左 or 右)
なので，上記表よりDQNかCEM, Deep Sarsaで解けば良いことがわかります．

Keras-RLにあるCEMで解く[サンプル](https://github.com/matthiasplappert/keras-rl/blob/master/examples/cem_cartpole.py)です．

```python
import gym
from keras.models import Sequential
from keras.layers import Dense, Activation, Flatten
from rl.agents.cem import CEMAgent
from rl.memory import EpisodeParameterMemory
env = gym.make("CartPole-v0")
nb_actions = env.action_space.n
model = Sequential()
model.add(Flatten(input_shape=(1,) + env.observation_space.shape))
model.add(Dense(nb_actions))
model.add(Activation('softmax'))
memory = EpisodeParameterMemory(limit=1000, window_length=1)
cem = CEMAgent(model=model, nb_actions=nb_actions, memory=memory,
               batch_size=50, nb_steps_warmup=2000, train_interval=50, elite_frac=0.05)
cem.compile()
cem.fit(env, nb_steps=100000, visualize=False, verbose=1)
cem.test(env, nb_episodes=5, visualize=True)
```

## References

### DQN

- [Playing Atari with Deep Reinforcement Learning](https://arxiv.org/abs/1312.5602), Mnih et al., 2013
- [Human-level control through deep reinforcement learning](http://www.nature.com/nature/journal/v518/n7540/abs/nature14236.html), Mnih et al., 2015
- [Deep Reinforcement Learning with Double Q-learning](http://www0.cs.ucl.ac.uk/staff/d.silver/web/Applications_files/doubledqn.pdf), van Hasselt et al., 2015
- [Dueling Network Architectures for Deep Reinforcement Learning](https://arxiv.org/abs/1511.06581), Wang et al., 2016
- [[Survey]Playing Atari with Deep Reinforcement Learning](https://www.slideshare.net/mooopan/ss-30336609), Fujita, 2014
- [[Survey]深層強化学習の動向 / survey of deep reinforcement learning](https://speakerdeck.com/takuseno/survey-of-deep-reinforcement-learning), Seno et al., 2017

### DDPG(Deep Deterministic Policy Gradient)

- [Deterministic Policy Gradient Algorithms](http://proceedings.mlr.press/v32/silver14.pdf), Silver et al., 2014
- [Continuous control with deep reinforcement learning](https://arxiv.org/abs/1509.02971), Lillicrap et al., 2015

### NAF(Normalized Advantage Functions)

- [Continuous Deep Q-Learning with Model-based Acceleration](https://arxiv.org/abs/1603.00748), Gu et al., 2016
- [[Survey][DL輪読会]Continuous Deep Q-Learning with Model-based Acceleration](https://www.slideshare.net/DeepLearningJP2016/dlcontinuous-deep-qlearning-with-modelbased-acceleration), 2017

### CEM(Cross-Entropy Method)

- [Learning Tetris Using the Noisy Cross-Entropy Method](http://www.mitpressjournals.org/doi/abs/10.1162/neco.2006.18.12.2936?journalCode=neco), Szita et al., 2006
- [Deep Reinforcement Learning (MLSS lecture notes)](http://learning.mpi-sws.org/mlss2016/slides/2016-MLSS-RL.pdf), Schulman, 2016

### Sarsa

- [Reinforcement learning: An introduction](http://people.inf.elte.hu/lorincz/Files/RL_2006/SuttonBook.pdf), Sutton and Barto, 2011

## References

- [これから強化学習を勉強する人のための「強化学習アルゴリズム・マップ」と、実装例まとめ](https://qiita.com/sugulu/items/3c7d6cbe600d455e853b)
- 小川雄太郎. つくりながら学ぶ! 深層強化学習 ~PyTorchによる実践プログラミング~. マイナビ出版, (2018).
- Justesen, Niels, et al. "Deep learning for video game playing." arXiv preprint arXiv:1708.07902 (2017).
- これからの強化学習, Makino et al., 2016.
- [Keras-RL](http://keras-rl.readthedocs.io/en/latest/agents/overview/), matthiasplappert, 2016
- [連続な空間における強化学習](http://sysplan.nams.kyushu-u.ac.jp/gen/edu/ContinuousSpace/ContinuousSpace.html), Kimura et al., 1999

### 補足

[^1]: NAF: [Normalized Advantage Function](https://arxiv.org/abs/1603.00748)の略称．DQNで行動空間が連続な問題を解くために用いられます．