Kwangmin Kim - Contextual Bandit

출처

이 글은 교재 직접 참조 없이 agent 사전학습 기반으로 작성되었다 (교재 미확인 — agent 사전학습 기반). 핵심 정리는 Li, Chu, Langford, Schapire (2010) A Contextual-Bandit Approach to Personalized News Article Recommendation 원논문에 한해 명시한다.

이 글은 Phase I 시리즈의 여섯 번째 글이다. 지금까지의 stochastic MAB (UCB, Thompson) 는 모든 사용자/시점이 동일 가정. Contextual 은 각 시점의 특성을 활용 한다.

1 진입 직관 — “사람마다 다르다”

지금까지의 MAB: 각 팔의 평균 보상 \(\mu_a\) 가 모든 사용자에게 동일. 그러나 현실은 다름:

추천 시스템: 다른 사용자가 다른 콘텐츠 선호
광고: 연령·성별·관심사에 따라 다른 광고 효과
임상: 환자의 baseline 위험 에 따라 다른 약 효과

Contextual Bandit 의 한 줄: 각 결정 시점에 context \(x_t\) 관찰. 보상이 팔 + context 의 함수 — \(\mathbb{E}[X_a | x_t]\).

1.1 메커니즘

각 시점 \(t\):

Context 벡터 \(x_t \in \mathbb{R}^d\) 관찰 (예: 사용자 특성)
팔 \(A_t\) 선택
Reward \(X_t \sim \nu(A_t, x_t)\) 관찰 — 분포가 context 에 의존

목표: 누적 보상 최대화. 각 사용자에게 적합한 팔 학습.

비유 — 의사 처방: 일반적 약은 모든 환자에 동일 효과 가정. 그러나 정밀 의학 (precision medicine) 은 환자 유전자·생활 습관 에 따라 약 선택. Contextual bandit 은 온라인 정밀 의학.

2 Linear Payoff 가정

가장 흔한 가정: 보상의 기대값이 context 의 선형 함수.

정의: Linear Contextual Bandit

각 팔 \(a\) 에 알려지지 않은 모수 벡터 \(\theta_a^* \in \mathbb{R}^d\) 가 존재.

\[ \mathbb{E}[X_a | x_t] = x_t^\top \theta_a^* \]

학습자는 \(\theta_a^*\) 를 데이터로부터 추정.

2.1 가정

Linearity: 보상의 기대값이 선형. 비선형 효과는 feature engineering 으로 처리 (예: 다항식, RBF 커널).
Bounded reward: \(X_a \in [0, 1]\) 또는 \(|X_a| \leq R\).
Bounded context: \(\|x_t\| \leq L\).
Stationary \(\theta_a^*\): 시간에 따라 변하지 않음.

2.2 왜 Linear 인가

Practical 이유: Closed-form regression 가능. Ridge regression 의 explicit 해. 비선형이면 복잡한 추정 필요.

이론 이유: Confidence ellipsoid 분석 가능. UCB 와 같이 낙관적 추정 하기 쉬움.

한계: 진짜 보상이 비선형이면 모델 misspecification. Yahoo! 사례에서는 수십 개 feature 의 선형 결합이 충분히 효과적이었음 (실증).

3 Ridge Regression — 모수 추정

3.1 데이터

팔 \(a\) 가 \(n_a\) 회 시도되었고, 각 시도의 context \(x_{a,1}, ..., x_{a,n_a}\) 와 reward \(r_{a,1}, ..., r_{a,n_a}\).

3.2 Ridge Regression

\(\theta_a\) 의 ridge regression 추정:

\[ \hat{\theta}_a = (X_a^\top X_a + \lambda I)^{-1} X_a^\top r_a \]

여기서 \(X_a\) 는 \(n_a \times d\) context 행렬, \(r_a\) 는 reward 벡터, \(\lambda > 0\) 는 정규화 매개변수.

수식 직관:

\(X_a^\top X_a\): context 의 공분산 행렬 (sample)

\(\lambda I\): 정규화 — singular 행렬 회피

\(X_a^\top r_a\): context 와 reward 의 공분산

\(\hat{\theta}_a\) 는 최소자승 + 정규화 의 닫힌 해.

3.3 Confidence Bound

\(\hat{\theta}_a\) 의 confidence ellipsoid:

\[ P(\|\hat{\theta}_a - \theta_a^*\|_{A_a} \leq \beta) \geq 1 - \delta \]

여기서 \(A_a = X_a^\top X_a + \lambda I\), \(\beta\) 는 높은 확률 보장 상수.

이 confidence ellipsoid 가 LinUCB 의 exploration 항 의 기반.

4 LinUCB Algorithm — Li, Chu, Langford, Schapire (2010)

4.1 의사코드

알고리즘: LinUCB (Disjoint)

입력: λ > 0 (ridge), α > 0 (exploration)
초기화: 각 팔 a 에 대해
  A_a = λ I_d        # d × d 정규화 행렬
  b_a = 0_d          # d-차원 영벡터

For t = 1 to N:
  Observe context x_t

  for each arm a:
    θ̂_a = A_a^{-1} b_a
    UCB_a = x_t^T θ̂_a + α * sqrt(x_t^T A_a^{-1} x_t)

  A_t = argmax_a UCB_a

  Observe reward r_t

  A_{A_t} += x_t x_t^T
  b_{A_t} += r_t * x_t

매개변수: - λ: ridge 정규화. 보통 1. - α: exploration 강도. Confidence level 에 의존 — 보통 sqrt(log(N)/2) 정도.

4.2 메커니즘 직관

두 항:

\(x_t^\top \hat{\theta}_a\): context-적응 평균 보상 추정 (exploitation)

\(\alpha \sqrt{x_t^\top A_a^{-1} x_t}\): 이 context 에서 그 팔의 추정 불확실성 (exploration)

수식 직관 — confidence 항: \(A_a^{-1}\) 는 모수 \(\theta_a\) 의 공분산. \(x_t^\top A_a^{-1} x_t\) 는 이 특정 context 의 보상 추정 분산. 자주 본 유사 context 일수록 작음, 새로운 낯선 context 일수록 큼.

4.3 Disjoint vs Hybrid

변형	의미
Disjoint	각 팔이 독립 모수 \(\theta_a\). 팔 간 정보 공유 없음.
Hybrid	일부 공통 모수 + 팔별 고유 모수. 정보 공유로 더 빠른 학습.

Yahoo! 의 사례에서는 Hybrid 가 약간 더 좋았음 (Li 외 2010).

4.4 Regret Bound

Abbasi-Yadkori, Pál, Szepesvári (2011): LinUCB 의 cumulative regret:

\[ R_N = O(d \sqrt{N} \cdot \log N) \]

\(d\) 는 context 차원. Stochastic MAB 의 \(O(\sqrt{KN \log N})\) 보다 — 팔 수 K 대신 차원 d. 차원 작으면 매우 효율적.

5 Yahoo! News Recommendation — 실증

5.1 시험 환경

Yahoo! Today Module (frontpage 의 news article 추천). 각 사용자에게 4 개 article slot 중 1 개 표시. 클릭 vs 스킵 = reward.

5.2 Context

Feature	차원
사용자 demographics (성별, 연령대 그룹)	~10
사용자 활동 패턴	~50
시간/요일	~10
콘텐츠 카테고리 사전 선호	~30
합계	~100 (압축 후 d=6 hybrid)

5.3 결과

Li 외 (2010) 실증:

LinUCB (Hybrid) 가 기존 random / popularity-based 보다 12.5% 클릭률 향상

Disjoint LinUCB 도 10% 향상

UCB1 (context 미사용) 은 5% 향상 — context 의 가치

함의: 사용자 세분화 가 강력. 모든 사용자에 동일 가정의 한계 명확.

5.4 실무 영향

이 논문 이후 추천 시스템·광고 분야에 LinUCB 변형 광범위. Netflix, Amazon, Google 등 contextual bandit 표준.

6 HTE (Heterogeneous Treatment Effect) 와의 연결

6.1 Causal Inference 의 HTE

Phase D, J 에서 다루는 HTE: 처치 효과가 환자 특성에 따라 다름. \(\mathbb{E}[Y(1) - Y(0) | X = x]\) — 조건부 평균 처치 효과 (CATE).

6.2 Contextual Bandit 의 HTE

Contextual Bandit 의 학습 결과: context \(x_t\) 에 따른 최선의 팔. 즉 처치 효과의 heterogeneity 학습.

6.3 차이

측면	Causal HTE	Contextual Bandit
데이터	관찰 또는 RCT	실시간 적응
목표	효과 추정	보상 최적화
시간	사후 분석	온라인
추정 vs 결정	추정	결정

공통: 둘 다 heterogeneity 인정. Causal 은 왜 효과가 다른가, Contextual 은 어떤 사용자에 어떤 처치 의 답.

7 비선형 확장

7.1 Kernel UCB

Linear 가정 비현실적이면 kernel trick. RBF, polynomial 등 다양한 kernel.

7.2 Neural Bandit

Neural network 으로 보상 예측. 비선형 흐름. 그러나 theoretical regret bound 약함.

7.3 Gaussian Process Bandit

Gaussian Process 로 사후 분포 모델링. uncertainty 자연스럽게 표현. 그러나 계산 비용 큼 (\(O(n^3)\)).

8 시뮬레이션 — LinUCB

import numpy as np

np.random.seed(42)

K = 3   # 팔 수
d = 5   # context 차원
N = 5000

# 진짜 모수
theta_star = np.random.randn(K, d)

# Context 생성
def get_context():
    return np.random.randn(d)

def linear_reward(arm, context):
    """Bernoulli reward — 평균은 sigmoid(linear)."""
    z = context @ theta_star[arm]
    p = 1.0 / (1.0 + np.exp(-z))
    return np.random.binomial(1, p)

def linucb(N, lambd=1.0, alpha=1.0):
    A = np.array([lambd * np.eye(d) for _ in range(K)])
    b = np.zeros((K, d))
    rewards = np.zeros(N)
    optimal_rewards = np.zeros(N)

    for t in range(N):
        x = get_context()
        ucb = np.zeros(K)
        for a in range(K):
            A_inv = np.linalg.inv(A[a])
            theta = A_inv @ b[a]
            mean = x @ theta
            uncertainty = alpha * np.sqrt(x @ A_inv @ x)
            ucb[a] = mean + uncertainty

        a_t = ucb.argmax()
        r = linear_reward(a_t, x)
        rewards[t] = r

        A[a_t] += np.outer(x, x)
        b[a_t] += r * x

        # 최선의 팔 (사후 비교용)
        true_means = [1.0 / (1.0 + np.exp(-x @ theta_star[a])) for a in range(K)]
        optimal_rewards[t] = max(true_means)

    return rewards, optimal_rewards

def random_baseline(N):
    rewards = np.zeros(N)
    optimal_rewards = np.zeros(N)
    for t in range(N):
        x = get_context()
        a_t = np.random.randint(K)
        r = linear_reward(a_t, x)
        rewards[t] = r
        true_means = [1.0 / (1.0 + np.exp(-x @ theta_star[a])) for a in range(K)]
        optimal_rewards[t] = max(true_means)
    return rewards, optimal_rewards

n_sim = 30
linucb_total = []
random_total = []
linucb_pseudo_regret = np.zeros((n_sim, N))

for s in range(n_sim):
    np.random.seed(s)
    r_linucb, opt_linucb = linucb(N)
    np.random.seed(s)
    r_random, opt_random = random_baseline(N)
    linucb_total.append(r_linucb.sum())
    random_total.append(r_random.sum())
    # Pseudo-regret: 매 시점 최선 vs LinUCB 선택
    linucb_pseudo_regret[s] = np.cumsum(opt_linucb - r_linucb)

print(f"[LinUCB vs Random — N={N}, d={d}, K={K}, {n_sim} sims]\n")
print(f"누적 보상 평균:")
print(f"  LinUCB:  {np.mean(linucb_total):>7.1f}")
print(f"  Random:  {np.mean(random_total):>7.1f}")
print(f"  격차:    {np.mean(linucb_total) - np.mean(random_total):>7.1f}")
print(f"  Lift:    {(np.mean(linucb_total) - np.mean(random_total)) / np.mean(random_total) * 100:.1f}%")

print(f"\n[Pseudo-Regret 시간 추이 — LinUCB]")
for t_check in [100, 500, 1000, 2000, 5000]:
    if t_check <= N:
        print(f"  t={t_check}: {linucb_pseudo_regret[:, t_check-1].mean():.1f}")

print(f"\n→ LinUCB 가 random 대비 큰 누적 보상 — context 활용의 가치")
print(f"→ Pseudo-regret 곡선이 sub-linear (sqrt 형태)")

결과 해석:

LinUCB 누적 보상: random 대비 상당한 우위 (보통 30~50%).

Pseudo-regret: sub-linear — 시간 갈수록 최선의 팔에 수렴.

Context 차원 d 가 클수록 학습 시간 길지만 결국 우월.

9 실무 응용

9.1 광고 추천 (예: Yahoo!, Google)

사용자 demographics + 행동 + 시간 → 광고 선택. CTR 최적화.

9.2 추천 시스템 (Netflix, Spotify)

사용자 시청 history + 시간 → 콘텐츠 추천. 시청 시간 최적화.

9.3 동적 가격 (Amazon, Uber)

시간·수요·재고 → 가격 결정. 매출 최적화.

9.4 임상 의사결정

환자 baseline + 유전 + 생활 → 처치 선택. 결과 최적화. 그러나 규제 도전 — 일반 임상 적용 어려움.

10 결론

Contextual Bandit 은 MAB 의 자연스러운 확장 — 사용자 특성을 활용하여 개인화. LinUCB 는 linear 가정 + UCB 원리 의 조합으로 실무에서 광범위 사용.

핵심 메시지:

Context 활용: 모든 사용자에 동일 가정의 한계 극복
Linear payoff: Closed-form, 분석 가능
LinUCB: Confidence ellipsoid 기반 UCB 확장
Yahoo! 실증: 12.5% 클릭률 향상
HTE 와 연결: Causal inference 의 heterogeneity
실무 표준: 광고·추천·동적 가격

다음 글: Non-stationary Bandit — 시간에 따라 변하는 환경.

11 관련 주제

선행 지식

Phase I 후속 글

다른 카테고리 연결

(Phase D, J) HTE — Causal inference 의 heterogeneity
Agent — 추천 시스템에서의 contextual bandit (placeholder)

12 참고문헌

Li, L., Chu, W., Langford, J., Schapire, R. E. (2010). A contextual-bandit approach to personalized news article recommendation. WWW ’10, 661-670.
Abbasi-Yadkori, Y., Pál, D., Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. NIPS.
Chu, W., Li, L., Reyzin, L., Schapire, R. (2011). Contextual bandits with linear payoff functions. AISTATS.
Auer, P. (2002). Using confidence bounds for exploitation-exploration trade-offs. J. Machine Learning Res. 3, 397-422.
Lattimore, T. & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press. (교재 미확인 — agent 사전학습 기반)