バンディットアルゴリズムによる最適化手法 4章

職場で開催中の「多腕バンディットアルゴリズム勉強会」の復習として実装してみた。オライリーのバンディットアルゴリズムによる最適化手法を参考にしたが、本のサンプルコードがあまりにも読みづらいので、写経のつもりが大幅な書き直しになった。

In [20]:

%matplotlib inline
import matplotlib.pylab as plt
from numpy import zeros, array, average, random as nprandom
import random

テスト実行と結果プロット用の処理¶

In [21]:

def test_algorithm(algo, arms, num_sims, horizon):
    chosen_arms = zeros((num_sims, horizon), dtype=int)  # 試行毎に選んだ腕
    rewards = zeros((num_sims, horizon))  # 試行毎に得られた報酬
    cumulative_rewards = zeros((num_sims, horizon))  # 累積報酬

    for sim in range(num_sims):
        algo.initialize(len(arms))
        for t in range(horizon):
            chosen_arm = algo.select_arm()
            chosen_arms[sim, t] = chosen_arm
            
            reward = arms[chosen_arm].draw()
            rewards[sim, t] = reward
            
            algo.update(chosen_arm, reward)
        cumulative_rewards[sim] = rewards[sim].cumsum()
    return chosen_arms, rewards, cumulative_rewards

In [22]:

def plot_results(simulate_num, horizon, best_arm, results):
    fig1, axes1 = plt.subplots(nrows=1, ncols=3, figsize=(11, 5))
    x = range(horizon)
    plot1, plot2, plot3 = axes1[0], axes1[1], axes1[2]
    
    for result in test_results:
        accuracy = zeros(horizon)
        reward_ave = zeros(horizon)
        cumulative_rewards = zeros(horizon)

        epsilon = result[0]
        chosen_arms_mat = result[1]
        rewards_mat = result[2]
        cumulative_rewards_mat = result[3]

        for i in xrange(horizon):
            best_arm_selected_count = len(filter(lambda choice: choice == best_arm, chosen_arms_mat[:,i]))
            accuracy[i] = best_arm_selected_count / float(simulate_num)
            reward_ave[i] = average(rewards_mat[:,i])
            cumulative_rewards[i] = average(cumulative_rewards_mat[:,i])

        plot1.plot(x, accuracy, label='%10.2f' % epsilon)
        plot2.plot(x, reward_ave, label='%10.2f' % epsilon)
        plot3.plot(x, cumulative_rewards, label='%10.2f' % epsilon)

    plot1.legend(loc=4)
    plot1.set_xlabel('Time')
    plot1.set_ylabel('Probability of Selecting Best Arm')
    plot1.set_title('Accuracy of the \nEpsilon Greedy Algorithm')

    plot2.legend(loc=4)
    plot2.set_xlabel('Time')
    plot2.set_ylabel('Average Reward')
    plot2.set_title('Performance of the \nEpsilon Greedy Algorithm')

    plot3.legend(loc=4)
    plot3.set_xlabel('Time')
    plot3.set_ylabel('Cumulative Reward of Chosen Arm')
    plot3.set_title('Cumulative Reward of the \nEpsilon Greedy Algorithm')

Epsilon-Greedyアルゴリズムの実装¶

In [23]:

class EpsilonGreedy(object):
    def __init__(self, epsilon):
        self.epsilon = epsilon # 探索する度合い
        self.counts = None
        self.values = None
        
    def initialize(self, n_arms):
        # 腕を何回引いたか
        self.counts = zeros(n_arms, dtype=int)
        # 引いた腕の報酬の平均値
        self.values = zeros(n_arms)
    
    def select_arm(self):
        """ 次に選択する腕のインデックスを返す """
        if self.epsilon > random.random():
            # epsilonの確率で探索を行なう
            return random.randrange(len(self.values))
        else:
            # それ以外は活用を行なう
            return self.values.argmax()
    
    def update(self, chosen_arm, reward):
        # 腕を選んだ回数をインクリメント
        self.counts[chosen_arm] += 1
        n = self.counts[chosen_arm]
        
        # 腕の平均報酬額を更新
        value = self.values[chosen_arm]
        new_value = ((n-1)/float(n)) * value + (1/float(n)) * reward
        self.values[chosen_arm] = new_value

腕の実装¶

In [24]:

class BernoulliArm():
    """ ベルヌーイ分布に基づいて報酬を返す腕 """
    def __init__(self, p):
        self.p = p
        
    def draw(self):
        # 確率pで1.0を返す
        return 1.0 if self.p > random.random() else 0.0

実行¶

In [25]:

SIMULATE_NUM = 5000
HORIZON = 250

means = [0.1, 0.1, 0.1, 0.1, 0.9]
random.shuffle(means)
arms = map(lambda mu: BernoulliArm(mu), means)
best_arm = array(means).argmax()

test_results = []
for epsilon in [0.1, 0.2, 0.3, 0.4, 0.5]:
    algo = EpsilonGreedy(epsilon)
    chosen_arms_mat, rewards_mat, cumulative_rewards_mat = test_algorithm(algo, arms, SIMULATE_NUM, HORIZON)
    test_results.append([epsilon, chosen_arms_mat, rewards_mat, cumulative_rewards_mat])
plot_results(SIMULATE_NUM, HORIZON, best_arm, test_results)

練習問題¶

In [26]:

# 腕を200本にした場合
SIMULATE_NUM = 5000
HORIZON = 250

means = nprandom.rand(200)
random.shuffle(means)
arms = map(lambda mu: BernoulliArm(mu), means)
best_arm = array(means).argmax()

test_results = []

for epsilon in [0.1, 0.2, 0.3, 0.4, 0.5]:
    algo = EpsilonGreedy(epsilon)
    chosen_arms_mat, rewards_mat, cumulative_rewards_mat = test_algorithm(algo, arms, SIMULATE_NUM, HORIZON)
    test_results.append([epsilon, chosen_arms_mat, rewards_mat, cumulative_rewards_mat])
plot_results(SIMULATE_NUM, HORIZON, best_arm, test_results)

現段階ではまだ簡単な問題設定でしかない。これが腕が増減したり、同じ腕でも得られる報酬が変化するようなパターンだとどうなるのかが気になる。