UCBアルゴリズム

早速ですがUCBアルゴリズムの説明をしていきます．UCBとはUpper Confidence Boundの略になります．前回紹介した楽観主義に基づいたアルゴリズムの１つです．

式から分かる特徴としては、

何度も選ばれている行動ほど選ばれにくくなる
すべての行動の選択回数が多くなってくるにつれて探索回数を減らすことができる

価値は小さいが選択回数が少ないアームがある場合は（それを選択する）探索を行うアルゴリズムになります．

$$A_t \dot{=} \underset {a}{\operatorname {argmax}}\Biggl[Q_t(a) + c\sqrt{\frac{\log t}{N_t(a)} } \Biggr]$$

ここで、

$A_t$ ：step tにおいて選択する行動
$Q_t(a)$ ：step t における行動aの価値
$c$ ：UCB用ハイパーパラメータ（２でOK？）
$t$ ：総step数（100step目であれば100）
$N_t(a)$ ：step t までに行動aが選択された回数

注意：『これからの強化学習』に載っているのは『UCB1アルゴリズム』です．よく似ていますが若干中身が異なります．

さくっと実装

UCB用コンストラクタの実装

これまでと同様、スロットが持つ10本のアームの中から最良アーム（長期的に報酬を最大化できるアーム）を選択することを学習させます．

今回あらたに必要となるのは、UCB用ハイパーパラメータcとなります．
またこれが定義されているか否かが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.,
                 sample_averages =False,  step_size = 0.1, UCB_param = None):      
        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

        self.sample_averages = sample_averages
        self.step_size = step_size
        
        self.UCB_param = UCB_param

行動選択メソッドへUCBアルゴリズムを追加

ε-greedy法とも組み合わせて使えます．εを設定した場合は、確率εでUCBで行動選択、それ以外はランダムで行動選択を行います．

    # get an action for this bandit
    # 行動（アーム）選択メソッド
    def act(self):
        #（乱数がεより小さければ完全にランダム）
        if np.random.rand() < self.epsilon:
            return np.random.choice(self.indices)
        
        # UCB
        if self.UCB_param is not None:
            UCB_estimation = self.q_estimation + \
                     self.UCB_param * np.sqrt(np.log(self.time + 1) / (self.action_count + 1e-5))
            q_best = np.max(UCB_estimation)
            return np.random.choice([action for action, q in enumerate(UCB_estimation) if q == q_best])

        # 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])

インスタンスの設定と学習の実行（simulate())

今回は、UCBアルゴリズム（ε=0）と、探索率を0.1および0.01としたε-greedy法の３つのインスタンスを作っています．価値推定法は共通で標本平均法としています．

学習STEPは1000でもよかったのですが、ε=0.01としたε-greedy法の学習が1000回では不十分だったので3000STEPとしています．

今回もbanditsリストに各インスタンスを格納して、simulate()に渡しています

def UCB(runs=2000, time=3000):
    bandits = []
    bandits.append(Bandit(epsilon=0, UCB_param=2, sample_averages=True))
    bandits.append(Bandit(epsilon=0.1, sample_averages=True))
    bandits.append(Bandit(epsilon=0.01, sample_averages=True))
    _, average_rewards = simulate(runs, time, bandits)

結果

以下に平均報酬の学習履歴を示します．

UCBアルゴリズムは収束性、平均報酬の両面で最も性能がよい結果となりました．
ε= 0.1のケースは、200 STEP目あたりまでは性能がよいですが、その後性能が頭打ちとなっています．
ε = 0.01のケースは最終的には平均報酬はUCBアルゴリズムと同程度まで上がっていますが、収束の速さで遅れをとる結果となりました．平均報酬に関しては、もう少しSTEP数をやれば逆転したかもしれません．