멀티암드밴딧 - (1-3) 확률적 밴딧: 적응적 탐색

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

확률적 밴딧

 

1.3 적응적 탐색

탐색-우선 기법과 입실론-그리디 기법 모두 탐색 스케쥴이 관측된 보상의 기록과는 관계 없다는 큰 결점이 존재한다. 하지만 탐색시에는 관측된 보상에 적응적으로 대응하는 것이 보통은 더 좋은 결과를 낸다. 비공식적으로, 우리는 "적응적"과 "비적응적" 탐색으로 분리한다. 이번 챕터에서 우리는 적응적 탐색을 구현하고 더 나은 에이전트를 얻기 위한 두가지 알고리즘을 소개한다.

 

$K = 2$의 경우부터 시작해보자. 한가지 자연스로운 아이디어는 둘 중 하나의 슬롯이 다른 슬롯보다 더 월등하다는 것을 찾을때 까지 하나씩 번갈아하며 선택하는 방법이다. 하지만 우리는 어떻게 하나의 슬롯이 다른 슬롯보다 월등하다는 것을 정확하게 정의할 수 있을까?

 

1.3.1 완전이벤트와 신뢰범위

이전에 다루었던 아이디어들을 더 구체화 해보자. 이것 또한 추가적인 알고리즘 들에 대한 기반이 될 것이다. 라운드는 $t$로 고정히키고, 라운드 $1,2,...,ㅅ$에서 슬롯 $a$로부터 얻어진 샘플들의 수를 $n_t(a)$, 슬롯 $a$로부터 얻어진 평균 보상으로 정의해보자. 호에프딩의 부등식은 다음과 같이 도출될 수 있다:

 

$Pr[|\bar{\mu}_t(a) - \mu(a)|] \ge 1 - \frac{2}{T^4}, where r_t(a) = \sqrt{\frac{2 log T}{n_t(a)}}$.    (1.4)

 

위 수식에서 $r_t(a)$은 "신뢰 반경"(confidence radius)이라고 한다. 우리는 보상 분포 $D_a$로부터 $n_t(a)$개의 랜덤 샘플들을 가지고 있다. 만약 $n_t(a)$가 미리 지정되어 있다면, 우리는 정해진 수의 랜덤변수들을 갖게 되는 것이고, 이는 수식 (1.4)에서 호에프딩의 부동식에 곧바로 적용될 수 있다 (이론 A.1). 하지만, $n_t(a)$ 또한 랜덤변수이다. 게다가 $n_t$는 슬롯 $a$의 과거 보상들에 기반하고, 이는 특정 $n_t(a)$의 실현에 조건부가 되고, 이에따라 $a$로부터 얻어진 샘플들은 독립적일 필요가 없어진다. 따라서 우리는 더 세심한 조건들이 필요하다. 이러한 조건은 다음 그림에 묘사되어 있다.

 

Figure 1.1: $j$번째 셀은 슬롯 $a$를 $j$번 당겼을 때의 보상을, 즉 $n_t(a) = j$ 일때의 슬롯 $a$의 보상을 의미한다.

 

각 슬롯 $a$에 대해, "보상 테이프"가 존재한다고 상상해보자: Figure 1.1에 표현된 것 처럼 각 셀에는 $D_a$에서 샘플된 $1 \times T$개의 보상의 테이블이다. 일반성을 제쳐두고, 보상 테이프는 보상을 다음과 같이 인코딩 한다: 슬롯 $a$가 알고리즘에 의해 $j$번째 선택되었을 때, 이에대한 보상은 해당 슬롯의 테이프의 $j$번째 셀에서 가져오는 것이다. 이제 호에프딩의 부등식을 사용해 다음 수식을 도출할 수 있다.

 

$\forall j \quad Pr(|\bar{v}_j (a) - \mu(a)| \le r_t(a) \ge 1 - \frac{2}{T^4})$.

 

합집합 경계를 적용하면, 다음과 같이 유도될 수 있다 ($K = 슬롯의 수 \le T$)

 

$Pr(\forall a \forall j |\bar{v}_j(a) - \mu(a)| \le r_t(a)) \ge 1 - \frac{2}{T^2}$.    (1.5)

 

수식 (1.5)의 이벤트는 다음을 내포하고 있다

 

$\varepsilon := \{\forall a \forall t |\bar{\mu}_t(a) - \mu(a)| \le r_t(a)\}$    (1.6)

 

따라서 우리는 다음을 증명하였다:

 

Lemma 1.5

$Pr|\varepsilon| \ge 1 - \frac{2}{T^2}$, $\varepsilon$은 수식 1.6에 정의를 따른다.

 

    수식 (1.6)의 이벤트는 다음 분석에 대해 "완전 이벤트"이다.

    이를 통해 우리는 다음과 같이 상계와 하계의 신뢰 범위 (upper/lower confidence bound, UCB/LCB)를 정의할 수 있다 (라운드 $t$와 슬롯 $a$에 대해서):

 

    $UCB_t(a) = \bar{\mu}_t(a) + r_t(a)$,

    $LCB_t(a) = \bar{\mu}_t(a) - r_t(a)$.

 

$[LCB_t(a); UCB_t(a)]$로 정의된 범위를 "신뢰구간"(confidence interval)이라 부른다.

 

1.3.2 연속적 제거 알고리즘 (Successive Elimination algorithm)

이전에 이야기한 아이디어를 다시 살펴보자: 하나의 슬롯이 다른 슬롯보다 더 뛰어나다는 것이 확인 될때 까지 반복하는 것이다. 이제 우리는 자연스럽게 신뢰범위를 활용해 "월등함"에 대해서 정의할 수 있다. 두개의 슬롯을 사용한 알고리즘 전체는 다음과 같다:

 

알고리즘 1.3: 두개의 슬롯에 대한 "높은-신뢰도를 사용한 제거" 알고리즘

임의의 짝수 라운드 $t$ 이후에 $UCB_t(a) < LCB_t(a')$를 만족할 때 까지 두개의 슬롯을 번갈아가며 선택한다;

위 조건을 만족한 뒤 부터는, 슬롯 $a$를 버리고 슬롯 $a'$을 선택한다.

 

분석을 위해 완전이벤트를 가정한다. "자격이 없는"(disqualified) 슬롯은 최적의 슬롯이 될 수 없다는 것을 유의하자. 하지만 하나의 슬롯을 자격이 없다고 판단하기 전에 얼마만큼의 후회값을 누적해야 할까?

 

반복을 멈추는 조건($UCB < LCB$), 즉 두 슬롯의 신뢰구간이 아직 겹쳐져 있을 때, 직전의 라운드를 $t$ 라고 가정해보자.

 

$\nabla := |\mu(a) - \mu(a')| \le 2(r_t(a) + r_t(a')$.

 

그리고 우리는 두 슬롯을 시점 $t$ 직전까지 반복하여 선택했기 때문에, 우리는 $n_t(a) = \frac{t}{2}$를 산정할 수 있고 (올림 및 내림을 적용하여), 이는 다음과 같이 도출될 수 있다.

 

$\nabla \le 2(r_t(a) + r_t(a')) \le 4\sqrt{\frac{2 log T}{\lfloor \frac{t}{2} \rfloor}} = O(\sqrt{\frac{log T}{t}})$

 

이에 따라 라운드 $t$까지 누적된 후회값은 다음과 같다.

 

$R(t) \le \nabla \times t \le O(t \cdot \sqrt{\frac{log T}{t}}) = O(\sqrt{t log T})$.

 

Figure 1.2: $t$는최종 두 신뢰구간이 겹쳐지는 마지막 라운드이다.

 

두 신뢰구간이 겹치지 않는 라운드 이후로부터 우리는 최적의 슬롯을 선택하였기 때문에, 우리는 $R(t) \le O(\sqrt{t log T})$의 후회값을 얻게 된다. 이 분석을 끝내기 위해서 우리는, 탐색-우선 알고리ㅏ즘에서 살펴보았던 것처럼, "악성이벤트" $\bar{\varepsilon}$가 무시해도 될 만큼 후회값에 영향을 주는지에 대해서 논의해야한다:

 

$\mathbb{E}[R(t)] = \mathbb{E}[R(t) | 완전이벤트] \times Pr[완전이벤트] + \mathbb{E}[R(t) | 악성이벤트] \times Pr[악성이벤트]$

$\quad\quad\quad \lt \mathbb{E}[R(t) | 완전이벤트] + t \times O(T^{-2})$

$\quad\quad\quad O(\sqrt{t log T})$.

 

우리는 다음과 같은 증명을 이끌어 낸다:

 

Lemma 1.6

두개의 슬롯에 대해서 알고리즘 1.3은 각 라운드 $t \le T$에 대해 $\mathbb{E}[R(t)] \le O(\sqrt{t log T})$의 후회값을 산출한다.

 

Remark 1.7

현재의 후회값 범위에서의 $\sqrt{t}$값은, 탐색-우선 알고리즘에서 $T^{\frac{2}{3}}$과는 반대되는 관계이다. 이는 개선점은 적응적 탐색 때문에 가능하다.

 

이 접근법은 $K > 2$ 슬롯인 상황에 대해 다음과 같이 확대될 수 있다:

 

알고리즘 1.4: 연속적 제거 알고리즘

최초에는 모든 슬롯을 "활성" 상태로 설정;
각 단계에서:
    모든 활성 상태의 슬롯을 시도한다 (따라서 단계는 다수의 라운드를 포함할 수 있다);
    $UCB_t(a) \lt LCB_t(a)$를 만족하는 $\exists 슬롯 a'$가 있다면 모두 비활성화 시킨다;
모든 라운드가 끝날때까지 반복한다.

 

위 알고리즘의 성능을 분석하기 위해서는, 수식 (1.6)에서 처럼 완전이벤트에만 집중해도 충분할 것이다. 이는 $K = 2$개의 슬롯의 상황에서도, 악성이벤트 $\bar{\varepsilon}$의 영향이 거의 없었기 때문이다.

 

$\mu(a) \lt \mu(a^*)$를 만족하는 최적의 슬롯 $a^*$와 다른 슬롯 $a$가 있다. $a$를 비활성화 하지 않은 마지막 라운드 $t$를 살펴보자 (혹은 $a$가 끝까지 활성화 되었다면 마지막 라운드 $T$). 이 조건에 의해 라운드 $t$에서의 $a$와 $a^*$ 두개의 슬롯의 신뢰 구간은 무조건 겹쳐져야 한다. 따라서:

 

$\nabla(a) := \mu(a^*) - \mu(a) \le 2(r_t(a^*) + r_t(a)) = O(r_t(a))$.

 

마지막 등식은 위의 알고리즘이 활성화된 슬롯들을 모두 번갈아가며 선택하기 때문에, $n_t(a)$ 와 $n_t(a^*)$가 최대 1의 차이가 난다는 것을 의미한다. 슬롯 $a$는 라운드 $t$ 이후에는 절대 선택되지 않기 때문에, $n_t(a) = n_T(a)$는 성립하고, 따라서 $r_t(a) = r_T(a)$ 역시 성립한다.

 

우리는 다음과 같은 중요한 사항을 증명하였다:

 

$\nabla(a) \le O(r_T(a)) = O(\sqrt{\frac{log(T)}{n_T(a)}}$    $\mu(a) \lt \mu(a^*)$를 만족하는 각 슬롯 $a$에 대하여. (1.7)

 

비공식적으로: 여러번 시도된 슬롯은 그렇게 나쁜 점수를 낼수는 없다. 다른 모든 분석은 오직 수식 (1.7)에만 의존한다. 다른 말로 하면, 이 속성은 취득하기 위해서 알고리즘의 종류는 상관이 없다는 말이다.

 

$R(t;a)$로 표기된 라운드 $t$에서 슬롯 $a$의 후회값에 대한 기여도는, 해당 슬롯이 선택된 각 라운드에 대해 $\nabla(a)$로 표현될 수 있다. 수식 (1.7)에 의해 우리는 이 값을 다음과 같이 제한할 수 있다.

 

$$R(t;a) = n_t(a) \cdot \nabla(a) \le n_t(a) \cdot O(\sqrt(\frac{log T}{n_t(a)}) = O(\sqrt{n_t(a) log T}$)$.

 

$A$가 모든 $K$개의 슬롯의 집합을 의미하고, $A^+ = {a : \mu(a) \lt \mu(a^*)}$는 후회값에 영향을 미친 모든 슬롯이라고 하자. 그렇다면 다음 수식을 유도할 수 있다:

 

$R(t) = \sum_{a \in A^+} R(t;a) = O(\sqrt{log T}) \sum_{a \in A^+} \sqrt{n_t(a)} \le O(\sqrt{log T}) \sum_{a \in A} \sqrt{n_t(a)}$.    (1.8)

 

$f(x) = \sqrt{x}$는 오목함수(concave function)이고, $\sum_{a \in A} n_t(a) = t$가 성립하기 때문에, 우리는 젠센 부등식 (Jensen's Inequality)에 의해 다음이 성립함을 알 수 있다.

 

$\frac{1}{K} \sum_{a \in A} \sqrt{n_t(a)} \e \sqrt{\frac{1}{K} \sum_{a \in A} n_t(a)} = \sqrt{\frac{t}{K}}$.

 

위 수식을 수식 (1.8)에 대입하면, 우리는 $R(t) \le O(\sqrt{K t log T})$가 성립함을 알 수 있다. 이에따라 우리는 다음을 증명한다:

 

Theorem 1.8

연속적 제거 알고리즘은 다음과 같은 후회값을 산출한다.

$\mathbb{E}[R(t)] = O(\sqrt{K t log T})$  모든 라운드 $t \le T$에 대해    (1.9)

 

우리는 수식(1.7)의 속성을 이용하여 다른 후회 범위를 도출할 수 있다. 수식(1.7)의 항들을 재배치하면, 우리는 $n_T(a) \le O(\frac{log T}{[\nabla (a)]^2})$를 산출할 수 있다. 다른말로 하면, 이는 좋지 않은 슬롯이 너무 자주 선택되는 것을 의미한다. 따라서 우리는 각 슬롯 $a \in A^+$에 대해 다음을 도출한다:

 

$R(T;a) = \nabla(a) \cdot n_T(a) \le \nabla(a) \cdot O(\frac{log T}{[\nabla(a)]^2}) = O(\frac{log T}{\nabla(a)})$.    (1.10)

 

이를 모든 슬롯 $s \in A^+$에 대해 적용하면:

 

$R(T) \le O(log T)[\sum_{a \in A^+} \frac{1}{\nabla(a)}]$.

 

Theorem 1.9

연속적 제거 알고리즘은 다음과 같은 후회값을 산출한다.

 

$\mathbb{E}[R(T)] \le O(log T)[\sum_{\mu(a) \lt \mu(a^*)를 만족하는 슬롯 a} \frac{1}{\mu(a^*) - \mu(a)}]$.    (1.11)

 

Remark 1.10

특정 문제에 있어서는 $T$값이 커질 수 있기 때문에, 위 후회 범위는 $T$에 로그를 적용한다. 상수값을 통해 산출된 후회 범위와 특정 값에 종속된 값에 의해 산출된 후회 범위의 차이는 멀티암드밴딧 문제에서는 매우 전형적인 문제에 해당한다. 대수의(logarithmic) 후회 범위의 존재는 비적응 탐색에 비교해 적응 탐색이 얻을 수 있는 장점이다.

 

Remark 1.11

평균 보상 $\mu$에 영향을 받지 않는 함수 $f(\cdot)$와 $T$에 영향을 받지 않는 상수 $C$를 가진 후회 범위 $C \cdot f(T)$를 살펴보자. 이런 식으로 $\mu$에 종속되지 않은 값 $C$는 후회 범위를 공식적으로는 "비종속값"(instance-independent)라고 부르고, 이와 반대되는 값을 "종속값"(instance-dependent)라고 부른다.

 

Remark 1.12

$Theorem 1.8$을 다른 방식으로 유도하는 것이 더 직관적일 것이다: 수식 (1.10)의 대수의 후회 범위로부터 시작해보자. 비공식적으로, 우리는 분모에 있는 작은 값인 $\nabla (a)$들을 제가해야 한다. $\epsilon \gt 0$의 값을 고정시킨다면, 후회값은 다음과 같이 두 부분으로 구성된다:

• $\nabla (a) \le \epsilon$을 가진 모든 슬롯 $a$는 각 라운드에 후회값에 최대 $\epsilon$ 만큼, 모든 라운드를 종합하면 $\epsilon T$만큼 기여한다;
• $\nabla (a) \gt \epsilon$을 가진 모든 슬롯 $a$는 최대 $R(T;a) \le O(\frac{1}{\epsilon} log T)$ 만큼 후회값이 기여한다; 따라서 이러한 슬롯들은 모든 라운드를 종합하면 최대 $O(\frac{K}{\epsilon} log T$ 만큼 기여한다.

 

이 두 부분을 하나로 병합하면, 우리는 (완전이벤트를 가정했을 때) 다음을 산출한다

 

$R(T) \le O(\epsilon T + \frac{K}{\epsilon} log T)$.

 

위 사실이 $\forall \epsilon \gt 0$에 대해 성립하기 때문에, 우리는 오른쪽 항을 최소화 하는 방향으로 $\epsilon$을 선정할 수 있다. $\epsilon T = \frac{K}{\epsilon} log T$를 보장하는 것은 $\epsilon = \sqrt{\frac{K}{T} log T}$를 산출하게 되고, 따라서 $R(T) \le O(\sqrt{K T log T})$가 성립하게 된다.

 

1.3.3 불확실성하에 낙관론

"불확실성하에 낙관론"(optimism under uncertainty)라는 적응적 탐색의 다른 접근법을 살펴보자: 지금까지 관찰한 것을 기반으로 각 슬롯이 최대한 좋은 슬롯이라고 가정하고, 이러한 낙관적인 측정 하에 가장 좋은 슬롯을 선택한다. 이러한 직관은 다음과 같은 간단한 알고리즘인 $UCB1$으로 이어진다:

 

알고리즘 1.5: UCB1 알고리즘

각 슬롯을 한번씩 시도한다;
각 라운드 $t$에서, $UCB_t(a) = \bar{\mu}(a) + r_t(a)$를 만족하는 $argmax_{a \in A} UCB_t(a)$를 선정한다;

 

Remark 1.13

왜 $UCB$기반의 선택 기법이 동작하는지 살펴보자. 라운드 $t$에서 슬롯 $a$가 선택된 것은 해당 슬롯이 큰 $UCB_t(a)$값을 가졌기 때문이고, 이는 다음 두가지 이유 때문일 것이다: 평균 보상 $\bar{\mu}_t(a)$이 크거나 (이 경우에는 해당 슬롯이 높은 보상값을 가질 확률이 높다), 신뢰 반경 $r_t(a)$이 크기 때문이다 (이 경우에는 해당 슬롯이 충분히 탐색되지 못했을 확률이 높다). 두가지 이유 모두 해당 슬롯을 선택할 충분한 이유가 된다. 또한, $UCB$의 $\bar{\mu}_t(a)$와 $r_t(a)$의 덧샘의 항은 각각 탐색과 활용을 의미하고, 이 둘을 더한다는 것은 자연스럽게 둘 사이의 균형을 유지한다는 것을 의미한다.

 

위 알고리즘을 분석하기 위해서 우리는 이전과 동일하게 완전이벤트 (1.6)에 대해 집중해보자. $a^*$는 최적 슬롯이고, 라운드 $t$에서 알고리즘에 선택된 슬롯을 $a_t$라고 가정했던 것을 기억하자. 알고리즘에 의해, $UCB_t(a_t) \ge UCB_t(a^*)$가 성립한다. 완전이벤트하에서는, $\mu(a_t) + r_t(a_t) \ge \bar{\mu}_t(a_t)$와 $UCB_t(a^*)$가 성립하고, 따라서 다음이 성립한다:

 

$\mu(a_t) + 2r_t(a_t) \ge \bar{\mu}_t(a_t) + r_t(a_t) = UCB_t(a_t) \ge UCB_t(a^*) \ge \mu(a^*)$.    (1.12)

 

또한 다음 수식 역시 뒤따라 온다.

 

$\nabla (a_t) := \mu(a^*) - \mu(a_t) \le 2r_t(a_t) = 2\sqrt{\frac{2 log T}{n_t(a_t)}}$.    (1.13)

 

이 귀여운 트릭은 더 일반적인 설정에서의 몇몇의 $UCB$와 유사한 알고리즘의 분석을 재적립 한다.

 

각 슬롯 $a$가 알고리즘에 의해 선택된 마지막 라운드 $t$에 대해 살펴보자. 수식 (1.13)을 해당 라운드에 적용하면 우리는 수식 (1.7)의 속성을 산출하게 된다. 이후의 모든 분석은 연속적 제거 알고리즘의 분석과 동일하게 해당 속성을 따라 진행하게 된다.

 

Theorem 1.14

알고리즘 $UCB1$은 수식 (1.9)와 (1.11)의 후회 범위를 만족한다.

 

---

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

arxiv.org/abs/1904.07272

Introduction to Multi-Armed Bandits