0. Abstract
강화학습에서 policy learning을 하는 동안, exp vs exp dillema에 빠지게 된다.
- empirically choose the best action
- explore the environment to find more profitable actions
MABP는 이 딜레마의 가장 간단한 예시이다.
Regret이 이 딜레마에서 인기있는 measure인데 optimal log regret을 찾는 알고리즘을 제안한다.
1. Introduction
K-armed bandit problem은
- 확률변수 $X_{i, n}$ for $1 \leq i \leq K \text { and } n \geq 1$ 로 이루어져 있고
- 이 때 $i$는 gambling machine의 index이고
- 머신 $i$의 연속적 플레이는 i.i.d. reward $X_{i, 1}, X_{i, 2}, \ldots$ 들의 값을 뱉는다.
- 머신들 간에도 독립적이다.
머신 $i$의 reward의 기댓값은 $\mu_i:= \mathbb E\left[X_i\right ]$으로 표기된다.
$A$ 는 이전의 플레이 기록과 보상들에 기반하여 다음의 머신을 선택하는 allocation strategy (policy으로도 불림) 이다.
- $T_i(n)$ 는 머신 $i$가 $n$회 동안 플레이된 횟수이다.
- Let $\Delta_{i} \stackrel{\text { def }}{=} \mu^{*}-\mu_{i}$
- Regret $R(n) = \sum_{s=1}^nX_{*, s}-\sum_{i=1}^K\sum_{s=1}^{T_{i}(n)}X_{i,s}$
- Expected regret $\begin{aligned}\mathbb E \left[R(n)\right]&=\mu^{*} n- \sum_{j=1}^{K} \mu_{j}\mathbb E\left[T_{j}(n) \right] \\ &=\sum_{j=1}^{K} \Delta_{j}\mathbb E\left[T_{j}(n) \right] \end{aligned}$ 는 policy $A$의 regret이다.
Regret은 best machine을 항상 플레이하지 못함에 따른 expected loss이다.
Lai and Robbins (1985)는 특정 reward distribution을 따르는 머신들에 대해 특정 policy가,
임을 보였다.
그래서 그 policy를 사용하면, optimal machine이 다른 머신들보다 exponentially 많이 실행된다는 것이다.
추가로, 어떤 $A$를 쓰더라도 임의의 머신 $j$에 대해 $\mathbb{E}\left[T_{j}(n)\right] \geq(\ln n) / KL\left(p_{j} | p^{*}\right)$ 임을 asymptotically 보였다.
결국 특정 policy가 optimal임을 보였다.
이에 대한 previous work이 있었는데 스킵하겠다.
이 논문에선 asymptotically가 아닌 모든 시간에 걸쳐서 regret이 log로 bounded됨을 보이겠다.
2. Main results
Theorem 1
If UCB1 is run on $K$ machines having arbitrary reward with support $\left[0,1 \right]$,
then its expected regret after $n$ plays is at most
증명을 하기 위해 알아야할 사실이 있다.
Fact 1 (Chernoff-Hoeffding bound)
Let $X_{1}, \ldots, X_{n}$ be i.i.d. random variables on $\left[0, 1\right]$ with $\mu = \mathbb E\left[X_i\right]$
Let $S_{n}=X_{1}+\cdots+X_{n}$
Then, for all $a \geq 0$,
(Proof)
Let $c_{t, s}=\sqrt{(2 \ln t) / s}$
Let $\ell$ be an arbitrary positive integer.
1번째 줄은 UCB1의 selection rule 때문이다.
2번째 줄의 $\leq$인 이유는 $\ell$회 미만으로 play될 때를 고려하여.
3번째 줄이 등식이 아닌 $\leq$인 이유는 선택 기준이 tie를 이룰 때를 대비.
4번째 줄은
- $i$ 머신을 $\ell \sim t-1$번 땡기게 된 경우와 최적머신을 $1\sim t-1$회 땡기게 된 경우를 동시에 고려해보자.
- 3번째 줄의 이벤트가 일어났을 때는 그 경우 중에 하나에 속할 것이다.
- 그 경우가 발생했었을 때의
- $i$ 머신의 선택 기준은 $\max _{\ell \leq s_{i}<t} \bar{X}_{i, s_{i}}+c_{t-1, s_{i}}$ 보단 작거나 같고
- 최적 머신의 선택 기준은 $\min _{0<s<t} \bar{X}_{s}^{*}+c_{t-1, s}$ 보단 크거나 같다
- 결론은 3번째 줄의 이벤트를 포함한다.
마지막 줄은 모든 이벤트를 포함시키려는 의도이다.
$\bar{X}_{s}^{*}+c_{t, s} \leq \bar{X}_{i, s_{i}}+c_{t, s_{i}}$은 세가지 사건 중 하나가 발생했음을 암시한다.
대우 명제로 확인
Chernoff-Hoeffding bound를 사용하여,
- $\mathbb{P}\left\{\bar{X}_{s}^{\star} \leq \mu^{\star}-c_{t, s}\right\} \leq e^{-4 \ln t}=t^{-4}$
- $\mathbb P\left\{\bar{X}_{i, s_{i}} \geq \mu_{i}+c_{t, s_{i}}\right\} \leq e^{-4 \ln t}=t^{-4}$
3번째 이벤트에 대한 확률은 임의의 양의 정수 $\ell (\leq s_i)$을 $(8 \ln n) / \Delta_{i}^{2}$보다 크게 잡을 때 0이 된다.
결국 $\ell= \left\lceil(8 \ln n) / \Delta_{i}^{2}\right]$에 대해서, $T_i(n)$의 부등식의 양변에 Expectation을 씌우면
Let $a_{n, r}=\sqrt{\frac{(1+\alpha) \ln (e n / \tau(r))}{2 \tau(r)}}$ where $\tau(r)=\left\lceil(1+\alpha)^{r}\right\rceil$
Theorem 2
For any $n \geq \max _{i: \mu_{i}<\mu^{*}} \frac{1}{2 \Delta_{i}^{2}}$
앞으로 증명은 일단 생략
필요하면 보강 예정
Bandit problem에서 간단하고 잘알려진 $\epsilon$-greedy rule이 있다.
$1-\epsilon$ 확률로 머신은 highest average reward를 실행하고 $\epsilon$ 확률로 랜덤하게 고른다.
Constant $\epsilon$은 $\log$가 아닌 $\mathbb E \left[R(n)\right] = O( n)$이다.
그래서 $\varepsilon_{n}$-GREEDY는 reward estimate이 정확해짐에 따라 $\epsilon \rightarrow 0$으로 보내는 방식으로 한다.
Theorem 3
If $0 < d \leq \min _{i: \mu_{i}<\mu^{*}} \Delta_{i}$, for $n \geq c K / d$
적당히 큰 $c > 5$가 주어졌을 때, 위의 bound는 $c /\left(d^{2} n\right)+o(1 / n)$이 된다.
이는 Theorem1과 Theorem2의 bound보다 좋은 bound가 된다.
하지만, $\min _{i: \mu_{i}<\mu^{*}} \Delta_{i}$이 무엇인 지 알아야 한다는 게 단점이다.
밴딧 머신들의 Reward의 분포가 normal distribution을 따르는 경우,
Theorem 4
Any $n > 0$,