UCB(Upper Confidence Bound) 알고리즘 이해하기

UCB(Upper Confidence Bound) 알고리즘 이해하기

강화 학습과 멀티 암드 밴딧 문제에서 자주 등장하는 UCB(Upper Confidence Bound) 알고리즘은 탐색과 활용의 균형을 맞추는 데 중요한 역할을 한다. 특히, 보상을 최대화해야 하는 환경에서 효율적으로 동작하며, 불확실성을 고려한 의사 결정을 가능하게 한다.

 

UCB 알고리즘

UCB 알고리즘은 주어진 선택지 중 최적의 선택을 찾기 위해 설계되었다. 단순한 탐욕적(greedy) 방법과 달리, 이 알고리즘은 선택지가 충분히 탐색되지 않았을 가능성을 고려한다. 즉, 평균 보상이 높을 뿐만 아니라 신뢰 구간이 넓은 선택지를 좀 더 자주 선택하면서 최적의 행동을 찾아가는 방식이다.

 

이를 위해 UCB는 선택지의 평균 보상뿐만 아니라 선택된 횟수를 바탕으로 보상의 불확실성을 추정하는 보정 항을 추가한다. 이 보정 항은 선택된 횟수가 적을수록 더 커지며, 점차 선택 횟수가 증가하면 감소하는 특성을 가진다. 이를 통해 적절한 탐색과 활용의 균형을 맞출 수 있다.

 

UCB 알고리즘은 다음과 같은 수식을 따른다.

 

$$A_t = argmax_{i} ( \bar{X}_i + c \sqrt{\frac{\ln t}{N_i}})$$

 

• $A_t$ : t번째 스텝에서 선택할 행동
• $\bar{X}_i$ : 선택지 i의 현재까지의 평균 보상
• $c$ : 탐색을 조절하는 상수
• $N_i$ : 선택지 i가 선택된 횟수
• $t$ : 현재까지의 총 선택 횟수

 

이 수식을 보면, 평균 보상($\bar{X}_i$)과 탐색 보정 항($c \sqrt{\frac{\ln t}{N_i}}$)의 합이 가장 큰 선택지를 고르게 된다. 탐색 보정 항이 높으면 아직 충분히 선택되지 않은 옵션이 더 자주 선택되도록 유도된다.

 

UCB는 다음과 같은 이유로 널리 사용된다.

 

• 탐색과 활용의 균형: 신뢰 구간을 활용해 불확실성이 높은 선택지를 탐색하는 동시에, 보상이 높은 선택지를 빠르게 학습한다.
• 수학적 성질 보장: 이론적으로 최적 해에 가까운 수렴 속도를 보장할 수 있다.
• 단순한 구현: 비교적 간단한 수식으로 멀티 암드 밴딧 문제를 해결할 수 있다.

 

UCB와 다른 탐색 기법 비교

UCB는 그리디 방법, 입실론-그리디 방법과 비교될 수 있다. 그리디 방법은 현재까지의 평균 보상이 가장 높은 선택지만 고려하기 때문에 최적 해를 찾지 못할 가능성이 크다. 반면, 입실론-그리디 방법은 일정 확률로 무작위 탐색을 수행하지만, 이 확률을 적절하게 조정하지 않으면 비효율적인 탐색을 하거나 너무 빨리 활용으로 수렴하는 문제가 생긴다.

 

UCB는 신뢰 구간을 기반으로 한 탐색을 수행하기 때문에 탐색이 효율적이며, 지나친 무작위성 없이 선택을 조정할 수 있다는 장점이 있다.

 

이처럼 UCB 알고리즘은 멀티 암드 밴딧 문제를 해결하는 데 강력한 도구로 활용된다. 신뢰 구간을 활용해 탐색과 활용의 균형을 맞추는 방식은 실용적이며, 다양한 응용 사례에서 효과적으로 사용된다. 특히, 보상이 불확실한 환경에서 최적의 선택을 해야 하는 문제를 해결하는 데 강력한 방법론으로 자리 잡고 있다.