
확률적 밴딧
이 증명은 정보이론(Information Theory)의 중요한 기법인 KL발산을 활용한다. 이번 섹션은 우리의 목적을 충족하기 위해서 KL발산에 대한 간단한 소개를 제공한다. 이 내용은 보통 정보이론의 개론에서 다룬다.
유한적인 샘플 공간 Ω, Ω에 대한 두개의 확률분포 p와 q를 고려해 보자. 그렇다면, 쿨백-라이블러 발산 혹은 KL발산은 다음과 같이 정의 된다:
KL(p,q)=∑x∈Ωp(x)lnp(x)q(x)=p[lnp(x)q(x)].
이는 두가지 분포의 거리를 표기하는 방법이다. 이 속성은 양수이며, p=q일때 0이고, p와 q가 가깝다면 작아지는 수치이다. 하지만 KL발산은 대칭적이지는 않으며 삼각 부등식을 만족하지 않는다.
Remark 2.3
KL발산은 매우 유용한 속성을 가진 수학적 기반이다 (아래에 제시될 Theorem 2.5를 살펴보자). 자세한 정의는 다음과 같은 속성들이 만족 된다면 우리의 목적과는 무관하다; 다른말로 하면, 같은 속성을 가진 어떠한 기반을 가지고도 동일한 성능을 낼 수 있다는 말이다. KL발산이 왜 특정 방식으로 정의되어야 하는지와 같은 깊은 이유들이 있지만, 이 이유들을 자세히 살펴보는 것은 이 책의 범위에는 벗어난다. KL발산의 정의와 유용한 속성들은 무한한 샘플 공간으로 확장된다. 하지만, 유한한 샘플 공간에 활용하는 것은 우리의 목적에 적합하고, 더 손쉽게 사용이 가능하다.
Remark 2.4
이제 왜 이 정의가 타당한지 살펴보도록 하자. 우리가 알고있지는 않지만, 고정된 분포 p∗에서 x1,...,xn∈Ω의 데이터 포인트들 독립적으로 추출하였다고 하자. 또한, 우리는 이 분포가 p 혹은 q라는 것을 알고 있고, 이 데이터를 사용해 둘 중 어떤 것이 더 알고자 하는 분포에 가까운지를 찾아내고 싶다고 하자. 분포 p가 분포 q보다 더 타당하다는 것을 찾아내는 일반적인 방식으로는 로그 유사도 비(log-liklihood ratio)가 있다,
Λn:=∑ni=1logp(xi)logq(xi).
KL발산은 이 속성의 기대값이고, 이는 p가 실제 분포라는 것을 제공하고, n→∞라는 리밋을 제공한다:
lim p^* = p에 대해.
우리는 우리가 필요한 KL발산에 대한 근본적인 속성들을 이 챕터를 통해 설명할 것이다. 이후로 부터는, RC_{\epsilon}, \epsilon \ge 0은 편향 \frac{\epsilon}{2}를 가진 편향된 랜덤한 동전을 의미한다 (예를 들어 기대값 \frac{(1+\epsilon)}{2}를 가진 \{0,1\}에 대한 분포).
Theorem 2.5
KL발산은 다음과 같은 속성들을 만족한다:
- 깁스 부등식 (Gibbs' Inequality): 모든 두개의 분포 p와 q에 대해, p = q를 만족한다면, KL(p,q) \ge 0를 만족한다.
- 분포곱에 대한 연쇄 법칙: 샘플 공간을 \Omega = \Omega_1 \times \Omega_2 \times ... \times \Omega_n, p와 q를 p = p_1 \times p_2 \times ... \times p_n and q = q_1 \times q_2 \times ... \times q_n를 만족하는 \Omega 위에 있는 두개의 분포, p_j와 q_j의 j는 j \in [n]이라고 한다면, KL(p,q) = \sum_{j=1}^{n} KL(p_j,q_j)를 만족한다.
- 핀스커 부등식 (Pinsker's Inequality): 어떠한 사건 A \subset \Omega에 대하여, 2(p(a) - q(A))^2 \le KL(p,q)를 만족한다.
- 랜덤 동전: 모든 \epsilon \in (0, \frac{1}{2})에 대해, KL(RC_\epsilon, RC_0) \le 2\epsilon^2와 KL(RC_0, RC_\epsilon) \le epsilon^2$를 만족한다.
이 속성들의 증명은 비교적 간단하다 (그리고 가르칠 수 있다). 우리는 KL 기법의 더 용이한 설명을 위해 부록 B에 이 증명을 포함시켰다.
전형적인 사용법은 다음과 같다. 두개의 랜덤 동전을 던지는 n개의 샘플을 (2)번에서의 설정을 고려하면: 각 j \in [n]에 대해, p_j = RC_\epsilon은 편향된 랜덤 동전, 그리고 q_j = RC_0은 공정한 랜덤 동전이다. 우리는 임의의 사건 A \subset \Omega에 대해 관심이 있고, \epsilon이 충분히 작다면, p(A)가 q(A)와 너무 멀지 않다는 것을 증명하려 한다:
2(p(A) - q(A))^2 \le KL(p,q) (핀스커 부등식에 의해)
\quad\quad = \sum^n_{j=1} KL(p_j,q_j) (연쇄 법칙에 의해)
\quad\quad \le n \cdot KL(RC_\epsilon, RC_0) (p_j와 q_j의 정의에 의해)
\quad\quad \le 2n \epsilon^2. ((4)번에 의해)
이것에 의해 |p(A) - q(A)| \le \epsilon \sqrt{n}역시 증명 된다. 특별히 \epsilon \lt \frac{1}{2\sqrt{n}}을 만족한다면, |p(A) - q(A)| \lt \frac{1}{2}를 만족하게 된다.
Lemma 2.6
샘플 공간 \Omega = \{0,1\}^n과 \epsilon > 0을 만족하는 \Omega에 대한 두개의 분포 p = RC^n_\epsilon과 q = RC_0^n가 있다. 그렇다면 어떠한 사건 A \subset \Omega에 대해 |p(A) - q(A)| \le \epsilon \sqrt{n}을 만족 한다.
Remark 2.7
KL발산의 비대칭 정의는 위의 주장 와는 상관 없다: 우리는 KL(p,q)를 KL(q,p)로서 표기할 수 있다. 따라서 이 챕터 전반적으로는 위 정의와 상관 없이 사용할 것이다.
이 글은 아래 링크의 책을 번역한 글 입니다.
Introduction to Multi-Armed Bandits
Multi-armed bandits a simple but very powerful framework for algorithms that make decisions over time under uncertainty. An enormous body of work has accumulated over the years, covered in several books and surveys. This book provides a more introductory,
arxiv.org