はじめに

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

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

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

2章はこちら

環境

Windows10
Python3系

バンディット問題とは

バンディット＝スロットマシン

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

下の図は強化学習中のスロットマシンとプレイヤーの相互関係を表しています。

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}$$
を安直に書き下してみます。

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} $$
となります。
これをプログラムで表すと

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台 のスロットマシンがある中で設定の良いスロット台を探索します。
強化学習中の報酬の合計や勝率も高い方がうれしい気持ちになります。

この図を覚えていますでしょうか。
強化学習中のプレイヤーとスロットマシンの関係図です。
バンディット問題の強化学習で何を行うのか順番に説明すると

プレイヤー(Agent)がレバーを引くスロット台(Action)を選択する
選んだスロット台(Action)のレバーを引いて、スロット台(State)からコイン(Reward)を得る
選んだスロット台(Action)とコイン(Reward)をもとに推定値Qを更新する
1 に戻る

です。

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

1. プレイヤー(Agent)がレバーを引くスロット台(Action)を選択する

強化学習中のプレイヤーの行動は大きく分けて2種類あります。

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

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

ε-greedy法は

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

を行います。

def get_action(self):でε-greedy法を使って行動を選択しています。

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は選択されたスロット台の番号です。

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はプレイヤーが選択したスロット台の番号です。

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. を決められた回数繰り返します。
そして結果も観たいです。

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()

結果

ステップごとの報酬の合計

ステップごとの勝率の変化

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

非定常問題

今まで扱ってきたバンディット問題は最初から最後までスロットの設定が変化しない定常問題でした。
設定を途中でいじることで非定常問題になります。
先ほどのclass Bandit:に一行加えてみます。

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回の試行したときの推定値をそれぞれ数式で表します。

Q_1=\alpha R_1+(1-\alpha)0 = \alpha R_1

Q_2 = \alpha R_2 + (1-\alpha)\alpha R_1=\alpha R_2+(\alpha^2-\alpha)R_1

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章はこちら