[RL] Lecture 9: Exploration and Exploitation by David Silver

| 강의 목표

• 강화학습에서 탐험과 이용의 딜레마를 이해한다.
• 다양한 알고리즘(ε-greedy, UCB, Thompson Sampling 등)을 통해
  장기 보상 극대화를 위한 전략을 학습한다.
• Multi-Armed Bandits, Contextual Bandits, MDP 각각에서의 적용 방식을 살펴본다.

---

| 개요: Exploration vs. Exploitation

선택	의미
Exploitation	지금까지 얻은 정보로 가장 좋은 선택 수행
Exploration	새로운 선택을 시도하여 정보 수집

원칙들

• Naive Exploration: ε-greedy 등 무작위 탐험
• Optimistic Initialisation: 초기 값을 높게 설정
• Upper Confidence Bound (UCB): 불확실성 높은 행동 선호
• Probability Matching: 최적 행동일 확률에 따라 선택
• Information State Search: 정보가치 기반 탐색

---

| Multi-Armed Bandits (MAB)

정의

• A: m개의 행동(arm)
• Ra: 행동 a의 보상 분포 (모름)
• 목표: 누적 보상 최대화

Regret

• 최적 행동 a*의 기대 보상: $Q(a^*)$
• 시간 t까지의 후회(regret):

---

| MAB 탐험 알고리즘들

Greedy & ε-Greedy

• Greedy: 현재 추정 Q값이 가장 높은 행동 선택 → 빠르게 수렴하지만 최적 행동을 놓칠 수 있음
• ε-Greedy: 확률 ε로 랜덤 선택

성능

• 탐험을 안 하면 후회는 선형
• 무조건 탐험만 해도 후회는 선형
  → 좋은 전략: Sublinear Regret

Optimistic Initialisation

• 모든 Q값을 높게 초기화
  → 자연스럽게 덜 시도한 행동을 선택
  → 하지만 여전히 선형 후회 발생 가능

Decaying ε-Greedy

• ε 값을 시간에 따라 점차 감소시키기
• εₜ = min(1, c / (d²t))
  → 이론적으로 logarithmic regret 가능
  → 단, gap Δa를 알아야 함

---

| Upper Confidence Bound (UCB)

"불확실성에 대해 낙관적으로 행동하라" – Optimism in the Face of Uncertainty

• UCB1 알고리즘:

• 잘 모르는 행동일수록 UCB가 큼 → 적극적 탐험
• logarithmic regret 달성 보장

---

| Bayesian Bandits

베이즈적 접근

• 보상 분포에 사전 분포를 둠: $p[R]$
• 관측된 데이터 $h_t$에 따라 후분포 계산: $p[R|h_t]$

Thompson Sampling

• 확률적 매칭 구현
• 매 step마다 보상 분포 $R$를 샘플링하고,
  그에 따라 $\arg\max Q(a)$를 선택

→ Lai & Robbins 하한을 달성하는 강력한 성능

---

| Information State Search (Bandit)

정보 상태란?

• 기존 밴딧은 단순한 1-step 문제
• 정보를 요약하는 상태 $\tilde{s}_t = f(h_t)$ 를 정의하면
  전체를 MDP로 확장 가능

Bayes-Adaptive MDP

• 상태: 〈α, β〉 = 각각 성공/실패 횟수

• 예: Drug Test

  • Drug 1: 성공 1 / 실패 2
  • Drug 2: 성공 2 / 실패 1

→ 각 상태 전이는 Beta 분포 업데이트와 동일

---

| Contextual Bandits

정의

• 각 step마다 환경이 상태 $s$를 생성
• 행동 $a$를 선택하면 보상 $r$을 받음
  → 상태에 따라 최적 행동이 달라짐

Linear UCB

• Q함수를 선형 근사: $Q_\theta(s,a) = \phi(s,a)^T \theta$
• 신뢰 구간: $\text{UCB} = Q + c \sqrt{ \phi^T A^{-1} \phi }$
• 최종 행동:

---

| MDP에서의 탐험 전략

적용 원칙

• 탐험 전략은 Bandit 환경뿐만 아니라 MDP에도 동일하게 적용 가능

주요 방법들

기법	설명
ε-Greedy	Sarsa, Q-learning 등에서 사용
Optimistic Initialisation	Q(s,a) = r_max / (1 - γ) 로 시작
UCB for MDP	Q + Uncertainty 보상
Thompson Sampling	전체 MDP를 샘플링하고 그 위에서 Q* 계산
Bayes-Adaptive MDP	후분포 기반 강화학습 수행

Bayes-Adaptive MDP

• 상태: $\langle s, \tilde{s} \rangle$
• $\tilde{s}$: 히스토리로부터 계산된 모델 사후분포
  → 최적의 탐험-이용 전략을 찾을 수 있지만 계산량 큼

→ 최근에는 샘플 기반 탐색(Guez et al.) 으로 해결

---

| 정리

환경	전략	장점
Bandits	ε-Greedy, UCB, Thompson	탐험 원리 정립
Contextual Bandits	Linear UCB	상황 기반 행동 선택
MDP	Optimistic Init., UCB, TS	정책 탐험 개선
Bayesian	Thompson Sampling	uncertainty에 기반한 전략