ゼロから作るDeepLearning❹をざっと理解する　～1章 バンディット問題～

# はじめに
研究で深層強化学習を使うことになったので、研究費でゲットした書籍で強化学習を勉強していきます。

筆者はPythonと知識とCNNを勉強して簡単なDeepLearningの知識があります。
強化学習の基本的な用語も知っています。
数式はニガテです。

この書籍では1～6章が強化学習、7～10章で深層強化学習を扱っています。

https://www.oreilly.co.jp/books/9784873119755/

2章はこちら

https://qiita.com/InaTai/items/ec0a29198fcc42c51d28


## 環境
Windows10
Python3系

# バンディット問題とは
バンディット ＝ スロットマシン

バンディット問題は設定の違うスロットマシンが複数台あるときに、一番設定の良いスロットマシンを探すという問題です。
強化学習の中で最もシンプルな問題です。

下の図は強化学習中のスロットマシンとプレイヤーの相互関係を表しています。
![バンディット問題枠組み.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3507440/dee59ae7-8e10-1f2f-22f9-06bf94ed4969.png)
**Agent**(エージェント)が**Action**(行動)した結果、**State**(環境)から**Reward**(報酬)を受け取る

の図です。
これは

**プレイヤー**が**レバーを引いた**結果、**スロットマシン**から**コイン**を受け取る

と言い換えることができます。

## バンディット問題の解き方
簡単に言うと、何回もスロットを回してその結果から期待値を推定します。

**期待値の推定方法**を示します。

| 試行回数 | スロットマシン1 | スロットマシン2 | 
| :------- | :-------------: | :-------------: | 
| 1回目    | 0               | 1               | 
| 2回目    | 0               | 0               | 
| 3回目    | 1               | 1               | 

- スロットマシン1の推定値
$$ Q_3 = \frac{0+0+1}{3} = 0.33\cdots $$

- スロットマシン2の推定値
$$ Q_3 = \frac{0+1+1}{3} = 0.66\cdots $$

推定値は $Q$(quality) です。
2つのスロットマシンを比べると、この試行回数ではスロットマシン2の方が設定がよさそうということになります。

$n$回の試行として一般化すると
$$ Q_n = \frac{R_1+R_2+\cdots+R_n}{n}$$

となります。



## プログラミングの目線から見た推定

$n$回の試行の時のスロットマシンの期待値の推定値
$$ Q_n = \frac{R_1+R_2+\cdots+R_n}{n}$$
を安直に書き下してみます。

```python
import numpy as np

steps = 10 # 行動回数
rewards = []

for n in range(steps):
    reward = np.random.rand() # 報酬をランダムに決める
    rewards.append(reward)
    Q = sum(rewards) / n # 推定値を更新
    print(Q)
```
このままでは**毎ステップ報酬の合計を求めなければなりません。**
ステップ数が多ければ多いほど計算回数はより増えていきます。

そこで
$$ Q_{n-1} = \frac{\bigl(R_1+R_2+\cdots+R_{n-1}\bigr)} {n-1} $$
$$ Q_n = \frac{\bigl(R_1+R_2+\cdots+R_{n-1}\bigr)+R_n}{n} $$
より共通部分$(R_1+R_2+\cdots+R_{n-1})$があるので代入して整理すると
$$ Q_n = Q_{n-1} + \frac{R_n - Q_{n-1}}{n} $$
となります。
これをプログラムで表すと
```python
Q = 0

for n in range(steps):
    reward = np.random.rand() # 報酬をランダムに決める
    rewards.append(reward)
    # Q = sum(rewards) / n 
    Q += (reward - Q) / n # 推定値を更新
    print(Q)
```
これで**毎ステップ報酬合計を求める必要がなくなりました。**


## バンディット問題を強化学習で解く
いよいよ強化学習をしていきます。

問題設定は **10台** のスロットマシンがある中で設定の良いスロット台を探索します。
強化学習中の**報酬の合計**や**勝率**も高い方がうれしい気持ちになります。

![バンディット問題枠組み.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3507440/dee59ae7-8e10-1f2f-22f9-06bf94ed4969.png)

この図を覚えていますでしょうか。
強化学習中のプレイヤーとスロットマシンの関係図です。
バンディット問題の強化学習で何を行うのか順番に説明すると
1. **プレイヤー**(Agent)が**レバーを引くスロット台**(Action)を選択する
1. **選んだスロット台**(Action)のレバーを引いて、**スロット台**(State)から**コイン**(Reward)を得る
1. **選んだスロット台**(Action)と**コイン**(Reward)をもとに**推定値Q**を更新する
1. 1 に戻る

です。

順にプログラムでの実装を説明します。

### 1. **プレイヤー**(Agent)が**レバーを引くスロット台**(Action)を選択する
強化学習中のプレイヤーの行動は大きく分けて2種類あります。

これまでの経験をもとに**最善の行動**を選択する　->　**活用**
スロットの設定をより精度よく推定するために**様々な選択**を試す　=>　**探索**

この「活用」と「探索」をバランスよく選ぶことが大切です。
強化学習でよく使われる最も基本的で最も応用の利く行動の選択法を**ε-greedy法(イプシロン-グリーディー法)** といいます。

ε-greedy法は

$\varepsilon$ の確率でランダムな行動 (探索)
$1-\varepsilon$ の確率で推定値が最大の行動 (活用)

を行います。

`` def get_action(self): ``でε-greedy法を使って行動を選択しています。
```python
class Agent:
    def __init__(self, epsilon, action_size):
        self.epsilon = epsilon
        self.Qs = np.zeros(action_size) # 各台の推定値
        self.ns = np.zeros(action_size) # 各台のスロットを回した回数
    
    def get_action(self):
        if self.epsilon > np.random.rand():
            return np.random.randint(0, len(self.Qs)) # εの確率でランダムな行動
        return np.argmax(self.Qs) # 1-εの確率で推定値が最大のスロットを回す
```


### 2. **選んだスロット台**(Action)のレバーを引いて、**スロット台**(State)から**コイン**(Reward)を得る
ここは普通に確率通りに報酬を渡せば大丈夫ですね。
``def play(self, arm):``で報酬を決定し返しています。
引数``arm``は選択されたスロット台の番号です。
```python
class Bandit:
    def __init__(self, arms):
        self.rates = np.random.rand(arms) # arms台のマシンの設定

    def play(self, arm):
        rate = self.rates[arm] # 選んだスロット台の設定を得る
        if rate > np.random.rand():
            return 1
        else:
            return 0
```

### 3. **選んだスロット台**(Action)と**コイン**(Reward)をもとに**推定値Q**を更新する
$$ Q_n = Q_{n-1} + \frac{R_n - Q_{n-1}}{n} $$
で推定値の更新を行うと嬉しいとはじめの方で学習しました。
``action``はプレイヤーが選択したスロット台の番号です。
```python
class Agent:
    def __init__(self, epsilon, action_size):
        self.epsilon = epsilon
        self.Qs = np.zeros(action_size) # 各台の推定値
        self.ns = np.zeros(action_size) # 各台のスロットを回した回数

    # 省略

    def update(self, action, reward):
        self.ns[action] += 1 # 選択したスロット台の試行回数を+1
        self.Qs[action] += (reward - self.Qs[action]) / self.ns[action]
                                          # 選択したスロット台の推定値更新
```

### 4. 1 に戻る
**1.** ～ **3.** を決められた回数繰り返します。
そして結果も観たいです。

```python
import numpy as np

class Bandit:
    # 省略
class Agent:
    # 省略
  
arms = 10 # スロットの台数
steps = 1000
epsilon = 0.1

bandit = Bandit(arms=arms)
agent = Agent(epsilon=epsilon, action_size=arms)
total_reward = 0
total_rewars = []
rates = []

for step in range(steps):
    action = agent.get_action()                 # 1. 行動を選択
    reward = bandit.play(arm=action)            # 2. 行動し、報酬を得る
    agent.update(action=action, reward=reward)  # 3. 行動と報酬をもとに推定値を更新
    total_reward += reward
    
    total_rewars.append(total_reward) # ステップごとに報酬の合計を保存
    rates.append(total_reward / (step+1)) # ステップごとにステップ時点での勝率を保存


# 結果表示のための図
import matplotlib.pyplot as plt

plt.ylabel('Total reward')
plt.xlabel('Step')
plt.plot(total_rewars)
plt.show()

plt.ylabel('Rate')
plt.xlabel('Step')
plt.plot(rates)
plt.show()

```

### 結果
ステップごとの報酬の合計
<img width="500" alt="バンディット_total_reward.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3507440/f0f83aa8-cb80-1612-92cb-52978744d86e.png">

ステップごとの勝率の変化
<img width="500" alt="バンディット_rate.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3507440/9fb5b886-8097-8efb-3ac6-e6f9503810cd.png">

ステップごとに勝率が上がっていって途中からはほぼ一定ですね。
きちんと学習できていることがわかりました。




# 非定常問題
今まで扱ってきたバンディット問題は最初から最後までスロットの設定が変化しない**定常問題**でした。
設定を途中でいじることで**非定常問題**になります。
先ほどの``class Bandit:``に一行加えてみます。
```python
class Bandit:
    def __init__(self, arms):
        self.rates = np.random.rand(arms) # arms台のマシンの設定

    def play(self, arm):
        rate = self.rates[arm] # 選んだスロット台の設定を得る
        ###
        self.rates += 0.1 * np.random.randn(self.arms) # 小さいノイズを追加
        ###
        if rate > np.random.rand():
            return 1
        else:
            return 0
```

これで非定常問題になりました。

## 非定常問題における推定
結論から言えば、非定常問題のときの推定は**固定値 α (0 < α < 1)** を使って
$$ Q_n = Q_{n-1} + \alpha(R_n - Q_{n-1}) $$
とした方が、推定への**後の報酬の重要度が高くなる**ので良い推定値が得られやすいです。
感覚ではわかりにくいので簡単に数式で考えてみます

***
**定常問題** のときに使用した推定値を求める式
$$ Q_n = Q_{n-1} + \frac{1}{n}(R_n-Q_{n-1})= \frac{R_1+R_2+\cdots+R_n}{n} $$
全ての報酬に1/nをかけたものの和が推定値です。
推定値に**全ての報酬が均一に影響**していることがわかります。この報酬に影響する係数を**重み**といいます。
これは非定常問題には向いていません。なぜならスロット台の設定が変わっていく問題では、最初の方の結果の重要度は低いからです。

***

固定値 $\alpha$ について考えてみます。
$$Q = Q_{n-1} + \alpha(R_n - Q_{n-1}) = \alpha R_n +(1-\alpha)Q_{n-1}$$
感覚的にわかりやすくするために、上式を使って3回の試行したときの推定値をそれぞれ数式で表します。
```math
Q_1=\alpha R_1+(1-\alpha)0 = \alpha R_1
```
```math
Q_2 = \alpha R_2 + (1-\alpha)\alpha R_1=\alpha R_2+(\alpha^2-\alpha)R_1
```
```math
Q_3=略=\alpha R_3 + (\alpha^2-\alpha) R_2 + (\alpha^3-\alpha^2-\alpha)R_1
```
$Q_3$ を見ると分かりやすいですが、$R_1$の重み$(\alpha^3-\alpha^2-\alpha)$は、$R_3$の重み$(\alpha)$と比べてどうでしょうか。
$R_1$の**影響をより小さくしようとする方向**に働いています。

***
今回推定で扱った数式

標本平均：$ Q_n = Q_{n-1} + \frac{1}{n}(R_n - Q_{n-1}) $
指数移動平均：$ Q_n = Q_{n-1} + \alpha(R_n - Q_{n-1}) $

# おわりに
最後までお読みいただきありがとうございます。
初めて記事を書いたのですが、見にくかったら申し訳ないです。
勉強しながらちょこちょこ書いていきますのでよろしくお願いします。


2章はこちら

https://qiita.com/InaTai/items/ec0a29198fcc42c51d28