N-슬롯 머신 문제

IT 위키

n-슬롯 머신 문제(n-armed bandit problem)은 강화학습에서 탐색(exploration)과 이용(exploitation)의 균형을 설명하기 위한 확률적 결정 문제로, 에이전트가 n개의 선택지 중에서 반복적으로 선택을 하며 최대 보상을 얻기 위한 전략을 학습하는 과제를 의미한다.

1 개요[편집 | 원본 편집]

n-슬롯 머신 문제는 카지노의 슬롯 머신을 확장한 개념으로, 각 슬롯 머신(팔 하나짜리 도둑, bandit)은 고유의 확률 분포에 따라 보상을 제공한다. 에이전트는 여러 번의 선택을 통해 어떤 슬롯이 높은 보상을 주는지 추정하고, 이를 바탕으로 총 보상을 최대화해야 한다.

이 문제는 비정적 환경에서도 적용 가능하며, 온라인 광고, 의료 임상시험 설계, 추천 시스템 등 다양한 실세계 문제에 활용된다.

2 문제 정의[편집 | 원본 편집]

n개의 행동(슬롯) 중 하나를 매 시간 선택하며, 각 행동은 고유의 확률 분포를 따라 보상을 발생시킨다. 에이전트의 목표는 시간이 충분히 지났을 때까지의 누적 보상의 평균을 최대화하는 것이다.

3 주요 해결 방법[편집 | 원본 편집]

  • ε-탐욕(ε-greedy) 방법
  • 소프트맥스(Softmax) 선택
  • 상한신뢰구간(Upper Confidence Bound, UCB)
  • 톰슨 샘플링(Thompson Sampling)
  • 베이지안 밴딧(Bayesian Bandit)

4 탐색 대 이용[편집 | 원본 편집]

이 문제는 탐색과 이용의 균형이라는 강화학습의 핵심 주제를 잘 설명해준다. 새로운 행동을 시도(탐색)해야 최적의 행동을 찾을 수 있지만, 현재까지 보상이 높았던 행동을 반복(이용)해야 보상을 극대화할 수 있다. 이 균형을 어떻게 조절하느냐가 성능에 큰 영향을 미친다.

5 예제 코드[편집 | 원본 편집]

아래는 Python으로 구현한 간단한 ε-탐욕 기반 n-슬롯 머신 문제의 예제이다:

import numpy as np

class Bandit:
    def __init__(self, n):
        self.n = n
        self.probs = np.random.rand(n)

    def pull(self, i):
        return 1 if np.random.rand() < self.probs[i] else 0

class Agent:
    def __init__(self, n, epsilon):
        self.n = n
        self.epsilon = epsilon
        self.counts = np.zeros(n)
        self.values = np.zeros(n)

    def select_action(self):
        if np.random.rand() < self.epsilon:
            return np.random.randint(self.n)
        return np.argmax(self.values)

    def update(self, action, reward):
        self.counts[action] += 1
        alpha = 1 / self.counts[action]
        self.values[action] += alpha * (reward - self.values[action])

# 실행
n = 10
bandit = Bandit(n)
agent = Agent(n, epsilon=0.1)

for step in range(1000):
    action = agent.select_action()
    reward = bandit.pull(action)
    agent.update(action, reward)

print("Estimated values:", agent.values)
print("True probabilities:", bandit.probs)

6 확장 문제[편집 | 원본 편집]

  • 비정적 n-슬롯 머신 문제 (보상 확률이 시간에 따라 변함)
  • 컨텍스트 기반 슬롯 머신 (Contextual Bandit)
  • 연속 행동 공간을 가지는 문제 (Continuous Action Bandit)

7 응용 분야[편집 | 원본 편집]

  • 온라인 광고 선택
  • 뉴스 기사 및 제품 추천
  • A/B 테스트 최적화
  • 금융 포트폴리오 선택

8 같이 보기[편집 | 원본 편집]

9 참고 문헌[편집 | 원본 편집]

  • Sutton, R. S., & Barto, A. G. (2018). "Reinforcement Learning: An Introduction" (2nd ed.). MIT Press.
  • Lattimore, T., & Szepesvári, C. (2020). "Bandit Algorithms." Cambridge University Press.

10 각주[편집 | 원본 편집]