今回の記事は、本テキストの主に2.5章からを整理したものになります．今回は、Non-stationary Problem（非定常問題）およびOptimistic Initial Values（楽観的初期値）について扱います．

Tracking a Non-stationary Problem

前回は、行動の真の価値が変化しない仮定（定常）のもと、多腕バンディット問題を扱いました．アームの真の価値は常に変わりませんでした．しかし、実際に時間変化を伴う現実の問題では必ずしもこれは適切ではありません．では、時間の経過とともに、行動の真の価値が変化する状態（Non-stationary Problem、非定常問題）を考えていきます．

真の価値が変化する非定常問題においては、遠い過去の報酬よりも直近の報酬に重みを置く方が理にかなっていると言えます．

もし、あなたがあるお菓子のCM担当者でイメージキャラクターにタレントを選ばなければならない場合、過去に一発当たったタレントを、現在流行りのタレントと同様には扱わないかと思います．

f:id:shirakonotempura:20190124055328p:plain

このように非定常問題においては、これまで価値の推定で使用した標本平均という考え方が適切でなくなるため、違った方法で価値を推定する必要があります．最もよく使われる方法は、ステップサイズパラメータと呼ばれる定数を用いる方法で、下式で表されます

$Q_{n+1} \dot{=} \; Q_n + \alpha [R_n - Q_n$ ]

ここで、 $\alpha$ がステップサイズパラメータを示し、 $\alpha \in (0, 1$ ]の定数となります．
（ $\alpha \in (0, 1$ ]は、 ${0} \lt \alpha \leq 1$ を意味します）

$Q_{n+1}$ は、過去の報酬と最初の推定量 $Q_1$ の加重平均となります．

\begin{align} Q_{n+1} \dot{=} \; Q_n + \alpha [R_n - Q_n]\ &= \alpha R_n + (1 - \alpha)[\alpha R_{n-1} + (1 - \alpha)Q_{n-1}]\\ &= \alpha R_n + (1 - \alpha) \alpha R_{n-1} + (1 - \alpha)^2 Q_{n-1}\\ &= \dots \\ &= (1 - \alpha)^n Q_1 + \sum_{i = 1}^{n} \alpha (1 - \alpha)^{n - i} R_i\\ \end{align}

Optimistic Initial Values

前述の式のとおり、これまでの方法は最初の行動価値の推定量 $Q_1(a)$ にある程度依存（偏り( bias)を持つとも言われる）しています．これまでは、あまり深く考えずに $Q_1(a) = 0$ としてきましたが、実は初期値の見積もり方は、結果に大きく影響することがあります．

例として最初に3回ずつスロットを回した結果で初期推定値を決める場合を以下に示します．
上図のように、初期推定値を真の価値より高く見積もってしまった場合は、試行が進むにつれ選択が誤っていたことに気が付くことができます．一方で、真の価値よりも初期推定値を低く見積もってしまった場合、それが最良の行動であるにも関わらず、他方の行動価値がその推定値を下回らなければ、最良の行動は選択されなくなってしまいます．

f:id:shirakonotempura:20190125013336p:plain — 楽観的勘違いの例

f:id:shirakonotempura:20190125013318p:plain — 悲観的勘違いの例

出典：これからの強化学習（一部改良）

このように初期値を楽観視する楽観主義の考え方の名前には、『不確かな時は楽観的に（optimism in face of uncertainty）』という名前が付けられおり、探索と利用のトレードオフにおいて重要な考え方であると言えます．

最も単純な楽観主義のアルゴリズムである楽観的初期値法を以下に示します．このアルゴリズムでは、学習前に各アームから報酬の最大値をK回観測していたとして、アームの推定価値を高く（楽観的な側）に見積もるというものです.

楽観的初期値法

報酬の最大値を $r_{sup}$ とする学習中に観測した結果に加え、各アームから $r_{sup}$ の報酬がK回観測されていたと考えて、各アームの報酬の期待値を計算する $$\acute{\mu_i} = \frac{これまで腕\;i\;から得られた報酬の和\;+\;Kr_{sup}}{これまで腕\;i\;をプレイした回数\;+\;K} $$ $\acute{\mu_i}$ が最大のアームを選ぶ

出典：これからの強化学習

ただし今回の実装では、このアルゴリズムは実装しておらず単に初期値に楽観的な値を入れるだけとしています．

実装して確認

初期値の影響を確認するために、 $Q_1(a) = 5$ として、再度多腕バンディット問題を解いてみます．今回は価値の推定に標本平均法ではなく、ステップサイズパラメータ（ $\alpha = 0.1$ ）を導入してみます．

ステップサイズパラメータと初期推定値の実装

今回は、追加修正した箇所のみ示します．こちらをみながら真似しているだけです．

コンストラクタへステップサイズパラメータの追加

コンストラクタに、step_sizeを追加しています．同時に、標本平均法を採用するかどうかを、sample_averages = True or Falseで判別するようにしています．

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

stepメソッドの修正

self.q_estimation[action]の計算に、step_sizeを導入した方法を追加しています．

sample_average = Trueであれば、標本平均法を、そうでなければstep_sizeを用いた手法となります．

    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
        
        
        if self.sample_averages:
            self.q_estimation[action] = (self.action_count[action] - 1.0) / self.action_count[action] * self.q_estimation[action] + reward / self.action_count[action]
        else:
            self.q_estimation[action] += self.step_size * (reward - self.q_estimation[action])

        return reward

関数e_greedyの修正

こちらは、今回使いませんが、コンストラクタにsample_average（デフォルト False）を追加していますので、インスタンスの定義において、sample_average = True`を追加しています．

def e_greedy(runs=2000, time=3000):
    # epsilonのサイズでパラスタ（0はgreedy行動選択）
    epsilons = [0, 0.1, 0.01, 0.5, 1.0]
    bandits = [Bandit(epsilon=eps, sample_averages = True) for eps in epsilons]    
    best_action_counts, rewards = simulate(runs, time, bandits)

関数optimistic_initial()の追加

テキストの内容に、初期Q値0.5でε=0.5および初期Q値0でε=0の2つのインスタンスを追加で定義しています．

def optimistic_initial(runs=2000, time=1000):
    bandits = []
    bandits.append(Bandit(epsilon=0,   initial=5, step_size=0.1))
    bandits.append(Bandit(epsilon=0,   initial=0, step_size=0.1))
    bandits.append(Bandit(epsilon=0.1, initial=5, step_size=0.1))
    bandits.append(Bandit(epsilon=0.1, initial=0, step_size=0.1))
    best_action_counts, _ = simulate(runs, time, bandits)

    plt.plot(best_action_counts[0], label='epsilon = 0, q = 5')
    plt.plot(best_action_counts[1], label='epsilon = 0, q = 0')
    plt.plot(best_action_counts[2], label='epsilon = 0.1, q = 5')
    plt.plot(best_action_counts[3], label='epsilon = 0.1, q = 0')
    
    plt.xlabel('Steps')
    plt.ylabel('% optimal action')
    plt.legend()

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