ε-Greedy부터 Thompson Sampling까지: 탐색 알고리즘

매일 점심시간이면 비슷한 고민에 빠진다. "어제 갔던 맛집에 또 갈까, 아니면 새로운 데 한 번 시도해볼까?"

이 단순한 고민은 사실 강화학습의 핵심 딜레마와 정확히 일치한다. 바로 Exploration(탐색) vs Exploitation(활용).

• Exploitation은 지금까지의 경험으로 가장 좋은 선택을 반복하는 전략이다.
  → "내가 잘 아는 그 집, 무조건 맛있으니까 또 가자!"
• Exploration은 새로운 선택지를 시도해서 더 나은 가능성을 찾는 전략이다.
  → "모르긴 해도 저 골목 새로 생긴 집, 혹시 대박일지도?"

현실에서도, AI 시스템에서도, 이 두 전략의 균형은 결과의 질을 결정짓는 핵심 요소다. 이런 선택의 균형을 다루는 Multi-Armed Bandit 문제를 시작으로, ε-Greedy, UCB, Thompson Sampling 같은 대표적인 알고리즘들을 하나씩 정리해본다.

탐색을 위한 대표적인 방법론들은 아래와 같은게 있다.

---

1. Exploration vs Exploitation

• Exploitation: 현재까지의 경험상 가장 좋은 선택을 반복. → 수익 극대화
  • 예: 단골 식당만 계속 감.
• Exploration: 아직 덜 시도한 선택지를 탐색. → 미래 수익 가능성 확보
  • 예: 새로운 식당을 시도함.

2. Multi-Armed Bandit (MAB)

• 슬롯머신(arm)마다 보상이 다르고 확률도 모름.
• 매 시점에 한 개의 arm을 선택해야 함.
• 목표는 전체 시간에 걸쳐 보상 합계 (cumulative reward) 를 최대화.

3. Regret

• 만약 항상 최적의 행동만 했다면 얻었을 이론적 보상과의 차이.
• 즉, 기회 손실(opportunity loss)

• Regret 최소화 ↔ 보상 극대화

---

방법론들이 잘 동작했는지 평가하는 기준

Regret 

• 가장 전통적인 평가 지표
• Regret = 최적 행동과의 차이 누적 손실
• Regret이 작을수록 → 탐색/활용 전략이 잘 작동한 것

Cumulative Reward (누적 보상)

• 반대로, 지금까지 받은 보상의 합이 높을수록 전략이 좋다고 평가
• Regret 최소화 ≡ Cumulative reward 최대화

Convergence Speed (수렴 속도)

• 얼마나 빨리 좋은 선택(혹은 최적 행동)에 수렴했는가?
• 특히 현실에서는 빠르게 좋은 결과를 내는 탐색 전략이 중요

---

ε-Greedy Algorithm

• 대부분은 가장 좋은 행동(exploitation)
• 가끔은 랜덤 행동(exploration)

→ 단순하면서도 효과적인 탐사-활용 균형 전략.

Optimistic Initialization 

• 초기 Q값을 실제보다 높게 잡는다.
  • 예: Q(a) = 100 (보상 기대치가 원래 10인데도)
• 그러면 agent는 실제 보상이 낮다는 것을 확인할 때까지 그 행동을 계속해서 시도해보게 됨.

효과

• 처음에는 대부분의 행동들이 Q값이 매우 높게 설정되어 있기 때문에, agent는 자연스럽게 모든 행동을 시도해보게 돼.
• 이후에는 관찰된 reward에 의해 Q값이 현실적인 수치로 수렴하면서 exploitation로 전환됨.

처음에 모든 행동의 Q값을 매우 높게 설정 → 자연스럽게 exploration 유도

Optimism in the Face of Uncertainty 

• 기존에 Q값 평균이 높지 않더라도, 불확실성(분산)이 큰 행동은 실제로 더 좋은 결과를 줄 가능성이 있음.
• 따라서, "확신은 없지만 잘될지도 모르는" 행동을 우선 시도해보자는 전략.
• 이는 탐색(Exploration)을 좀 더 "스마트하게" 하는 방식.

x축 (Q): 각 행동의 Q값 (기대 보상) y축 (p(Q)): 해당 Q값에 대한 확률 밀도 (불확실성) 각각의 곡선은 어떤 행동 a₁, a₂, a₃에 대해 우리가 생각하는 Q값의 분포를 나타냄

• 단순히 Q값만 보는 게 아니라 Q값의 분포(불확실성)까지 고려해 탐색
• 확신은 없지만 가능성이 있는 선택을 우선적으로 탐색
• 결국 정보 수집과 장기적 보상 극대화를 동시에 노리는 전략

파랑색그래프

• 평균은 낮지만 분산이 큼 → 아직 충분히 탐색되지 않음 (exploration 후보!)
• 정보를 더 수집할 수 있고, 결과적으로 장기적으로 regret을 줄이는 데 도움이 된다

UCB는 “나는 잘 모르니 몇 번 더 시도해볼게”라는 전략이고,
Thompson Sampling은 “혹시 얘가 잘 될지도 모르니까 한 번 해볼게”라는 확률적 직감

Upper Confidence Bound (UCB)

• 탐색 보너스를 더한 Q값을 기반으로 행동 선택
• 덜 시도된 행동일수록 보너스가 커져서 자연스럽게 탐색하게 됨

Thompson Sampling

• 각 행동마다 자신만의 보상 분포(Posterior)를 가정
• 그 분포에서 샘플링된 리워드를 기반으로 행동 선택

절차 요약

1. 각 행동의 보상 분포를 Bayesian 방식으로 업데이트 (예: Beta 분포, Gaussian 분포)
2. Posterior 분포에서 하나씩 샘플링
3. 가장 높은 샘플을 뽑은 행동 선택