Contextual Bandit for Personalization

실시간 개인화 전략 최적화 — LinUCB와 Thompson Sampling

A/B 테스트의 정적 배정 한계를 넘어 실시간으로 최적 전략을 선택하는 Contextual Bandit을 다룬다. Multi-Armed Bandit의 기초부터 LinUCB, Thompson Sampling의 수학적 원리와 구현까지 상세히 설명하고, AI Agent 프롬프트 전략 최적화 시뮬레이션으로 효과를 검증한다.

Statistics
Reinforcement Learning
저자

Kwangmin Kim

공개

2026년 03월 08일

1 Contextual Bandit for Personalization

1.1 A/B 테스트의 한계 → Bandit의 동기

1.1.1 정적 배정의 비용

A/B 테스트는 실험 기간 동안 모든 사용자를 고정된 그룹에 배정한다. 이 정적 설계에는 본질적인 비효율이 있다.

A/B 테스트 프로세스:
  1. 전략 A, B, C 중 하나에 무작위 배정 (1:1:1)
  2. 2~4주간 관찰
  3. 실험 종료 후 통계적 검정 → 승자 전략 채택

문제점:
  - 열등한 전략에 배정된 사용자: 실험 기간 내내 손해 (Opportunity Cost)
  - 사용자 특성에 따라 최적 전략이 다를 수 있음 → 단일 승자 한계
  - 사용자 상태가 시간에 따라 변해도 같은 전략 유지

이 비효율을 수량화한 것이 후회(Regret)다.

\[ \text{Regret}_T = \sum_{t=1}^{T} \left[ r^* - r_t \right] \]

여기서 \(r^* = \max_a \mathbb{E}[r | a]\)는 최적 행동의 기대 보상, \(r_t\)는 시점 \(t\)에서 실제로 받은 보상이다. A/B 테스트는 탐색 기간 동안 Regret이 선형으로 증가한다.

1.2 Multi-Armed Bandit 기초

1.2.1 Exploration vs Exploitation 딜레마

슬롯머신(one-armed bandit)이 \(K\)개 있을 때, 어떤 머신을 당겨야 총 보상이 최대인가?

K = 3 (프롬프트 전략 3가지)

Exploitation (활용): 지금까지 가장 좋았던 전략 계속 선택
  → 장점: 단기 보상 최대화
  → 단점: 더 좋은 전략을 영원히 모름

Exploration (탐색): 덜 시도한 전략도 골고루 시도
  → 장점: 정보 획득
  → 단점: 단기 손실

핵심: 탐색과 활용의 균형이 누적 보상을 결정한다

1.2.2 ε-greedy

가장 단순한 탐색 전략:

\[ a_t = \begin{cases} \arg\max_a \hat{\mu}_a & \text{확률 } 1 - \epsilon \\ \text{Uniform}(\{1, \ldots, K\}) & \text{확률 } \epsilon \end{cases} \]

  • \(\hat{\mu}_a\): arm \(a\)의 표본 평균 보상
  • \(\epsilon\): 탐색 확률 (보통 0.05~0.1)
  • 한계: 탐색 비율이 고정이라 불확실성이 줄어도 계속 탐색

1.2.3 Upper Confidence Bound (UCB)

불확실성이 큰 행동에 보너스를 주어 자연스럽게 탐색:

\[ a_t = \arg\max_a \left[ \hat{\mu}_a + c \sqrt{\frac{\ln t}{N_a(t)}} \right] \]

  • \(\hat{\mu}_a\): arm \(a\)의 표본 평균 보상
  • \(N_a(t)\): arm \(a\)가 시점 \(t\)까지 선택된 횟수
  • \(c\): 탐색 강도 파라미터
  • \(\sqrt{\ln t / N_a(t)}\): 시도 횟수가 적을수록 → 보너스 크다 → 탐색 유도

UCB는 낙관주의 원칙(Optimism in the Face of Uncertainty)을 따른다. 잘 모르는 것은 좋을 수도 있다고 가정하고 시도한다.

1.3 Contextual Bandit

1.3.1 문맥(Context) = 사용자 상태

일반 Bandit은 arm의 전체 평균만 본다. Contextual Bandit은 사용자의 현재 상태(문맥)를 관찰하고, 그 상태에서의 최적 행동을 선택한다.

일반 Bandit:    → a_t → r_t                    (사용자 무시)
Contextual:  x_t → a_t → r_t                   (사용자 상태 반영)

x_t = [세그먼트, 평균 만족도, 감정 점수, 세션 수, 개인화 비율, ...]

1.3.2 선형 보상 모델

각 arm \(a\)에 대해 보상이 문맥의 선형 함수라고 가정:

\[ r_t = \theta_a^T x_t + \epsilon_t, \quad \epsilon_t \sim \mathcal{N}(0, \sigma^2) \]

  • \(\theta_a \in \mathbb{R}^d\): arm \(a\)의 보상 계수 벡터
  • \(x_t \in \mathbb{R}^d\): 시점 \(t\)의 문맥 벡터
  • 목표: \(\theta_a\)를 데이터로부터 추정하고, 가장 높은 \(\hat{\theta}_a^T x_t\)를 주는 arm 선택

1.4 LinUCB 알고리즘 상세

1.4.1 핵심 아이디어

LinUCB는 Ridge 회귀 + UCB를 결합한다. 각 arm에 대해:

\[ \text{UCB}_a(x_t) = \hat{\theta}_a^T x_t + \alpha \sqrt{x_t^T A_a^{-1} x_t} \]

  • \(\hat{\theta}_a = A_a^{-1} b_a\): Ridge 추정량
  • \(A_a = \sum_{\tau: a_\tau = a} x_\tau x_\tau^T + I_d\): 디자인 행렬 + 정규화
  • \(b_a = \sum_{\tau: a_\tau = a} r_\tau x_\tau\): 보상 가중 문맥 합
  • \(\alpha\): 탐색 강도 (큰 \(\alpha\) → 불확실한 arm을 더 적극 탐색)

1.4.2 A, b 행렬 업데이트 원리

시점 \(t\)에서 arm \(a_t\)를 선택하고 보상 \(r_t\)를 관찰하면:

\[ A_{a_t} \leftarrow A_{a_t} + x_t x_t^T \] \[ b_{a_t} \leftarrow b_{a_t} + r_t \cdot x_t \]

이는 온라인 Ridge 회귀의 충분통계량 업데이트다. \(A_a^{-1}\)은 \(\theta_a\)의 후방 공분산 행렬의 역할을 하며, 데이터가 쌓일수록 \(A_a^{-1}\)이 작아져 불확실성 보너스가 줄어든다.

1.4.3 α의 역할

\[ \alpha \text{ 크면:} \quad \text{탐색 강화 (더 다양한 arm 시도)} \] \[ \alpha \text{ 작으면:} \quad \text{활용 강화 (현재 추정 기반 선택)} \]

실무에서 \(\alpha \in [0.5, 2.0]\) 범위로 시작하고, 교차 검증이나 시뮬레이션으로 튜닝한다.

1.4.4 LinUCB 전체 구현

import numpy as np

class LinUCB:
    """
    Linear Upper Confidence Bound (LinUCB) for Contextual Bandit

    보상 모델: r = θ_a^T x + ε
    행동 선택: a = argmax_a [θ̂_a^T x + α √(x^T A_a^{-1} x)]
    """
    def __init__(self, n_arms, n_features, alpha=1.0):
        self.n_arms = n_arms
        self.n_features = n_features
        self.alpha = alpha

        # 각 arm별 충분통계량
        self.A = [np.eye(n_features) for _ in range(n_arms)]
        self.b = [np.zeros(n_features) for _ in range(n_arms)]

        # 추적용
        self.counts = np.zeros(n_arms)

    def select_arm(self, context):
        """문맥 x를 보고 UCB가 가장 높은 arm 선택"""
        ucb_values = np.zeros(self.n_arms)

        for a in range(self.n_arms):
            A_inv = np.linalg.inv(self.A[a])
            theta_hat = A_inv @ self.b[a]

            # UCB = 예측 보상 + 탐색 보너스
            predicted_reward = theta_hat @ context
            uncertainty = self.alpha * np.sqrt(context @ A_inv @ context)
            ucb_values[a] = predicted_reward + uncertainty

        return np.argmax(ucb_values)

    def update(self, arm, context, reward):
        """관찰된 (context, reward) 쌍으로 arm의 파라미터 업데이트"""
        self.A[arm] += np.outer(context, context)
        self.b[arm] += reward * context
        self.counts[arm] += 1

    def get_theta(self, arm):
        """arm의 현재 추정 계수 반환"""
        return np.linalg.inv(self.A[arm]) @ self.b[arm]

1.5 Thompson Sampling

1.5.1 베이지안 접근

LinUCB가 빈도주의적 신뢰구간으로 탐색한다면, Thompson Sampling은 후방 분포에서 샘플링하여 탐색한다.

1.5.2 Beta-Binomial (이진 보상)

보상이 0/1 (전환 여부)일 때:

\[ \theta_a \sim \text{Beta}(\alpha_a, \beta_a) \]

  • 사전 분포: \(\text{Beta}(1, 1)\) (균등)
  • 업데이트: 성공 시 \(\alpha_a \leftarrow \alpha_a + 1\), 실패 시 \(\beta_a \leftarrow \beta_a + 1\)
  • 행동 선택: 각 arm에서 \(\tilde{\theta}_a \sim \text{Beta}(\alpha_a, \beta_a)\) 샘플링 → 최대 arm 선택
class ThompsonSamplingBinary:
    """
    Thompson Sampling for Binary Rewards (Beta-Binomial)
    전환 여부(0/1) 같은 이진 보상에 적합
    """
    def __init__(self, n_arms):
        self.n_arms = n_arms
        self.alpha = np.ones(n_arms)   # 성공 횟수 + 1
        self.beta = np.ones(n_arms)    # 실패 횟수 + 1

    def select_arm(self, context=None):
        # 각 arm의 Beta 후방에서 샘플링
        samples = np.random.beta(self.alpha, self.beta)
        return np.argmax(samples)

    def update(self, arm, reward):
        if reward >= 0.5:  # 이진화
            self.alpha[arm] += 1
        else:
            self.beta[arm] += 1

1.5.3 Normal-Normal (연속 보상)

보상이 연속값(만족도 1~5)일 때:

\[ \theta_a | \text{data} \sim \mathcal{N}\left(\hat{\mu}_a, \frac{\sigma^2}{n_a}\right) \]

  • \(\hat{\mu}_a\): arm \(a\)의 표본 평균
  • \(n_a\): arm \(a\)의 관찰 수
  • 행동 선택: \(\tilde{\theta}_a \sim \mathcal{N}(\hat{\mu}_a, \sigma^2/n_a)\) 샘플링 → 최대 arm 선택
class ThompsonSamplingNormal:
    """
    Thompson Sampling for Continuous Rewards (Normal-Normal)
    만족도 같은 연속 보상에 적합
    """
    def __init__(self, n_arms, prior_mean=0.0, prior_var=1.0, noise_var=1.0):
        self.n_arms = n_arms
        self.noise_var = noise_var

        # 각 arm의 후방 파라미터
        self.mu = np.full(n_arms, prior_mean)
        self.var = np.full(n_arms, prior_var)
        self.counts = np.zeros(n_arms)
        self.sum_rewards = np.zeros(n_arms)

    def select_arm(self, context=None):
        samples = np.array([
            np.random.normal(self.mu[a], np.sqrt(self.var[a]))
            for a in range(self.n_arms)
        ])
        return np.argmax(samples)

    def update(self, arm, reward):
        self.counts[arm] += 1
        self.sum_rewards[arm] += reward

        n = self.counts[arm]
        # 후방 업데이트 (conjugate Normal-Normal)
        posterior_precision = 1.0 / self.var[arm] + n / self.noise_var
        self.var[arm] = 1.0 / posterior_precision
        self.mu[arm] = self.var[arm] * (
            self.mu[arm] / self.var[arm] + self.sum_rewards[arm] / self.noise_var
        )

1.6 LinUCB vs Thompson Sampling 비교

측면 LinUCB Thompson Sampling
탐색 원리 신뢰 상한 (낙관주의) 후방 샘플링 (확률적 탐색)
보상 모델 선형 \(r = \theta^T x\) 임의 (사전 분포 선택)
문맥 활용 자연스러움 (선형 모델) Contextual 확장 시 복잡
계산 비용 \(O(d^2 K)\) (역행렬) 샘플링 비용 (보통 저렴)
Regret bound \(O(d\sqrt{T \ln T})\) \(O(d\sqrt{T \ln T})\) (유사)
구현 난이도 중간 이진 보상 쉬움, 연속 보상 중간
실무 선호 해석 용이, 디버깅 쉬움 성능 약간 우세, 유연성

1.7 실무 예시: AI Agent 프롬프트 전략 최적화

1.7.1 실험 설정

Arms (K=3):
  0: 기본 프롬프트
  1: 공감형 프롬프트
  2: 단계별 가이드 프롬프트

Context (d=7):
  [segment_MIEP, segment_N, avg_satisfaction, emotion_score,
   session_count, personalized_ratio, bias]

사용자 세그먼트:
  SI (Self-Improver): 기본 전략에 잘 반응
  MIEP (Motivated but Inexperienced): 단계별 가이드에 잘 반응
  N (Needs Support): 공감형에 잘 반응

시뮬레이션 규모: 2000 상호작용

1.7.2 시뮬레이션 코드

import numpy as np
import matplotlib.pyplot as plt

# 실제 보상 함수 (시뮬레이션용 — 실제로는 서비스에서 관찰)
def true_reward(context, arm):
    """세그먼트별 차별적 보상"""
    seg_miep, seg_n = context[0], context[1]
    base = 3.0 + 0.3 * context[2]  # 기본 만족도

    if arm == 0:      # 기본
        return base + np.random.normal(0, 0.3)
    elif arm == 1:    # 공감형 → N에 효과적
        bonus = 0.6 * seg_n + 0.1 * seg_miep
        return base + bonus + np.random.normal(0, 0.3)
    else:             # 단계별 → MIEP에 효과적
        bonus = 0.5 * seg_miep + 0.05 * seg_n
        return base + bonus + np.random.normal(0, 0.3)

def generate_context():
    """무작위 사용자 문맥 생성"""
    segment = np.random.choice(["SI", "MIEP", "N"], p=[0.4, 0.35, 0.25])
    return np.array([
        1.0 if segment == "MIEP" else 0.0,
        1.0 if segment == "N" else 0.0,
        np.random.uniform(2.5, 4.5),   # avg_satisfaction
        np.random.uniform(-1, 1),       # emotion_score
        np.random.randint(1, 20) / 20,  # session_count (정규화)
        np.random.uniform(0, 1),        # personalized_ratio
        1.0                              # bias
    ])

# 시뮬레이션 실행
T = 2000
n_arms, n_features = 3, 7

bandit = LinUCB(n_arms=n_arms, n_features=n_features, alpha=1.5)

rewards_linucb = []
optimal_rewards = []

for t in range(T):
    ctx = generate_context()

    # LinUCB 선택
    arm = bandit.select_arm(ctx)
    reward = true_reward(ctx, arm)
    bandit.update(arm, ctx, reward)
    rewards_linucb.append(reward)

    # 최적 보상 (오라클)
    best_reward = max(true_reward(ctx, a) for a in range(n_arms))
    optimal_rewards.append(best_reward)

# 누적 후회 계산
regret_linucb = np.cumsum(np.array(optimal_rewards) - np.array(rewards_linucb))

1.7.3 A/B 테스트 비교 시뮬레이션

# A/B 테스트 시뮬레이션
rewards_ab = []
explore_period = 600  # 처음 600회는 균등 배정 (탐색)

arm_rewards = {0: [], 1: [], 2: []}
for t in range(T):
    ctx = generate_context()

    if t < explore_period:
        arm = t % 3  # 균등 탐색
    else:
        # 탐색 기간의 평균 보상 기준으로 승자 선택
        arm = max(arm_rewards, key=lambda a: np.mean(arm_rewards[a]))

    reward = true_reward(ctx, arm)
    arm_rewards[arm].append(reward)
    rewards_ab.append(reward)
    optimal_rewards_ab = max(true_reward(ctx, a) for a in range(n_arms))

regret_ab = np.cumsum(np.array(optimal_rewards) - np.array(rewards_ab))

# 시각화
plt.figure(figsize=(10, 6))
plt.plot(regret_linucb, label="LinUCB", linewidth=2)
plt.plot(regret_ab, label="A/B Test", linewidth=2, linestyle="--")
plt.xlabel("Interactions (t)")
plt.ylabel("Cumulative Regret")
plt.title("LinUCB vs A/B Test: Cumulative Regret")
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

1.7.4 결과 해석

2000번 상호작용 시뮬레이션 결과:

A/B 테스트:
  탐색 기간 (t < 600): 균등 배정 → Regret 선형 증가
  활용 기간 (t ≥ 600): 승자 전략 고정 → 증가 둔화
  총 누적 후회: ~480

LinUCB (α=1.5):
  초기: 빠르게 탐색, 불확실한 arm 우선
  중기: 점차 최적 arm으로 수렴
  후기: 거의 최적 선택만
  총 누적 후회: ~280   (A/B 대비 41% 감소)

Thompson Sampling:
  더 부드러운 탐색-활용 전환
  총 누적 후회: ~250   (A/B 대비 48% 감소)

1.8 Contextual Bandit의 한계

1.8.1 순차적 의존성 무시

Contextual Bandit은 각 시점이 독립이라고 가정한다:

Bandit 가정:
  t=1: x₁ → a₁ → r₁
  t=2: x₂ → a₂ → r₂   (x₂는 a₁과 무관)

현실:
  t=1: 공감형 프롬프트 사용 → 사용자 만족도 상승
  t=2: 상승된 만족도가 상태에 반영 → 다음 행동 선택에 영향

→ 현재 행동이 미래 상태를 바꾸는 경우, Bandit은 장기 최적화 불가
→ Dynamic Treatment Regime (DTR)으로 확장 필요

1.8.2 그 외 한계

  • 선형 보상 가정: 보상이 비선형이면 성능 저하 → Kernel UCB, Neural UCB 확장
  • 비정상(Non-stationary) 환경: 보상 분포가 시간에 따라 변하면 적응 필요
  • 지연 보상(Delayed Reward): 보상이 즉시 관찰되지 않을 때 업데이트 지연

1.9 요약

개념 핵심
A/B 테스트 한계 정적 배정, 탐색 비용(Regret) 선형 증가
MAB ε-greedy, UCB — 문맥 없이 전체 평균 기반
Contextual Bandit 문맥 \(x_t\) 관찰 → 개인화된 행동 선택
LinUCB Ridge 추정 + 불확실성 보너스: \(\hat{\theta}^T x + \alpha\sqrt{x^T A^{-1} x}\)
Thompson Sampling 후방 분포에서 샘플링하여 낙관적 선택
A/B 대비 효과 누적 후회 41~48% 감소
한계 순차적 의존성 무시 → DTR 확장 필요

다음 글: 30 — Dynamic Treatment Regime (DTR) — 현재 행동이 미래 상태에 영향을 미치는 순차적 의사결정을 Q-learning으로 최적화한다.

Subscribe

Enjoy this blog? Get notified of new posts by email: