대단히 좋은 기회로 현재 미국에 연구 인턴을 오게 되었습니다. 이곳에서 여러 세미나를 듣고 다른 연구자들과 소통하면서 다양한 분야를 접하고 있는 중입니다. 그중에서도 특히 개인적으로 관심이 생긴 분야가 있는데, 바로 학습 이론(learning theory)입니다. 제가 들은 세미나 주제 중 상당수가 이 분야와 연관이 있었기 때문입니다. 원래도 잘 연구된 분야였겠지만, 최근 인공 지능과 기계 학습 분야의 괄목할 만한 성장이 큰 영향을 미치고 있다는 생각도 듭니다.
다중 슬롯머신 문제(multi-armed bandits problem)는 그중 가장 기본이 되는 문제입니다. 이 문제에 익숙하지 않으시면 영어 이름과 우리말 번역이 바로 대응되지 않아서 의아해하실 것 같습니다. 사실 제가 그랬습니다. 처음에 이 문제에 대해서 전혀 모르는 상태로 세미나를 듣는 중에 "multi-armed bandits"라는 말을 들었을 때 저는 이 문제가 강도(bandit)에게 다양한(multi) 방식으로 무장(armed)을 시키는 문제라고 생각했습니다. 나중에 검색을 하고 나서야 "bandit"이 슬롯머신을 뜻한다는 것을 알게 되었습니다. 슬롯머신을 돌리기 위해서는 매번 돈을 넣어야 하는데 정작 돈을 따는 경우는 별로 없을 테니 결국 돈을 탕진하게 되겠죠. 그 모습이 슬롯머신의 팔을 당길 때마다 돈을 훔쳐가는 것처럼 보여 "bandit"이라는 이름이 붙었다고 하네요.
이 글을 필두로 그동안 제가 다중 슬롯머신 문제를 공부한 내용을 정리해 보고자 합니다. 아무래도 이론을 좋아하고 연구하는 학생이다 보니 이번에도 이 문제의 이론적인 면을 주로 다룰 예정입니다. 실제 구현이나 실험적인 결과가 필요하신 분들은 다른 블로그의 글을 참고하시는 것을 추천합니다.
모델 소개
먼저 문제의 모델을 소개하겠습니다. 우리에게는 총 \(K\) 개의 슬롯머신의 집합 \(A\)가 주어집니다. 각 슬롯머신 \(a \in A\)를 작동하여 얻는 보상은 \([0, 1]\)에서 정의된 확률 분포 \(\mathcal{D}_a\)를 따릅니다. 당연히도 우리는 이 분포를 모르는 상태에서 시작합니다. 대신, 슬롯머신 \(a\)의 팔을 한 번 당기면 \(\mathcal{D}_a\)에서 독립적으로(independently) 샘플된 보상을 받게 됩니다. 총 \(T\) 번 슬롯머신을 작동시킬 수 있을 때, 이 문제의 목표는 "평균적으로 최대한 많은 보상"을 획득하는 것입니다. 이때 \(T\)는 \(K\)보다 꽤 큰 값이라고 가정하겠습니다.
광고 게재에서의 활용
이 문제를 해결하는 방법을 공부하기 전에, 이 문제가 왜 흥미로운지를 먼저 알아 보고자 합니다. 여러분이 어떤 모바일 앱의 광고 게재 담당자라고 해 봅시다. 이 앱을 쓰는 이용자는 여러분이 게재하는 광고를 보게 됩니다. 여러분은 현재 \(K\) 개의 서로 다른 광고를 갖고 있으며, 이용자가 앱을 사용할 때마다 이 중 하나를 골라 광고를 게재할 수 있습니다. 이때 여러분은 분명 이용자가 가장 관심 있어할 광고를 매번 게재하고 싶어할 것입니다. 그래야 광고를 맡긴 회사가 만족하여 다음에 더 큰 계약을 이끌어낼 수 있을 테니 말이죠. 그 척도를 이용자가 광고를 얼마나 눌렀는지로 판단해 보겠습니다.
문제는 각 이용자마다 관심이 있는 광고가 모두 다르다는 데에 있습니다. 따라서 여러분은 각 이용자에게 알맞는 광고를 보내기를 희망합니다. 이 상황은 곧 다중 슬롯머신 문제와 흡사합니다. 이용자 한 명을 고정해 봅시다. 이때 이 이용자에게 어떤 광고를 게재하는 것을 슬롯머신을 작동시키는 것에 대응해 볼 수 있습니다. 광고를 게재했을 때 그 이용자가 해당 광고를 눌렀다면 우리에게 1의 보상이 주어지는 것으로, 반대로 광고를 누르지 않았다면 0의 보상이 주어지는 것으로 해석하는 것이죠. 현재의 목표인 이 이용자가 최대한 광고를 누르게 하는 것은 곧 다중 슬롯머신 문제에서 최대한 많은 보상을 얻는 것에 대응합니다.
후회 (Regret)
아래에서는 다중 슬롯머신 문제를 해결하는 알고리즘을 소개할 것입니다. 하지만 그 전에 먼저 알고리즘의 성능을 평가하기 위한 척도를 명확히 할 필요가 있습니다. 각 슬롯머신 \(a \in A\)의 보상 분포 \(\mathcal{D}_a\)의 평균을 \(\mu(a)\)라고 하겠습니다. 만약 우리가 보상 분포를 미리 알고 있다면, \(\mu(a^*) := \max_{a \in A} \mu(a) \)의 평균 보상을 주는 슬롯머신을 끝날 때까지 계속 작동시키는 것이 평균적으로 최선의 방법임을 쉽게 알 수 있습니다. 따라서 슬롯머신을 총 \(t\) 회 작동시켰을 때, 알고리즘이 지금까지 \(a_1, a_2, \cdots, a_t\)의 슬롯머신을 순서대로 작동시켰다면, 이 알고리즘은 지금까지 평균적으로 \[R(t) := \mu(a^*) \cdot t - \sum_{i = 1}^t \mu(a_i) = \sum_{i = 1}^t (\mu(a^*) - \mu(a_i)) \]만큼의 손해를 보았다고 말할 수 있습니다. 이 값을 이 알고리즘의 \(t\) 단계에서의 후회(regret)라고 부르겠습니다. 즉, 적은 후회를 하는 알고리즘이 곧 좋은 알고리즘이라고 말할 수 있겠습니다.
문제의 모델에서 슬롯머신은 보상을 확률적으로 제공합니다. 따라서 알고리즘의 동작도 확률에 따라 달라진다고 생각하는 것이 자연스럽습니다. 게다가 알고리즘 자체가 내부적으로 확률 시행을 진행할 수도 있습니다. 그러므로 알고리즘이 매 단계마다 고르는 \(a_1, a_2, \cdots, a_T\)를 확률 변수로 생각하는 것이 마땅합니다. 따라서 슬롯머신의 보상 분포와 알고리즘 자체의 내부 시행에 대한 기대 후회(expected regret) \(\mathbb{E}[R(t)]\)를 최소화하는 것을 문제의 목표로 삼겠습니다. 경우에 따라서는 최종적인 기대 후회 \(\mathbb{E}[R(T)]\)를 최소화하는 것을 목표로 할 수도 있습니다. 어떤 것을 목표로 두는지는 아래에서 알고리즘을 설명할 때 밝히도록 하겠습니다.
탐사 우선 알고리즘 (Explore-First Algorithm)
이제까지 다중 슬롯머신 문제에 대해서 알아 보았으니, 이제 이를 해결하는 알고리즘을 살펴 봅시다. 이 문제가 어려운 이유는 슬롯머신의 보상 분포를 처음에 모른다는 데에 있습니다. 따라서 이 문제를 해결하는 일반적인 전략은 다음과 같습니다. 처음에는 모든 슬롯머신을 몇 번씩 작동시켜 보상을 관측해 각각의 분포가 어찌될지 유추합니다. 그러다가 어느 정도 신뢰할 만한 수준으로 분포를 유추했다면 최대의 평균 보상을 제공하는 슬롯머신을 끝날 때까지 작동시킵니다. 전자의 작업을 탐사(exploration)라고 부르며, 후자의 작업은 착취(exploitation)라고 부릅니다.
다음의 알고리즘은 위 아이디어를 통해 고안할 수 있는 가장 간단한 방법입니다.
모든 슬롯머신을 각각 \(N\) 번씩 작동시킨 후 관측된 보상들의 평균을 계산한다. 이후 가장 좋은 평균 관측 보상을 제공한 슬롯머신을 끝날 때까지 작동시킨다.
위에서 적절한 \(N\)을 고르면 우리는 이 알고리즘의 최종 기대 후회 \(\mathbb{E}[R(T)]\)가 그렇게 크지 않음을 보일 수 있습니다. 이를 분석하기 위해서는 먼저 다음의 부등식이 필요합니다.
정리 1. 호프딩의 부등식 (Hoeffding's Inequality)
\([0, 1]\)에서 정의되고 평균이 \(\mu\)인 확률 분포에서 독립적으로 추출한 확률 변수 \(X_1, X_2, \cdots, X_n\)에 대해, \(S := \sum_{i = 1}^n X_i \)라고 정의하자. 그러면 임의의 양수 \(\delta > 0\)에 대해, \[ Pr \left[ |S - \mathbb{E}[S] | \geq \delta \right] = Pr\left[ \left| \frac{S}{n} - \mu \right| \geq \frac{\delta}{n} \right] \leq 2 \cdot e^{-\frac{2 \delta^2}{n}} \]을 만족한다.
증명은 나중에 따로 정리하도록 하겠습니다. 참고로 이 부등식의 증명은 체르노프 부등식(Chernoff bound)의 증명과 매우 유사하다고 합니다. 궁금하신 분은 아래를 확인하셔도 좋겠습니다.
체르노프 부등식 (Chernoff Bounds)
여러분의 눈 앞에 총 \(n\)개의 서로 다른 상자가 놓여 있다고 합시다. 각 상자 안에는 흰 공과 검은 공으로만 차 있습니다. 여러분은 각 상자의 흰 공과 검은 공의 비율이 얼마나 되는지 모두 알
gazelle-and-cs.tistory.com
이제 분석을 시작하겠습니다. 알고리즘이 어떤 슬롯머신 \(a\)를 \(N\) 번 작동시켜 관찰한 보상을 \(X^a_1, X^a_2, \cdots, X^a_N\)이라고 하겠습니다. 알고리즘은 모든 슬롯머신을 탐사한 이후 \(\bar{\mu}(a) := \frac{\sum_{i = 1}^N X^a_i}{N}\)을 계산한 다음 그중 가장 큰 값을 주는 슬롯머신을 \(T\) 단계까지 작동시킵니다. 여기서 다음과 같은 의문이 듭니다. 과연 \(\bar{\mu}(a)\)는 \(\mu(a)\)를 얼마나 잘 표현하고 있을까요? 만약 잘 반영하지 못했다면 위 알고리즘은 엄청 멍청하게 동작할 것이기 때문입니다. 여기서 호프딩의 부등식을 통해 우리는 \(\bar{\mu}(a)\)가 \(\mu(a)\)를 높은 확률로 잘 표현하고 있다는 것을 알 수 있습니다.
정리 2. 관찰 평균 보상의 신뢰성
임의의 슬롯머신 \(a\)에 대해 \[ Pr \left[ |\bar{\mu}(a) - \mu(a) | \geq \sqrt{\frac{2 \ln T}{N}} \right] \leq \frac{2}{T^4} \]를 만족한다.
[증명] 정리 1에서 \(n := N\), \(\delta := \sqrt{2 N \ln T} \)로 두어 적용하면 위 식을 바로 얻을 수 있습니다. ■
위 사실을 통해 우리는 분석을 진행할 사건의 범위를 축소할 수 있습니다. 표현의 편의를 위해 \(\gamma := \sqrt{\frac{2 \ln T}{N}} \)이라고 하겠습니다. 모든 슬롯머신 \(a \in A\)가 \[ |\bar{\mu}(a) - \mu(a)| \leq \gamma \iff \mu(a) - \gamma \leq \bar{\mu}(a) \leq \mu(a) + \gamma \tag{1} \]를 만족하는 사건을 \(\mathcal{E}\)라고 부르겠습니다. 그러면 정리 2와 유니온 바운드(union bound)(a.k.a., 불의 부등식(Boole's inequality))에 의해, \[ Pr[\neg \mathcal{E}] \leq \sum_{a \in A} Pr[|\bar{\mu}(a) - \mu(a)| \geq \gamma ] \leq \frac{2K}{T^4} \tag{2} \]임을 알 수 있습니다. 이를 통해 \(\mathcal{E}\)의 여사건은 일어날 확률이 무척 적으며, 따라서 최종 기대 후회 \(\mathbb{E}[R(T)]\)에도 영향을 크게 주지 않을 것을 기대할 수 있습니다.
그렇다면 모든 슬롯머신에 대해 관찰된 평균 보상이 실제 평균 보상을 적절히 표현하고 있는 상황에서는 어떻게 될까요? 알고리즘이 모든 슬롯머신을 \(N\) 번씩 작동시킨 다음 최대의 관찰 평균 보상을 주는 슬롯머신을 선택하여 착취하는 단계에 들어갔을 때를 생각해 보겠습니다. 만약 알고리즘이 선택한 \(a\)가 실제 최대 평균 보상을 주는 슬롯머신 \(a^*\)와 달랐다고 해 보겠습니다. 즉, \( \bar{\mu}(a) \geq \bar{\mu} (a^*) \)를 만족하는 상황인 것이죠. 그런데 \(\mathcal{E}\)의 조건인 식 1에 의해 \[ \mu(a) + \gamma \geq \bar{\mu}(a) \geq \bar{\mu}(a^*) \geq \mu(a^*) - \gamma \implies \mu(a^*) - \mu(a) \leq 2 \gamma \]임을 이끌어낼 수 있게 됩니다. 다시 말해, \(\mu(a)\)와 \(\mu(a^*)\)가 그렇게 떨어져 있지 않다는 뜻이죠.
이를 통해 우리는 \(\mathcal{E}\) 아래에서의 최종 기대 후회의 상한을 계산할 수 있습니다. \[ \mathbb{E}[R(T) | \mathcal{E}] \leq KN + 2 \gamma \cdot (T - KN) \leq KN + 2\gamma T\] 이때 \(KN\)은 알고리즘이 처음 슬롯머신을 탐사하는데 발생하는 후회의 상한으로, 각 슬롯머신의 보상이 \([0, 1]\)로 주어지므로 성립합니다. 앞에서 구한 식 2를 위 식과 엮으면 이 알고리즘의 최종 기대 후회의 상한을 다음과 같이 구할 수 있습니다.
\[ \begin{array} {rl} \mathbb{E}[R(T)] & = \mathbb{E}[R(T) | \mathcal{E}] \cdot Pr[\mathcal{E}] + \mathbb{E}[R(T) | \neg \mathcal{E}] \cdot Pr[\neg \mathcal{E}] \\ & \displaystyle \leq KN + 2 \gamma T + T \cdot \frac{2K}{T^4} \\ & \displaystyle \leq KN + 2 T \sqrt{\frac{2 \ln T}{N}} + \frac{2}{T^2} \end{array} \]
이때 첫 번째 부등식에서 \(\mathbb{E}[R(T) | \neg \mathcal{E}] \leq T\)인 이유는 앞에서와 같이 슬롯머신의 보상이 \([0, 1]\)이므로 성립하며, 두 번쨰 부등식은 \(K \leq T\)이므로 성립합니다.
여기서 \(KN = 2 T \sqrt{\frac{2 \ln T}{N}}\)가 되는 \(N \approx 8 \left( \frac{T}{K} \right)^\frac{2}{3} ( \ln T )^\frac{1}{3} \)으로 설정하면, \[ \mathbb{E}[R(T)] \leq 16 T^\frac{2}{3} (K \ln T)^\frac{1}{3} + \frac{2}{T^2} = O\left( T^\frac{2}{3} (K \ln T)^\frac{1}{3} \right) \]이 됨을 알 수 있습니다. 이를 정리하면 다음과 같습니다.
정리 3. 탐사 우선 알고리즘의 최종 기대 후회
이 알고리즘의 최종 기대 후회 \(\mathbb{E}[R(T)]\)는 \(O\left( T^\frac{2}{3} (K \ln T)^\frac{1}{3} \right)\)을 만족한다.
엡실론-탐욕 알고리즘 (Epsilon-Greedy Algorithm)
앞에서 우리는 탐사 우선 알고리즘이 최종 기대 후회가 그렇게 크지 않다는 사실을 공부하였습니다. 하지만 이 알고리즘은 한 가지 아쉬운 점이 있는데요. 바로 모든 단계에서의 기대 후회에 대한 상한을 주지는 못한다는 것입니다. 이는 처음에 모든 슬롯머신을 탐사하기 때문에 발생하는 문제인데요. 따라서, 처음에 몽땅 탐사를 하는 대신 매 단계마다 일정한 확률로는 탐사를, 그 반대의 확률로는 착취를 수행한다면 모든 단계에서 크지 않은 기대 후회를 가질 것을 예상할 수 있습니다.
여기서 중요한 것은 매 단계마다 탐사를 수행할 확률을 어떻게 정하느냐인데요. 초기 단계에서는 주어진 정보가 없으니 탐사를 중점적으로 진행하는 것이 좋을 것입니다. 반대로 시간이 흐르면 기존의 탐사 과정을 통해 슬롯머신의 보상 분포를 어느 정도 유추한 상태일 것이므로 점차 착취를 수행하는 확률을 높이는 것이 좋겠죠. 다음의 알고리즘은 바로 위 전략을 구체화한 것입니다.
엡실론-탐욕 알고리즘 (Epsilon-greedy algorithm)
입력: \(K\) 개의 슬롯머신의 집합 \(A\)
출력: 매 단계에서 작동시킬 슬롯머신
- \(x \gets 1\)
- 각 슬롯머신 \(a\)에 대해 \(\bar{\mu}(a)\)를 그동안 관찰된 보상의 평균이라고 한다.
- 매 \(t\) 단계마다 아래를 수행한다.
- \( \varepsilon_t \gets 2 \cdot \left(\frac{K \log_2 t}{t}\right)^\frac{1}{3} \)을 수행한다. 단, \(\varepsilon_1 \gets 1\)로 설정한다.
- \(\min\{ \varepsilon_t, 1 \}\)의 확률로 아래를 수행한다.
- \(x\) 번째 슬롯머신을 작동시킨 후, 그것의 \(\bar{\mu}(a)\)의 값을 수정한다.
- \(x \gets x + 1\)을 수행한다. 만약 \(x > K\)이면, \(x \gets 1\)으로 돌아온다.[ㄱ]
- 그렇지 않으면 아래를 수행한다.
- \(\max_{a \in A} \bar{\mu}(a)\)를 주는 슬롯머신을 작동시킨다.
위 알고리즘이 매 \(t\) 단계에서 탐사를 수행할 확률인 \(\min\{ \varepsilon_t, 1 \}\)은 처음 의도대로 시간이 흐를수록 작아지기만 한다는 것을 확인하시기 바랍니다.
이제 이 알고리즘이 우리의 예상대로 매 \(t\) 단계에서 좋은 기대 후회 \(\mathbb{E}[R(t)]\)를 갖는다는 것을 분석해 보겠습니다. 증명은 이전 절에서 본 탐사 우선 알고리즘의 증명과 유사합니다. 이전 절에서의 증명을 요약하면 다음과 같습니다. 각 슬롯머신을 \(N = O\left( \left( \frac{T}{K} \right)^\frac{2}{3} (\log T)^\frac{1}{3} \right)\) 회 정도씩 동작시키면 평균 관찰 보상이 실제 평균 보상과 매우 유사하게 됩니다. 따라서 착취 단계에서 최적의 슬롯머신 \(a^*\)가 아닌 다른 슬롯머신 \(a\)를 동작시켜도 이는 \( \mu(a) \approx \mu(a^*) \)라는 뜻이 되어 최종 기대 후회가 그리 커지지 않게 됩니다.
이번 알고리즘의 증명은 이 방식과 다른 점이 두 가지 있습니다. 하나는 매 단계마다 알고리즘이 추가적으로 발생시키는 후회의 증가량 \(\Delta_t := \mu(a^*) - \mu(a_t)\)의 평균을 따로 계산한 후 이를 기댓값의 선형성에 의거해 합칠 것이라는 점입니다. 다른 하나는 각 슬롯머신을 탐사하는 횟수를 잘 다루어야 한다는 점입니다. 이전에는 각각 \(N\) 번씩 탐사하여 원하는 수준의 신뢰도를 이루었지만, 이 알고리즘에서는 그 횟수도 확률적으로 정해집니다. 따라서 각 슬롯머신을 탐사하는 횟수가 확률적으로 그리 적지 않음을 논의해야 합니다. 다음 정리에서 이 이슈들을 어떻게 처리하는지 확인하시기 바랍니다.
정리 4. 기대 후회 증가량의 상한
임의의 \(t \geq 2\)에 대해, \[ \mathbb{E} [\Delta_{t + 1}] \leq \left(2 \sqrt{2} + 2 \right) \cdot \left( \frac{K \log_2 t}{t} \right)^\frac{1}{3} + \frac{3}{t^2} \]을 만족한다.
[증명] 만약 \(\varepsilon_t = 2 \cdot \left( \frac{K \log_2 t}{t} \right)^\frac{1}{3} \geq 1\)이라면, 우리는 쉽게 \[ \mathbb{E}[\Delta_{t + 1}] \leq 1 \leq 2 \cdot \left( \frac{K \log_2 t}{t} \right)^\frac{1}{3} \leq \left( 2 \sqrt{2} + 2 \right) \cdot \left( \frac{K \log_2 t}{t} \right)^\frac{1}{3} + \frac{3}{t^2} \]를 만족한다는 것을 알 수 있습니다. 따라서 이제부터는 \( \varepsilon_t = 2 \cdot \left( \frac{K \log_2 t}{t} \right)^\frac{1}{3} < 1 \)을 만족한다고 하겠습니다. 참고로 이는 \( t > K \)이어야 성립함을 확인하시기 바랍니다.
\(\mathsf{exploit}\)은 \(t + 1\) 단계에서 착취 작업(즉, 알고리즘의 3-c)을 수행한 사건이라고 하겠습니다. 또한 \(\mathsf{explore}\)는 \(t + 1\) 단계에서 탐사 작업(즉, 알고리즘의 3-b)을 진행한 사건이라고 하겠습니다. 그러면 우리는 \[ \begin{array}{rl} \mathbb{E}[\Delta_{t + 1}] & = \mathbb{E} [\Delta_{t + 1} \mid \mathsf{exploit}] \cdot Pr[\mathsf{exploit}] + \mathbb{E} [\Delta_{t + 1} \mid \mathsf{explore}] \cdot Pr[\mathsf{explore}] \\ & \leq \mathbb{E} [\Delta_{t + 1} \mid \mathsf{exploit}] + \varepsilon_{t + 1} \end{array} \tag{3} \]을 얻을 수 있습니다. 여기서 부등식은 \( Pr[\mathsf{exploit}] \leq 1 \)과 \( \mathbb{E}[\Delta_{t + 1} \mid \mathsf{explore}] \leq 1 \)이라는 사실을 통해 이끌어 낼 수 있습니다.
이제 \( \mathbb{E}[\Delta_{t + 1} \mid \mathsf{exploit}] \)의 상한을 계산해 보겠습니다. \(M\)을 알고리즘이 \(t\) 단계까지 수행하는 동안 진행한 탐사 작업(알고리즘의 3-b)의 횟수라고 하겠습니다. 또한, 각 슬롯머신 \(a \in A\)에 대해 \(N_a\)를 알고리즘이 실제로 \(a\)를 탐사의 목적으로 작동시킨 횟수라고 하겠습니다. \(\mathcal{E}\)는 \(M \geq 1.3 \cdot t^\frac{2}{3} \cdot (K \log_2 t)^\frac{1}{3} =: \tau\)이면서 각 슬롯머신 \(a \in A\)에 대해서는 \( |\bar{\mu}(a) - \mu(a)| \leq \sqrt{\frac{2 \ln t}{N_a}} =: \gamma_a \)를 만족하는 사건으로 정의하겠습니다. 앞에서와 마찬가지로 이번에는 \[ \mathbb{E}[\Delta_{t + 1} \mid \mathsf{exploit}] \leq \mathbb{E}[\Delta_{t + 1} \mid \mathcal{E}, \mathsf{exploit}] + Pr[ \neg \mathcal{E}] \tag{4} \]로 나누어서 각각의 상한을 구하여 보도록 하겠습니다.
먼저 \( \mathcal{E} \)의 여사건이 발생할 확률 \(Pr[\neg \mathcal{E}]\)가 크지 않음을 논하겠습니다. 유니온 바운드에 의해 \[ \begin{array}{rl} Pr[\neg \mathcal{E}] & = Pr \left[ \left( M < \tau \right) \vee \bigvee_{a \in A} \left( |\bar{\mu}(a) - \mu(a)| > \gamma_a \right) \right] \\ & \leq Pr [M < \tau] + \sum_{a \in A} Pr \left[ |\bar{\mu}(a) - \mu(a)| > \gamma_a \right] \\ & \displaystyle \leq Pr[M < \tau] + \frac{2 K}{t^4} \\ & \displaystyle \leq Pr[M < \tau] + \frac{2}{t^3} \end{array} \tag{5}\]을 얻게 됩니다. 여기서 두 번째 부등식은 정리 2를 약간 변형하면 얻을 수 있으며, 마지막 부등식은 \(t > K\)이기 때문에 성립합니다.
식 5의 상한을 완성하기 위해서는 \(Pr[M < \tau]\)가 그리 크지 않음을 보여야 합니다. 알고리즘은 매 \(i\) 단계에서 \( \min \{ \varepsilon_i, 1 \} \)의 확률로 탐사 작업을 진행합니다. 이때 \(\min\{ \varepsilon_i, 1 \}\)의 값은 단계가 진행될수록 증가하지 않습니다. 이를 통해 우리는 \(M\)이 이항 분포 \(\mathsf{Binom}(t, \varepsilon_t)\)보다 확률적으로 우세하다(stochastically dominant)는 것을 알 수 있습니다. 왜냐하면 \(\mathsf{Binom}(t, \varepsilon_t)\)는 \(t\) 단계까지 매번 \(\varepsilon_t\)의 확률로 탐사 작업을 진행했을 때 그동안의 탐사 횟수에 대응하기 때문이죠. 다시 말해, \[ Pr[M < \tau] \leq Pr[\mathsf{Binom}(t, \varepsilon_t) < \tau] \]를 만족합니다. 이항 분포와 호프딩의 부등식을 엮으면 이 확률에 대한 상한을 다음과 같이 구할 수 있습니다.
정리 4-1. 이항 분포의 집중(concentration)
\( Pr[\mathsf{Binom}(t, \varepsilon_t) < \tau] \leq \frac{1}{t^2}\)
[증명] 호프딩의 부등식에 \(n := t\), \(X_i := \mathsf{Bernoulli}(\varepsilon_t)\), \(\delta := \sqrt{t \ln t}\)을 대입하면 \(S = \mathsf{Binom}(t, \varepsilon_t)\)에 대해, \[ Pr \left[ \left| \mathsf{Binom}(t, \varepsilon_t) - t \varepsilon_t \right| \geq \sqrt{t \ln t} \right] \leq \frac{2}{t^2} \]를 이끌어 낼 수 있습니다. 이항 분포는 평균에 대칭을 이루므로 \[ Pr[ \mathsf{Binom}(t, \varepsilon_t) \leq t \varepsilon_t + \sqrt{t \ln t} ] \leq \frac{1}{t^2} \]을 알 수 있습니다. 마지막으로 \(K \geq 2\)에 대해, \[ t \varepsilon_t + \sqrt{t \ln t} = t^\frac{2}{3} (K \log_2 t)^\frac{1}{3} \left(2 - \frac{(\ln t)^\frac{1}{2}}{t^\frac{1}{6} (K \log_2 t)^\frac{1}{3}} \right) \geq \tau \]임을 계산할 수 있습니다. 계산은 생략합니다. ■
정리 5를 식 4에 적용하면 \[ Pr[\neg \mathcal{E}] \leq \frac{1}{t^2} + \frac{2}{t^3} \leq \frac{3}{t^2} \tag{6} \]를 얻을 수 있습니다.
마지막으로 \(\mathbb{E}[\Delta_{t + 1} \mid \mathcal{E}, \mathsf{exploit}]\)의 상한을 계산해 보겠습니다. \(\mathcal{E}\)의 정의에 의해 \( M \geq \tau = 1.3 t^\frac{2}{3} (K \log_2 t)^\frac{1}{3} \)을 만족합니다. 이때 알고리즘의 동작에 의해 우리는 모든 슬롯머신 \(a \in A\)가 \[ N_a \geq \left\lfloor \frac{M}{K} \right\rfloor = \left\lfloor 1.3 \left( \frac{t}{K} \right)^\frac{2}{3} (\log_2 t)^\frac{1}{3} \right\rfloor \]을 만족한다는 것을 알 수 있습니다. \(\varepsilon_t < 1\)이라는 조건에 의해 우리는 \( \left( \frac{t}{K} \right)^\frac{1}{3} > 2 (\log_2 t)^\frac{1}{3} \)을 얻게 되며, 따라서 \[ \left( \frac{t}{K} \right)^\frac{2}{3} (\log_2 t)^\frac{1}{3} \geq 4 \log_2 t \geq 4 \]임을 이끌어 낼 수 있습니다. 여기서 마지막 부등식은 \(t \geq 2\)라는 정리의 조건에서 유도할 수 있습니다. 이를 위 식에 적용하면 \[ \left\lfloor \frac{M}{K} \right\rfloor \geq \left( \frac{t}{K} \right)^\frac{2}{3} (\log_2 t)^\frac{1}{3} \]을 얻을 수 있습니다. 결론적으로, 이전 절의 논의를 그대로 적용하면, \[ \mathbb{E}[\Delta_{t + 1} \mid \mathcal{E}, \mathsf{exploit}] \leq 2 \sqrt{\frac{2 \ln t}{\lfloor M / K \rfloor}} \leq 2 \sqrt{\frac{2 \log_2 t}{\left( \frac{t}{K} \right)^\frac{2}{3} (\log_2 t)^\frac{1}{3} }} = 2\sqrt{2} \cdot \left( \frac{K \log_2 t}{t} \right)^\frac{1}{3} \]를 얻을 수 있습니다.
위 식과 식 6을 식 4에 적용하면 우리는 \( \mathbb{E}[\Delta_{t + 1} \mid \mathsf{exploit}] \leq 2 \sqrt{2} \left( \frac{K \log_2 t}{t} \right)^\frac{1}{3} + \frac{3}{t^2} \)이 됨을 알 수 있습니다. 이를 식 3에 적용하면 \[ \begin{array}{rl} \mathbb{E}[\Delta_{t + 1}] & \displaystyle \leq 2 \sqrt{2} \left( \frac{K \log_2 t}{t} \right)^\frac{1}{3} + \frac{3}{t^2} + \varepsilon_{t + 1} \\ & \displaystyle \leq (2 \sqrt{2} + 2) \left( \frac{K \log_2 t}{t} \right)^\frac{1}{3} + \frac{3}{t^2} \end{array} \]가 되어 정리의 명제가 성립함을 증명하게 됩니다. ■
이제 우리의 최종 목표를 다음과 같이 증명할 수 있습니다.
정리 5. 엡실론-탐욕 알고리즘의 매 단계에서의 기대 후회
임의의 \(t \geq 1\)에 대해 매 \(t\) 단계에서의 알고리즘의 기대 후회는 \[ \mathbb{E} [R(t)] = O\left( t^\frac{2}{3} (K \log t)^\frac{1}{3} \right) \]을 만족한다.
[증명] \(t \leq 2\)에 대해서는 \(R(t) \leq 2\)를 만족하므로 따로 보이지 않겠습니다. \(t \geq 3\)에 대해서 기댓값의 선형성에 의해 \[ \mathbb{E}[R(t)] = \sum_{i = 1}^t \mathbb{E} [\Delta_i] \leq 2 + \sum_{i = 2}^{t - 1} \mathbb{E}[\Delta_{i + 1}] \leq 2 + \sum_{i = 2}^t \mathbb{E}[\Delta_{i + 1}] \]가 성립하게 됩니다. 이때, \[ \begin{array}{rl} \displaystyle \sum_{i = 2}^t \mathbb{E}[\Delta_{i + 1}] & \displaystyle \leq \sum_{i = 1}^t \left[ (2 \sqrt{2} + 2) \left( \frac{K \log_2 i}{i} \right)^\frac{1}{3} + \frac{3}{i^2} \right] \\ & \displaystyle \leq (2 \sqrt{2} + 2) \cdot (K \log_2 t)^\frac{1}{3} \cdot \sum_{i = 1}^t \left( \frac{1}{i} \right)^{\frac{1}{3}} + 3 \cdot \sum_{i = 1}^t \frac{1}{i^2} \\ & \displaystyle \leq (3 \sqrt{2} + 3) t^\frac{2}{3} (K \log_2 t)^\frac{1}{3} + \frac{\pi^2}{2} \end{array} \]를 얻을 수 있습니다. 마지막 부등식은 \(\sum_{i = 1}^t \left(\frac{1}{i}\right)^\frac{1}{3} \leq \int_0^t \left( \frac{1}{x} \right)^\frac{1}{3} dx = \frac{3}{2} t^\frac{2}{3}\)이라는 사실과 \(\sum_{i = 1}^\infty \frac{1}{i^2} = \frac{\pi^2}{6}\)이라는 바젤 문제(Basel problem)의 증명에서 이끌어 낼 수 있습니다. ■
마치며
이것으로 다중 슬롯머신 문제에 대한 정리를 마칩니다. 이 문제와 관련하여 우리말로 적힌 블로그 글도 많은 것 같은데, 이런 재미있는 문제를 왜 이제야 알게 된 것인지 아쉬운 마음이 듭니다. 그럼에도 이 문제의 이론적인 면을 조명한 글은 그리 많지 않은 것 같아서 잘 정리했다는 생각이 듭니다. 특히 엡실론-탐욕 알고리즘의 경우에는 증명이 엄밀하지 못한 경우가 많이 있더라고요. 이 글이 해당 부분을 잘 보충해 주기를 바랍니다.
본문에서 소개한 탐사 우선 알고리즘이나 엡실론-탐욕 알고리즘의 동작을 잘 생각해 보면, 탐사를 할 때 매우 멍정하게 동작한다는 사실을 포착할 수 있습니다. 어떤 슬롯머신이 탐사를 진행할 때마다 계속 나쁜 보상을 제공한다고 해 봅시다. 어느 정도 확신이 들면 탐사를 진행할 때 이 슬롯머신은 고려 대상에서 제외하는 것이 어찌 보면 자연스러울 것입니다. 하지만 본문의 두 알고리즘은 그런 정보를 전혀 고려하지 않고 탐사를 진행하죠. 이렇게 얻은 보상 정보를 활용하지 않고 탐사를 하는 알고리즘을 일컬어 비적응 탐사 알고리즘(non-adaptive exploration algorithm)이라고 합니다. 그렇다면 얻은 보상 정보를 활용하는 알고리즘은 어떻게 될까요? 더 좋은 기대 후회를 얻을 수 있을까요? 아니면 다를 바 없을까요? 이는 다음 글에서 정리해 보도록 하겠습니다.
고맙습니다.
참고 문헌
[1] Aleksandrs Slivkins. "Introduction to multi-armed bandits." Foundations and Trends® in Machine Learning 12, 2019.
각주
[ㄱ] 엡실론-탐욕 알고리즘의 훨씬 잘 알려진 구현은 탐사를 진행할 때 균등한 확률로 슬롯머신을 고르는 것입니다. 이렇게 동작시켜도 결국 높은 확률로 각 슬롯머신을 탐사하는 횟수가 고르게 분포할 것이고, 따라서 (직접 써 보지는 않았지만) 본문의 논의를 확장하여 적용할 수 있을 것입니다. 하지만 오히려 증명이 복잡해지기만 하고 성능이 더 좋아지는 것은 또 아니어서 본문에서는 결정론적으로(deterministically) 균등하게 탐사하는 방식으로 기술하였습니다.