Epsilon-Greedy — Fixed · Decaying 의 한계

출처

이 글은 교재 직접 참조 없이 agent 사전학습 기반으로 작성되었다 (교재 미확인 — agent 사전학습 기반). 핵심 정리는 Sutton & Barto (2018) Reinforcement Learning: An Introduction 등 표준 자료에 한해 인용한다.

이 글은 Phase I 시리즈의 두 번째 글이다. MAB 문제 정의 에서 정의한 exploration vs exploitation 의 가장 단순한 해법인 ε-greedy 를 다룬다.

1 진입 직관 — “대부분 좋은 선택, 가끔 모험”

이전 글에서 순수 exploitation 과 순수 exploration 모두 선형 regret (\(O(N)\)) 임을 보았다. 자연스러운 절충은 대부분 best arm 을 당기되, 가끔 무작위 탐색.

ε-greedy 의 한 줄: 확률 ε 로 무작위 팔 선택, 확률 1-ε 로 현재 최선 추정 팔 선택.

이 단순한 발상이 놀라울 정도로 효과적. ε = 0.1 정도면 순수 exploration 보다 훨씬 좋은 보상 + 순수 exploitation 의 함정 회피.

비유 — 식당 선택: 매일 점심에 동전을 던져 (확률 0.1) — 앞면이면 새 식당 무작위 시도, 뒷면이면 지금까지 가장 만족스러웠던 식당. 단순하지만 합리적.

2 알고리즘 정의 — 의사코드

정의: ε-Greedy Algorithm

입력: K (팔 수), N (총 시점), ε ∈ [0, 1]
초기화:
  pulls[a] = 0  for all a
  sums[a] = 0   for all a

For t = 1 to N:
  u ← Uniform(0, 1)
  If u < ε:
    A_t ← Uniform({1, ..., K})       # Exploration
  Else:
    means[a] = sums[a] / pulls[a]
    A_t ← argmax_a means[a]           # Exploitation

  Observe X_t ~ ν_{A_t}
  pulls[A_t] += 1
  sums[A_t] += X_t

핵심 매개변수: ε.

• ε 큼: 탐색 많이, 학습 빠르나 보상 손실
• ε 작음: 활용 많이, 보상 높으나 잘못된 팔에 갇힐 위험

Tie-breaking 주의: 초기 단계에 모든 팔의 평균이 0 (시도 0 회) — argmax 가 항상 0번 팔 만 선택. 해결책: 각 팔 1 회씩 사전 시도 또는 무작위 tie-breaking.

3 Fixed ε — 본질적 한계

3.1 문제

Fixed ε 는 N → ∞ 에도 매 시점 ε 의 확률로 무작위 선택. 이는 suboptimal 팔의 영구적 시도 를 의미.

3.2 Regret 분석

수식: \(K\) 팔 중 suboptimal 팔 \(a\) 의 평균 시도 횟수:

\[ \mathbb{E}[\text{pulls}_a] \geq \frac{\varepsilon \cdot N}{K} \]

Suboptimal 팔에 고정 비율 시도 — gap \(\Delta_a = \mu^* - \mu_a\) 와 곱하면:

\[ R_N \geq \sum_{a \neq a^*} \Delta_a \cdot \frac{\varepsilon \cdot N}{K} = \Theta(\varepsilon \cdot N) \]

결론: Fixed ε 는 cumulative regret 이 N 에 선형 — Lai-Robbins 하한 \(O(\log N)\) 을 못 달성.

3.3 직관

영원히 ε 비율로 무작위 탐색 — 학습이 충분히 진행된 후에도 같은 비율 탐색. 이는 낭비.

3.4 실무 처방

작은 ε (예: 0.01~0.1) 사용. 그러나 너무 작으면 탐색 부족 → 학습 매우 느림. Hyperparameter tuning 필요. Fixed ε 의 본질적 함정.

4 Decaying ε — log N regret 달성

4.1 정의

시간이 지날수록 ε 감소. 일반적 형태:

\[ \varepsilon_t = \min\left(1, \frac{c K}{d^2 t}\right) \]

\(c, d\) 는 hyperparameter. 또는 단순화:

\[ \varepsilon_t = \frac{1}{t} \quad \text{또는} \quad \varepsilon_t = \frac{C}{t} \]

4.2 메커니즘

초기 시점 \(t = 1\): \(\varepsilon = 1\) (모든 팔 균등 시도).

시점 \(t = 100\): \(\varepsilon = 0.01\) (거의 exploitation).

시간이 지날수록 학습 정보 누적 + 추가 탐색의 marginal value 감소 → 탐색 비율 감소 가 합리적.

4.3 Regret 분석 (informal)

Auer et al. (2002) 의 분석:

\[ R_N = O\left(K \cdot \log N\right) \quad \text{with } \varepsilon_t = \min(1, cK/(d^2 t)) \]

Lai-Robbins 하한 달성 — 상수 배 이내. UCB 와 동일 위계.

4.4 그러나 한계

Decaying ε 의 상수 \(c, d\) 는 알기 어려움 — gap \(\Delta_a = \mu^* - \mu_a\) 에 의존. 진짜 값 은 사전 모름.

실무에서는 간단한 1/t decay 또는 고정 ε 를 사용. 최적 hyperparameter tuning 은 어려움.

반사실 — 이론 vs 실무: 이론은 log N regret 이지만 상수 가 클 수 있음. 실무에서는 Thompson Sampling 또는 UCB 가 더 robust. ε-greedy 는 baseline.

5 Optimistic Initialization — 변형

5.1 동기

Decaying ε 의 hyperparameter 의존 회피. 낙관적 초기값 으로 자연스러운 탐색 유도.

5.2 메커니즘

각 팔의 초기 평균값 을 낙관적으로 (예: 1.0 — Bernoulli 의 최대) 설정. Greedy 알고리즘은 덜 시도된 팔의 추정값이 여전히 1 에 가까움 → 자동 탐색.

초기화:
  means[a] = R_max  (낙관적, 모든 보상의 상한)
  pulls[a] = ...    (작은 양수, 가중치)

For t = 1 to N:
  A_t ← argmax_a means[a]
  Observe X_t ~ ν_{A_t}
  Update means[A_t] = (means[A_t] * pulls[A_t] + X_t) / (pulls[A_t] + 1)
  pulls[A_t] += 1

5.3 효과

충분히 시도된 팔의 평균 → 진짜 평균 으로 수렴. 덜 시도된 팔은 낙관적 값 유지 → 다음에 시도. 자연스러운 exploration.

한계: Bernoulli 처럼 bounded reward 가정 필요. Stationary 만 작동. Non-stationary 환경에서는 낙관 편향이 새 정보 무시.

6 Hyperparameter 민감도 — 실무 권고

6.1 시뮬레이션 결과 (다음 코드 참조)

ε	짧은 시간 (N=100)	중간 (N=1000)	긴 시간 (N=10000)
0.01	학습 너무 느림	좋음	매우 좋음
0.1	좋음	보통	regret 누적
0.3	좋음 (탐색 많음)	regret 큼	regret 매우 큼
Decaying 1/t	보통	좋음	좋음

6.2 권고

짧은 horizon (N < 1000): ε = 0.1 정도 (탐색 보장)

긴 horizon (N > 10000): Decaying ε 또는 UCB / Thompson

Robust 선택: 잘 모르겠으면 Thompson Sampling (Phase I-4). Hyperparameter 자유.

7 시뮬레이션 — Fixed vs Decaying

import numpy as np
import matplotlib.pyplot as plt

np.random.seed(42)

K = 5
true_means = np.array([0.30, 0.50, 0.70, 0.40, 0.60])
mu_star = true_means.max()
N = 5000

def epsilon_greedy(true_means, N, epsilon, decay=False):
    K = len(true_means)
    pulls = np.zeros(K)
    sums = np.zeros(K)
    rewards = np.zeros(N)

    # 각 팔 1 회씩 사전 시도
    for a in range(K):
        r = np.random.binomial(1, true_means[a])
        pulls[a] = 1
        sums[a] = r
        rewards[a] = r

    for t in range(K, N):
        eps_t = epsilon / (t + 1) if decay else epsilon
        if np.random.random() < eps_t:
            a = np.random.randint(K)
        else:
            means = sums / pulls
            a = means.argmax()
        r = np.random.binomial(1, true_means[a])
        pulls[a] += 1
        sums[a] += r
        rewards[t] = r
    return rewards

def cumulative_regret(rewards, mu_star):
    return np.arange(1, len(rewards) + 1) * mu_star - np.cumsum(rewards)

n_sim = 100
configs = [
    ("Fixed ε=0.01", 0.01, False),
    ("Fixed ε=0.10", 0.10, False),
    ("Fixed ε=0.30", 0.30, False),
    ("Decaying 1/t (c=1)", 1.0, True),
    ("Decaying 10/t (c=10)", 10.0, True),
]

results = {}
for name, eps, decay in configs:
    regrets = np.zeros((n_sim, N))
    for s in range(n_sim):
        rewards = epsilon_greedy(true_means, N, eps, decay)
        regrets[s] = cumulative_regret(rewards, mu_star)
    results[name] = regrets.mean(axis=0)

print(f"[ε-Greedy 비교 — N={N}, K={K}, 100 회 시뮬레이션]")
print(f"진짜 means: {true_means}, mu* = {mu_star}\n")
print(f"{'설정':<25} {'최종 regret (N=5000)':>20}")
for name, _, _ in configs:
    print(f"{name:<25} {results[name][-1]:>20.1f}")

print()
print("→ Fixed ε=0.30: regret 매우 큼 (탐색 과다)")
print("→ Fixed ε=0.10: 적당, 그러나 N 커지면 누적")
print("→ Fixed ε=0.01: 짧은 horizon 에 학습 느림, 긴 horizon 에 좋음")
print("→ Decaying: 잘 튜닝하면 log N regret 달성")

결과 해석:

1. Fixed ε 는 시간 따라 선형 증가. ε 가 클수록 기울기 큼.
2. Decaying 은 log N 곡선 — 시간 갈수록 추가 regret 감소.
3. Fixed ε 의 선형 함정 이 그래프로 명확.

8 A/B Test 와의 연결

8.1 A/B Test = Pure Exploration → Pure Exploitation

A/B 테스트는 본질적으로 탐색 단계 (균등 할당) + 결정 후 exploitation (승자 100%) 의 명확한 두 단계 분리.

8.2 ε-Greedy = 연속적 mixing

ε-greedy 는 동시에 두 단계 — 매 시점 탐색과 활용 mixed.

8.3 Trade-off

측면	A/B Test	ε-Greedy
학습-결정 분리	명확	연속적
효과 추정 정밀성	강 (균등 sample)	약 (불균등)
학습 중 보상	낮음 (균등 할당)	중간 (greedy 활용)
실시간 의사결정	불가능	가능

하이브리드 권고: 짧은 burn-in 단계 (균등 할당, ε=1) 후 decaying ε 또는 UCB/Thompson 으로 전환. 통계적 유의성 검증 + 실시간 최적화 양립.

9 결론

ε-Greedy 는 MAB 의 가장 단순한 baseline. Fixed ε 의 선형 regret 함정은 본질적이지만, decaying 으로 log N 달성 가능. 그러나 hyperparameter 민감도가 실무 도전.

핵심 메시지:

1. Fixed ε: 선형 regret. ε 가 작아도 영원한 탐색 — 누적 regret.
2. Decaying ε ∝ 1/t: log N regret. 그러나 상수 튜닝 어려움.
3. Optimistic Init: 자연스러운 탐색. Bernoulli 같은 bounded reward 에 유효.
4. 실무 권고: 짧은 horizon 은 ε=0.1, 긴 horizon 은 decaying 또는 UCB/Thompson.
5. A/B test 와의 차이: 연속적 mixing vs 명확한 두 단계 분리.

다음 글: UCB1 — 신뢰구간 기반 결정론적 탐색.

10 관련 주제

선행 지식

• MAB 문제 정의

Phase I 후속 글

• UCB1 — 신뢰구간 기반 탐색
• Thompson Sampling — Beta-Bernoulli·Gaussian

11 참고문헌

• Sutton, R. S. & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.), Ch. 2. MIT Press.
• Auer, P., Cesa-Bianchi, N., Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning 47, 235-256.
• Lai, T. L. & Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Adv. Appl. Math. 6, 4-22.
• Lattimore, T. & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press. (교재 미확인 — agent 사전학습 기반)