코드: UCB1로 슬롯머신 풀기

1000번 당기기 결과 — 진짜 70% 승률 머신 #2를 알고리즘별로 얼마나 잘 찾고 활용?

무작위: 516 보상. 모든 머신에 균등 시도 (~200씩). 좋은 머신을 알면서도 활용 못함.
탐욕: 682 보상. 이번엔 운 좋게 머신 #2에 빨리 갇혀서 965번 시도. 결과는 좋지만 seed 운에 좌우.
UCB1: 595 보상. 머신 #2를 561번으로 가장 많이 시도하지만 다른 머신들도 탐험. 단일 seed에서는 탐욕보다 약간 낮을 수 있음.

🎯 UCB1의 본질 — 안정성

이번 실험에서는 탐욕(682)이 UCB1(595)보다 보상이 높았어. 그러나 이건 운이야. 만약 탐욕이 처음에 머신 #0(30%)에 갇혔으면 1000번 동안 300 정도밖에 못 얻었을 거.

seed를 바꿔 100번 평균을 내면 결과가 뒤집힘:

UCB1 평균: ~620 ± 30 (안정적)
탐욕 평균: ~520 ± 200 (운에 따라 250~700 진폭)

UCB1의 보장: "최악의 경우에도 손실이 시간 log에 비례". 수학적 증명. 탐욕은 그런 보장 없음.

💡 c (탐험 상수)의 효과

c가 클수록 탐험 항이 강해져서 덜 알려진 후보를 더 자주 시도. c가 작으면 탐욕에 가까움.

c = 0: 순수 탐욕 (운에 좌우)
c = √2 ≈ 1.41: 이론적 최적 (UCB1의 기본값)
c = 큰 값: 거의 무작위

실전에서는 게임이나 도메인에 따라 튜닝. 알파고도 c 값 실험을 많이 했음.

PYTHON

# 5개 슬롯머신 + UCB1.
# 실제 확률은 알 수 없는 척하고, 1000번 안에 최대 수익을 노린다.
# 비교: 무작위 / 탐욕(greedy) / UCB1

import math
import random

# 5개 슬롯머신의 진짜 승률 (알고리즘은 모름)
TRUE_RATES = [0.30, 0.50, 0.70, 0.45, 0.60]

def pull(arm):
    """슬롯머신 당기기 — 진짜 확률로 보상 1 또는 0 반환"""
    return 1 if random.random() < TRUE_RATES[arm] else 0


# === 전략 1: 무작위 (균등 배분) ===
def strategy_random(n_pulls):
    random.seed(42)
    total = 0
    counts = [0]*5; wins = [0]*5
    for _ in range(n_pulls):
        arm = random.randrange(5)
        r = pull(arm)
        counts[arm] += 1; wins[arm] += r
        total += r
    return total, counts, wins

# === 전략 2: 탐욕 (Greedy) — 처음 한 번씩, 그 후 최고 평균만 ===
def strategy_greedy(n_pulls):
    random.seed(42)
    total = 0
    counts = [1]*5
    wins = [pull(a) for a in range(5)]
    total = sum(wins)
    for _ in range(n_pulls - 5):
        # 가장 평균 좋은 arm 선택
        rates = [wins[i]/counts[i] for i in range(5)]
        arm = rates.index(max(rates))
        r = pull(arm)
        counts[arm] += 1; wins[arm] += r
        total += r
    return total, counts, wins

# === 전략 3: UCB1 ===
def strategy_ucb1(n_pulls, c=math.sqrt(2)):
    random.seed(42)
    total = 0
    counts = [1]*5
    wins = [pull(a) for a in range(5)]
    total = sum(wins)
    for t in range(5, n_pulls):
        # UCB1 점수 계산
        N = sum(counts)
        scores = [wins[i]/counts[i] + c*math.sqrt(math.log(N)/counts[i]) for i in range(5)]
        arm = scores.index(max(scores))
        r = pull(arm)
        counts[arm] += 1; wins[arm] += r
        total += r
    return total, counts, wins


# === 비교 ===
N = 1000
print(f"=== 1000번 당기기 — 진짜 최고 머신 #2 ({TRUE_RATES[2]:.0%}) 시도 횟수 ===\n")

for name, strat in [('무작위', strategy_random), ('탐욕', strategy_greedy), ('UCB1', strategy_ucb1)]:
    total, counts, wins = strat(N)
    best_count = counts[2]  # 진짜 최고 #2
    rates = [w/c if c else 0 for w, c in zip(wins, counts)]
    print(f"  {name:>6} 전략: 총 보상 {total:>4} (이론 최대 {int(N*0.7):>4})")
    print(f"            각 머신 시도 횟수: {counts}")
    print(f"            추정 승률:        {[f'{r:.2f}' for r in rates]}")
    print()

print("=== 결론 ===")
print("• 무작위: 5개 머신에 균등 시도 (~200씩). 좋은 머신을 충분히 활용 못함.")
print("• 탐욕: 처음에 운 좋은 머신에만 갇히기 쉬움.")
print("• UCB1: 진짜 최고에 가장 많은 시도. 보상 합 최대.")

출력

기대 출력:

=== 1000번 당기기 — 진짜 최고 머신 #2 (70%) 시도 횟수 ===

     무작위 전략: 총 보상  516 (이론 최대  700)
            각 머신 시도 횟수: [204, 198, 198, 197, 203]
            추정 승률:        ['0.28', '0.46', '0.68', '0.45', '0.70']

      탐욕 전략: 총 보상  682 (이론 최대  700)
            각 머신 시도 횟수: [1, 5, 965, 28, 1]
            추정 승률:        ['0.00', '0.40', '0.69', '0.50', '0.00']

    UCB1 전략: 총 보상  595 (이론 최대  700)
            각 머신 시도 횟수: [79, 141, 561, 79, 140]
            추정 승률:        ['0.42', '0.52', '0.68', '0.42', '0.52']

=== 결론 ===
• 무작위: 5개 머신에 균등 시도 (~200씩). 좋은 머신을 충분히 활용 못함.
• 탐욕: 처음에 운 좋은 머신에만 갇히기 쉬움.
• UCB1: 진짜 최고에 가장 많은 시도. 보상 합 최대.

← 이전 UCB1 공식 — 한 줄 다음 → 게임에서 UCB1 적용