2. Multi-armed Bandits

k = 10
n_run = 2000
n_time = 1000
epsilons = [0, 0.1, 0.01]
bandits = [Bandit(k=k, epsilon=eps, sample_average=True) for eps in epsilons]
rewards, best_action_counts, best_actions = simulate(n_run, n_time, bandits, rt_raw=True)

cols = [f'$\epsilon={eps:.2f}$' for eps in epsilons]
fig, ax = plt.subplots(1, 1, figsize=(8, 4), dpi=1200)
sns.histplot(
    data=pd.DataFrame(best_actions.T, columns=cols), 
    bins=10, common_bins=True, discrete=True, multiple='fill', ax=ax)
ax.set_xticks(np.arange(k))
ax.set_xticklabels([f'{i}' for i in range(k)])
ax.set_ylabel('Percentage of best action')
ax.set_xlabel('Actions')
plt.show() 

fig, axes = plt.subplots(1, 2, figsize=(16, 4), dpi=1200)
ax1, ax2 = axes
sns.lineplot(data=pd.DataFrame(rewards.T, columns=cols), dashes=False, ax=ax1)
sns.lineplot(data=pd.DataFrame(best_action_counts.T, columns=cols), dashes=False, ax=ax2)
ax1.set_xlabel('Steps')
ax1.set_ylabel('Average reward')
ax2.set_xlabel('Steps')
ax2.set_ylabel('Percentage of Optimal action')
ax1.legend()
ax2.legend()
plt.tight_layout()
plt.show()

class Bandit:
    def __init__(
            self,
            k: int=10, 
            epsilon: float=0.0, 
            initial: float=0.0, 
            true_reward: float=0.0, 
            step_size: float=0.1, 
            sample_average: bool=False,
            ucb_param: float|None=None,
            gradient: bool=False,
            gradient_baseline: bool=False,
        ):
        self.k = k
        self.actions = np.arange(self.k)
        self.epsilon = epsilon
        self.initial = initial
        self.true_reward = true_reward
        self.step_size = step_size
        self.average_reward = 0.0

        self.sample_average = sample_average
        self.ucb_param = ucb_param
        self.gradient = gradient
        self.gradient_baseline = gradient_baseline

    def reset(self):
        # real reward for each action at time t
        self.q_true = np.random.randn(self.k) + self.true_reward

        # estimation for each action at time t
        self.q_estimation = np.zeros(self.k) + self.initial

        # # of chosen times for each action
        self.action_count = np.zeros(self.k)
        self.best_action = np.argmax(self.q_true)

        self.time = 0

    def act(self):
        if np.random.rand() < self.epsilon:
            return np.random.choice(self.actions)
        
        q_best = np.max(self.q_estimation)
        return np.random.choice(np.where(self.q_estimation == q_best)[0])
    
    def step(self, action):
        # give reward at time t by choosing action
        reward = np.random.randn() + self.q_true[action]
        # update records
        self.time += 1
        self.action_count[action] += 1
        self.average_reward += (reward - self.average_reward) / self.time
        
        if self.sample_average:
            # update estimation using sample averages
            self.q_estimation[action] += (reward - self.q_estimation[action]) / self.action_count[action]
        else:
            # update estimation with constant step size
            self.q_estimation[action] += self.step_size * (reward - self.q_estimation[action])
        
        return reward

def simulate(n_run: int, n_time: int, bandits: list[Bandit]):
    """Simulate multi-armed bandit experiment
    Args:
        n_run (int): number of run, each run means using a k-armed bandit with n_times
        n_time (int): number of time to experience for each bandit
        bandits (list[Bandit]): bandits list, each bandit has different experiment settings
    """
    rewards = np.zeros((len(bandits), n_run, n_time))
    best_action_counts = np.zeros(rewards.shape)
    best_actions = np.zeros((len(bandits), n_run))
    for i, bandit in enumerate(bandits):
        for r in tqdm(range(n_run), total=n_run, desc=f'Simulating Exp-{i}'):
            bandit.reset()  # reset bandit: the same bandit can be used for multiple runs
            best_actions[i, r] = bandit.best_action
            for t in range(n_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
                    
    mean_best_action_counts = best_action_counts.mean(axis=1)
    mean_rewards = rewards.mean(axis=1)
    return mean_rewards, mean_best_action_counts, best_actions

Figure: epsilon greedy 실험 결과 초깃값이 모두 동일($q_0(a) = 0.0$)할 때, greey policy는 평균적으로 $1$의 보상을 얻었다. $\epsilon$이 높을 수록 탐색 초기에는 보상이 높았으나, 시간이 점점 지날 수록 작은 $\epsilon$과 큰 $\epsilon$간의 간극이 줄어든 것을 볼 수 있다. 다만, 최적의 선택을 고른 비율에서는 탐색을 상대적으로 많이 하는 경우 경험을 많이 할 수록 더 높다는 것을 알 수 있다. 높은 $\epsilon$의 문제점은 최적의 선택이 어떤 것인지 대략 안 상황에서 계속해서 10% 확률로 다른 것을 탐색한 다는 것이다. 즉, 효율적이지 않다는 것이다.

행여나 실험에서 Best Action이 불균형하게 세팅될 수도 있다는 걱정이 있었는데, 각 실험 Bandit의 best action histogram을 그려보니, 모든 action이 거의 균등하게 세팅되어 있었다(3개 실험의 bar의 길이가 비슷비슷하다).

만약에 보상에 더 많은 노이즈(noise)가 있다고 하면, greedy 보다 $\epsilon$-greedy가 더 좋은 전략이 될 수 있을까? 물론 그렇다, 더 많은 탐색을 할 수록 더 높은 보상을 취할 수 있을 것이다. 이런 점이 탐색(exploration)을 **“학습한다”**라고 말하는 이유다. 그렇다면 determinsitic reward이면 어떻게 될까? 이때 최적의 전략은 각 action을 한 번씩 취한 다음에 greedy 전략으로 가는 것이다.