멀티암드밴딧 - (2) 하계 (Lower Bounds)

 

 

 

 

 

 

 

 

 

 

 

 

하계 (Lower Bounds)

이번 챕터는 밴딧 알고리즘이 할 수 없는 일들에 대해서 다룬다. 우리는 지난 챕터에서 다룬 후회값 비율이 가능한 최적이라는 것을 내포하는 두가지의 근본적인 결과를 보여준다.

 

우리는 다른 어떠한 밴딧 알고리즘도 더 좋은 후회값을 얻지 못하는, 즉 모든 밴딧 알고리즘들에 적용 가능한 하계(lower bound)에 대해 관심이 있다. 우리는 이번 챕터를 전반적으로 $\Omega(\sqrt{KT})$ 하계를 증명하는데 사용한다. 그리고 우리는 종속적인 하계 $\Omega(log T)$를 정의하고 이것에 대해 다룬다. 이러한 하계값들은 어떠한 상계값이 얻을 수 있는 최적의 값인지에 대한 감각을 심어준다.

 

$\Omega(\sqrt{KT})$의 하계는 다음과 같이 명시한다:

 

Theorem 2.1

확률적 멀티암드밴딧에 대해서, 시간수평선 $T$와 슬롯의 숫자 $K$를 고정시킨다. 모든 밴딧 알고리즘을 대상으로, $\mathbb{E}[R(T)] \ge \Omega(\sqrt{KT})$를 만족하는 문제가 존재한다.

 

이 하계는 "최악의-케이스"(worst-case)이며, 많은/대부분의 다른 문제들보다 더 낮은 후회값을 가질 가능성을 열어준다. 이 하계값을 증명하기 위해서는, 어떤 알고리즘이든 속일(fool) 수 있는 문제들의 모임 $F$를 정의해야 한다. 이를 진행하기 위한 일반적인 두가지 방법이 있다:

1. $F$에 속한 문제가 어떤 알고리즘이든 높은 후회값을 가지게 한다는 것을 증명,
2. "랜덤성이 있는"(randomized) 문제를 정의한다: $F$에 대한 분포를 정의하고, 이 분포에 대하여 어떤 알고리즘이든 높은 기대되는 후회값을 가진다는 것을 증명한다.

 

Remark 2.2

위 Theorem에서 2는 1을 내포하고 있다. 왜냐하면, 문제들에 대한 기대값의 후회값이 높으면, 적어도 하나의 문제는 높은 후회값을 가지고 있다는 것을 뜻한다. 반대로 만약 $|F|$가 상수라면 1은 2를 내포한다: 실제로 만약 우리가 $F$ 안의 어떠한 문제에 대해 높은 후회값 $H$를 가진다면, $F$ 후회값에 대한 균등분포에 대한 기대값은 적어도 $\frac{H}{|F|}$가 된다. 하지만 이는 $|F|$가 너무 크다면 성립하지 않는다. 그럼에도, 더 강력한 버전의 1은 $F$ 안에 있는 문제들의 등분수(constant fraction)에 대한 후회값이 크다고 말하고, 이는 문제들에 대한 균등분포를 가지고, $|F|$의 크기와 무관하게 2를 내포한다.

 

높은 수준에서의 증명은 다음과 같다. 우리는 0-1의 보상과 $\epsilon \gt 0$의 분석을 통해 조정 가능한 매개변수를 가진 문제를 살펴본다:

 

$I_j = \begin{cases} \mu_i = \frac{(1+\epsilon)}{2}   & \text{슬롯 i = j 에 대해} \\ \mu_i = \frac{1}{2} & \text{슬롯 i \ne j에 대해} \end{cases}$    (2.1)

 

위 수식은 각 $j = 1,2, ..., K$에 대하여 성립한다. ($K$는 슬롯의 숫자이다). 지난 챕터에서 각 슬롯을 $\tilde{O}(\frac{1}{\epsilon^2})$번 샘플링 하는 것이 후회값의 상계를 만족한다고 설명한 것을 기억하자. 우리는 각 슬롯의 좋고 나쁨을 판단하기 위해 $\Omega(\frac{1}{\epsilon^2}$번 샘플링 하는 것이 필요하다는 것을 증명할 것이다. 이는 후회값 $\Omega(\frac{K}{\epsilon})$을 유도하게 된다. 우리는 $\epsilon = \Theta(\sqrt{\frac{K}{T}})$를 대입함으로서 증명을 마무리 한다. 하지만, 기술적인 내용은 꽤 난해하다. 우리는 이를 조금 더 점잖은 방식으로 살펴보고자 한다.

 

 

---

이 글은 아래 링크의 책을 번역한 글 입니다.

arxiv.org/abs/1904.07272

Introduction to Multi-Armed Bandits