상한 신뢰구간 기반 행동 선택 (Upper Confidence Bound Action Selection)

📘 2.7 상한 신뢰구간 기반 행동 선택 (Upper Confidence Bound Action Selection)

✅ 1. 탐험이라는 문제는 끝나지 않았다

---

지금까지 우리는 ε-greedy와 낙관적 초기값이라는 두 가지 방식으로 강화학습에서의 ‘탐험 문제’를 다루어 왔습니다.
ε-greedy는 일정 확률로 무작위 행동을 고르고, 낙관적 초기값은 Q값을 일부러 높게 시작해서 실망을 유도함으로써 간접적으로 모든 행동을 탐험하게 했습니다.

하지만 이들 방식에는 한 가지 근본적인 한계가 있었습니다.

"무작위로 고르거나, 실망을 유도하는 방식은 탐험의 타당성 여부를 판단하지 않는다."

이런 질문을 수학적으로 정의해낸 방식이 바로 UCB(Upper Confidence Bound)입니다.

✅ 2. 평균이 낮아도, 가능성은 클 수 있다

---

Q값이 낮다고 해서 그 행동이 나쁜 것일까요?
아닙니다. 아직 시도 횟수가 너무 적어서 제대로 평가되지 않았을 수도 있습니다.
UCB는 바로 그 점에서 출발합니다. “아직 확실히 알 수 없는 행동은 낙관적으로 보정해서 선택하자.”

반응형

 

✅ 3. UCB 수식의 전체 구조

---

UCB는 다음 수식을 기준으로 행동을 선택합니다:

$$ A_t = \arg\max_a \left[ Q_t(a) + c \cdot \sqrt{\frac{\ln t}{N_t(a)}} \right] $$

이 수식은 다음과 같은 두 부분으로 구성됩니다:

• $Q_t(a)$: 현재까지 행동 a의 평균 보상
• $\sqrt{\frac{\ln t}{N_t(a)}}$: 정보 부족에 대한 보정

여기서 $c$는 그 보정을 얼마나 낙관적으로 반영할 것인지 결정하는 상수입니다.

✅ 4. 각 항의 의미 ― 수식 안에 숨겨진 철학

---

$Q_t(a)$: 지금까지 좋았던 행동
→ 평균 보상. 높을수록 좋음

$N_t(a)$: 행동 a를 해본 횟수
→ 작을수록 정보 부족. 분모에 들어가므로 값이 작으면 보정 항이 커짐

$\ln t$: 전체 시간 step의 로그
→ 시간이 흐를수록 탐험을 조금씩 줄이되, 갑작스럽게 줄이면 안 됨 → 로그 사용

$\sqrt{\cdot}$: 보정이 과도하게 커지는 걸 막음
→ Hoeffding 불평등 기반 신뢰구간 구조 반영

$c$: 탐험 강도 조절
→ 클수록 낙관적, 작을수록 현실적 → $c=0$이면 greedy 정책, $c>0$일수록 더 많이 탐험함

✅ 5. 수치 예시로 직접 계산해보자

---

현재 $t = 100$, $c = 2$일 때 다음과 같은 상황을 가정합니다:

행동	Q값	N값
A	1.2	50
B	1.0	5
C	0.8	1

계산 결과:

• A: 1.2 + 2 × √(4.6 / 50) ≈ 1.81
• B: 1.0 + 2 × √(4.6 / 5) ≈ 2.92
• C: 0.8 + 2 × √(4.6 / 1) ≈ 5.10

→ C는 평균 보상은 낮지만 거의 해보지 않았기 때문에 가장 높은 UCB 값을 갖습니다.

반응형

 

✅ 6. 실험 결과: ε-greedy와의 성능 비교

---

책의 Figure 2.4에서는 다음 실험이 수행됩니다:
- 환경: 10-armed bandit - 방식: - ε-greedy (ε = 0.1) - UCB (c = 2)

초반 100 step까지는 ε-greedy가 앞서지만,
200 step 이후부터는 UCB가 더 빠르게 최적 행동에 수렴합니다.
→ 최적 행동 선택률 90% 이상, 평균 보상도 지속적으로 더 높음

✅ 7. 한계: 비정상성 환경에선 취약하다

---

UCB는 과거 시도를 기준으로 보정을 합니다.
→ 하지만 환경이 바뀐다면 그 정보는 오히려 독이 됩니다.

예를 들어 행동 A가 초반에는 좋지 않았지만, 나중에 최적이 되었다고 합시다.
→ 이미 $N_t(a)$가 크기 때문에 다시 시도될 가능성이 매우 낮아집니다.
→ ε-greedy는 무작위 탐험이 지속되므로 이런 경우에도 다시 탐험할 수 있음

✅ 8. 철학적 해석 ― UCB는 낙관적 무지를 활용한다

---

UCB는 “확신할 수 없으면 낙관적으로 가정하자”는 전략입니다.
무작위가 아니라, **정보가 부족한 곳에 기회를 주는 수학적 정의**입니다.

이는 인간의 의사결정과도 유사합니다.
“아직 안 해봐서 잘 모르지만, 가능성이 있다면 시도해본다”는 심리적 탐색 행동.
→ UCB는 그 탐색을 **수식으로 실현한 방식**입니다.