• MAB(Multi Armed Bandit) 의미
    • 수익률이 각기 다른 N개의 슬롯머신(Bandit) 존재하며, 슬롯머신의 수익률을 알지 못 하는 상태
    • 이 때 어떤 슬롯머신의 손잡이(arm)를 내려야 수익이 극대화되는지를 푸는 문제

 

  • MAB의 핵심은 Exploration과 Exploitation의 trade-off
    • Exploration : 더 높은 보상을 얻을 수 있는 지점을 찾기 위해 새로운 시도를 해보는 것
    • Exploitation : 현재까지의 경험 중 현 상태에서 최대의 보상을 얻을 수 있는 행동을 하는 것
    • Exploration과 Exploitation을 적절히 사용해야 최적점에 도달 가능

 

  • MAB 알고리즘 
    • 1. Greedy Algorithm
      • 로직
        • 현재 시점에서 보상을 극대화하는 행동을 취함
        • (예) 현재 시점에서 클릭 확률이 가장 높은 광고 노출
      • 특징
        • Exploitation에 치우쳐진 알고리즘
        • 새로운 최적점 발견하는데 오랜 시간이 걸림
    • 2. Epsilon(ε) Greedy Algorithm
      • 로직
        • 1-ε의 확률로는 Greedy Algorithm 수행 (Exploitation)
        • ε의 확률로는 랜덤 (Exploration)
      • 특징
        • 최적의 행동을 찾은 경우에도 ε의 확률만큼은 랜덤하게 행동하므로 최적값과 멀어질 수 있음
    • 3. UCB(Upper Confidence Bound)
      • 로직
        • 각 행동을 취했을 때 구해지는 보상에 대한 신뢰구간의 upper-bound 값을 이용하여 최적 행동을 결정
          •  
          • 현재 시점까지의 행동수(N_t(a))가 작을수록 upper-bound 상승 (exploration)
          • 기대보상(Q_t(a))이 클수록 uppder-bound 상승 (exploitation)
      • 특징
        • 결정론적 알고리즘(deterministic)
          • 보상에 대한 신뢰구간의 upper-bound값에 따라 행동이 결정됨
        • 단순히 Random Exploration을 하지 않고, 최적이 될 수 있을만한 쪽으로 Exploration 진행
          • ε-greedy 알고리즘 대비 효율적으로 탐색 진행
    • 4. Thompson Sampling
      • 로직

        • 모수에 대해 사전분포 정의 후, 관측된 값으로부터 사후 분포 유도
          • 1. 사전분포 가정
            • (예) 광고 : Beta(클릭수+1, 비클릭수+1)
              • 이전에 노출된 적이 없는 광고에 대해서는 Beta(1, 1) 분포 가정 (=uniform(0, 1) 분포와 동일)
          • 2. 각각의 사전분포에서 샘플링 수행 (Exploration & Exploitation 동시 수행)
          • 3. 샘플링 된 값에서 가장 큰 값을 보인 행동을 취함
          • 4. 행동에 대한 반응을 이용하여 사후 분포 업데이트
            • 해당 광고 클릭시 : Beta(ɑ, β) → Beta(ɑ+1, β)
            • 해당 광고 비클릭시 : Beta(ɑ, β) → Beta(ɑ, β+1)
          • 5. 위의 과정 반복
    • 예시 
      • Thomson Sampling을 통해 추천 알고리즘 설계한다고 가정
      • 1. 개별 상품의 클릭 확률에 대해 사전분포 가정
        • 어떤 상품을 클릭할 확률이 베타분포를 따른다고 가정
        • 이전에 노출된 적이 있는 상품에 대해서는 Beta(클릭수+1, 비클릭수+1) 분포 가정
        • 이전에 노출된 적이 없는 상품에 대해서는 Beta(1, 1) 분포 가정 (=uniform(0, 1) 분포 가정하는 것과 동일)
      • 2. 가정한 사전분포에서 랜덤 샘플링 수행
        • 클릭 확률에 대해 가정된 사전분포로부터 랜덤 샘플링 수행
        • 상품이 N개 존재한다면, N개의 랜덤 샘플링 값 나오게 되는 것
      • 3. 샘플링된 값에서 가장 큰 값을 보인 상품을 추천
        • A라는 상품에서 샘플링된 값이 가장 큰 값을 보였을 경우 A라는 상품을 추천 상품으로 노출
      • 4. 추천에 대한 반응을 이용하여 해당 상품의 클릭 확률에 대한 사후 분포 업데이트
        • 유저가 추천 상품을 클릭한 경우 : Beta(ɑ, β) → Beta(ɑ+1, β)
        • 유저가 추천 상품을 클릭하지 않은 경우 : Beta(ɑ, β) → Beta(ɑ, β+1)
      • 5. 위의 과정 반복
    • 특징
      • 베이지안 방법
      • 확률적 알고리즘(probabilistic)
        • 특정 분포에서 랜덤 샘플링 진행하여 행동 결정
      • 일반적으로 UCB보다 나은 성능을 보임 

 

저작자표시 비영리 변경금지

+ Recent posts

티스토리툴바