멀티암드밴딧 - (1-2) 확률적 밴딧: 균등한 탐색

 

 

 

 

 

 

 

 

확률적 밴딧

 

1.2 균등한 탐색

간단한 아이디어로부터 시작한다: 이전에 관측된 결과가 무엇이든 슬롯을 균등하게(같은 비율로) 탐색(explore)하고, 경험적으로 최적의 슬롯을 활용(exploit)한다. "탐색-우선"으로 알려진 이 알고리즘은 첫 라운드 들을 탐색에 집중하게 하고, 나머지 라운드들을 활용에 사용한다.

 

알고리즘 1.1: 매개변수 N을 사용한 탐색-우선 알고리즘

1. 탐색 단계: 각 슬롯을 $N$번 선택에 시도한다;
2. 가장 높은 평균 보상을 주는 슬롯 $\hat{a}$를 선택한다 (동점시에는 임의의 선택을 따른다);
3. 활용 단계: 슬롯 $\hat{a}$를 나머지 모든 라운드에 사용한다.

 

매개변수 $N$은 미리 선정된 값이다. 추후에 이 값은 시간수평선 $T$와 슬롯의 수 $K$의 함수로서 후회값을 최소화 하는 방향으로 선정될 것이다. 이제 이 알고리즘의 후회값을 분석해보자.

 

탐색 단계 이후의 각 행동 $a$에 대한 평균보상을 $\bar{\mu}(a)$로 표기한다.우리는 평균 보상을 실제 기대되는 보상에 대한 좋은 예측값이 되기를 원한다. 예를 들면, $|\bar{\mu}(a) - \mu(a)|$ 값이 작아야 한다. 우리는 "호에프딩의 부등식"(Hoeffding inequality)을 사용해 평균과 실제 기대값의 편차를 측정할 수 있다. 신뢰 반경을 $r(a) = \sqrt{\frac{2 log T}{N}}$으로 정의하고, 호에프딩의 부등식을 사용하면 다음과 같다:

 

$Pr{|\bar{\mu} - \mu(a)| \le r(a)} \ge 1 - \frac{2}{T^4}$,    (1.2)

 

따라서 평균과 실제 기대값의 편차가 커질 확률은 매우 작다.

 

우리는 수식(1.2)가 모든 슬롯에 대해 만족하는 사건을 "완전이벤트"(clean event)로 정의한다. 우리는 완전이벤트와 반대되는 이벤트를 "악성이벤트"(bad event)로 정의하고, 이 둘을 분리하여 다룬다.

 

Remark 1.2

이 접근법으로, 증명의 다른 모든 확률에 대한 부분을 걱정할 필요가 없어졌다. 완전이벤트를 정의하고 수식(1.2)를 만족하는 것 만으로 확률에 대한 부분은 해결된다. 또한, 우리는 악성이벤트가 일어날 확률이 너무 작기 때문에 악성이벤트에 대한 부분 역시 고려하지 않아도 된다. 우리는 이 "완전이벤트"접근법을 기술적인 사항을 간단히 하기 위해 다른 여러가지 증명에 사용할 것이다. 이 접근법의 단점은 확률에 대해 더 세심히 다뤄져야 하는 증명을 통해 얻어질 수 있는 비교적 좋지 않은 상수를 자주 초래한다.

 

단순함을 위해, 슬롯이 $K = 2$인 경우를 살펴보자. 완전이벤트 상황을 살펴보자. 만약 우리가 둘 중 더 좋지 않은 슬롯을 선택했을 때, 두 슬롯의 기대되는 보상값의 차이가 그리 크지 않기 때문에, 상황은 그렇게 나쁘지 않다는 것을 증명해본다.

 

최적의 슬롯을 $a^*$로 정의하고 알고리즘이 $a \ne a^*$인 슬롯을 선택했다고 하자. 이는 측정된 $a$의 평균 보상이 $a^*$보다 높았기 때문, 즉 $\bar{\mu}(a) \gt $\bar{\mu}(a^*)$를 만족했기 때문일 것이다. 이는 완전이벤트이기 때문에 다음을 만족한다:

 

$\mu(a) + r(a) \ge \bar{\mu}(a) \ge \mu(a^*) - r(a^*)$

 

위 수식을 재정의 하면 다음과 같다:

 

$\mu(a^*) - \mu(a) \le r(a) + r(a^*) = O(\sqrt{\frac{log T}{N}})$

 

따라서, 각 라운드의 탐색 단계는 최대 $O(\sqrt{\frac{log T}{N}})$ 만큼 후회값에 기여한다. 그리고 각 라운드의 탐색 단계는 최대 1까지는 거의 기여하지 않는다. 우리는 두개의 항(첫 $N$라운드 만큼의 탐색과 $T - 2N$라운드 만큼의 활용)으로 나누어져 있는 후회값의 상계(upper bound)를 다음과 같이 유도한다:

 

$R(T) \le N + O(\sqrt{\frac{log T}{N}} \times (T - 2N))$

$\quad\quad\;\; \le N + O(\sqrt{\frac{log T}{N}} \times (T))$

 

첫 라운드 이전에 알고리즘에 주어진다면, 우리는 $N$에 어떤 값이든 설정할 수 있다. 따라서 우리는 오른쪽 항을 대략적으로 최소화 하는 방향으로 $N$을 선정할 수 있다. 덧셈의 두 항이 한쪽은 $N$에 의해 단조적으로 증가하고, 다른 항은 $N$에 의해 단조적으로 감소한다는 것을 유의하여, 우리는 두 항이 대략적으로 거의 같게 되는 방향으로 $N$을 설정할 수 있다. $N = T^{\frac{2}{3}} (log T)^{\frac{1}{3}})$ 으로 설정하면, 우리는 다음 수식을 얻을 수 있다:

 

$R(T) \le O(T^{\frac{2}{3}} (log T)^{\frac{1}{3}}))$

 

증명을 마무리하기 위해, 우리는 악성이벤트의 경우를 분석해야 한다. 후회값은 최대 $T$가 될 수 있고 (각 라운드의 후회값은 최대 1), 악성이벤트는 매우 작은 확률($\frac{1}{T^4}$)로 발생하기 때문에, 이 경우의 (기대되는) 후회값은 무시될 수 있다. 이를 수식화하면,

 

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

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

$\quad\quad\quad\quad \le O(\sqrt{log T} \times T^{\frac{2}{3}})$

(1.3)

 

위 수식으로 $K=2$개의 슬롯에 대한 증명을 마친다.

 

$K > 2$개의 슬롯에 대해서 우리는 수식 (1.2)에 $K$개의 슬롯에 대한 "합집합 경계" (union bound, 부울의 부등식)를 적용하고, 다른 매개변수에 대해서는 위에서와 같은 조건을 따를 수 있다. 우리는 각 슬롯을 최소 한번 이상 사용하기 때문에 $T$는 $K$보다 크다는 것을 알 수 있다. 최종 후회값 계산을 위해서 우리는 $K$에 영향을 미치는 요소들을 알아볼 필요가 있다: 특별히, 탐색 단계에서 축척된 후회값의 상계는 $KN$에 설정된다는 점이다. 이를 증명하기 위해 우리는 수식에 다음과 같이 대입한다: $R(T) \le NK + O(\sqrt{\frac{log T}{N}} \times T)$. 전과 동일하게, 우리는 덧셈의 두 항을 대략적으로 최소화 함으로서, 이 수식을 대략적으로 최소화 한다. 더 자세하게는 $N = (\frac{T}{K})^{\frac{2}{3}} \cdot O(log T)^{\frac{1}{3}}$을 대입한다. 수식 (1.3)과 동일하게 증명을 완료하면 우리는 다음 이론을 도출할 수 있다:

 

Theorem 1.3

탐색-우선 알고리즘은 후회값 $E[R(T)] \le T^{\frac{2}{3}} \times O(K log T)$을 얻는다.

 

탐색-우선 알고리즘의 한가지 문제점은 탐색단계에서의 성능이 매우 좋지 않다는 점이다. 시간에 다라 탐색을 균등하게 배분 하는 것이 더 좋다. 이는 입실론-그리디 (epsilon-greedy) 알고리즘을 통해 구현된다:

 

알고리즘 1.2: 탐색 확률($\epsilon_1$, $\epsilon_2$, ...)을 사용한 입실론-그리디

for 라운드 t = 1, 2, ... do
    성공 확률 $\epsilon_t$로 동전을 던진다;
    if 성공 then
        탐색: 균등한 랜덤 확률로 한개의 슬롯을 선택
    else
        활용: 지금까지 가장 높은 평균 보상을 주는 슬롯을 선택
end

 

단기간에 걸쳐 최적의 옵션을 선택하는 것을 컴퓨터과학에서는 "탐욕적"(greedy) 선택이라 부르고, 이로부터 "입실론-그리디" 알고리즘의 이름이 파생되었다. 탐색 기법은 "탐색-우선"알고리즘에서의 "라운드-로빈"(round-robin) 탐색과 유사하게 모든 슬롯에 대해 균등한 기회를 부여한다. 이로서 탐색 기법은 시간에 따라 균등하게 배분 되었기 때문에, 작은 $t$에 대해서도 의미있는 후회값의 범위(bound)를 도출해낼 수 있다. 우리는 탐색-우선에서의 시간수평선 $T=t$와 유사하게, 기대되는 탐색의 횟수가 $t^{\frac{2}{3}}$에 의해 $t$로 반올림 될 수 있도록, 탐색 확률 $\epsilon_t ~ t^{-\frac{1}{3}}$을 활용한다 ($K$와 $log t$에 대한 의존성은 잠시 무시한다). 후회값의 범위는 Theorem 1.3과 동일하게 도출할 수 있지만, 이제는 모든 라운드 $t$에 대해서도 만족하게 된다. 이 증명은 다음 섹션에서 소개될 더 정제된 완전이벤트에 의존한다.

 

Theorem 1.4

탐색 확률 $\epsilon_t = t^{-\frac{1}{3}} \times (K log t)^{\frac{1}{3}}$을 사용한 입실론-그리디 알고리즘은 각 라운드 $t$에 대해 $\mathbb{E}[R(t)] \le t^{\frac{2}{3}}$의 후회값의 범위를 취득할 수 있다.

 

---

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

arxiv.org/abs/1904.07272

Introduction to Multi-Armed Bandits