[CS246] Bandits (1) - Problem Settings

Multi-Armed Bandit: Learning through Experimentation

세상에는 탐색을 통해 특정 전략을 수립할 필요가 있다.

구글 광고:

광고 수익을 최대화 하고 싶어한다. 과거에는 pay by impression(CPM) 전략을 사용했으나 광고 효과(effectiveness)는 알 수 없었다는 점이 문제였다. 현재는 pay per click(CPC) 전략을 사용하고 있으며 기대수익(expected revenue)를 찾는 것이 핵심이다.

query $q$에 대하여 광고 $a$의 기대수익은 다음과 같이 계산된다.

\[ E[\text{revenue}_{a, q}] = P(\text{click}_a | q) \cdot \text{amount}_{a,q} \]

$q$의 $a$의 입찰(bid)는 $\text{amount}_{a,q}$이며 이는 우리가 알고 있는 값이다.

문제는 user가 광고를 클릭할 확률을 알 수 없다는 것이 문제다. $P(\text{click}_a | q)$를 추정하기 위해서는 정보를 더 얻어야 한다.

 

임상실험

서로 다른 치료(treatment)에 대하여 부작용을 최소화하는 최적의 치료법을 조사해야한다.

 

적응적 라우팅 (Adaptive Routing)

다른 routing을 조사/탐색하면서 네트워크의 delay는 최소화해야한다.

 

이러한 문제들을 bandit이라는 관점으로 해결하고자 한다.

Multi-Armed Bandits

k-Armed Bandit

각 슬롯머신의 arm을 $a$라 하자. 각 $a$마다 $\mu_a$의 확률로 승리(reward=1)하고 $1-\mu_a$의 확률로 패배(reward=0)한다고 생각할 수 있다. $k$개의 arm이 있으므로 $\mu_1, \dots, \mu_k$가 존재하며 $k$개의 $\mu_a$는 당연히 unknown prob이다.

이때, 어떻게 arm을 당겨야 전체 보상의 최댓값을 구할 수 있을까? 

 

각 queary는 bandit, 광고는 arm 그리고 광고 CTR을 $\mu_a$로 대응시킨 문제와 동일하다.

매번 arm을 당기는 것은 'experiment'라고 부른다.

 

Stochastic k-Armed Bandit

Setting

• $k$개의 선택지가 존재한다. (arm)
• 각 선택 $a$는 미지의 확률 $P_a$와 연관되어 있고, $P_a \in [0, 1]$이다.
• 전체 $T$번의 게임이 주어진다.
• 각 $t$번째 라운드마다 arm $a$를 선택하고, random sample $X_t$를 $P_a$로부터 얻는다.
• Goal: maximize $\sum_{t=1}^{T}X_t$
• Problem: $\mu_a$는 알지 못한다. 각 라운드 $t$마나 $\mu_a$에 대한 약간의 정보를 얻을 수 있다.

 

Metric: Regret

bandit algorithm/strategy/rule 의 성능을 어떻게 평가할 수 있을까?

$\mu_a$를 $P_a$의 기대 보상(mean reward)라 하자. 그러면 best arm은 $\mu^* = \underset{a}{\max} \mu_a$ 이다.

$i_1, i_2, \dots, i_T$를 sequence of pulled arms라 하자. 그러면 $t$단계에서 regret은 $r_t = \mu^* - \mu_{i_t}$ 이다.

따라서 $T$까지의 regret의 총합은 다음과 같다.

\[ R_T = \sum_{t=1}^{T}r_t \]

 

Goal: 우리는 $T \to \infty$가 되면 $\cfrac{R_T}{T} \to 0$ 가 되는 policy/strategy를 원한다.

 

payoff($\mu_a$)을 알고있다면, 어떤 arm을 당겨야 하는가? → $\underset{a}{\text{argmax}} \mu_a$

payoff $\mu_a$를 추정하려면?

$k$개의 arm은 동일하게 $\frac{T}{k}$로 선택한다.

Estimate: $\widehat{\mu_a} = \cfrac{k}{T}\sum_{j=1}^{T/k}X_{a,j}$

Regret: $R_T = \cfrac{T}{k}\sum_{a=1}^{k}(\mu^* - \widehat{\mu_a})$

 

Exploration vs. Exploitation

간단하게 Greedy한 전략을 생각해보자.

2개의 action(arm) A1, A2 가 있다고 하자.

A1: 0.3의 확률로 reward=1

A2: 0.7의 확률로 reward=1

 

각각 한번씩 탐색하여 A1에서 1을, A2에서 0의 reward를 얻었다고 하자.

여기서 문제가 발생한다.

A1에서 이미 reward=1이기 때문에, A1에서 얻는 avg. reward는 절대로 0이 될 수 없다.

그러므로 A2를 다시는 선택하지 않게되는 문제가 발생한다. 

 

이런 상황은 decision making에서 발생하는 대표적인 문제(classic problem)이다.

즉, exploration과 exploitation간에 trade off가 존재한다.

exploration: arm으로부터 데이터를 얻는 것

exploitation: 지금까지 모은 데이터를 바탕으로 decision making을 하는 것 (e.g. pull an arm $a$)

 

따라서 greedy algorithm은 충분히 탐색하지 않는다.

또, greedy algorithm은 $\mu_a$의 추정치를 너무 확실하게 한다는 문제점이 있다. 위 예시에서 보듯이, A2에서 단 하나의 reward가 0이라 해서 앞으로도 계속 0으로 수렴하지는 않는다.

Greedy can converge to a suboptimal solution!

 

다음 포스팅에서는 이를 보완한 제대로 된 알고리즘을 살펴볼 것이다.

 

반응형