개발블로그

확률적 밴딧 이 증명은 정보이론(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.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, 슬롯)이 선택 가능하도록 주어진다. 각 라운드에서 이 알고리즘은 어떤 슬롯에서 보상을 수..