멀티 암드 밴딧

Multi-Armed Bandit

슬롯머신이 여러 개 있을 때
슬롯머신마다 "터지는" 비율이 다름
어떤 슬롯머신을 "당길" 것인가?
MAB 문제는 강화학습의 일종
상태 또는 문맥은 1가지
각 행동은 즉시 보상을 주며 다음 환경 상태에 영향을 주지 않음
여러 시점에 걸쳐 주어진 대안 중 하나를 반복 선택
목표는 전체 기간의 누적 보상을 최대화하는 것

여러 슬롯머신 중 하나를 선택하는 Multi-Armed Bandit 예시

슬롯머신 아이콘

탐색과 활용의 균형

탐색: 새로운 시도를 해보는 것
활용: 기존에 알려진 최선을 반복하는 것
탐색만 하는 전략:
- 모든 슬롯머신을 골고루 당겨본다
- 각 슬롯머신의 수익률을 가장 정확히 파악할 수 있음
- 돈은 모든 슬롯머신의 평균만큼만 벌 수 있음
활용만 하는 전략:
- 슬롯머신을 하나 정해서 무조건 그것만 당겨본다
- 다른 슬롯머신의 수익률은 알 수 없음
- 운 좋게 잘 터지는 슬롯머신을 고를 경우 대박, 그렇지 않으면 망함
강화학습에서는 탐색과 활용이 모두 보상이 따르는 행동이므로 탐색을 늘리면 그만큼 활용을 적게 하게 됨

MAB 문제의 활용

홈페이지/광고 디자인(홈페이지나 광고의 디자인을 무엇으로 할까?)
제품 추천(고객에게 어떤 제품을 추천할 것인가?)
약물 적용(환자에게 어떤 약을 적용할 것인가?)
기존에는 전문가 의견, A/B 테스트와 같은 방법 사용
A/B 테스트: 고객 또는 환자를 A군과 B군으로 나누어 다른 방법을 적용

MAB 환경

class MultiArmedBandit(gym.Env):
    def __init__(self, p_dist, r_dist):
        self.p_dist = np.array(p_dist)  # 확률
        self.r_dist = np.array(r_dist)  # 보상
        self.action_space = gym.spaces.Discrete(len(p_dist))  # 행동
        self.observation_space = gym.spaces.Discrete(1)  # 상태(1가지 밖에 없음)

    def step(self, action):
        p = self.p_dist[action]
        r = np.random.binomial(1, p) * self.r_dist[action]
        return 0, r, False, False, {}

후회 regret

강화학습의 목표: 가치(할인된 보상의 합)의 기댓값을 최대화
MAB는 한 행동이 이후 상태에 영향을 주지 않음 → 보상만 고려
후회(regret): 한 번의 행동의 기회비용

l_{t} = E [V_{*} (s_{t}) - Q (s_{t}, a_{t})]

전체(total) 후회: 에피소드 전체에서 후회의 합계

L_{T} = E [t = 1 \sum T V_{*} (s_{t}) - Q (s_{t}, a_{t})]

누적 보상의 최대화 = 전체 후회의 최소화

입실론 퍼스트 epsilon first method

일정 비율(ε, epsilon)만큼 탐색
이후로는 가장 가치가 높은 행동만 한다 (활용)
일상적으로 많이 하는 방법
예시:
- 슬롯머신을 각각 100번씩 당겨본 후, 그 후로는 가치가 가장 높은 슬롯머신만 당긴다
- 홈페이지 디자인 A안과 B안을 1만명의 고객에게 무작위로 보여준 후, 가치가 더 높은 디자인을 골라 모든 고객에게 보여준다

입실론 퍼스트

class EpsilonFirstAgent:
    def __init__(self, env, epsilon, n_episodes=1000):
        self.env = env
        self.epsilon = epsilon
        self.n_episodes = n_episodes
        self.Q = np.zeros(env.action_space.n)
        self.N = np.zeros(env.action_space.n, dtype=int)
        self.Q_history = np.empty((n_episodes, env.action_space.n))
        self.returns = np.empty(n_episodes)
        self.actions = np.empty(n_episodes, dtype=int)

입실론 퍼스트

def select_action(self, episode):
    n_explore = int(self.n_episodes * self.epsilon)
    if episode < n_explore:
        return self.env.action_space.sample()  # 탐색
    else:
        return np.argmax(self.Q)  # 활용

def update_estimates(self, action, reward):
    self.N[action] += 1
    self.Q[action] = self.Q[action] + (reward - self.Q[action]) / self.N[action]
    # 평균의 다른 계산법(뒷장에서 설명)

입실론 퍼스트

def run(self):
    for e in tqdm.trange(self.n_episodes):
        action = self.select_action(e)
        _, reward, done, _, _ = self.env.step(action)
        self.update_estimates(action, reward)
        self.Q_history[e] = self.Q
        self.returns[e] = reward
        self.actions[e] = action
        if done:
            self.env.reset()
    return self.returns, self.Q_history, self.actions

평균의 다른 계산법

일반적인 평균 계산법

v_{n} = \frac{R _{1} + R _{2} + \dots + R _{n}}{N}

강화학습에서 많이 사용하는 평균 계산법

self.Q[action] = self.Q[action] + (reward - self.Q[action]) / self.N[action]

v_{n} = v_{n - 1} + \frac{1}{n} (R_{n} - v_{n - 1})

합계를 구하지 않고 평균 구함
수학적으로는 동일하나 합계를 저장해둘 필요가 없는 장점
컴퓨터 계산 특성상 합계가 너무 커져서 생기는 overflow 등 문제를 피할 수 있음

평균 계산법의 해석

v_{n} = v_{n - 1} + \frac{1}{n} (R_{n} - v_{n - 1})

$v_{n - 1}$ : 기존의 가치
$R_{n}$ : 새로운 보상
새로운 보상 > 기존의 가치 → 가치를 UP
새로운 보상 < 기존의 가치 → 가치를 DOWN

입실론 퍼스트 실험

env = MultiArmedBandit(p_dist=[0.3, 0.1], r_dist=[0.1, 0.2])
agent = EpsilonFirstAgent(env, epsilon=0.1)
returns, Q_history, actions = agent.run()

시각화

100개씩 묶어 평균

def moving_average(x, window=100):
    return np.convolve(x, np.ones(window), 'valid') / window

시각화

import matplotlib.pyplot as plt

plt.plot(moving_average(returns), label='returns')
plt.plot(moving_average(actions), label='actions')
plt.legend()

입실론 퍼스트 실험의 returns와 actions 이동평균

행동 가치 추정치의 변화

plt.plot(Q_history[:, 0], label='0')
plt.plot(Q_history[:, 1], label='1')
plt.legend()

입실론 퍼스트 실험에서 행동 가치 추정치가 변하는 그래프

입실론 퍼스트의 문제점

충분히 탐색을 하지 못할 가능성
- 100번으로는 슬롯머신의 가치를 충분히 정확히 추정하기에 부족하다면?
시간에 따라 변화하는 상황에 대응하지 못함
- 여름에 실험한 결과는 겨울에 통하지 않는다면?

퀴즈

문제 1 / 9맞음: 0힌트: 0틀림: 0채점중: 0남음: 9

멀티 암드 밴딧(Multi-Armed Bandit)에 대한 설명으로 가장 알맞은 것은 무엇입니까?

○하나의 상태 또는 문맥에서 행동을 반복 선택하고 각 선택의 즉시 보상을 관찰하는 문제
○여러 상태를 전이하면서 각 행동의 장기적 결과를 추적하는 순차 제어 문제
○정답 라벨이 주어진 데이터로 각 행동의 보상을 미리 학습하는 지도학습 문제
○모든 행동의 보상을 동시에 관찰한 뒤 다음 행동을 선택하는 완전정보 문제

퀴즈를 풀려면 대화형 기능을 불러와야 합니다.

멀티 암드 밴딧(Multi-Armed Bandit)에 대한 설명으로 가장 알맞은 것은 무엇입니까?

같은 선택 상황이 반복되지만, 선택하지 않은 슬롯머신의 보상은 관찰할 수 없습니다.

하나의 상태 또는 문맥에서 행동을 반복 선택하고 각 선택의 즉시 보상을 관찰하는 문제여러 상태를 전이하면서 각 행동의 장기적 결과를 추적하는 순차 제어 문제정답 라벨이 주어진 데이터로 각 행동의 보상을 미리 학습하는 지도학습 문제모든 행동의 보상을 동시에 관찰한 뒤 다음 행동을 선택하는 완전정보 문제

하나의 상태 또는 문맥에서 행동을 반복 선택하고 각 선택의 즉시 보상을 관찰하는 문제

탐색과 활용에 대한 설명으로 올바른 것을 모두 고르세요.

탐색은 정보 획득에, 활용은 현재 추정치에 따른 보상 획득에 초점을 둡니다.

탐색은 새로운 시도를 해보는 것이다활용은 현재 가치가 가장 높다고 추정한 행동을 선택하는 것이다한 시점에서 탐색을 선택하면 그 시점에는 활용을 포기하게 된다활용만 반복해도 선택하지 않은 행동의 가치를 정확히 추정할 수 있다

탐색은 새로운 시도를 해보는 것이다, 활용은 현재 가치가 가장 높다고 추정한 행동을 선택하는 것이다, 한 시점에서 탐색을 선택하면 그 시점에는 활용을 포기하게 된다

MAB로 다루는 문제에 기존부터 쓰이던 A/B 테스트에 대한 설명으로 알맞은 것은 무엇입니까?

두 방법의 성과를 공정하게 비교하려면 무엇을 갈라 놓아야 할지 생각해 보세요.

고객이나 환자를 A군과 B군으로 나누어 서로 다른 방법을 적용한다한 고객에게 A안을 보여준 뒤 같은 고객에게 B안을 다시 보여준다고객이 올 때마다 지금까지 성과가 가장 좋은 안을 골라 보여준다전문가가 A안과 B안 중 더 나을 것으로 판단한 안을 모두에게 적용한다

고객이나 환자를 A군과 B군으로 나누어 서로 다른 방법을 적용한다

한 시점의 후회(regret)를 가장 잘 설명한 것은 무엇입니까?

실제로 고른 행동을 그 시점에 고를 수 있었던 최선의 행동과 비교해 보세요.

최적 행동의 기대 보상과 실제 선택한 행동의 기대 보상 차이선택한 행동의 관측 보상과 현재 가치 추정치의 차이현재 행동의 최대 가치 추정치와 최소 가치 추정치의 차이탐색으로 선택한 모든 행동에서 얻은 관측 보상의 합

최적 행동의 기대 보상과 실제 선택한 행동의 기대 보상 차이

전체 후회(total regret)와 누적 보상의 관계로 알맞은 것은 무엇입니까?

매 시점 최선의 행동을 했다면 받을 수 있었던 보상의 총합은 정해져 있습니다. 실제로 받은 보상이 늘어나면 그 차이는 어떻게 될까요?

누적 보상을 최대화하는 것은 전체 후회를 최소화하는 것과 같다누적 보상을 최대화하는 것은 전체 후회를 최대화하는 것과 같다전체 후회는 누적 보상과 무관하게 탐색 횟수만으로 결정된다전체 후회는 각 시점에서 실제로 받은 보상을 모두 더한 값이다

누적 보상을 최대화하는 것은 전체 후회를 최소화하는 것과 같다

입실론 퍼스트 방법의 핵심은 무엇입니까?

전체 실행 기간을 탐색 구간과 활용 구간으로 나누는 전략입니다.

일정 비율만큼 먼저 탐색한 뒤 이후로는 가장 가치가 높은 행동만 한다매 선택마다 일정한 확률로 탐색하고 나머지에는 가장 가치가 높은 행동을 선택한다초기에는 탐색을 많이 하고 시간이 지날수록 탐색 확률을 서서히 줄인다각 행동의 초기 가치를 높게 설정하고 가장 가치가 높은 행동만 선택한다

일정 비율만큼 먼저 탐색한 뒤 이후로는 가장 가치가 높은 행동만 한다

증분 평균식을 사용하는 주된 계산상 장점은 무엇입니까?

업데이트식에 필요한 값과 별도로 저장하지 않아도 되는 값을 구분해 보세요.

이전 평균과 새 보상, 관측 횟수만으로 새 평균을 계산할 수 있다새 보상에 항상 같은 고정 가중치를 주어 최근 변화에 빠르게 대응한다관측 횟수 없이 마지막 보상만으로 전체 보상의 평균을 계산할 수 있다누적 보상 합계만 저장하면 관측 횟수 없이 평균을 계산할 수 있다

이전 평균과 새 보상, 관측 횟수만으로 새 평균을 계산할 수 있다

행동의 성공 확률이 0.3이고 성공했을 때 보상이 0.1이라면 이 행동의 기대 보상은 얼마입니까?

성공하면 0.1, 실패하면 0을 받으므로 각 보상에 발생 확률을 곱해 더합니다.

0.03

입실론 퍼스트의 문제점으로 지적된 것을 모두 고르세요.

탐색을 앞쪽에 한 번 몰아서 끝낸다는 점이 추정의 정확도와 시간에 따른 변화 각각에 어떤 부담을 주는지 생각해 보세요.

탐색 구간이 짧으면 각 행동의 가치를 충분히 정확하게 추정하지 못할 수 있다탐색을 끝낸 뒤에 상황이 달라지면 바뀐 환경에 대응하지 못한다탐색 구간에도 가치가 가장 높은 행동만 선택하므로 새로운 정보를 얻지 못한다활용 구간에서도 매번 무작위로 행동을 선택하므로 누적 보상이 낮아진다

탐색 구간이 짧으면 각 행동의 가치를 충분히 정확하게 추정하지 못할 수 있다, 탐색을 끝낸 뒤에 상황이 달라지면 바뀐 환경에 대응하지 못한다