【알고리즘】 11-1강. Multi-armed Bandit (MAB)

11-1. Multi-armed Bandit (MAB)

 

추천글 : 【제어이론】 9강. 확률적 제어이론, 【알고리즘】 11강. 강화학습 

---

1. 개요 [본문]

2. ϵ-greedy exploration [본문]

3. UCB [본문]

4. 톰슨 샘플링 [본문]

---

 

1. 개요 [목차]

⑴ MAB(multi-armed bandits)

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

 

Figure 1. MAB

 

② 다음과 같은 상황에서 특히 필요

○ 목적 함수를 계산하기 어려운 경우 (black-box algorithm)

○ 명시적인 분석적 형태(analytic form)가 없는 경우

○ 특이값(singular value)이 존재하는 경우

○ 미분 가능하지 않은 경우

○ 데이터에 노이즈가 많은 경우 

⑵ 두 가지 전략의 trade-off

① 행동은 exploitation, exploration으로 구분할 수 있음

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

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

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

⑶ 종류 1. 베이지안 최적화(Bayesian optimization)

① Bayes' theorem

 

 

○ 각 arm의 reward distribution에 대해 사전 분포(prior distribution, surrogate model)이 주어져 있음

○ 주로 사용되는 prior 모델은 가우시안 프로세스

○ 각 reward를 관측할 때마다 사후 분포(posterior distribution)를 얻게 됨

② 획득함수 : 다음 보상이 극대화되도록 샘플링을 수행함 

 

 

○ 모든 획득 함수는 사후 분포를 기반으로 평균 μ(x)와 분산 σ2(x)을 계산하며, 이를 통해 탐색 전략을 설계

○ 종류 1. EI(expected improvement) : 다음 수식에서 EI(x)에 대한 두 번째 식은 가우시안 프로세스일 때만 성립함

○ 단, Φ와 𝜙는 표준정규분포의 CDF와 PDF이고 Z는 x를 표준화한 것

○ λ가 클수록 exploration을 더 많이 하게 됨

 

 

○ 종류 2. MPI(maximum probability of improvement)

 

 

○ 종류 3. UCB

 

 

③ 가우시안 프로세스(Gaussian process) : 베이지안 최적화 중 정규분포 가정을 하는 경우 

 

 

x <- c(-3, -1, 0, 2, 3)
f <- data.frame(x=x, y=cos(x))
x <- f$x
k_xx <- varCov(x,x)
k_xxs <- varCov(x, x_star)
k_xsx <- varCov(x_star, x)
k_xsxs <- varCov(x_star, x_star)

f_star_bar <- k_xsx %*% solve(k_xx)%*%f$y              # Mean
cov_f_star <- k_xsxs - k_xsx %*% solve(k_xx) %*% k_xxs # Var

plot_ly(type='scatter', mode="lines") %>%
  add_trace(x=x_star, y=f_star_bar, name="Function Estimate") %>%
  add_trace(x=x_star, y=f_star_bar-2*sqrt(diag(cov_f_star)), 
              name="Lower Confidence Band (Function Estimate)",
            line = list(width = 1, dash = 'dash')) %>%
  add_trace(x=x_star, y=f_star_bar+2*sqrt(diag(cov_f_star)), 
              name="Upper Confidence Band (Function Estimate)",
            line = list(width = 1, dash = 'dash')) %>%
  add_markers(x=f$x, y=f$y, name="Obs. Data", marker=list(size=20)) %>%
  add_trace(x=x_star, y=cos(x_star),line=list(width=5), name="True f()=cos(x)") %>%
  layout(title="Gaussian Process Simulation (5 observations)", legend = list(orientation='h'))

 

④ 하이퍼파라미터 최적화 

○ 최대 우도 추정(MLE)을 통해 주어진 데이터 X와 y가 발생할 확률(marginal likelihood)을 최대화하는 하이퍼파라미터를 탐색

○ marginal likelihood 및 가우시안 프로세스의 하이퍼파라미터는 다음과 같이 정의됨 

 

 

○ 장점 : underfitting 및 overfitting 개선 

⑷ 종류 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를 최소화하는 것과 동일함. 전체 K 단계에서의 regret은 다음과 같이 정의

 

 

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

⑦ 예 1. N개의 arm 중 n번 arm을 골랐을 때 belief state update 방정식

 

 

⑧ 예 2. Thomson sampling 

 

 

2. ϵ-greedy exploration [목차]

⑴ 과정 

① 단계 1. 맨 처음에는 arm을 모두 play

② 단계 2. (1 - ϵ)의 확률로 최대 표본평균 arm을 고르고 ϵ의 확률로 랜덤하게 arm을 선택

③ 단계 3. 각 arm 별로 표본평균을 업데이트하고 단계 2로 이동

⑵ 특징

① 전체 K 단계에서 regret R_K = Ο(K) : 매 스텝에서 ϵ만큼의 오차가 누적되므로 

 

 

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

⑴ 개요

① 톰슨 샘플링과 함께 현존하는 전체 bandit 알고리즘 중 가장 많이 쓰이는 알고리즘

② UCB는 자연스럽게 exploitation과 exploration의 균형을 취함 

③ 불확실성에 대한 낙관주의를 제공 

⑵ 과정

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

 

 

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

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

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

○ true mean은 μ_i,t와 같이 표시

② 보너스 항 

 

 

○ exploration을 가능하게 함

○ 다음과 같이 수렴성과 연결됨 

 

 

③ UCB(upper confidence bound)

 

  

○ optimism : 실제 기댓값보다 높은 확률(99.9% 이상)로 더 높게 본다는 의미

○ 뒤의 항은 exploration을 가능하게 하고 다음과 같이 수렴성과 연결됨  

④ 단계 1. 맨 처음에는 arm을 모두 play

⑤ 단계 2. 각 단계에서 UCB_i,t가 최대인 arm인 i_t를 선택

⑥ 단계 3. 매 시간 단계마다 empirical mean과 UCB를 업데이트 : 한 번씩 관측할 때마다 uncertainty를 나타내는 UCB가 줄어듦

⑶ 수렴성 증명

① 정리 

모든 N > 1에 대해, support가 [0, 1]인 임의의 reward 분포 P₁, ···, P_N을 가진 N개의 arm에서 UCB 정책을 실행하면, 임의의 시행 횟수 T 후의 기대 후회 

 

 

는 다음 값 이하이다.

 

 

여기서 μ₁, ···, μ_N은 분포 P₁, ···, P_N의 평균이고, Δ_i = μ₁ (best arm) - μ_i이다.

② 증명 

c_t,s := √(2 log(t) / s)라 두자. 또한 X̄_nⁱ = (1/n) ∑_{t=1 to n} X_t와 같이 정의하자. 여기서 {X_tⁱ}_t∈N은 arm i를 연속해서 당겼을 때의 보상에 대한 확률과정이다. 임의의 arm i에 대해, 우리는 어떤 play sequence에서도 UCB_i(T)의 상계를 구할 것이다. 시각 t에 선택된 arm을 I_t라 하면, 임의의 양의 정수 ℓ에 대해 다음을 얻는다.

 

 

그런데 X̄_s* + c_t,s ≤ X̄_siⁱ + c_t,si이면, 다음 중 적어도 하나는 성립함을 관찰할 수 있다.

 

X̄_s* ≤ μ* - c_t,s,  X̄_siⁱ ≤ μ_i + c_t,si,  μ* < μ_i + 2c_t,si

 

그렇지 않으면 다음과 같은 모순이 발생한다.

 

X̄_s* + c_t,s > μ* ≥ μ_i + 2c_t,si > X̄_siⁱ + c_t,si

 

처음 두 사건의 확률은 Azuma-Hoeffding 부등식의 변형으로 한정할 수 있다. 그 이유는 sX̄_s* - sμ*와 s_iX̄_siⁱ - s_iμ_i가 각각 증가분이 [-μ*, 1 - μ*] 및 [-μ_i, 1 - μ_i]에 속하는, 0에서 시작하는 Martingale이기 때문이다. 따라서 다음이 성립한다.

 

 

또한, 다음이 성립한다.

 

 

여기서 s_i ≥ 8 log(T) / Δ_i²와 T ≥ t를 썼다. 따라서 ℓ = ⌈8 log(T) / Δ_i²⌉로 잡으면 μ* < μ_i + 2c_t,si는 일어날 수 없고, 위의 세 부등식 중 앞의 두 개만 가능하다. 그러므로 다음을 얻는다. 

 

 

따라서 𝔼[n_i,T] ≤ 𝔼[UCB_i(T)] ≤ 8log(T) / Δ_i² + C로부터 Regret(T) ≤ 8 log(T) / Δ_i + C∑Δ_i 를 얻을 수 있다. 

③ 증명 2 

○ Azuma-Hoeffding inequality (관련 개념 : Martingale) 

 

 

○ 수식화 : 추후 업데이트 

④ 결론

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

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

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

⑷ 비교 : UCB vs ϵ-greedy exploration

① 차이점 1. total regret은 UCB가 O(log T), ϵ-greedy exploration가 O(T)

② 차이점 2. 평균 보상은 UCB가 ϵ-greedy exploration보다 뛰어남

 

출처: Figure 2.3 in Sutton and Barto

Figure 2. UCB vs ϵ-greedy exploration

 

⑸ 비교 : UCB vs 톰슨 샘플링

① 공통점 1. total regret은 O(log T) : per time regret은 O(log T / T)로 0으로 수렴함 

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

③ 차이점 2. UCB는 deterministic하고 thomson sampling은 probabilistic (randomized)

 

 

4. 톰슨 샘플링(Thomson sampling) [목차]

⑴ 개요

① 가장 오래된 bandit 알고리즘 : 톰슨에 의해 1933년에 소개됨. UCB보다도 오래됨

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

③ 모드가 두 개여도 잘 작동함 

⑵ 과정 

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

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

② 단계 2. 각 prior distribution으로부터 estimated reward를 추출

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

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

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

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

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

⑶ 예시 : 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은 독립된 관측의 횟수 

 

 

⑸ 예시 : 동적계획법 문제 (ref, ref, ref)

⑹ 수렴성

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

 

 

② Beta 분포

 

 

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

 

 

⑺ UCB와 톰슨 샘플링의 비교

① 공통점 1. total regret은 O(log T) : per time regret은 O(log T / T)로 0으로 수렴함 

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

③ 차이점 2. UCB는 deterministic하고 thomson sampling은 probabilistic (randomized)

 

입력: 2021.12.10 00:52

수정: 2026.03.13 16:08