多腕バンディット問題を解説していくんだぜ

### 前提条件: 強化学習とは
強化学習って普通のAIと何が違うのか、定義をはっきりさせておきましょう。
よく聞く教師あり学習（MNISTの数字認識AIなど）は、正解ラベルというものが用意されています。つまり、私たち人間が正解を与えることで学習をさせ、問題を解けるようなモデルにさせるものです。
教師なし学習は、正解ラベルは存在せず、データの特徴を見つけるためのものです（おもにグループ分けや特徴抽出など）。
では**強化学習とは？** 強化学習の最たる特徴は、エージェント（ここでいうAI）が環境とのやりとりを繰り返して、集めたデータを使って高い報酬を得る方法を学習することです。

### 強化学習の最も有名な例: 多腕バンディット問題
バンディットはスロットマシーンのことです。多腕バンディット問題は簡単にいうと、**1~n個あるスロットマシーンの中からスロットマシーンを何回もプレイすることで、一番勝率のいい方法を見つけるAIモデルをいかにして作るか**という問題です。
ここでは1~n個のスロットマシーンに確率(n)が付与されているとします。
例えば0,1,5,10点がそれぞれ確率で出るスロットマシーンがあるとします。このとき、このスロットマシーンのそれぞれの点数の確率が分かれば、これをプレイすることの期待値が計算できます。**つまりn個のマシーン全ての期待値が最初からわかっていれば、最善の戦略を取ることができます。**
では、期待値がわからない場合、どのようにして最善に近い戦略を取るようにできるでしょうか？

ではスロットマシーンa,bの二つが存在するとして考えてみましょう。
考え方に必要な数式を紹介していきます。
ここで報酬をRとすると、Rはとある確率でそれぞれR={0,1,5,10}をとります。これは確率変数と言います。どのスロットを選ぶかという行動ActionをA遠くと、A={a,b}と置けます。
ここで、期待値をEと置くと報酬Rの期待値EはE[R]と書ける。また、Aをした時のRのEはE=E[R|A]とかける。
行動価値関数qを定義すると、A(a)をした時の行動価値関数q(a)=E[R|A=a]と書ける。

**バンディットアルゴリズムは何があれば成り立つか？**
・目的は、スロットをプレイして一番期待値の高いスロットを回し続けたい。
・もし期待値がわかっていれば、最善の戦略を取れる。
・わからないので、マシーンの価値を推定する必要がある。

ここでaのマシーンを3回プレイした時、0,1,5点という点数が出たとすると、**Q(a)=(0+1+5)/3=2**となる。
bを3回プレイした時、1,0,0だったとすると **Q(b)=0.3333...** となる。
つまりそれぞれのマシーンを**3回プレイした時の推定では、マシーンaの方が期待値が高い**とわかる。
ここで、Q(n)（標本平均という）の計算の仕方を工夫してみる。
```math
Q_n = \frac{1}{n} \sum_{i=1}^n R_i
```
ここで、n-1回目を考えると
```math
Q_{n-1} = \frac{1}{n} \sum_{i=1}^{n-1} R_i 
```
```math
\sum_{i=1}^{n-1} R_i = (n-1)Q_{n-1}
```
となり、よって
```math
Q_n = \frac{1}{n}(R_1+...+R_{n-1}+R_n)=\frac{1}{n}\left\{ (n-1) Q_{n-1}+R_n\right\}=(1-\frac{1}{n})Q_{n-1}+\frac{1}{n}R_n
```
最終的に
```math
Q_n=Q_{n-1}+\frac{1}{n}(R_n-Q_{n-1})
```
という形になる。
ここでのポイントは
```math
Q_n=Q_{n-1}+....
```
**Q_nをQ_n-1で表せる形**になっているということ。
よって最後の式の形から、**Q_nはQ_n-1から1/n(R_n-Q_n-1)だけ進んだ量**だということ、Q_n-1,Rn,nが分かれば標本平均を計算できることがわかる。
この時1/nは学習率と捉えることができる。n=∞の時、Q_n=Q_n-1となり、変化しなくなる。
標本平均をコードにしてみると
```
Q=0
for n in range(1,11):
    reward = np.random.rand()
    Q = Q+(reward-Q)/n  
    print(Q)
```
Q += (reward - Q)/nとも書ける（意味は一緒）

### どんな戦略が考えられるか？
・最善のマシーンをプレイし続ける戦略（greedyな戦略）:例えば1回目でa=0,b=1だったら、その後ずっとbのみを選び続ける
この方法の問題点は、本当はaの期待値がbよりも高い時でも、bを選び続けてしまう。つまり**誤った戦略を取り続けてしまう**可能性があるという点である。
つまり考えられる良さそうな戦略は
**・良さそうなマシンだけ使う(greedy)**
**・これまでの結果からいいマシンを割り出す(活用)** を両立することだと考えら得る。

### ε-greedy法
上記の条件を満たす方法で最も単純な方法がε-greedy法である。
ここではε=0.1（任意の数）,1-εで活用をするようにする。また、問題を単純化するために1点か0点かの二通りのみ、マシーンの数は10台にする。
**Banditを定義する**
```
import numpy as np

class Bandit:
    """
    複数のスロットマシン（アーム）を管理するクラス
    """
    def __init__(self, arms=10):
        """
        インスタンス作成時に実行される初期化処理
        
        arms: スロットマシンの数
        """
        # 各スロットマシンの「当たり確率」を0.0〜1.0のランダムな値で初期化
        # この確率はエージェントには知らされない
        self.rates = np.random.rand(arms)

    def play(self, arm):
        """
        指定された番号のスロットマシンをプレイする
        
        arm: プレイするマシンの番号 (0から始まる)
        """
        # 選択されたマシンの当たり確率を取得
        rate = self.rates[arm]
        
        # 当たり確率(rate)と、0.0〜1.0のランダムな数値を比較
        # rateの方が大きければ「当たり(1)」、小さければ「ハズレ(0)」を返す
        if rate > np.random.rand():
            return 1  # 当たり
        else:
            return 0  # ハズレ
        
```
armsの数はスロットの数。np.random.arnd(arms)で各マシーンに0~1.0の数を割り当てて、あたりの確率とする。
playしたとき、rate>np.random.rand()の時１、そうでなければ０を返す。
**Agentを定義する**
```
class Agent:
    """
    ε-greedy法に基づいて行動し、学習するエージェントのクラス
    """
    def __init__(self, epsilon, action_size=10):
        """
        インスタンス作成時に実行される初期化処理
        
        epsilon: 「探索(Exploration)」を行う確率 (例: 0.1)
        action_size: 選択肢の数（スロットマシンの数）
        """
        self.epsilon = epsilon
        
        # 各マシンの価値の推定値(Q値)を保存する配列。すべて0で初期化。
        self.Qs = np.zeros(action_size)
        
        # 各マシンをプレイした回数を記録する配列。すべて0で初期化。
        self.ns = np.zeros(action_size)

    def update(self, action, reward):
        """
        行動(action)と報酬(reward)に基づいて、価値の推定値(Q値)を更新する
        """
        # 選択したマシンのプレイ回数を1増やす
        self.ns[action] += 1
        
        # 標本平均の式を使って、選択したマシンのQ値を更新
        # Q_n = Q_{n-1} + (1/n) * (R_n - Q_{n-1})
        self.Qs[action] += (reward - self.Qs[action]) / self.ns[action]

    def get_action(self):
        """
        ε-greedy法に基づいて次の行動を決定する
        """
        # 0.0〜1.0のランダムな数値を生成し、epsilonと比較
        if np.random.rand() < self.epsilon:
            # 【探索】epsilonの確率で、ランダムに行動を選択する
            return np.random.randint(0, len(self.Qs))
        else:
            # 【活用】1-epsilonの確率で、現時点で最もQ値が高い行動を選択する
            # np.argmax(self.Qs)は、Qs配列の中で最も大きい値を持つ要素の「インデックス番号」を返す
            return np.argmax(self.Qs)
```
Qs,nsは10個の要素をもつ1次元配列。
updateは標本平均の計算をしてどれがいいマシーンかの更新を行う。get_actionはεの確率で適当なマシーンを選んで探索、1-εでself.Qsの最大値を取る。
**BanditクラスとAgentクラスを使って動かしてみる**
ここでは1000回行動して得れる結果を見てみる。
```
# シミュレーション設定
steps = 1000      # 総ステップ数
epsilon = 0.1     # ε-greedy法のε値

# スロットマシンとエージェントを作成
bandit = Bandit()
agent = Agent(epsilon)

total_reward = 0
total_rewards = [] # 累積報酬の履歴
rates = []         # 勝率の履歴

# 1000回ループ
for step in range(steps):
    # 1. エージェントが行動を決定
    action = agent.get_action()
    
    # 2. 決定した行動でスロットマシンをプレイし、報酬を得る
    reward = bandit.play(action)
    
    # 3. 行動と報酬を元に、エージェントが学習（Q値を更新）
    agent.update(action, reward)
    
    # 4. 報酬と勝率を記録
    total_reward += reward
    total_rewards.append(total_reward)
    rates.append(total_reward / (step + 1))

# 最終的な合計報酬を表示
print(f"合計報酬: {total_reward}")

# 最終的な勝率を表示
print(f"最終的な勝率: {rates[-1]:.3f}")

# (参考) 各スロットマシンの真の当たり確率
# print("真の当たり確率:", bandit.rates)
# (参考) エージェントが学習したQ値
# print("エージェントのQ値:", agent.Qs)

```
Agentのactionからrewardを得る。その行動と報酬からupdateで学ぶ。
**出力結果：　870**(実行ごとに結果は変わります）
これは1000回プレイしてそのうち870回があたりだったということ。
ここでprint(rates)をすると、1000回の実行中の勝率が見れます。今回の実行では最終的な勝率は0.886でした。これは役88％の確率で勝っているということです.
plot.plt(rates)を実行してみると、勝率が右肩上がりになっているグラフが出力されます。**spteを重ねるごとに勝率が増えていっていることから、ε-greedy法は正しく機能していることがわかります。**
**強化学習のアルゴリズムの良し悪しを比較するときは、一回の結果で比較してもあまり意味がありません**。なぜならいいアルゴリズムじゃなかったとしても、運で上振れする時、逆に下振れする時もあるからです。これは**行動の選択にランダム性があ**ることに起因します。
なので平均的な良さを評価する必要があります。
では200回同じ実験を行なって、その結果を平均したグラフを見てみましょう。
```
runs=200
steps=1000
epsilon=0.1
all_rates=np.zeros((runs,steps))

for run in range(runs):
    bandit=Bandit()
    agent=Agent(epsilon)
    total_reward=0
    rates=[]

    for step in range(steps)
        action=agent.get_action()
        reward=bandit.play(action)
        agent.update(action, reward)
        total_reward += reward
        rates.append(total_reward / (step+1))

    all_rates[run] = rates

avg_rates = np.average(all_rates, axis=0)

plt.plot(avg_rates)
plt.show()
```
all_ratesは(200,1000)の形状の配列。
各ステップ（1~1000)の勝率を、200回分集めて、それぞれの平均をグラフにplotする。結果は一回だけの時と変わらず、右肩上がりのグラフが出力される。
アルゴリズムを評価するときは、このように平均した結果を用いることが大切。このコードで出力したグラフの方が、ε-greedy法の特徴がより安定して見える。
![Figure_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3895365/ed6dadec-b47b-4ea1-a198-672dd509a235.png)
εの値を変えることも、学習率を上げることに効果的である。なぜなら、探索の頻度を変えることが、いい方策を見つけることに直結するからである。
問題によって適切な値を見つけることも、いいアルゴリズムを見つけるポイントになる。
### 非定常問題
ここまで話してきたバンディット問題は**定常問題**に分類される問題だった。
**定常問題とは？** → **報酬の確率分布が変わらない**問題のこと
今回の例では、最初にランダムで設定されたスロットマシンの勝率は、プレイ中に変化しなかった。
ではもし、banditのself.ratesが少しずつ変化したら？それは**非定常問題**に分類される。
ではこれから**非定常問題では、どのようにして標本平均を取るべき**か考えてみる。
標本平均の式は
```math
Q_n = \frac{1}{n} \sum_{i=1}^n R_i
```
これを変形すると
```math
= \frac{1}{n}R_1+\frac{1}{n}R_2+...+\frac{1}{n}R_n
```
と変形できる。
最後の指揮の形を見ると、1/nを**各報酬の重み**と見なすことができる。
非定常問題では、環境が変わるので過去のデータの重みは軽くすべき（直近のデータを重要視すべき）なので、そのように重みを調整する必要がある。
では式を変形して重みを調節できる形にしていく
```math
Q_n = Q_{n-1}+\frac{1}{n}(R_n-Q_{n-1})
```
```math
ここで \frac{1}{n} = α(0<α<1) とすると
```
```math
Q_n = Q_{n-1}+α(R_n-Q_{n-1})
```
```math
=αR_n+Q_{n-1}-αQ_{n-1}=αRn+(1-α)Q_{n-1}
```
ここで、n-1回目の式を考えると
```math
Q_{n-1} = αR_{n-1}+(1-α)Q_{n-2}
```
以上の式より、式変形するとQ_nは
```math
Q_n = αR_n-α(1-α)R_{n-1}+...+α(1-α)^{n-1}R_1+(1-α)^nQ_0
```
となる。
この式の形から、進んでいくにつで、Rnの重みが減っていっているのがわかる。
Rnの重みはαで、Rn-1はα(1-α)、Rn-2はα(1-α)^2というふうに、指数関数的に重みが減少しているのがわかる。このような計算を指数移動平均という。
### では非定常Banditを実装してみる
```
class NonStatBandit:
    """
    当たり確率が時間とともに変動する非定常なスロットマシン
    """
    def __init__(self, arms=10):
        self.arms = arms
        self.rates = np.random.rand(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
```
追加したコードはself.rates += 0.1 * np.random.randn(self.arms)だけです。
これを追加することで、プレイするたびにself.ratesに小さな乱数を加えることで、非定常な形にしています。
次はAgentを実装します
```
class AlphaAgent:
    """
    固定学習率(alpha)を用いて学習するエージェント
    """
    def __init__(self, epsilon, alpha, actions=10):
        self.epsilon = epsilon
        self.Qs = np.zeros(actions)
        self.alpha = alpha  # 固定学習率

    def update(self, action, reward):
        # ★★★ここが変更点★★★
        # 更新式に、試行回数(n)ではなく、固定値(alpha)を使う
        # Q_new = Q_old + alpha * (reward - Q_old)
        self.Qs[action] += (reward - self.Qs[action]) * self.alpha

    def get_action(self):
        # 行動選択のロジックは通常のAgentと同じ
        if np.random.rand() < self.epsilon:
            return np.random.randint(0, len(self.Qs))
        return np.argmax(self.Qs)
```
推定値をself.alphaのステップサイズで更新するようになりました。（前に式で説明した通り）
![Figure_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3895365/a3831c83-c8ba-4e7e-b1b9-36a117e9afdf.png)
以前のものと比べると、固定値αで更新した方が結果が良くなっていることがわかります。これより、標本平均が時間の経つタスクにうまく対応できていないことがわかります。

強化学習、おもしろいですよね。発展させていけばどんなゲームでも人間を上回ることができるんじゃないでしょうか。
またいつか、別の記事でお会いしましょう