ナード戦隊データマン

機械学習, 自然言語処理, データサイエンスについてのブログ

探索と活用のトレードオフ: バンディットアルゴリズムでの検証

探索と活用のトレードオフとは、情報の探索にかける時間と、情報を活用する時間をどう割り振るかによって引き起こるトレードオフです。

今回は、バンディットアルゴリズムによって探索と活用のトレードオフが起こることを示し、改善策を示します。

github.com

バンディットアルゴリズムの概要

f:id:mathgeekjp:20190913154532j:plain

  • epsilon: 探索を選ぶ確率
  • アーム: 選択肢
  • 報酬: 選択肢を選んだときに、何らかのメカニズムによって発生する利益
  • 探索: 選択肢をランダムに選ぶフェーズ。
  • 活用: 今までの報酬情報を利用して、最も良い選択肢を選択するフェーズ。

epsilon-Greedy法では、以下の手順で選択をします。

  1. 確率epsilonで探索し、確率1-epsilonで活用する。
  2. 探索した場合、ランダムに複数の選択肢から一つを選ぶ。
  3. 問題固有のメカニズムによって、報酬が発生する。
  4. 活用のために過去の報酬情報を更新する。

直感的には、探索が多ければそれだけ早くベストなアームを見つけ出せる可能性が高くなるはずです。一方で、活用が多ければ、これまでに発見したベストなアームを高い頻度で選ぶことになるので、十分な探索が行われていれば活用を増やしたほうが良いような気がします。

このように、探索を増やせば活用の機会が減り、活用を増やせば探索の機会が減ることを「活用と探索のトレードオフ」といいます。

コーディング

それでは、この概念を検証するためにコーディングします。

epsilon_greedy.py

import numpy as np


class EpsilonGreedy:
    def __init__(self, n_arms, epsilon=0.5, counts=None, values=None):
        self.epsilon = epsilon
        if counts is None:
            self.n_arms = n_arms
            self.counts = np.zeros(n_arms, dtype=np.int32)
            self.values = np.zeros(n_arms, dtype=np.float)
        else:
            self.n_arms = self.counts.shape[0]
            self.counts = np.array(counts, dtype=np.int32)
            self.values = np.array(values, dtype=np.float)

    def select_arm(self):
        if np.random.uniform() > self.epsilon:
            return np.argmax(self.values)
        else:
            return np.random.randint(0, self.n_arms)

    def update(self, selected_arm, reward):
        self.counts[selected_arm] += 1
        n = self.counts[selected_arm]
        v = self.values[selected_arm]
        r = reward
        self.values[selected_arm] = float(v * n - v + r) / float(n)
        return self.values[selected_arm]

bernoulli_arm.py

報酬の発生メカニズムを自動化するために、ベルヌーイ分布にしたがって報酬を発生させます。

import numpy as np


class BernoulliArm:
    def __init__(self, p):
        self.p = p

    def draw(self):
        return np.random.binomial(1, self.p)

simulator.py

モンテカルロ・シミュレーションを行うためのクラスを作成します。

import numpy as np
from epsilon_greedy import EpsilonGreedy
from bernoulli_arm import BernoulliArm


class Simulator:
    def __init__(self, n_arms, Arm=BernoulliArm, means=None):
        if means is None:
            self.n_arms = n_arms
            self.means = [np.random.uniform(0, 1, n_arms)]
        else:
            self.means = np.array(means, dtype=np.float)
            self.n_arms = self.means.shape[0]
        self.arms = [Arm(p) for p in self.means.tolist()]

    def simulate(self, epsilon=0.5, n_sim=10, horizon=100, mult_epsilon=None):
        n_total = n_sim * horizon
        selected_arms = np.zeros(n_total, dtype=np.int32)
        rewards = np.zeros(n_total, dtype=np.float)
        cumulative_rewards = np.zeros(n_total, dtype=np.float)
        sim_nums = np.zeros(n_total, dtype=np.int32)
        times = np.zeros(n_total, dtype=np.int32)

        for i_sim in range(n_sim):
            if mult_epsilon is not None:
                mi = 0
                epsilon = mult_epsilon[mi]["epsilon"]
            bandit = EpsilonGreedy(self.n_arms, epsilon)
            for i_horizon in range(horizon):
                if mult_epsilon is not None and mult_epsilon[mi]["p"] is not None:
                    h_rate = float(i_horizon) / float(horizon)
                    if h_rate > mult_epsilon[mi]["p"]:
                        mi += 1
                        bandit.epsilon = mult_epsilon[mi]["epsilon"]
                index = i_sim * horizon + i_horizon
                sim_nums[index] = i_sim
                times[index] = i_horizon
                selected_arms[index] = bandit.select_arm()
                rewards[index] = self.arms[selected_arms[index]].draw()

                if i_horizon == 0:
                    cumulative_rewards[index] = rewards[index]
                else:
                    cumulative_rewards[index] = cumulative_rewards[
                        index - 1] + rewards[index]
                bandit.update(selected_arms[index], rewards[index])
        return {
            "selected_arms": selected_arms,
            "rewards": rewards,
            "cumulative_rewards": cumulative_rewards,
            "simulation_index": sim_nums,
            "times": times
        }

jupyter notebookで実行

In[1]:

%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
from simulator import Simulator

In[2]:

# それぞれのアームの報酬の発生確率とアームの数を設定
simulator = Simulator(n_arms=3, means=[0.1, 0.9, 0.1])

In[3]:

data1 = simulator.simulate(epsilon=0.1, n_sim=250, horizon=250)
data2 = simulator.simulate(epsilon=0.5, n_sim=250, horizon=250)
data3 = simulator.simulate(epsilon=0.9, n_sim=250, horizon=250)

In[4]:

plt.plot(np.mean(np.split(data1["cumulative_rewards"], 250), axis=0))
plt.plot(np.mean(np.split(data2["cumulative_rewards"], 250), axis=0))
plt.plot(np.mean(np.split(data3["cumulative_rewards"], 250), axis=0))
plt.legend(["epsilon=0.1","epsilon=0.5","epsilon=0.9"])

f:id:mathgeekjp:20190913160029p:plain

この時点で、探索と活用のトレードオフが発生していることがわかります。探索が多いほど、ベストな選択肢を見つけるのが早いため、早い段階で累積報酬が急激に増加します。しかし、活用が少ないので、長期的には活用を多く行っているシミュレーションのほうが高い利益が得られます。

そこで、「早い段階では探索を行い、徐々にepsilonを減らしていくことで活用を増やす。」という戦略を検証してみます。

In[5]:

m_eps = [
    {"epsilon": 0.9, "p": 0.05},
    {"epsilon": 0.5, "p": 0.1},
    {"epsilon": 0.1, "p": None}
]
data5 = simulator.simulate(mult_epsilon=m_eps, n_sim=250, horizon=250)

In[6]:

plt.plot(np.mean(np.split(data1["cumulative_rewards"], 250), axis=0))
plt.plot(np.mean(np.split(data2["cumulative_rewards"], 250), axis=0))
plt.plot(np.mean(np.split(data3["cumulative_rewards"], 250), axis=0))
plt.plot(np.mean(np.split(data5["cumulative_rewards"], 250), axis=0))
plt.legend(["epsilon=0.1","epsilon=0.5","epsilon=0.9", "mult"])

f:id:mathgeekjp:20190913160611p:plain

このように、epsilonを徐々に減らすことにより、累積報酬が最も高い戦略が得られました。

まとめ

  • バンディットアルゴリズムは、探索と活用によって選択肢を決定する。
  • 探索と活用にはトレードオフがある。
  • 最初の段階では探索を増やし、徐々に活用を増やすことによって、より良い戦略が得られる。

参考

https://www.amazon.com/Bandit-Algorithms-Website-Optimization-Developing/dp/1449341330