멀티암드밴딧 - (1-5) 확률적 밴딧: 참고 문헌 및 용어 정리

 

 

 

 

 

 

 

 

 

 

 

 

확률적 밴딧

 

1.5 참고 문헌 및 용어 정리

이번 챕터는 멀티암드밴딧에 폭넓게 유용한 몇가지 기법들을 소개한다. 이는 네가지 알고리즘 기법 (탐색-우선, 입실론-그리디, 연속적 제거, UCB기반 슬롯 선택), 분석을 위한 완전이벤트 기법, 그리고 수식 (1.12)에 설명한 UCB 트릭이다. 연속적 제거는 Even-Dar et al. (2002)에서, $UCB1$는 Auer et al. (2002a)에서 소개되었다. 탐색-우선과 입실론-그리디는 매우 긴 시간 동안 알려져 왔고, 이들은 최초의 언급자에 대한 부분은 명확하지 않다. 최초의 $UCB1$ 버전은 다음과 같은 신뢰 반경을 가졌다.

 

$r_t(a) = \sqrt{\alpha \cdot \frac{ln(t)}{n_t(a)}}$    (1.14)

 

$\alpha = 2$로 설정되었다; 이번 챕터에서 $log T$는 $log t$로 변경 되었다 (챕터 1.4 참고). 이 버전은 더 복잡한 분석에서 같은 후회 범위를 제공한다.

 

최적성

챕터2에서 다룰 하계(lower bound)에 의하면, (1.9)와 (1.11)에서의 후회 범위는 근-최적이다. (1.9)에서의 종속값의 후회 범위는 $O(log T)$ 요인까지 최적이다. Audibert and Bubeck (2010)은 $log T$ 요인을 제거하여 종속값의 후회 범위 $O(\sqrt{K T})$를 얻어냈다.

 

(1.11)에서의 대수의 후회 범위는 상수 요인까지 최적이다. 여러 연구들이 $O()$의 증식적인 상수를 최적화 하는데 분투하였다. 특별히, Auer et al. (2002a); Bubeck (2010); Garivier and Cappe (2011)는 $UCB1$의 상수를 분석하여 최종적으로는 $\frac{1}{2ln2}$까지 최적화를 달성하였다. 이 요인은 섹션 2.5에서의 하계에 의한 가능한 최적이다. 또한, (Audibert et al., 2009; Honda and Takemura, 2010; Garivier and Cappe, 2011; Maillard et al., 2011)은 $UCB1$ 알고리즘을 개정하여 더 향상된 후회 범위를 얻었다: 그들의 후회 범위는 최소한 기존의 알고리즘과 동일한 성능을 내고, 특정 보상 분포에 대해서는 더 좋은 성능을 낸다.

 

높은 확률의 후회값

기대되는 후회값 $\mathbb{E}[R(T)]$의 상계를 정하기 위해서는, $R(T)$에 대한 높은-확률(high-probability)의 상계를 취득해야 한다. 이는 완전이벤트 기법을 통해 취득한 후회 범위에서는 흔한 일이다. 하지만, 높은-확률의 후회 범위는 더 심화된 밴딧 시나리오들에서(예를 들어, 챕터6에서의 적대적 밴딧과 같은) 더 많은 계산을 요한다.

 

모든 라운드에 대한 후회값을 동시에

만약 시간 수평선 $T$가 미리 알려져 있지 않다면 어떻게 해야할까? 그렇다면 우리가 $t \le T$ 뿐만 아니라 모든 라운드 $t$에 대해 적용될 수 있는 후회 범위를 얻어낼 수 있을까? "연속적 제거"와 "$UCB1$"에서는 $T$값은 신뢰 반경 $r_t(a)$를 정의하기 위해서만 필요했다는 것을 기억하자. 다음과 같은 몇가지 해결책이 있다:

- 상계 $T$가 알려져 있다면, 알고리즘에서 $T$를 대체하여 사용할 수 있다. 후회 범위는 $T$에 대하여 대수적으로만 영향을 받기 때문에, 어느정도의 과대평가된 수치는 감당이 가능하다.

- Auer et al. 2002a에서 제안한 것 처럼, $UCB1$에 신뢰 반경 $r_t(a) = \sqrt{\frac{2 log t}{n_t(a)}}$을 사용한다. 이 버전은 $T$를 사용하지 않고, 후회값 분석은 임의의 $T$값으로도 동작한다.

- "더블링 트릭"(doubling trick)을 사용하면 알고있는 시간 수평선을 활용한 알고리즘은 (대개) 임의의 시간 수평선을 활용한 알고리즘으로 변환될 수 있다. 여기서, 새로운 알고리즘은 지수적인 수행시간으로 진행된다. 각 단계 $i = 1, 2, ...$는 $2^i$라운드동안 진행되고, 기존의 알고리즘을 새롭게(처음부터) 실행하게 된다. 이 접근법은 "알맞는" 이론적인 보증을 성립한다. 하지만, 매 단계에서 모든 기억을 지워버리는 것은 실용적이지 못하다.

 

즉각적인 후회값

대안적인 개념의 후회값은 각 라운드를 별도로 고려한다: 각 라운드 $t$에서의 "즉각적인 후회값"은 (단순후회값, simple regret으로도 불림) $\gamma(a_t) = \mu^* - \mu(a_t)$으로 정의 되고, 여기서 $a_t$는 해당 라운드에서 선정된 슬롯을 의미한다. 낮은 누적 후회값을 가지는 것에 더해, 즉각적인 후회값이 솟는 여러 라운드에 "균등하게" 후회값을 퍼뜨리는 것이 필요할 수 있다. 그렇다면 즉각적인 후회값에 대한 상계가 시간에 따라 단조롭게 감소하는 것을 기대할 수 있을 것이다.

 

예측을 위한 밴딧

밴딧 알고리즘의 일반적인 목표는 누적 보상을 최대화 하는 것이지만, 대안적인 목표는 각 라운드 $t$에서 예측값 $a^*_t$를 출력하는 것이다. 그렇다면 이 알고리즘은 예측값의 성능에 대해서만 평가될 수 있다. 특별히, 이 경우에는 얼마나 많은 누적 보상이 축적되는지에 대한 평가는 필요하지 않다. 이러한 목적함수를 수식화 하는 데에는 두가지 일반적인 방법이 있다: (1) 즉각적인 후회값 $\mu^* - \mu(a^*_t)$를 최소화 하는 것, 그리고 (2) 최적의 슬롯을 선택할 확률: $Pr[a^*_t = a^*]$을 최대화 하는 것. 전자는 "완전-탐색 밴딧"(pure-exploration), 그리고 후자는 "최적-슬롯 식별"(best-arm identification)이라 불린다. 최종적으로는 "연속적 제거"나 "$UCB1$과 같은 누적 후회를 위한 좋은 알고리즘 역시 이러한 류의 작업에 적용될 수 있다. 하지만, 특정 제도 하에서는 더 개선될 여지가 있다 (예, Mannor and Tsitsiklis, 2004; Even-Dar et al., 2006; Bubeck et al., 2011a; Audibert et al., 2010).

 

가능한 슬롯

만약 알고리즘에 의해 선정된 슬롯이 항상 선택 가능한 슬롯이 아니라면 어떻게 될까? Kleinberg et al. (2008a)이 제안한 "잠자는 밴딧"(sleeping bandits)은 슬롯이 잠에 들 수 있도록 (선택 불가능) 허용한다. 이에 따라, 최적 슬롯은 특정 라운드에서 잠들어있을 수 있기 때문에 평가의 기준은 슬롯의 최적의 고정된 랭킹이 된다: 각 라운드에서 랭킹이 가장 높게 매겨진 슬롯들 중 깨어있는 슬롯을 선정한다. Chakrabarti et al. (2008)의 "필멸 밴딧"(mortal bandit)에서는, 알고리즘에게 제공된 (랜덤성이 가미될 수도 있는) 일정에 의해 슬롯들은 영원히 선택 불가능해진다. $UCB1$류의 알고리즘들은 두가지 모델에서 모두 잘 동장한다.

 

부분적 피드백

부분적 피드백의 대안적인 모델들이 연구되었다. "듀엘링 밴딧"(dueling bandits) (Yue et al., 2012; Yue and Joachims, 2009)에서는 수치적인 보상이 알고리즘에게 제공되지 않는다. 대신, 두개의 슬롯을 결투하게 하여 어떤 슬롯의 보상이 더 큰지 찾아내게 된다. 동기는 웹 검색 최적화로부터 오게 된다. 행동들이 검색 결과에 해당한다면, 수치적인 보상은 사용자의 만족도에 대한 정확하지 않은 근사일 것이다. 하지만, "인터리빙"(interleaving)이라는 방법을 사용하면, 두개의 슬롯중 어떤것이 더 정확한 것인지를 측정할 수 있게 된다. 이에 대한 배경은 (Hofmann et al., 2016)의 서베이 논문을 살펴보면 된다. 이 모델의 추가적인 연구는 다음 논문들을 포함한다: (Ailon et al., 2014; Zoghi et al., 2014; Dud´ık et al., 2015).

 

"부분적 모니터링"(partial monitoring)이라는 다른 모델은, 슬롯 $a$를 선택하는 것의 결과가 (보상, 피드백) 페어이고, 여기서 피드백은 임의의 메시지가 될 수 있다. IID를 가정할 때, 결과값은 가능한 결과로부터 정해진 분포 $D_a$에서 독립적으로 선택된다. 따라서, 피드백은 밴딧피드백 이외에 추가적인 피드백이거나 (예를들어, 다른 슬롯들의 보상), 또는 밴딧피드백보다 적은 피드백일 수 있다 (예를 들어, 보상이 $[0,1]$사이의 값일때 0보다 크다는 정보). 특별한 케이스는 슬롯 $a$를 선택한 것에 대한 피드백이 슬롯 $a$와 인접한 모든 슬롯들의 보상 정보를 포함할 수 있도록, 피드백이 그래프의 노드로서 정의되는 것이다 (Alon et al., 2013, 2015).

 

느슨한 기준

만약 너무 많은 슬롯들이 주어졌다면 (그리고 이에대한 추가적인 도움이 되는 구조가 없다면), 최적의 슬롯을 찾는 작업은 너무 많은 비용이 들 것이다. 하지만 우리가 기준을 느슨하게 낮추어 정해진 $\epsilon > 0$에 대해 가장 좋은 $\epsilon$-비율의 슬롯들을 무시한다면 어떨까. 우리는 가장 좋은 잔여 슬롯들에 대한 후회값에 관심이 있다. 이들을 $\epsilon$-후회값이라 부르도록 하겠다. 만약 우리가 $\frac{1}{\epsilon}$을 효과적인 슬롯의 숫자라고 정했다고 하자. 그렇다면 우리는 실제 슬롯의 숫자 $K$가 아닌, $\frac{1}{\epsilon}$에 대한 $\epsilon$-후회값에 대한 범위(bound)를 구하면 된다. Kleinberg (2006)는 $\frac{1}{\epsilon} \cdot T^{\frac{2}{3}} \cdot polylog(T)$ 형태의 $\epsilon$-후회값을 취득하였다. (더블링 트릭에 기반한 이 알고리즘은 매우 간단하지만, 이에대한 분석은 간단하지만은 않다). 이 알고리즘의 결과는 $\epsilon$-비율이 임의의 슬롯들의 "기반 분포"(base distribution)에 비례하여 정의되게 하였고, 또한 무수히 많은 슬롯들에 대하여 확장될 수 있다. 이 설정에서 더 나은 후회 범위를 얻을 수 있을지에 대한 것은 아직 불분명 하다.

 

초기 정보를 포함한 밴딧

베이지안 밴딧, 립시츠 밴딧, 선형 밴딧은 챕터3, 챕터4, 챕터7에서 각각 다루게 된다. 오목한 보상 / 볼록한 비용을 가진 밴딧은 조금 더 고급 기술을 요하고, 이 책에서는 다루지 않는다. 이러한 방향은 Kleinberg (2004), Flaxman et al. (2005) 의 연구들로부터 시작되었고, 최근 (Hazan and Levy, 2014; Bubeck et al., 2015, 2017)와 같은 연구로 발전하였다. 이 주제의 종합적인 연구는  (Hazan, 2015)에서 찾아볼 수 있다.

 

---

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

arxiv.org/abs/1904.07272

Introduction to Multi-Armed Bandits