18. Multi-Armed Badit with Recommend System

Multi-Armed Bandit  k개의 슬롯머신을 N번 플레이한다고 가정했을 때, 각 슬롯머신에서 얻을 수 있는 reward 확률이 모두 다름

    - 이때 수익을 최대화하기 위해서는 arm을 어떤 순서대로 혹은 어떤 정책(policy)를 수립하여 당겨야 하는가?

 

Exploration(탐색) : 더 많은 정보를 얻기 위하여  새로운 arm을 선택하는 행위

Exploitation(활용) : 기존 경험 혹은 관측 값을 토대로 가장 좋은 arm을 선택하는 행위

    - Exploration & Exploitation trade-off

 

이때 모든 action에 대한 reward의 분포도를 알 수 없으므로 추정을 통해 진행.

 

1. Greedy Algorithm(=simple average method)

    - timestep별로 각 arm 별 관측값을 토대로 표본 평균을 사용. 이후 가장 reward가 높은 action을 선택하는 것.

 

2. Epsilon-Greedy Algorithm

    - Exploration이 부족한 Greedy Algorithm의 policy를 수정한 전략

    - 일정확률에 의해 랜덤으로 슬롯머신을 선택하거나 greedy algorithm을 수행하거나!

 

3. Upper Confidence Bound(UCB)

 

 

4. LinUCB

    - Context : 유저의 데모그래픽이나 아이템의 카테고리,태그와 같은 여러 특성 정보

    - Contextual Bandit : 유저의 context 정보에 따라 동일한 action이더라도 다른 reward를 가짐.

 

Naver AiRS : 인기도 기반 필터링을 통해 탐색(Exploration) 대상을 축소한 뒤, Contextual Bandit 알고리즘을 통해 유저의 취향을 탐색 및 활용

 

 

 

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

 

Greedy Algorithm에 의해 노출시킨 배너를 선정한 후, reward에 따라 분포를 업데이트

    - 반복