MAB를 활용한 최적화

MAB : Multi armed bandit이란 무엇인가?

최대 기대이익을 얻기 위해 "제한된 시간/자원"을 어떻게 분배(선택)하는지에 대한 알고리즘이다.

탐색/실험을 통해 기대이익을 찾아내고, 높은 기대이익을 주는 자원에 나머지를 집중적으로 배치시켜야 하는데 이를 동시에 진행해야 하는 "현실"의 trade-off문제 때문에 탐색과 착취(?)의 비율을 결정하는 문제로 간단하게 이해할 수 있음.

 

일정기간동안 샘플의 변화를 비교하고 최종 결과를 기반으로 가장 좋은 성능을 가진 옵션을 선택하는 방법이 AB테스트라면, MAB는 최소한의 탐색기간을 통해 얻어진 (성능)결과값에 비례해서 샘플크기를 조정하는 방법이다. 시간이 지남에 따라 성능이 각 옵션의 샘플크기를 작게 또는 크게 바꿀 수 있다. 즉, 각각  탐색만 하는 비교법과 탐색과 적용을 반복하는 비교법을 의미함.

think of the algorithm exploring at a rate of many visitors per second, arriving at constantly shifting winning baselines and continuously allocating the majority of your traffic dynamically to the variant that has the higher chance of winning at that instant (exploitation).

AB testing	MAB
목적 : 데이터 수집 및 분석결과를 해석하기 위해서	목적 : 타겟지표를 자동으로 최적화하기 위해서
언제 사용해야 할까? - 비즈니적인 중요한 결정을 해야 할 때 - 어떤 요소가 타겟지표에 영향을 주는지 알아야 할 때	언제 사용하나? - 결과해석할 필요 없을 때 (최적화 해야 할 때) - 통계적 유의성을 짧은 시간에 내야 할 때

언제 MAB를 사용할까?

1. 실험때문에 서비스(전환율)에 피해줄 가능성이 큰 경우

2. 시간에 민감한 서비스(실시간 클릭율)때문에 빠르게 최적화해야 하는 경우

short shelf life of news pieces means that quick optimization is essential. They optimize and test headlines, photo thumbnails, video thumbnails, recommended news articles, and popular articles to drive maximum clicks inside a short window.

3. 지속적인 최적화를 해야하는 경우

4. 실험표본(트래픽)을 얻는데 오랜 시간이 걸릴 경우

 

*언제 AB-testing을 해야 하나? ☝️ 

1. 통계적으로 robust한 결과를 얻고 싶을 때

2. 여러가지 목표지표에 대해 최적화를 해야 할 때
Mature experimentation teams track 4+ goals per experiment, as experiences are composite of primary and secondary goals. - MAB는 지표 하나만 최적화하는데 적합함.

3. 사후 실험분석을 해야 할 경우 
충분한 실험데이터가 있으면 분산분석도 해보고, 특정 변수를 기준으로 다중비교도 할 수 있다.
to check how different segments reacted to modifications on their web properties. 
- MAB는 지표 성과가 낮은 그룹variations의 데이터가 적게 수집되기 때문에 샘플차이로 비교분석할 수 없음.

4. 모든 비교군(실패한 옵션포함)을 통해 비즈니스 결정을 내려야 하는 경우 

 

MAB에 속하는 주요 알고리즘
- 어떤 알고리즘을 선택해야 할까?

The gambler iteratively plays one lever per round and observes the associated reward.
The objective is to maximize the sum of the collected rewards.

The bandit problem is formally equivalent to a one-state Markov decision process

 The regret(후회비율) after T rounds is defined as the expected difference between the reward sum associated with an optimal strategy and the sum of the collected rewards. 


A common formulation is the Binary multi-armed bandit or Bernoulli multi-armed bandit,
 which issues a reward of one with probability, and otherwise a reward of zero.
Or 각 arm 을 Markov machine으로 본다.

1. Optimal Solution - UCB

# Upper Confidence Bandits

2. Approximate Solutions - Greedy

# e-greedy

3. Approximate Solutions - Probability matching strategies

# Tompson Sampling ( Bayesian Bandit )

4. Approximate Solutions - Pricing strategies

5. 고급버전

- Contextual Bandit : 밴딧을 선택할 때의 외부환경(변수)을 고려하자. 

- Adversarial Bandit : 선택 밴딧의 이익과 비선택 밴딧의 불이익을 동시에 고려하기.

 

 

 

 

- 위키 : en.wikipedia.org/wiki/Multi-armed_bandit#The_multi-armed_bandit_model

-  AB testing 비교하기 : vwo.com/blog/multi-armed-bandit-algorithm/

-  이론적 소개 및 설명 : arxiv.org/pdf/1904.07272.pdf.  

-  AutoML활용하기? : cloud.google.com/blog/products/ai-machine-learning/how-to-build-better-contextual-bandits-machine-learning-models