Multi-Arm Bandit

설명

슬롯머신 투자를 최적화하기 위해 시작된 알고리즘

 

각 슬롯머신의 승률이 다르다는 경험적 사실을 바탕으로 시작.

각 슬롯머신마다 다른 reward를 고려했을 때, 1)어떤 슬롯을 2)어떤 순서로 당겨야 가장 많은 보상을 확보할 수 있는가

 

Exploration(탐색): 각 슬롯머신의 승률을 확인하는 과정

Exploitation(활용): 가장 높은 승률이 예상되는 슬롯머신을 선택해 arm(손잡이)를 당기는 과정

 

탐색-활용의 비율 조정에 따라 알고리즘이 나뉨

• Epsilon-Greedy
• Softmax
• UCB(Upper Confidence Bound)
• Thompson Sampling

 

사용 예시

[개인화 추천 서비스에서 사용]

 

장점 1) 실제 환경에서 목표를 학습할 수 있음

 MAB는 강화 학습 기반의 프레임워크로써, 에이전트가 실제 환경에서 직접 상호작용을 하며 피드백을 학습합니다. 즉, 추천 모델이 유저 u에게 아이템 i를 추천해 주고 그에 대한 실제 피드백을 관찰하며 모델을 업데이트합니다.
최적화하고자 하는 목표(Objective)가 클릭이라고 가정해보겠습니다.  이 경우 피드백으로 받게 되는 보상(Reward) r_u, i는 ‘유저 u에게 아이템 i를 추천해 줬을 때 그 추천 결과를 클릭하였는지’로 정의할 수 있습니다.
구현된 현실 추천 시스템에서 사용자에게 모델이 직접 추천을 하고 그에 대한 반응으로서의 피드백을 학습합니다.

↔ CF 모델의 경우 전체 서비스의 방대한 과거 데이터를 사용할 수 있다는 장점이 있지만, 개별 추천 행동(Action) 과는  무관하게 사용자의 이력(History)으로부터 선호도를 추출하고자 합니다. 
CF 모델은 학습할 경우에는 목적 함수(Objective Function)를 어떻게 설정하여야 할까요? 모델의 추천 결과를 사람에게 보여주고 이에 대한 반응(피드백)을 살펴볼 수 없기 때문에 ‘추천해 줬을 때 클릭을 하는지’를 직접적으로 최적화할 수는 없습니다. 그렇기 때문에 실제 목표도 잘 맞출 수 있도록 유도하는 대리 목표(Surrogate Objective)를 설정하게 됩니다.
 즉, 클릭을 많이 받는 추천 시스템을 만들고자 했을 때, 기존에 축적된 서비스 로그를 통해 y_u, i를 ‘유저 u가 아이템 i를 클릭한 적 있는지’와 같이 정의합니다. 그러면 모델 f(y_u,i|X)는 어떤 사용자가 해당 아이템을 소비했을 확률을 예측하고 소비하지 않은 아이템 중 확률 값이 높은 아이템을 추천합니다. 다시 말해, 대리 목표(Surrogate Objective)를 최적화함으로써 간접적으로 실제 목표(Real Objective) 또한 잘 맞추도록 학습되길 기대하는 것입니다. 
실제 시스템에서 행동(Action)에 대한 피드백을 취한 게 아닌, 과거 데이터로부터 정의한 대리 목표(Surrogate Objective)를 정답으로 학습한 모델의 경우, 실제 현업에서 해당 추천 시스템의 클릭률/구매율 등의 KPI를 최적화하고자 할 때에는 실제 목표(Real Objective)와 간극이 발생할 수밖에 없습니다. 

장점 2) 탐색을 통해 장기적 보상을 최적화해줄 수 있음

MAB는 T 번의 타임 스텝(Time Step) 동안 행동(Action)을 취하는 일종의 MDP(Markov Decision Process, 마르코프 결정 과정) 하에서 누적 보상(Reward)를 최대화할 수 있도록 설계된 알고리즘
탐색(Exploration)- 당장 현재 스텝(Step)에서 기대 보상(Reward)이 높지 않더라도 이후 미래의 보상을 높여줄 수 있다면 해당 행동을 선택 (사용자가 익숙하지 않지만 좋아할 수도 있는 새로운 아이템을 추천하기도 함)

↔ 전통적인 CF 프레임워크에서는 과거 데이터를 바탕으로 현재 가장 선호할 아이템만을 추천.
Only 활용(Exploitation)- 고정된 하나의 타임 프레임(Time Frame)을 가정하기 때문에 미래의 보상과 같은 개념은 없음 

장점 3) 실시간성

MAB 알고리즘의 또 다른 장점은, 사용자의 피드백이 실시간으로 모델에 적용되어 추천 결과에 나타난다는 것입니다. 이러한 실시간 업데이트는 사용자의 경험에 긍정적으로 작용하는 정성적 효과뿐만 아니라 실제 클릭률 지표에도 수치적으로 영향을 미칩니다. 

추천 결과를 보여주고 그에 대한 사용자의 피드백이 모델에 반영되어 다시 추천 결과에 나타나는 한 번의 루프(Loop)에 드는 시간이 얼마나 짧은지에 따라 실제 클릭률이 유의미하게 달라지며, 실험 결과 이러한 업데이트 소요 시간이 짧으면 짧을수록 클릭률도 올라갔습니다. 

 

참고: https://tech.kakao.com/2021/06/25/kakao-ai-recommendation-01/