Multi Armed Bandit

MAB(Multi-armed bandit) 문제

  • 외팔이 강도가 우연한 기회로 눈 앞에 여러 개의 슬롯머신을 공짜로 H시간 동안 플레이 할 수 있는 기회를 얻었다고 생각해보자.

  • 강도는 한 번에 한 개의 슬롯머신의 arm만 당길 수 있으며 (즉 총 H번 시도할 수 있다) 각각의 슬롯머신에서 얻을 수 있는 reward는 다르다고 가정한다.

  • reward는 어떤 확률분포에 의해 출력되는 랜덤변수

  • 이 때, 강도가 가장 수익을 최대화하기 위해서는 arm을 어떤 순서대로, 어떤 policy대로 당겨야할까?

핵심 고려사항: 착취와 탐색(Exploitation and Exploration)

  • 이 문제에서 가장 큰 난점은, 슬롯머신마다 보상이 다르고, 한 번에 한 슬롯머신의 보상만 관측할 수 있다는 점임

  • 예를 들어 아래와 같이 전략을 수립할 수 있음

    • 한 슬롯머신을 골라서 계속 그 슬롯머신만 당기기

      → 다른 슬롯머신에서 더 좋은 보상을 얻었을 수도 있기 때문에 항시 가장 좋은 최적의 전략은 아님

    • 모든 슬롯머신을 동일한 횟수만큼 반복하여 당기기

      → 슬롯머신 중에서 최고의 보상을 보이는 머신이 존재하며, 이를 위주로 당겨야하므로 해당 방법 역시 가장 좋은 전략은 아님

  • 즉, 최적의 전략 수립을 위해서는 '현재보다 더 좋은 보상이 존재하는가?'를 알아보기 위해 다른 머신을 당겨보는 탐색(exploration)과, '가장 좋은 보상을 확보!'하기 위해 현재까지의 정보로부터 파악된 가장 좋은 머신을 선택하는 착취(exploitation)를 수행해야함.

  • 이 둘은 trade-off 관계에 있으므로 좋은 전략을 짜서 균형을 맞추는 것이 MAB 문제의 핵심임

Algorithm 1: ε-greedy algorithm

  • MAB 문제를 푸는 가장 대표적이면서도 간단하고 직관적인 알고리즘 중 하나

  • 0<=ε<=1으로 정의되며, ε의 확률로 탐색을, 1-ε의 확률로 착취를 선택함. 탐색시에는 랜덤한 머신을 채택함

  • 이 알고리즘의 단점은 아래와 같음

  • 시간이 많이 지나 최적의 머신이 무엇인지 알게 되었더라도, ε만큼의 확률로 불필요한 탐색을 수행함

  • ε의 확률로 탐색하는 과정 중 균일한 랜덤으로 머신을 선택하므로 한정된 시간동안 충분한 정보를 많이 얻게 되지 못하는 머신이 발생할 수 있음

Algorithm 2: Thompson sampling

MAB문제에서 강력한 성능을 보이는 톰슨 샘플링에 대해 소개하며, 기본적인 컨셉의 이해를 돕고자 함

베타분포

톰슨 샘플링을 알기위해 필수적인 사전 배경지식인 베타분포를 살펴봄

  • Probability density function (PDF)

    • 베타분포의 PDF는 아래 수식과 같음. 여기서 x는 성공확률을 의미하며, 기호 alpha는 성공횟수 + 1, 기호 beta는 실패횟수 + 1을 의미함.

    • 수식에서 B(alpha,beta) 베타함수이며, 감마함수(Gamma)로 연산됨. 여기서 베타함수의 역할은 PDF를 위해 전체 분포의 합이 1이 되도록 정규화 시키는 값임

    • 즉 베타분포는 alpha,beta에 결정되며, 변수 0<=x<=1의 범위에 대한 분포를 도시함

    • alpha, beta값이 커질수록 분산이 작은 종모양이 되며, alpha, beta값이 1보다 작은 경우 U자형을 띔

Beta(α,β)=f(x;α,β)=xα−1(1−x)β−1∫01uα−1(1−u)β−1du=xα−1(1−x)β−1B(α,β)=Γ(α+β)Γ(α)Γ(β)xα−1(1−x)β−1Beta(\alpha ,\beta ) = f(x;\alpha ,\beta ) = {{x^{\alpha - 1} (1 - x)^{\beta - 1} } \over {\int_0^1 {u^{\alpha - 1} (1 - u)^{\beta - 1} du} }} = {{x^{\alpha - 1} (1 - x)^{\beta - 1} } \over {B(\alpha ,\beta )}} = {{\Gamma (\alpha + \beta )} \over {\Gamma (\alpha )\Gamma (\beta )}}x^{\alpha - 1} (1 - x)^{\beta - 1}

베타분포 계산 사이트

  • 이항분포(binomial distribution)과의 비교

이항분포는 성공 횟수(x)를 모델링하는 반면, 베타분포는 성공확률(p)을 모델링함.

알고리즘 for MAB

확률분포가 Bernoulli distribution을 따른다고 할 때, 베타분포를 사용할 수 있으며, 이때 알고리즘은 아래와 같음. 아래 '예제'를 보면 이해에 도움이 될 것으로 보임.

예제: 광고 배너 시스템

  • 문제: 3개의 광고 배너(1/2/3번) 중 사람들의 이목을 끌기 위해서는 무슨 배너가 가장 좋은가?

  • 해결전략:

    1. 임의의 배너를 노출하고 그에따른 사용자의 클릭 성공/실패 여부를 저장

    2. 배너 별 Beta(성공횟수+1, 실패횟수+1)로 베타분포를 갱신

    3. Thompson sampling을 통한 MAB 문제 해결

Step 1. 아무런 데이터가 없는 상태 → 초기 확률분포 만들기

세 배너 모두 아무런 정보가 없던 상태에서부터 아래 3번의 step을 통해 초기 확률분포를 생성함

initial state
step 1-1
step 1-2
step 1-3

banner1

누적현황

노출0, 성공0, 실패0

노출1, 성공1, 실패0

노출2, 성공1, 실패1

노출3, 성공2, 실패1

베타분포

Beta(1,1)

Beta(2,1)

Beta(2,2)

Beta(3,2)

banner2

누적현황

노출0, 성공0, 실패0

노출1, 성공0, 실패1

노출2, 성공0, 실패2

노출3, 성공1, 실패2

베타분포

Beta(1,1)

Beta(1,2)

Beta(1,3)

Beta(2,3)

banner3

누적현황

노출0, 성공0, 실패0

노출0, 성공0, 실패0

노출1, 성공1, 실패0

노출2, 성공1, 실패1

베타분포

Beta(1,1)

Beta(1,1)

Beta(2,1)

Beta(2,2)

Step 2. 초기 확률분포 → Thompson sampling 적용하여 최적의 배너 찾기

각 배너로부터 성공확률을 샘플링하고 그 중 가장 높은 성공률을 보이는 배너를 채택함.

해당 배너 노출 및 그 결과로부터 분포 갱신하는 작업(step 2-0~4)을 반복

수많은 실험 후 어떤 배너가 사용자의 반응을 잘 이끌어내는지 결과(step 2-k)가 나옴 → 배너 3번이 가장 좋은 배너인 결과가 나옴

step 2-0
step 2-1
step 1-2
step 1-3
step 2-4

배너별 베타분포

banner1: Beta(3, 2) banner2: Beta(2, 3) banner3: Beta(2, 2)

banner1: Beta(3, 2) banner2: Beta(2, 3) banner3: Beta(3, 2)

banner1: Beta(3, 3) banner2: Beta(2, 3) banner3: Beta(3, 2)

banner1: Beta(4, 3) banner2: Beta(2, 3) banner3: Beta(3, 2)

banner1: Beta(4, 3) banner2: Beta(2, 3) banner3: Beta(4, 2)

샘플링 결과

banner1: [ 0.38695794] banner2: [ 0.43873433] banner3: [ 0.61692633]

banner1: [ 0.8606323] banner2: [ 0.07932551] banner3: [ 0.43033056]

banner1: [ 0.66165054] banner2: [ 0.36745788] banner3: [ 0.28561718]

banner1: [ 0.42296478] banner2: [ 0.18102569] banner3: [ 0.78204765]

banner1: [ 0.42437534] banner2: [ 0.48749753] banner3: [ 0.82210968]

노출배너/결과

banner3 → 클릭 O

banner1 → 클릭 X

banner1 → 클릭 O

banner3 → 클릭 O

banner3 → 클릭 O

PreviousHypothesis TestNextBayesian Inference

Last updated