안녕하세요, 에디터 스더리입니다!

영화관에서 최애 장르를 볼지, 요즘 핫한 영화를 볼지. 이런 고민, 한 번쯤 해보신 적 있지 않나요? 인생은 선택의 연속이고, 우리는 익숙함과 새로움 사이에서 늘 망설입니다. 기업들도 마찬가지입니다. 클릭률이 높은 상품을 또 추천할지, 가능성 있는 신상품을 밀어볼지 선택해야만 하죠.

이런 고민은 사실 수학적으로 설명해볼 수 있는데요, 바로 MAB라고도 불리는 멀티 암 밴딧(Multi-Armed Bandit)입니다. 오늘은 Multi-Armed Bandit의 개념과 주요 알고리즘에 대해 살펴보도록 하겠습니다! 🧐

Multi-Armed Bandit?

Multi-Armed Bandit(MAB)은 원래 카지노 슬롯머신에서 유래한 개념입니다. 여러 개의 슬롯머신 중 어떤 것이 가장 높은 당첨 확률을 갖고 있는지 알 수 없는 상황에서, 각 머신을 하나씩 시도해 보며 보상을 최대화하는 전략을 세우는 문제입니다. 조금 더 일상적인 예시로 MAB에 대해 설명해보도록 하겠습니다.

ⓒ deep daiv. 

새로 이사한 동네에서 점심 식당을 고르는 상황을 떠올려봅시다. 어디가 맛집인지 모른 채 식당을 고르는 순간, 우리는 MAB 문제를 풀고 있는 셈입니다. 각 식당은 선택 가능한 Arm(선택지), 식사 후 만족도는 Reward(보상)로 정의합니다.

처음 갔던 식당이 생각보다 괜찮았을 때, 다음 날 우리는 고민하게 되죠. 어제 갔던 분식집을 또 갈까? 아니면 옆 포케 가게에 도전해볼까? 이때 우리가 하는 고민이 바로 활용(Exploitation) vs 탐색(Exploration), 즉 활용과 탐색의 트레이드오프입니다. 활용은 지금까지 가장 좋은 결과를 줬던 선택을 반복하는 전략입니다. 어제 분식집이 맛있었다면, 오늘도 같은 분식집을 가는 거죠. 이는 실패 확률이 낮고, 안정적인 보상을 기대할 수 있다는 점에서 매력적입니다.

반면, 탐색은 아직 잘 모르는 식당에 도전하는 전략입니다. 이번엔 실패할 수도 있지만, 어쩌면 지금까지 몰랐던 맛집을 발견하게 될지도 모릅니다. 즉, 불확실성을 감수하고 더 나은 보상을 찾기 위한 시도입니다. 하지만 활용만 고수하게 되면 더 좋은 식당을 찾을 기회를 놓치게 되고, 반대로 탐색만 반복하면 매번 새로운 시도에 만족하지 못하고 불안정한 결과만 얻게 될 수 있습니다.

모든 선택지의 평균 보상 분포를 미리 알고 있다면 항상 최고의 선택을 할 수 있겠죠? 하지만 현실에서는 그렇지 않기 때문에, 우리는 시행착오를 거치며 좋은 선택을 학습하게 됩니다. 여기서 Regret(후회)이라는 개념도 등장하는데요. 이때 생기는 비용 — 즉, 모든 것을 알았다면 얻었을 보상과 실제로 얻은 보상의 차이를 Regret이라고 합니다. 이를 수학적으로 나타내면 다음과 같습니다.

μ* (optimal)는 최적 Arm의 평균 보상을, μₐₜ (chosen)는 시간 t에 선택한 Arm의 평균 보상을 의미합니다.  이들의 차를 Regret, R(T)로 정의합니다. ⓒ deep daiv.

위 식의 Optimal 항, μ*는 가장 좋은 식당(Arm)의 평균 만족도(Reward), Chosen 항은 시간 t에 선택한 식당의 만족도입니다. 즉, R(T)는 항상 최고의 Arm만 골랐을 때의 얻을 수 있는 보상의 총합과 우리가 실제로 선택한 Arm들의 보상 총합의 차이를 의미합니다. MAB는 이처럼 탐색과 활용 사이의 균형을 조절하면서, 이 Regret을 최소화하려는 전략적 구조인 것이죠.

안정과 탐색 사이, Epsilon-Greedy 전략

가장 기본적인 전략은 'Greedy 전략'입니다. 위 예시로 설명하자면, 모든 식당을 한 번씩 가본 뒤 그중에서 가장 만족도가 높았던 식당에만 계속 가는 것입니다. 깊이 고민하지 않아도 우리는 이 전략에 치명적인 단점이 있다는 것을 알 수 있습니다. 모든 식당을 한 번밖에 가지 않고 판단하는 것이기 때문인데요. 어떤 식당은 첫 방문에서 덜 만족스러운 경험을 했지만, 사실은 가장 맛있는 식당일 수도 있습니다. 즉, Greedy 전략은 탐색이 충분히 이루어지지 않기 때문에 장기적으로는 더 큰 손해(Regret)를 초래할 수 있습니다.

이러한 문제를 보완하기 위해 등장한 것이 바로 ε-Greedy 전략입니다. 이 개념 또한 간단한데요, ε% 탐색을 하고 1-ε의 확률로 가장 만족스러운 선택지를 고르는 것입니다. 활용 중심으로 하되, 탐색도 놓치지 않는 구조인 것이죠.

 ε-Greedy 전략은 대부분의 경우(1−ε) 가장 좋아 보이는 선택지를 고르는 '활용'을 하고, 나머지 경우(ε)에는 새로운 선택지를 시도하는 '탐색'을 수행합니다. ⓒ deep daiv.

예를 들어, ε = 0.1이라면, 90% 확률로는 가장 만족도가 높았던 식당에 가고, 10% 확률로는 아직 충분히 시도하지 않은 식당을 랜덤하게 골라 가보는 것이죠. 이를 통해 현재까지의 경험을 활용하면서도, 더 나은 가능성을 놓치지 않는 전략이 만들어집니다.

ε-Greedy 전략은 구현이 간단하고 직관적이라는 장점이 있습니다. 하지만 탐색이 무작위로 이루어지기 때문에, 탐색이 비효율적으로 이루어질 수도 있고 ε 값에 따라 성능 차이가 크게 날 수도 있다는 한계가 있습니다. ε가 너무 크면, 무작위 탐색이 지나치게 자주 일어나면서 이미 충분히 좋은 Arm을 찾았음에도 계속 불필요한 시도를 하게 됩니다. 반대로 ε가 너무 작으면, Greedy 전략과 크게 다르지 않게 됩니다. 이를 극복하기 위해 더 정교한 전략들이 등장하게 되었는데, 대표적인 예인 UCB 전략부터 살펴보겠습니다.

정보가 부족한 게 죄는 아니잖아. UCB 전략

UCB(Upper Confidence Bound) 전략은 앞서 살펴본 ε-Greedy 전략의 무작위 탐색을 보완하기 위해, 불확실성이 큰 선택지에 보너스 점수를 부여하여 보다 체계적이고 효율적인 탐색을 가능하게 합니다. 불확실성이 큰 선택지에 보너스 점수를 준다는 것은 무엇일까요? 이는 아래의 식으로 쉽게 이해할 수 있습니다.

 ⓒ deep daiv. 

위 수식은 두 개의 항으로 구성되어 있습니다. 첫 번째 항인 x̄는 arm i의 현재까지의 평균 보상을 의미하고, 두 번째 항인 루트 속 값은 앞서 언급한 불확실성에 대한 보너스 항입니다. 이 보너스 항에는 n_i, 즉 arm i가 선택된 횟수가 분모로 들어갑니다. 따라서 자주 선택된 식당은 n_i가 커지고 보너스 항은 작아집니다. 반대로, 거의 선택되지 않은 식당은 분모의 값이 작음에 따라 보너스 항이 커지게 되어 탐색의 우선순위가 높아지는 것이죠. 즉, 아직 충분히 시도하지 않은 Arm에게 추가 점수를 부여함으로써 그 선택지를 한 번 더 고려해볼 수 있도록 유도하는 구조입니다.

그렇다면, 식의 나머지 요소인 log t와 그 앞의 상수 2는 어떤 의미일까요?

먼저 t는 전체 선택이 이루어진 시점, 즉 시간의 흐름을 나타냅니다. 따라서 log t는 시간이 지남에 따라 탐색에 대한 보너스를 점점 줄이는 역할을 합니다. 초기에는 모든 Arm에 대해 정보가 거의 없기 때문에, 불확실성이 큰 Arm에 더 큰 보너스가 부여되도록 루트 항이 크게 작용합니다. 하지만 시간이 지날수록 log t가 완만하게 증가하고, 많이 선택된 arm은 n_i가 증가하면서 루트 항 전체가 작아지기 때문에, 탐색보다는 활용 쪽으로 전략이 자연스럽게 수렴하게 되는 것입니다.

상수 2 또한 임의의 숫자가 아닙니다. 이는 Hoeffding’s Inequality(호프딩 부등식)이라는 확률 이론에서 유도된 값입니다. (자세한 내용은 수학적인 증명이 필요하므로 생략하도록 하겠습니다.) 호프딩 부등식은 관측된 평균값이 실제 평균값과 얼마나 차이 날 수 있는지를 정해진 신뢰 수준 하에 수학적으로 보장해 줍니다. 예를 들어 우리가 식당 A를 4번 갔을 때 만족도의 평균이 4.5/5였다고 해도, 실제로 그 식당의 평균 만족도는 이보다 더 높거나 낮을 수 있습니다. 이때, 보너스 항의 크기를 조정해 이러한 오차 범위를 고려하는데, 신뢰 수준을 적절히 확보하기 위해 등장하는 계수가 바로 2이며, 이는 탐색과 활용 사이의 균형을 정교하게 조절하는 역할을 하게 됩니다.

이러한 UCB 전략에도 한계가 있습니다. 보상의 분포가 복잡하거나 Arm이 많을수록 보너스 항의 설계만으로는 탐색과 활용 사이의 균형을 정교하게 맞추기 어렵다는 것입니다. 다음으로 설명할 전략은 이를 확률적으로 접근하여 해결해보는 Thompson Sampling입니다.

확률로 접근하는 Thompson Sampling

UCB 전략은 “안 가본 식당일수록 점수를 더 줘서 한 번쯤 가보게 하자”는 방식이었죠. 그날그날 가장 좋아 보이는 선택지를 하나 뽑아서 가는 건 어떨까요? Thompson Sampling은 확률 분포를 이용한 방법으로 실제로 Netflix나 Microsoft 등 여러 기업의 실험에서 좋은 결과를 보여준 알고리즘입니다.

이 알고리즘은 베이지안 정리라는 확률 이론을 기반으로 작동합니다. 핵심 아이디어는 각 선택지(Arm)가 얼마나 좋은지에 대한 ‘믿음’을 확률 분포의 형태로 표현한 뒤, 그 분포에서 무작위로 하나의 값을 뽑아 가장 높게 나온 선택지를 고르는 것입니다. 즉, 지금까지의 데이터를 바탕으로 “이 식당이 좋아”라는 믿음을 확률 분포를 만든 다음, 하나의 식당을 뽑는 구조입니다.

이러한 확률적 믿음을 구현하기 위해 Thompson Sampling은 주로 베타 분포(Beta Distribution)를 사용합니다. 이 분포는 1과 0으로 이루어진 이진 보상 환경, 예를 들어 '만족했는가/불만족했는가', '클릭했는가/안 했는가'와 같은 상황에서 유용하며, 성공과 실패 횟수를 기반으로 계속 업데이트됩니다.

예를 들어 식당 A가 지금까지 7번 성공하고 3번 실패했다면,

ⓒ deep daiv.

로 표현됩니다. 처음에 1을 더하는 이유는 Beta(1,1)이라는 중립적인 분포에서 시작하기 위함이며, 경험이 쌓일수록 성공한 횟수는 α(알파), 실패한 횟수는 β(베타)로 누적되며 분포가 점점 좁고 뾰족하게 됩니다. 아래의 그래프로 이를 한 눈에 확인할 수 있습니다.

Thompson Sampling에서 사용하는 베타 분포는 성공 횟수(α)와 실패 횟수(β)에 따라 모양이 달라집니다. α와 β의 합이 클수록 분포는 더 뾰족해져 확신이 커집니다. ⓒ deep daiv.

다시 본론으로 돌아가 알고리즘이 어떻게 동작하는지 살펴보겠습니다.

먼저 각 arm i에 대해 그동안의 성공 횟수 α_i, 실패 횟수 β_i를 기반으로 θ_i ~ Beta(α_i, β_i)에서 하나의 값을 뽑습니다. 이렇게 해서 모든 선택지에 대해 샘플링(Sampling)을 마친 후, 가장 큰 값을 가진 Arm을 선택합니다. 각 Arm에 대해 샘플링을 하는 것은, 이 Arm이 얼마나 좋은지에 대해 가지고 있는 믿음(= 분포)에서 한 번 상상해서 점수를 뽑아보는 것과 같습니다. 어떤 날은 같은 식당 A에 대해서라도 큰 수가 뽑힐 수도 있고 작은 수가 뽑힐 수도 있는 것이죠. 이러한 랜덤성이 탐험을 도와주는 것입니다.

이후 가장 큰 값을 가진 선택지를 실행해보고 그에 대한 보상 r_t ∈ {0, 1} (성공 or 실패)를 관찰합니다. 이 결과를 바탕으로 분포를 업데이트하는데, 성공했다면 α에, 실패했다면 β에 1을 더합니다. 이런 식으로 Thompson Sampling은 시행할수록 각 선택지에 대한 확률적 추정을 더 정밀하게 조정해 나가며 좋은 선택지를 더 자주 고르게 되는 구조로 수렴하게 됩니다. 특히 분포가 좁고 뾰족해질수록 해당 Arm에 대해 더 높은 확신을 가지고 선택할 수 있게 되는 것이죠.

Thompson Sampling은 산업 현장에서도 효과적인 전략으로 활용되고 있습니다. Microsoft에서는 뉴스 포털에서 기사 클릭률을 높이기 위해 사용했으며, Netflix의 추천시스템에는 Thompson Sampling을 포함한 여러 Multi-Armed Bandit 방법론들이 사용되고 있다고 알려져 있습니다.

이렇게 MAB의 개념과 대표적인 알고리즘, Epsilon-Greedy, UCB, Thompson Sampling에 대해 알아보았습니다. Epsilon-Greedy는 간단하지만, 탐험 비율에 따라 불필요한 탐험이 계속될 수 있으며, UCB는 그에 비해 안정적이지만 새로운 정보를 빠르게 반영하기 어렵기도 하다는 한계가 있습니다. Thompson Sampling은 확률 분포를 활용해 탐험과 활용을 조절하며, 실제 환경에서도 성능이 뛰어난 전략으로 평가받습니다.

이 외에도 Bayesian UCB, Neural Bandits, Conservative Bandits 등 다양한 변형 기법들이 존재하며, 상황과 목적에 따라 적절한 선택이 중요합니다. 사용자 정보나 맥락까지 반영하는 Contextual Bandit에 대해 알아보는 건 어떨까요?