[Boostcamp AI Tech] Bandit for Recommendation

1. Multi-Armed Bandit (MAB)

• k개의 슬롯머신에서 얻을 수 있는 reward의 확률이 모두 다르다고 가정.
• 수익을 최대화하힉 위해서는 arm을 순서대로 혹은 어떤 정책(policy)에 의해 당겨야 하는가?
• exploration(탐색): 더 많은 정보를 얻기 위해 새로운 arm을 선택.
  exploitation(활용): 기존의 경험 혹은 관측 값을 토대로 가장 좋은 arm을 선택하는 것.
• exploration과 exploitation 사이의 trade-off 발생.
• 유저 추천: 클러스터링을 통해 비슷한 유저끼리 그룹화한 뒤에 해당 그룹 내에서 bandit을 구축함.

 

2. MAB 알고리즘

1. Greedy Algorithm

• 실제 기대값의 가장 간단한 추정 방식으로 표본 평균을 사용.
• 가장 간단한 policy로서 평균 리워드가 최대인 action을 선택. -> exploration이 부족.

2. Epsilon-Greedy Algorithm

• exploration이 부족한 greedy algorithm의 policy를 수정.
• 일정한 확률에 의해 랜덤으로 슬롯머신을 선택. (심플하면서도 강력.)

3. Upper Confidence Bound (UCB)

• 해당 action이 최적의 action이 될 수도 있는 가능성 (불확실성) 추가

4. Thompson Sampling

• 주어진 k개의 action에 해당하는 확률 분포를 구하는 문제.