Exploration vs. Exploitation Dilemma

• Online decision-making은 근본적인 선택을 포함한다.
  • Exploitation : 현재 정보를 바탕으로 제일 좋은 선택을 한다
  • Exploration : 더 많은 정보를 모은다.
• 이 2개를 잘 조절해야한다!

The Multi-Armed Bandit

• A multi-armed bandit은 <A,R>의 튜플이다.
  • One Step MDP
• 각 스텝 t마다 agnet가 action을 select한다$a_t\in A$
• 환경이 reward를 생성하고
• 목표는 cumulative reward r를 maximise하는것이다.

Regret

• action-value : mean reward for action a
  • $Q(a) = \mathbb{E}[r|a]$
• Optimal value =
  • $V^= Q(a^) = max_aQ(a)$
• regret은 기회손실 for one step
  • Action별로 정의되는 개념이다.
  • $l_t = \mathbb{E}[V^*-Q(a_t)]$
• total regret은 t=1 ~ t=t 까지 한 regret을 전부 더한것의 기댓값
• Maximise culuative reward = Minimise total regret
  • 축적된 리워드를 최대화하는것은 토탈 후회를 최소화 하는것.
  • 우리의 이해에 도움을 준다. 어떤 알고리즘이 가장 가능한 한 가장 잘 할 수 있는 한계가 어느정도인지

Counting Regret

• count $N_t(a)$ = action a를 몇번 할 것 같은지 기대값
• gap $\triangle_a$ = action a 마다 정의되는 Optiml action $a^*-Q(a)$이다.