개발블로그

확률적 밴딧 이 증명은 정보이론(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$가 가깝다면 작아지는..

확률적 밴딧 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 완전이벤트와 신뢰범위 이전에 다..