Today I Learned

오늘 공부한 내용은 MAB!

---

MAB

Multi-Armed Bandit. 제한된 자원으로 최대의 보상을 얻기위한 의사결정 알고리즘

• MAB의 두가지 전략에는 Trade-off 관계가 있다.

1. 탐색(Exploration) : 아직 잘 모르는 선택지(새로운 arm)를 시도해보는 것
2. 활용(Exploitation) : 이미 알고있는 높은 보상(arm)의 선택지를 선택하는 것

• MAB공식

  $q_*(a) \doteq \mathbb{E}[R_t | A_t = a]$

  $t$ : 시점
  $A_t$ : t 시점에 play한 action
  $R_t$ : t시점에 받은 reward
  $q_*(a)$ : 액션 a에 따른 reward의 실제 기대값

• 목표 : t시점에서 $q_*(a)$에 대한 추정치 $Q_t(a)$를 정밀하게 추정하는 것
  추정 가치가 최대인 action을 greedy action이라 한다.

Greedy Algorithm

가장 기본적인 접근 방식. 현재까지 관측된 데이터를 바탕으로 가장 높은 보상을 주는 행동을 선택하는 단순한 전략

• 표본 평균을 사용해 각 선택지의 가치를 추정한다.

• 평균 reward가 최대인 action을 계속 선택한다. 그 선택지의 표본평균은 계속 갱신된다.

• 하지만 탐색(Exploration)이 부족해 처음에 뭘 선택하는지나, reward의 왜곡이 있을 수 있는 부분이 단점이다.

ε-greedy 알고리즘(epsilon)

MAB 문제에서 탐색(exploration)과 활용(exploitation)의 균형을 맞추기 위한 개선된 접근 방식

• ε(epsilon)의 확률로 무작위 탐색을 수행하고, 1-ε의 확률로 greedy action을 수행한다.
  ε는 하이퍼파라미터다.

• 단순하지만 탐색과 활용을 조화롭게 병행할 수 있다. 잘못된 전략에 영원히 고착되는 것을 방지할 수 있고, 구현이 간단하고 직관적이다.

• 그러나 충분히 탐색된 뒤에 수행되는 ε 확률의 탐색 과정은 불필요한 소모다.

UCB 알고리즘

Upper Confidence Bound. simple greedy에 불확실성을 고려한 방법.

• 공식

  $A_t = \arg\max_a \left[Q_t(a) + c\sqrt{\frac{\ln t}{N_t(a)}}\right]$

  $Q_t(a)$ : 행동 a의 현재까지의 평균 보상
  $c$ : 탐색을 조절하는 하이퍼파라미터
  $N_t(a)$ : 행동 a가 선택된 횟수

• Greedy Algorithm에 불확실성을 고려한 탐색을 넣은 방법으로, 충분한 탐색이 진행 된 뒤에는 뒷 항이 0이 되어 탐색을 더이상 진행하지 않고 활용의 단계로 효율적이게 넘어간다.

• 현재까지의 평균 보상은 활용 요소로, 불확실성 범위는 탐색 요소로 본다.

---

RecSys with Bandit

• 클릭이나 구매를 모델의 reward로 지정해서 최대화가 되는 방향으로 bandit 알고리즘을 적용하는 방법.

• 무거운 모델을 적용시키지 않아도 간단하게 CTR 같은 지표를 개선할 수 있다.

• 클릭이나 구매를 1/0의 reward로 설정하고, item은 MAB의 action에 매칭시키는 방향으로 recsys에 적용한다.
  탐색은 유저의 취향 탐색이나 추천 풀 확장, 활용은 유저 취향에 맞는 아이템 추천.

• 유저별로 모든 아이템의 탐색을 하는 것은 불가능하다. 그래서 클러스터링을 통해 비슷한 유저끼리 그룹화 한 뒤 그룹 내에서 bandit을 구축한다. 아이템에 대해서도 유사도를 구해서 아이템에 대한 bandit을 만들수도 있다.

Thompson sampling

각 행동(arm)의 보상 확률에 대한 믿음을 확률 분포로 표현하고, 이를 점진적으로 업데이트하는 방식으로 작동하는 알고리즘

• 주로 확률분포로 베타 분포를 사용한다. 클릭할 확률 알파, 클릭 안할 확률 베타.

• 어느 정도수준까지는 랜덤하게 노출을 시켜서 각각의 베타 분포를 추정하고, 그 베타 분포에서 샘플링해서 계속 베타 분포를 업데이트하고 분포가 수렴할 때까지 반복하는 방식

• 확률분포에 따라서 탐색과 활용이 자연스럽게 균형을 이룬다.

LinUCB

컨텍스트 정보를 활용하는 MAB 알고리즘

• contextual bandit : 유저의 context에 따라 동일한 액션에도 다른 reward를 가진다.
  ()s context-free bancit

• 각 행동(arm)의 보상을 선형 함수로 모델링하며, 컨텍스트 정보를 활용하여 개인화된 추천을 제공한다.

• 공식

  $a_t = \arg\max_a [x_{t,a}^T\theta_a + \alpha\sqrt{x_{t,a}^T(D_a^TD_a + I_d)^{-1}x_{t,a}}]$

  $x_{t,a}$: t 시점의 컨텍스트 벡터
  $θ_a$: 행동 a에 대한 학습 파라미터
  $D_a$: 학습 데이터 행렬
  $α$: 탐색을 조절하는 파라미터

• 공식에서 + 앞부분은 활용, 뒷부분은 탐색. 탐색부분은 시간이 지날수록 0에 수렴.

• context 벡터와 같은 차원의 각 action에 대한 학습 파라미터 $θ_a$가 구해진다.

• 장점
  컨텍스트 정보를 활용한 개인화 추천 가능
  선형 모델의 단순성과 해석 가능성
  실시간 학습 및 적용 가능

• 아이템이 너무 많으면 학습이 힘들기 때문에 인기도 기반 같은걸로 필터링 후 돌리기도 한다.