【알고리즘】 23강. MAB(multi-armed bandits)

23강. MAB(multi-armed bandits)

 

추천글 : 【알고리즘】 알고리즘 목차

---

1. 개요 [본문]

2. UCB [본문]

3. thomson sampling [본문]

4. UCB와 thomson sampling의 비교 [본문]

---

 

1. 개요 [목차]

⑴ 문제 정의 : 가장 payoff가 높은 최적의 arm을 선택하는 것

⑵ 두 가지 전략의 trade-off

① exploitation : 현재 가지고 있는 데이터로부터 얻은 empirical mean을 가지고 reward를 극대화하는 것

② exploration : empirical mean이 true mean과 일치하도록 개선하는 것

③ 우연히 초기 데이터가 데이터의 진실한 분포와 다른 경우 exploration을 게을리 하면 잘못된 판단을 고칠 수 없음

⑶ 종류 1. Bayesian bandits

① 각 arm의 reward distribution에 대해 prior distribution이 주어져 있음

② 각 reward를 관측할 때마다 posterior를 얻게 됨

③ 관련 논문

○ Osband, Russo, and Van Roy 2013

○ Rusoo and Van Roy 2014, 2015, 2016

○ Bubeck and Liu 2013

④ 예시 : UCB

○ Thomson sampling과 함께 현존하는 전체 bandit 알고리즘 중 가장 많이 쓰이는 알고리즘

⑷ 종류 2. stochastic multi-armed bandit

① 특징 1. online decision : 각 시간 t = 1, ···, T에서 N개의 arm 중 i_t번째 arm을 선택

② 특징 2. stochastic feedback : 각각의 arm이 제공하는 보상은 정해져 있지만 알려져 있지 않은 분포를 따름

③ 특징 3. bandit feedback : 각 시간 단계에서 내가 선택한 arm에 대한 보상만 볼 수 있음

④ 목표 : 전체 T 단계에 걸친 cumulative expected rewards를 최대화하는 것

 

 

⑤ reward를 최대화하는 것은 regret = μ* - μ_t를 최소화하는 것과 동일함

 

 

⑥ bandit : 강도처럼 실패했을 때 뺏어간다는 의미

⑦ 예시 : Thomson sampling

○ UCB와 함께 현존하는 전체 bandit 알고리즘 중 가장 많이 쓰이는 알고리즘

 

 

2. UCB(upper confidence bound) [목차]

⑴ 수식화

① t까지의 시간 동안 arm i에서의 empirical mean

 

 

○ 분자 : arm i에서 얻어진 reward의 총합

○ I{i_s = i} : i_s = i인 경우에만 1을 출력하고 나머지는 0인 함수

○ n_i,t : t까지의 시간 동안 i가 뽑아진 횟수

② UCB(upper confidence bound)

 

 

○ optimism : 실제 기댓값보다 높은 확률로 더 높게 본다는 의미

○ 높은 확률 : 99.9% 이상

③ 각 단계에서 UCB가 최대인 arm을 선택

 

 

④ 매 시간 단계마다 empirical mean과 UCB를 업데이트

○ 한 번씩 관측할 때마다 uncertainty를 나타내는 UCB가 줄어듦

⑵ 수렴성 증명

① regret의 정의 : 임의의 시간 T에 대하여,

 

 

② 수렴성 : 수학적으로 엄밀하게 증명됨

 

 

③ 결론

○ per time regret은 0으로 수렴함 : 매 선택이 최선의 선택이 된다는 의미

○ UCB가 아니라 empirical mean을 가지고 하면 그러한 arm의 선택이 optimal하다는 보장이 없음

○ 즉, optimal arm을 한 번도 시도하지 않은 경우가 생김

 

 

3. Thomson sampling [목차]

⑴ 개요

① 가장 오래된 bandit 알고리즘 : thomson에 의해 1933년에 소개됨

② 자연스럽고 효율적인 휴리스틱 알고리즘

⑵ 알고리즘

① 각 arm에 대한 파라미터의 belief를 유지함 (예 : mean reward)

○ prior distribution은 Beta 분포, Gaussian 분포 등을 이용함

② 각 prior distribution으로부터 estimated reward를 추출

○ 단순한 샘플링을 의미하므로 기댓값을 추출하는 것이 아님

○ 관측값이 적으면 분산이 증가하는데 이 경우에 쉽게 추출될 수 있게 하기 위함

③ estimated reward가 최대인 arm을 선택하고 그 arm에 대한 posterior reward를 관찰

○ posterior distribution은 항상 연구자가 가지고 있어야 함

④ posterior를 Bayesian 방식에 대입하여 prior belief를 업데이트함

⑤ mode가 두 개여도 잘 working 함

⑶ 예시 : Beta 분포를 이용한 Thomson sampling

① 모든 arm에 대해 Beta(1, 1)을 prior belief로 하여 시작

② 각 시간 t에 대하여,

○ prior : Beta(α, β)

○ 각 arm에 대해 독립적으로 θ_i,t를 추출

○ i_t = argmax_i θ_i,t인 i_t를 선택

○ Beta(α+1, β) : 1을 관찰한 경우

○ Beta(α, β+1) : 0을 관찰한 경우

⑷ 예시 : Gaussian 분포를 이용한 Thomson sampling

① 모든 arm에 대해 N(0, ν²)을 prior belief로 하여 시작

② 각 시간 t에 대하여,

○ prior : N(0, ν²)

○ 각 arm에 대해 독립적으로 θ_i,t를 추출

○ i_t = argmax_i θ_i,t인 i_t를 선택

○ 그 arm에 대하여 empirical mean µˆ을 업데이트 (posterior) : 이때 n은 독립된 관측의 횟수 

 

 

⑸ 수렴성

① 일정 횟수 이후에는 두 arm 간의 well-separation이 결국 best arm을 만들도록 하게 됨

 

 

② Beta 분포

 

 

③ Gaussian 분포 : Azuma-Hoeffding inequality에 근거함

 

 

 

4. UCB와 Thomson sampling의 비교 [목차]

⑴ 공통점

① total regret은 O(log T) : per time regret은 O(log T / T)로 0으로 수렴함

⑵ 차이점

① thomson sampling이 많은 경우 UCB보다 좋음 : 즉, UCB는 조금 더 보수적인 알고리즘으로 조금 늦게 수렴함

② UCB는 deterministic하고 thomson sampling은 probabilistic (randomized)

 

입력: 2021.12.10 00:52