MAB (Multi-Armed Bandit) 설명과 코드

해당 내용은 Richard Sutton과 Barto Andrew의 Reinforcement Learning: An Introduction의 내용을 토대로 공부한 내용이다.  

이공계는 대부분 원서로 공부하기도 하고 굳이 번역하기는 귀찮아서 거의 다 그냥 원문 그대로 적었다.  

 

 

Every step, take an action that has maximum expected value, which is called $greedy$ action.
By exploiting, select greedy action, and by exploring select an non-greedy action.

 

Let $q_(a)$ be the true (actual) value of action $a$.
Denote $Q_t (a)$ be the estimated value on the $t$ th step.

The $t$ th time step action $a$ has been chosen $N_t (a)$ times prior to $t$,
yielding rewards $R1, R2, ..., R_{N_t (a)}$,  

 

then its value is estimated to be

$Q_t (a)$ = $\frac{R1 + R2 + ... + R_{N_t (a) }}{N_t (a)}$

If $N_t (a) = 0 $, then we define $Q_1 (a) = 0$.

As $N_t (a) \to \infty$, by the law of large numbers, $Q_t (a)$ converges to $q(a)$.  

 

The highest greedy action ${A_t}^{*}$ can be obtained by  

$Q_t ({A_t}^{*}) = \operatorname{max}_a Q_t (a)$.

 

Therefore, $A_t = \underset{a}{\operatorname{argmax}} Q_t (a)$.

 

Recursive Form of $Q_t (a)$

$k$ th estimated reward $Q_k$ is the average of its first $k-1$ rewards.

 

consequentley,

$Q_{k+1}$ = $\frac{1}{k} \sum_{i=1}^{k} R_i$

 

= $ \frac{1}{k} ( R_k + \sum_{i=1}^{k-1} R_i )$
= $ \frac{1}{k} ( R_k + (k - 1){Q_k} + Q_k - Q_k )$
= $ \frac{1}{k} ( R_k + k{Q_k} - Q_k )$
= $ \frac{1}{k} ( R_k - Q_k )$

 

The update rule is as follows.

 

NewEstimate $\leftarrow$ OldEstimate + StepSize[Target - OldEstimate]

 

and [Target - OldEstimate] is an $\it{error}$ in the estimate.

 

 

아래에서는 MAB의 코드를 파이썬으로 구현한다.

하지만 MAB를 실제로 적용할 때는 가끔 다른 액션을 탐사해야 한다.

epsilon만큼의 확률로 탐사하여, 최적의 액션이 아닌 다른 선택을 하는 MAB의 코드는 아래와 같다.

 

import torch
import numpy as np

class EpsilonGreedyMAB:
    def __init__(self, n_actions, epsilon):
        self.n_actions = n_actions
        self.epsilon = epsilon
        self.q_values = torch.zeros(n_actions)  # 각 행동의 추정 보상
        self.action_counts = torch.zeros(n_actions)  # 각 행동의 선택 횟수

    def select_action(self):
        if np.random.rand() < self.epsilon:
            # 탐색: 무작위 행동 선택
            return np.random.randint(self.n_actions)
        else:
            # 활용: 가장 높은 추정 보상을 가진 행동 선택
            return torch.argmax(self.q_values).item()

    def update(self, action, reward):
        # 선택한 행동의 보상 업데이트
        self.action_counts[action] += 1
        # Q 값 업데이트, recursive form, (r_k - q_k) / k
        self.q_values[action] += (reward - self.q_values[action]) / self.action_counts[action]

 

MAB에서 흔히 action의 수를 슬롯머신의 수로 비유하고는 한다.

다음은 slot machine이 5개인 케이스다.  그리고 엡실론은 0.1이다.  

 

# 예시
n_actions = 5  # 행동의 수
epsilon = 0.1  # 탐색 확률
mab = EpsilonGreedyMAB(n_actions, epsilon)

# 시뮬레이션
n_steps = 1000
rewards = np.random.rand(n_steps, n_actions)  # 각 행동의 보상 시뮬레이션

for step in range(n_steps):
    action = mab.select_action()
    reward = rewards[step, action]  # 선택한 행동의 보상
    mab.update(action, reward)

print(f"Rewards of actions for each time step:: {rewards}")
print("추정된 Q 값:", mab.q_values)
print("각 행동의 선택 횟수:", mab.action_counts)

>>
Rewards of actions for each time step:: [[0.23396093 0.39176933 0.47828123 0.08659093 0.68558934]
 [0.56971491 0.77114928 0.12942449 0.50244322 0.57781646]
 [0.73496188 0.29391943 0.79205529 0.54720967 0.05186339]
 ...
 [0.44686328 0.35942159 0.57614481 0.00148395 0.95739789]
 [0.07829514 0.65808864 0.95272359 0.73708321 0.35371674]
 [0.90348422 0.08491202 0.94967534 0.71058641 0.09573027]]
추정된 Q 값: tensor([0.4812, 0.4991, 0.4014, 0.5164, 0.4670])
각 행동의 선택 횟수: tensor([168.,  23.,  16., 739.,  54.])