MAB란

• reward를 최대화하기 위해 매 시간마다 최선의 Action을 찾는 방법

Exploration과 Exploitation

• Exploration(탐색) : 더 많은 정보를 얻기 위해 새로운 Arm을 탐색하는 것

• Exploitation(활용) : 기존의 경험을 토대로 가장 좋은 Arm을 선택하는 것

  → 탐색 높 & 활용 낮 : 높은 reward를 얻을 수 없음

  → 탐색 낮 & 활용 높 : 잘못된 arm을 활용할 경우 높은 reward를 보장할 수 없음

Simplie Average Greedy 알고리즘

• 간단히 말해서, 지금까지 평균 리워드가 최대인 Action을 선택하는 것(greedy)
  • $\frac{(해당 action이)얻은 reward의 합}{시도한 횟수}$
• 문제점 : Exploration이 부족

Epsilon-Greedy 알고리즘

• 특정 확률(하이퍼파라미터) 에 해당하면 greedy(exploitation)를 사용하고, 해당하지 않으면 랜덤 선택(exploration)을 하는 것
• 문제점 : 데이터가 충분히 쌓인 후에도 계속해서 탐색을 하기 때문에, 후반에는 비교적 손해를 많이 보는 알고리즘

Upper Confidence Bound(UCB) 알고리즘

• Greedy term과 불확실성 term을 두고, 데이터가 충분히 쌓인 이후에는 Greedy를 사용하도록 한 것.

  • $Q_t(a)$ : 시간 t에서 액션 a에 대한 reward 추정치(simple average)
  • $N_t(a)$ : 지금까지의 관측값들 중에서 액션 a를 선택했던 횟수
  • $c$ : exploration을 조정하는 하이퍼파라미터

  → 자연스럽게 exploration에서 exploitation으로 policy가 넘어가게 됨

Thompson Sampling 알고리즘

• 주어진 k개의 action에 해당하는 확률분포(확률 변수가 특정한 값을 가질 확률을 나타내는 함수)를 구하는 문제이다.