# Reinforcement Learning : day 2 Q-Learning

## 題材
[巡回セールスマン問題](https://en.wikipedia.org/wiki/Travelling_salesman_problem)を強化学習で解いてみたいと思う。

## 問題設定
巡回セールスマン問題を「Framework for Reinforcement Learning」に落とし込む。
使うデータは[ここ](https://amano-tec.com/data/megacities.html)
* State
* 彼が現在いる国. 状態の数は国の数と一致する
* Action
* 彼が次に訪れる予定の国. 行動の数は国の数と一致する
* Policy
* 彼が一度訪れた国は選択できない（一度訪れた国の遷移確率は0である）
* Transition
* 宣言した国に必ず行ける（確定的行動をとれる）
* Reward
* **++現在いる国と次に訪れる国との距離++**

この Reward をどう定義するかが学習の鍵だが、、いったんこれで学習する

## 実装
https://github.com/kazukingh01/kkpackages/blob/master/kkreinforce/main/main.py#L10-L19

## 学習
とりあえず学習した。
episode は一連の学習を示す単位である。
ここでは、初期状態から全ての国に到達するまでの過程を1 episode とする。
### episode = 0
### episode = 1000
### episode = 5000

## 課題と考察
問題設定時点で分かってはいたが、彼が学習しているのは、「**次に行く国のさらに次に行く国に近い国があるか**」みたいな指標である。
これは全体距離を最適化するような学習にはなっていない。
全体距離を最適化するには、**過去に行った国に依存した学習が必要不可欠だからだ**。
それを実現しようとすると、状態$s^{(t)}$は次のように行った国に依存する。

現在 80 カ国を定義している。
過去に行った国に依存しない現在のQ-tableの状態は80である。
これに過去に行った国の依存を考慮すると
状態は、国80×過去訪問履歴$2^{80}$×step数80の値になり、とてもじゃないが学習できない。

簡単のため、国の数を7にして、step数を無視してやってみた。
Q-table は下記のように定義してみる。

例
| | 国1 | 国2 | ... | 国7|
| -------- | -------- | -------- | -------- | -------- |
| 国1,0,0,0,0,0,0,0 | 0.2 | 3 | ... | 2.3 |
| 国1,0,0,0,0,0,0,1 | 0.3 | 3 | ... | 2.3 |
| 国1,0,0,0,0,0,1,0 | 0.4 | 2.2 | ... | 1.3 |
| 国1,0,0,0,0,0,1,1 | 0.3 | 1 | ... | 2.3 |
| ... | ... | ... | ... | ... |
| 国7,1,1,1,1,1,1,1 | 0.2 | 3 | ... | 2.3 |

Reward が難しくて（何が正解かわからないが）とりあえず次のようにしてみた。
全ての国を回った時
　合計距離
それ以外
　国と国の距離

結果

うーんうまくいかない。
とりあえず実装をのせておく
https://github.com/kazukingh01/kkpackages/blob/master/kkreinforce/main/main.py#L22-L31

[次勉強するための参考]
https://www.slideshare.net/RyoIwaki/ss-87924430
https://qiita.com/panchovie/items/86323946cceca6695e91
https://arxiv.org/pdf/1611.09940.pdf
https://github.com/MichelDeudon/neural-combinatorial-optimization-rl-tensorflow