개발블로그

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

강화학습 불확실성과 결정과정 (Uncertainty & Decision Process) 강화학습에서는 Trial-and-error를 통해서 여러차례 반복을 통해 학습을 하는 경우가 많다. 보통의 기계학습과는 다르게 에이전트가 놓여진 환경에서 스스로 학습 데이터를 만들어내고 학습한다. 처음보는 불확실한 환경속에서 에이전트는 여러 차례 시도를 통해 학습하는데, 이러한 프로세스를 불확실성(uncertainty) 속의 결정과정(decision making process) 라고 한다. K-armed bandit 문제 이러한 문제는 강화학습에서 종종 Bandit문제로 표현된다. Bandit이란 슬롯머신의 손잡이를 일컷는 말로, 각 슬롯머신 손잡이를 선택했을 때 각 손잡이를 당겼을 때 얻는 보상이 다를때의 상황을 이..