[Day38] Bandit for Recommendation 10-1 : MAB 개요 & MAB 알고리즘 기초

Bandit은 강화학습에서 많이 사용되지만 구현방법이 간단하면서 좋은 성능을 보이기 때문에 추천시스템에서도 종종 사용한다.

Multi-Armed Bandit : MAB

One-Armed Bandit

=slot machine

한 번에 한 개의 slot machine의 arm을 당길 수 있고 그에 따른 보상을 받게 된다.

 

one-armed bandit을 여러 개로 늘린 문제가 multi-armed bandit이다.

카지노에 k개의 slot machine을 n번 플레이 할 수 있을 때 어떻게 하면 가장 큰 보상을 받을 수 있을까? 보상을 최대화하기 위해서 arm을 어떤 순서로 어떤 정책(policy)에 의해 당겨야하는지를 학습하는 알고리즘이다.

 

하지만 슬롯머신이 얼마의 확률로 reward를 주는지 정확히는 알 수 없다.

 

• Exploration(탐색)
  : 더 많은 정보를 얻기 위해서 새로운 arm을 선택하는 것
  다양한 슬롯머신을 당겨보며 정확한 예측값을 얻는 행위
  ->리워드를 많이 얻지는 못한다
• Exploitation
  : 기존의 경험이나 관측된 데이터를 가지고 가장 좋은 슬롯머신을 선택하는 것
  리워드가 높은 슬롯머신을 찾았을 때 그 슬롯머신만 당기는 행위
  ->탐색을 다 하지 않고 잘못해서 exploitation만 하게 될 경우에는 장기적으로 리워드는 적다.

그래서 exploration & exploitation Trade-off는 발생할 수 밖에 없다.

 

MAB Formula

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

 

• t
  time step = play number
  arm을 당기는 시간
• $A_t$
  action t
  t step에 내가 선택한 슬롯머신(=action)
• $R_t$
  $A_t$가 a일 때 얻는 리워드
• $q_*(A)$
  reward의 기대값
  이 값을 정확하게 추정하는 것이 중요한 문제이다.

$q_*(a)$를 정확하게 알고 있다면 $q_*(a)$가 가장 높은 action만 취하면 된다. 하지만 실제 reward에 대한 데이터들, true distribution이 없기 때문에 $q_*(a)$를 바로 구할 수 없다. 그래서 시간 t에서의 추정치인 $Q_{t}(a)$를 정의해서 최대한 $q_*(a)$와 비슷하게 구하는 것이 MAB의 목표이다. 

 

Greedy Action : time step마다 $Q_t (a)$를 계산하고 추정 가치가 최대인 action을 선택하는 것

 

greedy action을 선택하는 것이 exploitation이 될 것 이고, 다른 선택을 하게 된다면 exploration이 될 것이다.

 

 

MAB 알고리즘

Greedy Algorithm = Simple Average Method

단순하게 평균을 사용한다.

$$Q_t(a)\doteq \frac{\text{sum of rewards when a taken prior to t}}{\text{number of times a taken prior to t}} = \frac{\sum_{i=1}^{t-1}R_i\cdot 1_{A_i=a}}{\sum_{i=1}^{t-1} 1_{A_i=a}}$$

 

실제 기대값 $q_*(a)$을 가장 간단하게 추정하는 방식으로 표본 평균을 사용한다. 각각의 action에 대해서 관측된 reward의 평균값을 사용한다.

 

그 action을 수행한 전체 중에 얻은 보상 $\sum_{i=1}^{t-1}R_i\cdot 1_{A_i=a}$를 action을 수행한 횟수$\sum_{i=1}^{t-1} 1_{A_i=a}$로 나누어 평균 리워드$Q_t(a)$를 구한다. 

 

$Q_t(a)$를 구한 이후에 평균 리워드가 최대한 action을 계속해서 선택하는 것이 greedy이다. $Q_t(a)$는 time step마다 update되고, 표본 평균이 제일 높은 action을 계속해서 선택하는 것이 greedy이다.

$$ A_t = \arg\max_{a} Q_t(a)$$

argmax를 통해 $Q_t(a)$(표본평균) 중에서 최대를 고르고 그것을 $A_t$action을 선택하는 식이다. 

 

하지만 policy가 처음 선택될 때 action과 reward에 크게 영향을 받는다. 실제로는 reward가 굉장히 높은 action이지만 초반에 낮은 리워드가 주어졌을 때 선택될 기회를 잃게 된다. 충분한 exploration을 하지 못하게 되는 것이다.

 

Epsilon-Greedy Algorithm

exploration이 부족한 greedy algorithm의 policy를 수정해서 random exploration을 추가했다.

 

일정한 확률에 의해 랜덤으로 슬롯머신을 선택하게 강제한다.

$\epsilon$(epsilon)=0.5라고 하면 0.5의 확률로 지금까지 계산했던 greedy를 이용하던지 랜덤으로 선택하는지가 결정된다.

 

$$A_t=\left\{\begin{matrix}\underset{a}{\text{argmax}} Q_t(a) \quad \text{with probability } 1-\epsilon \\\text{a random action} \quad \text{with probability } \epsilon\end{matrix}\right.$$

 

epsilon greedy 알고리즘은 단순하면서도 강력하다. exploration과 exploitation을 항상 어느정도 보장한다. baseline으로 많이 사용된다. 하지만 time step이 많이 지나고 데이터가 충분히 쌓여서 각 action에 true distribution을 충분히 추정해도 계속 랜덤하게 선택하기 때문에 후반으로 가면 손해를 본다.

 

UCB : Upper Confidence Bound

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

• $Q_t(a)$
  표본 평균
  greedy algorithm 에서의 simple average
• $t$
  time step
• $N_t(a)$
  지금까지의 관측에서 해당 action a가 선택됬던 횟수
• c
  불확실성 term을 얼마나 크게할지 작게할지 조정하는 하이퍼 파라미터

UCB는 greedy algorithm에 하나의 term을 더 추가해서 exploration이 잘 되도록 했다. 해당 action이 최적의 action이 될 수도 있을 불확실성을 표현했다. action a가 선택됬던 횟수가 적어서 데이터가 부족한 경우에는 분모의 값이 낮으면 불확실성 term이 커져서 그 action이 선택될 확률이 높아진다. 즉, 적게 탐색했던 action을 시도해 볼 수 있는 것이다. 나중에 모든 action이 충분히 탐색된 이후에는 $N_t(a)$값은 모두 높을 것이고, t는 로그 함수여서 증가폭이 줄어들기 때문에  불확실성 term이 0으로 수렴하게 되고, 데이터가 충분히 모인 상태에서 지금까지 구해진 $Q_t(a)$으로 최종 exploitation을 수행하게 된다.

 

MAB 알고리즘의 파라미터 튜닝

Reinforcement Learning: An Introduction –Second edition, in progress

UCB가 일반적인 MAB상황에서 기대 reward가 높다. 하지만 bandit알고리즘에 튜닝해야할 파라미터가 있다. epsilon-greedy알고리즘은 epsilon을, UCB는 c를 조절해야하는데, 그에 따른 그래프를 보면 모두 거꾸로된 U자형을 그리고 있다. MAB의 최적의 policy를 찾기 위해서는 적절한 하이퍼 파라미터를 찾고, exploitation과 exploration도 trade-off가 잘 된 optimal한 point를 찾아야 한다.

 

더 심화된 알고리즘은 다음 글에서 소개한다.

[Day38] Bandit for Recommendation 10-2 : MAB 알고리즘 심화 : Thompson Samling, LinUCB

MAB를 이용한 추천 시스템

MAB를 추천시스템에 어떻게 활용될까

1. 유저에게 아이템별 선호도를 계산해서 Top-N개의 아이템을 추천
2. 주어진 아이템과 유사한 아이템을 추천 

과 같은 기존의 추천 시스템 방식을 MAB에서는 사용하지 않는다. 평점, 유사도도 사용하지 않는다.

 

추천을 통해서 최종적으로 얻어지는 클릭이나 구매를 모델의 reward로 두고 reward가 최대화되는 방향으로 MAB알고리즘을 학습한다. 그래서 무거운 추천 프로그램을 사용하지 않고 간단한 bandit 기법을 적용해도 결국 우리가 원하는 온라인 지표(CTR,CVR)가 좋아진다.

 

기존 recommendation system	MAB
아이템을 추천한다	개별 action
유저에게 아이템을 추천하는 방식	policy
item을 추천했을 때, 클릭 여부	reward
지속적으로 변화하는 유저의 취향 탐색, 새로운 추천 아이템이 들어왔을 때 아이템의 정보를 얻는 것	exploration
탐색이 끝난 이후 유저의 취향에 가장 적합한 아이템을 계속해서 추천하는 것	exploitation

로 대응시켜서 구현할 수 있다. 그동안의 추천 시스템보다 훨씬 구현도 간단하기도하고 이해하기도 쉽다. 실제 비즈니스 앱에서도 원하는 클릭을 직접 향상시키는 쪽으로 알고리즘이 학습되어 유용하다.

 

유저 추천

유저에게 아이템을 추천한다고 헀을 때, 개별 유저 한 명 한 명에 대해서 모든 아이템의 bandit을 구하는 것은 불가능하다. 개인별로 수집되는 데이터는 한계가 있고 bandit도 수렴하지 않을 것이다. 따라서 클러스터링을 통해 유저를 그룹화해서 그룹별로 bandit을 구축하는 방법을 사용한다. 유저 클러스터 별로 아이템 후보 리스트를 인기도 기반이나 CF등의 방법으로 생성한다.

필요한 Bandit의 개수 = 유저 클러스터 개수 x 후보 아이템 개수(=아이템 후보 리스트의 길이)

유사 아이템 추천

유사한 아이템을 추천하려면 어떻게 해야할까?

주어진 아이템과 유사한 후보 아이템 리스트를 생성하고 그 안에서 bandit을 적용한다.

 

유사한 아이템을 추출하기 위해서 MF,Item2Vec, content-based 유사도를 사용해서 후보 아이템을 찾는다.

필요한 bandit의 개수 = 주어진 아이템 개수 x 후보 아이템 갯수

서비스와 적용방식에 맞게 후보 아이템 리스트를 뽑고 bandit을 적용할 수 있다.