はじめに

今回は先日紹介した強化学習の本の２章に登場するMulti-armed Banditsをとりあげます．
２章で取り上げられているので問題としては非常に単純な問題なのですが、いまだに研究の題材としては度々扱われます．2018年12月に開かれた国際会議NeurIPS 2018においてもBandit問題を扱った発表は多数見られました．

以下では、大学の講義ノートも参考にしながらバンディット問題を解説していきます．

Multi-armed Banditsとは

あたり（報酬）がでる確率の異なるアーム（スロットマシンをガチャンとやるアレです）を複数持つスロットがあると仮定します．プレイヤーはどのアームのあたり確率が高いかを知りません．

当然、プレイヤーはできるだけあたりの確率が高いアームだけを選び続けたいと考えます．同時にできるだけ早くそのアームを知りたいはずです．一般化して書けば限られた試行回数の中で、最良の選択を探すことが、が多腕バンディット問題で達成したい目的になります．

補足：k本の腕とせず、1本の腕を持つk台のマシンとして説明される場合もありますが、同じことです．今回は本に従い、k本の腕を持つマシンを仮定して進めていきます．

例１）k本の腕を持つマシンから1本を選んでN回プレイ、最良の腕を見つける
例２）k台のマシンから1台を選んでN回プレイ、最良の台を見つける

行動価値の計算

$q_*(k)$ を、アームkが持つ価値だとします．以下の４つのアームについて、価値を計算してみましょう．

１番のアーム：常に報酬８が得られる
- 1番のアームの価値は $q_*(1) = 8$
２番のアーム：88%の確率で報酬０、12%の確率で報酬１００が得られる
- 2番のアームの価値は $q_*(2) = .88 * 0 + .12 * 100 = 12$
３番のアーム：報酬は-10から35までの間で、等確率でランダムに等しく得られる．
- 3番のアームの価値は $q_*(3) = (-10 + 35) / 2 = 12.5$
４番のアーム：1/3の確率で報酬０、1/3の確率で報酬２０、1/3の確率で{8, 9, ..., 18}から等確率でランダム
- 4番のアームの価値は $q_*(4) = 1/3 * 0 + 1/3 * 20 + 1/3 * (8 + 18) /2 = 11$

そのアームの価値、つまり選んだ行動kの価値は得られる報酬の期待値で計算することができます．
上の計算は合っていると思いますが、間違っていたらご指摘ください．

The k-armed Bandit Problem（k-armed バンディット問題）

繰り返しになりますが、数式をいれて再度バンディット問題を整理します．時間ステップ $t = 1, 2, 3, \dots$ において、ｋ個の選択肢の中から１つを選び（ $A_t$ ）、 $A_t$ に対して報酬 $R_t$ を得られるとします．

行動aの真の価値 $q_*(a)$ は、以下のように行動aで得られる報酬の期待値として計算されます

$$q_*(a) \dot{=} \boldsymbol{E}[R_t | A_t = a], 　 \forall_a \in [1, \dots, k] 　true values $$

プレイヤー（腕を選んでスロットを回す人）は、アームの真の価値および分布を知りません．にもかかわらず、プレイヤーは得られる報酬を最大化しなければなりません．つまり、できるだけベストなアームを選び続けつつ、各アームの価値を探る必要があります．この２つはトレードオフの関係にあり、探索と利用のジレンマ（Exploration and Exploitation Dilemma）と呼ばれます．

The Exploration/Exploitation Dilemma

時刻 $t$ におけるgreedy（貪欲）行動 $a_t$ を次のように定義します．

$$ Q_t(a) \dot{=} \underset {a} {\operatorname {argmax}} Q_t(a)$$

ここで、
$A_t = A_t^*$ なら、利用（exploiting)

$A_t \neq A_t^*$ なら、探索（exploring)

プレイヤーは利用と探索の両方を同時にはできませんが、この両方をバランスよく必要があります．

行動価値 $Q_t(a)$ について

探索と利用のバランスよく行う方法の説明の前に、行動価値 $Q_t(a)$ について整理します．

バンディット問題における行動価値 $Q_t(a)$ は以下のように書くことができます．

$$Q_t(a) \dot{=} \frac{sum\; of\; rewards\; when\; a\; taken\; prior\; to\; t}{number\; of\; times\; a\; taken\; prior\; to\; t} = \frac{\sum_{i = 1}^{t - 1}R_i・\boldsymbol{1}_{A_i = a}}{\sum_{i=1}^{t-1} \boldsymbol{1}_{A_i = a}}$$

標本平均は無限回の試行が行われる場合、真の値に収束すると考えられます．

$$ \lim_{N_t(a) \to \infty} Q_t(a) = q_*(a)$$

ここで、 $N_t(a)$ は、時刻tまでに行動aがとられた回数を意味します

ε-greedy 法

では、探索と利用をバランス良く行うための最もベーシックな方法であるε-greedy 法について説明します．おさらいですが、greedyな行動選択とは常に最もよい選択のみを取り続けることを指します．つまり、探索を行いません．

ε-greedy 法では、基本的にはgreedyな行動をとり続け、たまにεの確率でランダムに行動選択を行います．

以下にε-greedy 法によるアルゴリズムを示します．

A simple bandit algorithm

$Initialize,\; for\; a\; =\; 1\; to\; k:$
$\qquad Q(a) \leftarrow 0$
$\qquad N(a) \leftarrow 0$

$Repeat\; forever:$
$\qquad A\;\leftarrow \left\{ \begin{array}{} \underset {a} {\operatorname {argmax}} Q_t(a)\qquad with\; probobability\; 1-\varepsilon \qquad (breaking\; ties\; randomly) \\ a\; random\; action\; with\; probability\; \varepsilon \end{array} \right.$
$\qquad R\; \leftarrow bandit(A)$
$\qquad N(A)\; \leftarrow N(A) + 1$
$\qquad Q(A)\; \leftarrow Q(A) + \frac{1}{N(A)}[R - Q(A)$ ]

実装例

ε-greedy法の効果を探るため、実際に学習を行ってみます．
実装にあたっては、githubで公開されているソースの一部を変更（無関係なところを削除）しています．

問題設定 10本の腕を持つスロットを想定し、3000回の学習を行います．学習の目的は最良のアームを選択、得られる報酬を最大化することなります．学習は2000台のスロットに対して行い、獲得報酬、最良アーム選択率の平均を求めています．行動選択は、greedy法とε-greedy法の2つを行い結果の比較を行います．
真の価値[tex:q*(a)]について各アームの真の価値[tex:q(a)]は平均0、分散1の正規分布から決めています．また２平均[tex:q_(a)]、分散1の正規分布から、各アームを引いた際に得られる報酬を生成します．当然、 $q_*(a)$ の値や分布についてプレイヤーは知りません．

2000台のスロットそれぞれ、最良のアームおよび真の価値は異なることに注意してください．

行動選択についてアームの選択は、ε-greedy法を用いています．εの違いによる結果への影響を見るため、ε=0, 0.01, 0.1, 0.5, 1.0として比較しています．ε = 0 はgreedyな行動（利用）のみをとり、ε = 1 は探索ばかりを繰り返すことになります．

必要なライブラリのインポート

公開されているgithubのコードは、宣言をすれば改変が認められているんですね．絶対しませんけど． tqdmは、実行中のfor文に使うことでforループの進捗状況をバー表示することができます．

#######################################################################
# Copyright (C)                                                       #
# 2016-2018 Shangtong Zhang(zhangshangtong.cpp@gmail.com)             #
# 2016 Tian Jun(tianjun.cpp@gmail.com)                                #
# 2016 Artem Oboturov(oboturov@gmail.com)                             #
# 2016 Kenta Shimada(hyperkentakun@gmail.com)                         #
# Permission given to modify the code as long as you keep this        #
# declaration at the top                                              #
#######################################################################

import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
import numpy as np
# 進捗状況を示すバーの表示
from tqdm import tqdm

Banditクラスの定義

ほぼ写経＋意味の追加です．元々のものはUCBアルゴリズムなどにも対応できるようしっかりと作りこまれていますが、今回の内容と関連しない部分は私の頭がついていけないので、削除しています．

少しはクラスの勉強しておいてよかった・・．

#Banditクラスの定義
class Bandit:
# @k_arm: # of arms
# @epsilon: probability for exploration in epsilon-greedy algorithm
# @initial: initial estimation for each action
# コンストラクタ
    def __init__(self, k_arm=10, epsilon=0., initial=0.,  true_reward=0.):      
        self.k = k_arm # 腕の数
        self.indices = np.arange(self.k) # k個のインデックスを作成
        self.time = 0 # time 初期値0
        self.average_reward = 0 # （平均）報酬の初期値0
        self.true_reward = true_reward # 真の報酬(クラス定義で指定しなければ0)
        self.epsilon = epsilon # クラス定義で指定しなければ0
        self.initial = initial # クラス定義で指定しなければ0
    
    # 初期化メソッド
    def reset(self):
        # real reward for each action
        # k本のアーム分、真の報酬を正規分布から選ぶ
        self.q_true = np.random.randn(self.k) + self.true_reward
        
        # estimation for each action
        # qの推定値の初期化（initialが0なら、0とするだけ）
        self.q_estimation = np.zeros(self.k) + self.initial

        # # of chosen times for each action
        # 行動選択の数の初期化→0に
        self.action_count = np.zeros(self.k)
        
        # ベストアクションの初期化→初期化したq_trueのうち、最大のもの
        self.best_action = np.argmax(self.q_true) 

    # get an action for this bandit
    # 行動（アーム）選択メソッド
    def act(self):
        #（乱数がεより小さければ完全にランダム）
        if np.random.rand() < self.epsilon:
            return np.random.choice(self.indices)
        # qの推定値の最大値をq_bestとする
        q_best = np.max(self.q_estimation)
        # q がq_bestと一致する行動の中からランダムで1つ選ぶ
        return np.random.choice([action for action, q in enumerate(self.q_estimation) if q == q_best])

    # take an action, update estimation for this action
    # 
    def step(self, action):
        # generate the reward under N(real reward, 1)
        # 報酬を平均（真の報酬）、分散１の正規分布からランダムに作成（スロットも確率的だということ）
        reward = np.random.randn() + self.q_true[action]
        
        self.time += 1
        
        # 平均報酬は、
        self.average_reward = (self.time - 1.0) / self.time * self.average_reward + reward / self.time
        
        # 行動カウンターを更新
        self.action_count[action] += 1
        
        #self.q_estimation[action] += 1.0 / self.action_count[action] * (reward - self.q_estimation[action])
        self.q_estimation[action] = (self.action_count[action] - 1.0) / self.action_count[action] * self.q_estimation[action] + reward / self.action_count[action]

        return reward

計算実行部分の定義

関数simulateで計算のメイン部分を行っています．

3つのfor文で構成されており、

最初のfor文がインスタンスの数だけ回すループで、今回はパラスタを行うεの数である5回周ります．
次のfor文が平均をとるために複数回同じ学習を回すループで、個のループは2000回まわります．
最後のfor文が、1台に対して行う学習ステップで、今回は3000となります．

def simulate(runs, time, bandits):
  
    # ベストアクションカウンターと、報酬リストを空にする
    best_action_counts = np.zeros((len(bandits), runs, time))
    rewards = np.zeros(best_action_counts.shape)
    
    # インスタンスの数だけループ
    for i, bandit in enumerate(bandits):
      
        # 複数台のマシンに対するループ（平均をとるため）
        for r in tqdm(range(runs)):
            bandit.reset() # 初期化（マシンごとのベストアクション、価値はここで決められる）
            
            # 1台に対して行う学習STEP
            for t in range(time): #
                action = bandit.act() # 行動を選択
                reward = bandit.step(action) # 行動に対する報酬を取得
                rewards[i, r, t] = reward # 報酬リストに保存
                
                # 選んだ行動がベストアクションであれば、カウントする
                if action == bandit.best_action:
                    best_action_counts[i, r, t] = 1
                    
    # 学習曲線は、2000本(runの数だけ)存在する．
    # ベストアームを選んだ回数および報酬を2000台に対して平均を取る
    best_action_counts = best_action_counts.mean(axis=1)
    rewards = rewards.mean(axis=1)
    
    return best_action_counts, rewards

図化および計算実行用の関数

e_greedy()：インスタンスの定義を行い、実行用関数に渡しています．こんな風にリスト化したインスタンスを関数に渡せるんですね．

test_bed()：乱数で発生させた報酬の分布をviolinplotという方法で図化する関数．実際に学習の中で使っている乱数の値や分布とは異なりますが、概ねこういった分布をスロットの報酬として仮定しているということを示しています．という理解ですが間違っていたらご指摘ください．

f:id:shirakonotempura:20190124035035p:plain

def test_bed():
# N(0,1)の標準正規分布からランダムに選んだ10の数値を平均μa．
# N（μa, 1)の正規分布からランダムに選んだ200の数値の分布を図化
# あくまでイメージ図のため200としているでOK？

    plt.violinplot(dataset=np.random.randn(200,10) + np.random.randn(10))
    plt.xlabel("Action")
    plt.ylabel("Reward distribution")
    plt.savefig('./images/test_bed.png')
    plt.close()

def e_greedy(runs=2000, time=3000):
    # epsilonのサイズでパラスタ（0はgreedy行動選択）
    epsilons = [0, 0.1, 0.01, 0.5, 1.0]
    # epsごとにインスタンスを作成、banditsにリストとして保存→次の関数へ
    bandits = [Bandit(epsilon=eps) for eps in epsilons]    
    best_action_counts, rewards = simulate(runs, time, bandits)

    plt.figure(figsize=(10, 20))

    plt.subplot(2, 1, 1)
    for eps, rewards in zip(epsilons, rewards):
        plt.plot(rewards, label='epsilon = %.02f' % (eps))
    plt.xlabel('steps')
    plt.ylabel('average reward')
    plt.legend()

    plt.subplot(2, 1, 2)
    for eps, counts in zip(epsilons, best_action_counts):
        plt.plot(counts, label='epsilon = %.02f' % (eps))
    plt.xlabel('steps')
    plt.ylabel('% optimal action')
    plt.legend()

    plt.savefig('./images/e_greedy.png')
    plt.close()

if __name__ == '__main__':
    test_bed()
    e_greedy()

結果について

得られたグラフを以下に示します．

ε = 0.0 では常にグリーディな行動を選択します．そのため、 0.0以上の価値をもつ行動が見つかれば、その行動を常に選択し続けるようになり、それ以外の行動を探索しません．そのため，得られる報酬の平均値は常に一定（大体1.0程度）となっています．
ε = 0.01では、学習により報酬の平均値は1.5近くまで上がっています．3000 step以降でも、もう少し学習の余地がありそうです．学習のスピードは遅いですが、性能は最もよく学習ができているようです．
ε = 0.1,も、報酬の平均値は1.4程度に達しておりますが、必ず1割はランダム行動を行ってしまうため、報酬、最良アーム選択率とも頭打ちになっております．
ε = 0.5では、行動の半分をランダムに選択するため学習した結果を大分すてていることになります．平均では、greedy行動よりも悪い結果となってしまいました．
ε = 1.0では、学習した結果をまったく利用せずランダムな行動をとり続けます．そのため学習stepがいくら進んでも報酬の平均値や、最良アーム選択率はまったく上がっておりません．