Multi-Armed Bandit

#Multi-Armed-Bandit

목차

  • Epsilon Greedy
  • Optimistic Initial Values
  • UCB1 (Upper Confidence Bound 1)
  • Thompson Sampling
  • 알고리즘 비교

Multi-Armed Bandit 문제

  • 3개의 슬롯 머신있는데 돌릴 때마다 돈이 든다고 하고 각 기계의 당첨 확률은 다음과 같다
  • 1번 기계: 30% 확률로 당첨
  • 2번 기계: 20% 확률로 당첨
  • 3번 기계: 10% 확률로 당첨
  • 두 개의 기계로 3번씩만 해봤을 때 어떤 기계는 3번 전부 당첨, 다른 기계는 0번 당첨
  • 그러면 1번째 기계가 더 좋은걸까?

Explore-Exploit Deilema

  • 첫 번째 기계가 좋았으니 첫 번째 기계를 더 돌려볼까? (Exploit, 일종의 몰빵)
  • 첫 번째 기계가 좋았던게 운일 수도 있으니 모든 기계를 랜덤으로 돌려 데이터를 더 모을까? (Explore)
  • Explore를 할 수록 정확한 정보를 얻을 수 있지만 비용이 많이 들음
  • 좋은 기계에 가능하면 Exploit하고 싶음

A/B Test에의 응용

  • A 광고와 B 광고 중 어떤 광고가 좋은 광고인지 알고 싶음
  • 하지만 광고 기록 데이터를 수집할 때 마다 비용이 생김 (서버 관리, 시간 등)
  • 몇 시간 지켜보니까 A가 좋아보이니까 A 광고를 계속 실는게 좋지 않을까?
  • 하지만 A가 일시적으로 좋은 것일 수 있으니까 비용을 들여서라도 조금 더 지켜보는게 좋지 않을까?

1. Epsilon Greedy

#1.-Epsilon-Greedy

특정 확률에 따라 랜덤 하게 A나 B를 보거나, 가장 결과가 좋았던 광고를 탐색할지 선택

1) 0에서 1 사이에 매우 작은 epsilon 지정 (exploration 확률)

2) @@0@@

3) @@1@@=> 광고를 랜덤하게 보여줌

4) @@2@@=> 가장 좋았던 광고 보여줌

  • 즉 epsilon 확률로 랜덤하게 보여줄지 가장 좋은거를 보여줄지 선택하는 알고리즘
  • 10%의 확률을 탐색하는데 사용
  • 그렇다면 @@0@@일 때 가장 좋았던 광고는 어떻게 평가할까?
  • 기계의 당첨됐던 평균 @@0@@ 이용
  • 하지만 평균을 그냥 계산하면 모든 관측 값들을 이용해야 되서 비효율적
  • @@1@@: 현재 관측 값과 과거 관측 값의 가중평균 이용

@@0@@에 따라 수렴 속도나 정확성이 다를까?

실험 설계

  • @@1@@로 다르게 설정하여
  • 기계 1의 보상: @@2@@에서 랜덤하게
  • 기계 2의 보상: @@3@@에서 랜덤하게
  • 기계 3의 보상: @@4@@에서 랜덤하게
  • 기계의 보상이 같기 때문에 3번 기계를 계속 선택하는 것이 합리적인 상황
Loading output library...
Loading output library...
  • x축은 시행 횟수, y축은 평균 보상(당첨)
  • 탐색 비용이 가장 높은 @@0@@이 초반 부터 평균 보상이 가장 높고 수렴도 거의 가장 빠름
  • 탐색 비용이 가장 낮은 @@1@@이 초반 부터 평균 보상이 가장 낮고 수렴도 거의 가장 느림
  • 수렴한 이후 부터는 탐색 비용이 낮을 수록 보상이 높아짐
  • seed에 따라 달라지는 경우도 있지만 대체로 이러한 경향을 보임

=> 탐색 비용이 높을 수록 초반 보상이 높지만 나중에 가서는 손해

문제점

  • 계속 시행하다가 광고 A가 B보다 훨씬 좋은 것을 알게 되도 같은 행동 반복
  • A에서 Click을 했을 때 보상이 1, 아닐 때 0이라고 하면 N번 시행 후 보상은 @@0@@로 N보다 낮음
  • 만약 epsilon=0.1이라고 하면 보상은 0.95N

2. Optimistic Initial Values

#2.-Optimistic-Initial-Values

만약 모든 기계의 보상이 10보다 작은 것을 알 때는?

  • 초기 값을 높게 잡으면 진행하면서 점점 작아져서 수렴을 잘할 것 (낙관적 초기값 설정)
  • 만약 실제 평균이 1로 낮다면 => exploitation을 통해 진짜 평균 값으로 낮아질 것
  • 만약 다른 기계들을 충분히 탐색하지 않았다면=> 평균 보상이 여전히 높아 더 많은 탐색을 하게 됨
  • Epsilon의 설정이 필요 없음

알고리즘

1) A,B,C는 각각 10으로 설정

2) 3개 중 하나를 땡김

3) 만약 B가 선택 되었고 보상이 없었음 => B=5로 낮아짐

4) A,C는 10으로 가장 높기 때문에 둘 중 하나를 땡김

5) 만약 A가 선택 되었고 보상이 2였음 => A=6으로 낮아짐

6) 이제 C가 제일 높기 때문에 C를 땡김

7) 이 과정 계속 반복

Loading output library...
Loading output library...

3. UCB1 (Upper Confidence Bound 1)

#3.-UCB1-(Upper-Confidence-Bound-1)

샘플이 너무 적으면 신뢰 구간이 넓어짐 (기각을 못함)

  • 더 타이트한 Upper bound가 있을 때 최대 승률에 대한 확신을 갖게 됨

__Chernoff-Hoeffding bound))

  • 정규 분포의 신뢰구간 보다 더 타이트함
  • @@0@@ 일때 @@1@@ 은 항상 성립 (부등호 반대도 성립)
  • 전개 하면 @@2@@
  • Upper bound에만 관심
  • 샘플이 많아질 수록 신뢰구간이 지수적으로 감소

@@0@@

  • @@1@@으로 설정
  • @@2@@
  • N은 게임을 지금까지 플레이한 총 횟수
  • @@3@@는 기계당 지금까지 플레이한 횟수

적용 방법

  • @@0@@보다 증가 속도가 작음 => 따라서 모든 신뢰 구간은 시행 횟수에 따라 줄어 들음
  • 큰데서 작은데로 점점 줄여간다는 점이 Optimistic Initial Value랑 비슷

Pseudo code

  • @@0@@
  • @@1@@
  • While True:
  • @@2@@

play arm @@3@@

  • update @@4@@
  • @@5@@
Loading output library...
Loading output library...
  • 수렴하면 거의 3의 값에 가까워짐

4. Thompson Sampling

#4.-Thompson-Sampling
  • Thompson Sampling은 베이지안 방법을 이용해 Multi-armed bandit 문제 해결
  • 각 기계의 사후 확률의 최대화 하는 샘플을 선택
  • 데이터가 들어올 수록 분포가 점차 업데이트 되어 자동적으로 exploration을 할지 exploitation을 할지 조절
  • Explore: 데이터가 적음 =>분포가 뚱뚱해짐=> 높은 값을 샘플링
  • Exploit: 데이터가 많아짐=> 분포가 얇아짐=> 실제 참 값 부근에서 샘플링

Bayesian A/B Testing

  • 데이터의 분포:@@0@@
  • 사전 분포:@@1@@
  • 사후 분포@@2@@

실험 설계

사후 분포에서 샘플링한 값이 높은 기계 업데이트

1) @@0@@를 샘플링

2) @@1@@: 가장 높은 확률의 샘플을 주는 기계

3) @@2@@: 기계 @@3@@로 게임

4) @@4@@

5) @@5@@

알고리즘 쉽게 이해하기

Bandit이 당첨 될 진짜 확률이 1번: 0.2, 2번:0.5,3번: 0.75라고 가정

1) @@0@@

2) @@1@@

3) 2번째 bandit이 가장 높으므로 2번째 bandit 당김

4) @@2@@

5) 담청 됨: X=1

6) 2번 사후 확률 업데이트: @@3@@

7) 이와 같은 과정 t=1부터 20000까지

Loading output library...
Loading output library...

결과

  • 5번 시뮬레이션: 1번,2번, 3번 모두 분산이 큼
  • 20번 시뮬레이션: 3번이 0.9정도 지점에서 치솟음
  • 50번 시뮬레이션: 1번은 가장 왼쪽에 있으면서 분산이 매우 높고 3번은 점점 뾰족 2번은 점점 뾰족하나 3번 보다 낮음
  • 500번 시뮬레이션: 3번이 심하게 뾰족하고 거의 0.8이 중심이 되고 1번이 가장 낮고 2번이 그 다음
  • 2000번 정도 했을 때 거의 정확해짐

결과 해석

  • 사후 분포가 데이터가 많아질 수록 점점 더 얇아짐 (분산이 작아짐) => 데이터가 많아질 수록 추정량에 대한 확신이 강해져서

수렴성 진단

  • CTR이 가장 좋은 bandit에 수렴할까?
Loading output library...
Loading output library...
  • 10,000번 정도 쯤에 가장 좋은 3번 bandit에 수렴

5. 비교

#5.-비교

4가지 방법 중에 어떤 것이 가장 뛰어날까?

  • 4가지 방법 모두 결국에는 수렴하지만 현실 문제에서는 얼마나 빨리 수렴하는지가 중요할 수 있음
  • Epsiolon Greedy 방법은 A가 B보다 훨씬 좋은 것을 알게 되도 같은 행동 반복하기 때문에 성능이 가장 안 좋음
  • @@0@@로 설정해 점차 작아지는 adaptive한 방법 사용
  • 진행할 수록 점차 4가지 방법 모두 큰 차이가 없음