Kwangmin Kim - Non-stationary Bandit — Sliding Window

출처

이 글은 교재 직접 참조 없이 agent 사전학습 기반으로 작성되었다 (교재 미확인 — agent 사전학습 기반). 핵심 정리는 Garivier & Moulines (2011) On Upper-Confidence Bound Policies for Switching Bandit Problems 에 한해 명시한다.

이 글은 Phase I 시리즈의 일곱 번째 글이다. Stationary 가정 (분포 시간 불변) 의 비현실성을 다루고, 적응 메커니즘 을 정리한다.

1 진입 직관 — “어제의 좋은 선택이 오늘은 나쁠 수 있다”

지금까지의 MAB (UCB, Thompson) 는 분포 stationary 가정. 그러나 현실은 변한다:

광고: 새 trend 등장, 기존 콘텐츠 노후
추천: 시즌 (여름/겨울), 요일 (주말/평일) 효과
주식: 시장 상태 변화
임상: 신규 약 등장, 환자 인구 변화

결정적 함정: Stationary 알고리즘 (UCB) 을 non-stationary 환경에 사용하면 — 과거 데이터에 묶임. 변화한 환경 적응 못 함. 새 최선의 팔을 영원히 놓침.

비유 — 단골 식당: 3 년간 즐겨찾던 식당 의 주방장이 바뀌었다. UCB 는 과거 3 년 데이터 를 기반으로 여전히 좋다고 판단 — 새 주방장이 만든 음식이 나빠도 적응 못 함. 최근 데이터에 더 가중치 가 필요.

2 Stationary 가정의 4 가지 위반 패턴

2.1 1. Abrupt Change (갑작스런 변화)

특정 시점에 분포가 크게 변함. 예: 새 알고리즘 deploy, 광고 정책 변경.

2.2 2. Gradual Drift (점진적 변화)

분포가 천천히 변함. 예: 사용자 선호 변화, 콘텐츠 노후.

2.3 3. Seasonal (주기적)

반복되는 패턴. 예: 요일·시즌·시간대.

2.4 4. Adversarial (적대적)

분포가 학습자에 적대적. Game theory 영역. 본 글에서는 다루지 않음 (Phase J 또는 별도 시리즈).

3 Sliding Window UCB

3.1 메커니즘

가장 단순한 적응 — 최근 W 개 시도만 UCB 계산에 사용.

알고리즘: Sliding Window UCB

입력: 윈도우 크기 W

For t = 1 to N:
  for each a:
    # 최근 W 개 시도만 사용
    recent_pulls_a = pulls[a][-W:]
    if len(recent_pulls_a) == 0: UCB_a = ∞
    else:
      n_a^W = len(recent_pulls_a)
      mean_a^W = mean(recent_pulls_a)
      UCB_a = mean_a^W + sqrt(2 ln min(t, W) / n_a^W)

  A_t = argmax_a UCB_a
  Observe r_t, append r_t to pulls[A_t]

3.2 직관

오래된 데이터 폐기. 환경이 변하면 과거 데이터 무관. 최근 데이터만 현재 상태 반영.

3.3 매개변수 W

W 작음	W 큼
빠른 적응	느린 적응
큰 분산 (적은 sample)	작은 분산
Abrupt change 좋음	Gradual drift 좋음

Trade-off: 적응 속도 vs 추정 정밀성.

실무 권고: 변화 빈도에 따라 W = 100~1000. 모르면 복수 W 동시 운영 + 결과 비교.

4 Discounted UCB

4.1 메커니즘

Sliding window 가 binary (in window / out window) 라면, discounted 는 부드러운 가중치 감소.

알고리즘: Discounted UCB

입력: discount factor γ ∈ (0, 1)

각 팔 a 에 대해:
  N_a(t) = sum over τ <= t : γ^(t-τ) * I[A_τ = a]
  X_a(t) = sum over τ <= t : γ^(t-τ) * X_τ * I[A_τ = a]

UCB_a(t) = X_a(t) / N_a(t) + sqrt(2 ln(t) / N_a(t))

A_t = argmax_a UCB_a(t)

4.2 직관

최근 데이터 가중치 1, 1 시점 전 γ, 2 시점 전 γ², …. 오래될수록 영향 감소.

4.3 γ 의 의미

γ	효과
γ = 1	일반 UCB (모든 데이터 동등)
γ = 0.99	약간의 적응 — 100 시점 후 영향 약 37%
γ = 0.95	중간 적응 — 50 시점 후 영향 약 8%
γ = 0.9	빠른 적응 — 20 시점 후 영향 약 12%

Effective window: \(W_{\text{eff}} \approx 1/(1-\gamma)\). γ = 0.99 면 약 100 시점, γ = 0.95 면 약 20 시점.

5 Regret Bound — Garivier & Moulines (2011)

5.1 정리

Sliding Window UCB 와 Discounted UCB 모두:

\[ R_N = O\left(\sqrt{N \cdot \Upsilon_N \cdot \log N}\right) \]

여기서 \(\Upsilon_N\) 는 시점 N 까지의 abrupt change 횟수.

5.2 직관

Stationary 의 \(O(\log N)\) 보다 훨씬 큼 — 변화에 적응의 비용. 그러나 일반 UCB 의 선형 regret 보다는 훨씬 작음.

5.3 Trade-off

변화 빈도 \(\Upsilon_N\)	regret
0 (stationary)	\(O(\sqrt{N \log N})\)
작음	\(O(\sqrt{N \Upsilon_N \log N})\)
큼 (\(\Upsilon_N = N\))	\(O(N \log N)\) — 선형

즉 변화가 너무 자주 면 학습 자체 불가능. 적응 알고리즘도 무력.

6 Change Detection 접근

6.1 CUSUM (Cumulative Sum)

통계적 change point detection. 누적 합이 임계값 초과 시 변화 신호.

6.2 EWMA (Exponentially Weighted Moving Average)

Discounted 의 일종. 최근 sliding 평균이 예상 범위 벗어남 시 변화 신호.

6.3 Page-Hinkley Test

변화 직후 빠른 감지 에 강함.

6.4 Bandit + Detection

변화 감지 시 알고리즘 재시작. UCB 를 처음부터 다시 학습.

반사실: Sliding window 가 연속적 적응 이라면, change detection 은 이산적 재시작. 적용에 따라 다른 적합성.

7 Thompson Sampling 의 Non-stationary 변형

7.1 Discounted Thompson Sampling

Posterior 업데이트 시 오래된 sample 가중치 감소.

또는 forgetting factor — Beta(α, β) 의 α, β 를 주기적으로 감소.

7.2 Particle Filter Bandits

더 정교한 방법 — 분포 자체 의 시간 진화 모델링.

8 실무 응용

8.1 동적 광고

광고 trend 매주 변화. Sliding window W = 7일 또는 discounted γ = 0.95.

8.2 추천 시스템

시즌 효과 (여름/겨울). 별도 seasonal contextual bandit 가능 (context = 시즌).

8.3 콘텐츠 노후

새 콘텐츠 bonus, 오래된 콘텐츠 discount. Adaptive contextual bandit.

8.4 금융

시장 상태 변화 — regime detection + change detection.

9 시뮬레이션 — Sliding Window vs UCB

import numpy as np

np.random.seed(42)

K = 3
N = 5000

# 비-stationary 환경: 시점 2500 에 분포 변화
def get_means(t):
    if t < 2500:
        return np.array([0.30, 0.50, 0.70])   # 팔 2 가 최선
    else:
        return np.array([0.70, 0.50, 0.30])   # 팔 0 이 최선

def regular_ucb(N):
    K = 3
    pulls = np.zeros(K)
    sums = np.zeros(K)
    rewards = np.zeros(N)
    for a in range(K):
        means = get_means(a)
        r = np.random.binomial(1, means[a])
        pulls[a] = 1
        sums[a] = r
        rewards[a] = r
    for t in range(K, N):
        means_arr = sums / pulls
        ucb = means_arr + np.sqrt(2 * np.log(t + 1) / pulls)
        a = ucb.argmax()
        true_means = get_means(t)
        r = np.random.binomial(1, true_means[a])
        pulls[a] += 1
        sums[a] += r
        rewards[t] = r
    return rewards

def sliding_window_ucb(N, W=200):
    K = 3
    history_arms = []
    history_rewards = []
    rewards = np.zeros(N)
    # 각 팔 1 회 사전 시도
    for a in range(K):
        means = get_means(a)
        r = np.random.binomial(1, means[a])
        history_arms.append(a)
        history_rewards.append(r)
        rewards[a] = r
    for t in range(K, N):
        # 최근 W 시도만 사용
        recent_arms = history_arms[-W:]
        recent_rewards = history_rewards[-W:]
        pulls_w = np.array([recent_arms.count(a) for a in range(K)])
        sums_w = np.array([sum(r for ar, r in zip(recent_arms, recent_rewards) if ar == a) for a in range(K)])
        means_arr = np.where(pulls_w > 0, sums_w / np.maximum(pulls_w, 1), 0)
        # ∞ 처리: 시도 안 한 팔
        ucb = np.where(pulls_w > 0,
                        means_arr + np.sqrt(2 * np.log(min(t + 1, W)) / np.maximum(pulls_w, 1)),
                        1e9)
        a = ucb.argmax()
        true_means = get_means(t)
        r = np.random.binomial(1, true_means[a])
        history_arms.append(a)
        history_rewards.append(r)
        rewards[t] = r
    return rewards

n_sim = 50
ucb_total = []
sw_total = []
ucb_late = []  # 변화 후 (t > 2500) 의 보상
sw_late = []

for s in range(n_sim):
    np.random.seed(s)
    r_ucb = regular_ucb(N)
    np.random.seed(s)
    r_sw = sliding_window_ucb(N, W=200)
    ucb_total.append(r_ucb.sum())
    sw_total.append(r_sw.sum())
    ucb_late.append(r_ucb[2500:].sum())
    sw_late.append(r_sw[2500:].sum())

print(f"[Non-stationary 환경: 변화 시점 t=2500, N={N}, K={K}, {n_sim} sims]\n")
print(f"전체 누적 보상:")
print(f"  Regular UCB:      {np.mean(ucb_total):>7.1f}")
print(f"  Sliding W=200:    {np.mean(sw_total):>7.1f}")
print(f"\n변화 후 (t>2500) 보상:")
print(f"  Regular UCB:      {np.mean(ucb_late):>7.1f}")
print(f"  Sliding W=200:    {np.mean(sw_late):>7.1f}")
print(f"  Optimal (사전 알면): ~0.70 * 2500 = 1750\n")

print(f"→ Regular UCB 는 변화 후에도 *과거 최선의 팔* 에 묶여 적응 실패")
print(f"→ Sliding W=200 은 변화 감지 + 새 최선 학습")
print(f"→ 적응의 비용은 *변화 직후의 짧은 학습 기간*")

결과 해석:

변화 후 보상: Regular UCB ≈ 0.30 * 2500 = 750 (과거 최선의 팔 = 새 최악의 팔).

Sliding W = 200: 약 200~500 시점 후 새 최선 학습 — 보상 회복.

적응 비용: 변화 직후 짧은 학습 기간 의 regret.

10 W vs γ — 선택 기준

측면	Sliding Window W	Discounted γ
메커니즘	Hard cutoff	Soft decay
메모리	\(O(W)\)	\(O(K)\)
변화 패턴	Abrupt 적합	Gradual + Abrupt
매개변수 의미	직관적	약간 추상적
권장 시작값	\(W = 1/(1-\gamma)\)	\(\gamma = 1 - 1/W\)

실무 권고:

변화 빈도 대략 알 때: Sliding window

변화 부드럽게 진행: Discounted

둘 다 모름: 둘 다 시도 + Best 채택

11 결론

Non-stationary 환경에서 stationary 알고리즘은 무력. Sliding window 또는 discounted 로 적응 메커니즘 도입 필수. 변화 빈도와 패턴에 따라 W 또는 γ 선택.

핵심 메시지:

Stationary 가정의 비현실성: 광고·추천·금융 모두 변함
Sliding Window UCB: 최근 W 개만 사용
Discounted UCB: 가중치 부드럽게 감소
Garivier-Moulines regret: \(O(\sqrt{N \Upsilon_N \log N})\)
Change detection: CUSUM, Page-Hinkley + 알고리즘 재시작
실무: W·γ 의 trade-off 평가

다음 글: Best Arm Identification — cumulative regret 이 아닌 simple regret 최적화.

12 관련 주제

선행 지식

Phase I 후속 글

Best Arm Identification

13 참고문헌

Garivier, A. & Moulines, E. (2011). On upper-confidence bound policies for switching bandit problems. Algorithmic Learning Theory, 174-188.
Auer, P., Cesa-Bianchi, N., Freund, Y., Schapire, R. E. (2002). The nonstochastic multiarmed bandit problem. SIAM J. Comput. 32, 48-77.
Page, E. S. (1954). Continuous inspection schemes. Biometrika 41, 100-115. (CUSUM 원논문)
Russac, Y., Vernade, C., Cappé, O. (2019). Weighted Linear Bandits for Non-Stationary Environments. NeurIPS.
Lattimore, T. & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press. (교재 미확인 — agent 사전학습 기반)