개발블로그

확률적 밴딧 이 증명은 정보이론(Information Theory)의 중요한 기법인 KL발산을 활용한다. 이번 섹션은 우리의 목적을 충족하기 위해서 KL발산에 대한 간단한 소개를 제공한다. 이 내용은 보통 정보이론의 개론에서 다룬다. 유한적인 샘플 공간 $\Omega$, $\Omega$에 대한 두개의 확률분포 $p$와 $q$를 고려해 보자. 그렇다면, 쿨백-라이블러 발산 혹은 KL발산은 다음과 같이 정의 된다: $KL(p, q) = \sum_{x \in \Omega} p(x) ln \frac{p(x)}{q(x)} = \mathbb{p} [ln \frac{p(x)}{q(x)}]$. 이는 두가지 분포의 거리를 표기하는 방법이다. 이 속성은 양수이며, $p=q$일때 0이고, $p$와 $q$가 가깝다면 작아지는..

하계 (Lower Bounds) 이번 챕터는 밴딧 알고리즘이 할 수 없는 일들에 대해서 다룬다. 우리는 지난 챕터에서 다룬 후회값 비율이 가능한 최적이라는 것을 내포하는 두가지의 근본적인 결과를 보여준다. 우리는 다른 어떠한 밴딧 알고리즘도 더 좋은 후회값을 얻지 못하는, 즉 모든 밴딧 알고리즘들에 적용 가능한 하계(lower bound)에 대해 관심이 있다. 우리는 이번 챕터를 전반적으로 $\Omega(\sqrt{KT})$ 하계를 증명하는데 사용한다. 그리고 우리는 종속적인 하계 $\Omega(log T)$를 정의하고 이것에 대해 다룬다. 이러한 하계값들은 어떠한 상계값이 얻을 수 있는 최적의 값인지에 대한 감각을 심어준다. $\Omega(\sqrt{KT})$의 하계는 다음과 같이 명시한다: Theor..

확률적 밴딧 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..

확률적 밴딧 1.4 초기 정보를 가진 밴딧 문제에 대한 정보가 알고리즘에게 먼저 알려질 수 있고, 이는 알고리즘의 성능을 개선하기 위해 사용될 수 있다. 이러한 "초기 정보"는 평균 보상 벡터 $\mu$에 큰 도움을 준다. 초기 정보를 부여하기 위한 두가지 일반적인 방법이 있다: $\mu$에게 "얌전함"(well-behaved)을 강요하는 것, 그리고 베이지안(Bayesian) 사전 확률을 부여하는 것이다. 중요한 후회 범위를 가지는 어떤 모델들은 슬롯의 숫자에 영향을 받지 않고, 따라서 무수히 많은 슬롯을 수용할 수 있다. $\mu$에 얌전함을 강요하는 것 정석적인 모델은 다음과 같다. 슬롯은 $\mathbb{R}^d$ 내의 포인트들과 일치한다. 우리는 $\mu$를 각 슬롯을 알맞는 평균 보상에 연결하..

확률적 밴딧 1.3 적응적 탐색 탐색-우선 기법과 입실론-그리디 기법 모두 탐색 스케쥴이 관측된 보상의 기록과는 관계 없다는 큰 결점이 존재한다. 하지만 탐색시에는 관측된 보상에 적응적으로 대응하는 것이 보통은 더 좋은 결과를 낸다. 비공식적으로, 우리는 "적응적"과 "비적응적" 탐색으로 분리한다. 이번 챕터에서 우리는 적응적 탐색을 구현하고 더 나은 에이전트를 얻기 위한 두가지 알고리즘을 소개한다. $K = 2$의 경우부터 시작해보자. 한가지 자연스로운 아이디어는 둘 중 하나의 슬롯이 다른 슬롯보다 더 월등하다는 것을 찾을때 까지 하나씩 번갈아하며 선택하는 방법이다. 하지만 우리는 어떻게 하나의 슬롯이 다른 슬롯보다 월등하다는 것을 정확하게 정의할 수 있을까? 1.3.1 완전이벤트와 신뢰범위 이전에 다..

확률적 밴딧 1.2 균등한 탐색 간단한 아이디어로부터 시작한다: 이전에 관측된 결과가 무엇이든 슬롯을 균등하게(같은 비율로) 탐색(explore)하고, 경험적으로 최적의 슬롯을 활용(exploit)한다. "탐색-우선"으로 알려진 이 알고리즘은 첫 라운드 들을 탐색에 집중하게 하고, 나머지 라운드들을 활용에 사용한다. 알고리즘 1.1: 매개변수 N을 사용한 탐색-우선 알고리즘 1. 탐색 단계: 각 슬롯을 $N$번 선택에 시도한다; 2. 가장 높은 평균 보상을 주는 슬롯 $\hat{a}$를 선택한다 (동점시에는 임의의 선택을 따른다); 3. 활용 단계: 슬롯 $\hat{a}$를 나머지 모든 라운드에 사용한다. 매개변수 $N$은 미리 선정된 값이다. 추후에 이 값은 시간수평선 $T$와 슬롯의 수 $K$의 함수..

확률적 밴딧 이 챕터는 가장 기본적인 형태의 멀티암드밴딧인 IID(identically independently distributed, 독립적이고 동일하게 분포된)의 보상을 가진 밴딧에 대해 다룬다. 우리는 몇가지의 알고리즘을 소개하고, 해당 알고리즘들의 성능을 후회값(regret)으로 분석한다. 이 챕터에서 소개된 개념들은 기본적인 모델에 이어 이 책의 모든 부분에 적용된다. 1.1 모델과 예제 우리는 확률적 밴딧(stochastic bandits)이라 불리는, IID의 보상을 가진 기본적인 모델을 살펴본다. 이 알고리즘은 알고있는 숫자 $K$와 $T$에 대해 $T$개의 라운드 동안 $K$개의 가능한 행동(arm, 슬롯)이 선택 가능하도록 주어진다. 각 라운드에서 이 알고리즘은 어떤 슬롯에서 보상을 수..