문맥 밴딧

통계 최적설계 수치해석 마지막 수정: 2026-08-22 04:13:52

1. 개요[편집]

문맥 밴딧 Contextual Bandit
다른 이름	연합 강화학습(associative RL) · 부분 라벨 학습 · "원스텝 RL"
한 줄 요약	매 라운드 문맥 $x_t$ 를 보고 팔을 고른다. 단, 상태 전이는 없다
선형 모형	$\mathbb{E}[r \mid x,a] = x_a^\top \theta^*$
대표 알고리즘	LinUCB (Li 외 2010) · 선형 톰슨 샘플링 · ε-탐욕
후회	$\tilde{O}(d\sqrt{T})$ — 팔 개수가 아니라 특징 차원이 지배
오프라인 평가	IPS · 이중강건(DR) — 겹침(positivity) 가정 필수
주 용도	추천·광고 · 적응적 실험설계 · 파라미터 자동 튜닝

문맥 밴딧(contextual bandit)은 매 라운드마다 문맥(context) $x_t$ 를 먼저 관측하고, 그 문맥에 따라 팔을 하나 골라 그 팔의 보상만 받는 순차적 의사결정 문제다. 다중 슬롯머신이 “어느 기계가 제일 잘 터지는가”를 묻는다면, 문맥 밴딧은 “이 사람에게는 어느 기계가 제일 잘 터지는가” 를 묻는다. 최적 팔이 하나로 고정되지 않고 문맥의 함수가 되는 순간, 문제는 순수한 탐험-활용 문제에서 지도학습과 탐험의 교배종으로 바뀐다.

형식은 단순하다. 라운드 $t$ 에서

환경이 문맥 $x_t$ 를 내놓는다(사용자 특징, 시간, 기기, 재고 상태 등).
학습자가 팔 $a_t \in \{1,\dots,K\}$ 를 고른다.
보상 $r_t$ 를 받는다. 고른 팔의 보상만 관측한다.

여기서 팔의 개수 $K$ 가 수만 개여도, 문맥과 팔이 $d$ 차원 특징 벡터로 요약되고 보상이 그 특징에 선형이라면 후회가 $K$ 가 아니라 $d$ 로 결정된다. 이 “특징을 통한 정보 공유”가 문맥 밴딧을 실용적으로 만든 결정적 성질이다.

2. 강화학습과의 경계선[편집]

이 문서에서 제일 먼저 못 박아야 할 것. 문맥 밴딧에는 상태 전이가 없다.

전면적 강화 학습에서는 행동이 다음 상태를 바꾼다 — 지금의 선택이 미래에 마주칠 상황을 결정하므로, 보상을 시간축 뒤로 되돌리는 신용 할당과 벨만 방정식·부트스트래핑이 필요하다. 문맥 밴딧에서는 $x_{t+1}$ 이 $a_t$ 와 독립이다. 문맥은 외부에서 i.i.d.로(혹은 적대적으로) 주어질 뿐 우리가 건드리지 못한다.

그래서 세 가지가 통째로 사라진다.

할인율도, 가치함수도 필요 없다. 매 라운드가 독립적인 원스텝 결정이므로 즉시 보상이 곧 목적함수다.
시간적 신용 할당이 없다. 보상 $r_t$ 는 명백히 $a_t$ 때문이다. 남는 것은 “어느 특징이 기여했나”라는 구조적 문제뿐이고, 그건 회귀 모형이 처리한다.
탐험의 목적이 다르다. 강화학습의 탐험은 “가보지 않은 상태에 가보는” 것이기도 하지만, 밴딧의 탐험은 순전히 보상 함수의 불확실성을 줄이기 위한 것이다.

마르코프 결정 과정의 언어로 쓰면, 문맥 밴딧은 상태 공간이 있지만 전이 확률이 정책과 무관한 MDP, 즉 $P(x_{t+1} \mid x_t, a_t) = P(x_{t+1})$ 인 퇴화한 MDP다. 밴딧이 상태 하나짜리 MDP였다면, 문맥 밴딧은 상태가 여럿이지만 그 상태들이 우리 행동에 반응하지 않는 MDP인 셈이다.¹

이 경계선이 실무에서 실제로 무너지는 지점도 분명하다. 추천을 계속 노출하면 사용자의 취향과 이후 방문 자체가 바뀐다(피드백 루프). 가격을 바꾸면 시장이 반응한다. 이런 경우 문맥 밴딧의 모형 가정이 깨지므로, 단기 지표는 좋아지는데 장기 지표가 나빠지는 전형적인 사고가 난다. “상태 전이가 없다”는 가정이 성립하는지를 먼저 확인하는 것이 알고리즘 선택보다 중요하다.

3. 선형 모형과 LinUCB[편집]

가장 널리 쓰이는 모형화는 선형 보상이다. 문맥 $x$ 와 팔 $a$ 를 합쳐 특징 벡터 $x_a \in \mathbb{R}^d$ 로 만들고

\mathbb{E}[r \mid x, a] = x_a^\top \theta^*

를 가정한다. 팔마다 별도의 $\theta_a$ 를 두는 분리형(disjoint)과, 모든 팔이 하나의 $\theta$ 를 공유하고 팔 정보를 특징에 넣는 공유형(shared/hybrid)이 있는데, 공유형이 팔 사이 정보 이전이 되므로 팔이 많고 데이터가 적을 때 유리하다.

LinUCB(Li, Chu, Langford, Schapire 2010)는 이 위에서 능형회귀와 신뢰타원을 결합한다. 지금까지 쓴 특징들을 모아

A_t = \lambda I + \sum_{s<t} x_{a_s} x_{a_s}^\top, \qquad \hat\theta_t = A_t^{-1} \sum_{s<t} x_{a_s} r_s

로 능형회귀 추정치를 만든다( $\lambda I$ 가 정칙화 항이자 초기 사전정보다). 그리고 각 팔에 대해

\mathrm{UCB}(a) = x_a^\top \hat\theta_t + \alpha \sqrt{x_a^\top A_t^{-1} x_a}

를 계산해 최대인 팔을 당긴다. 뒤의 항이 핵심이다. $\sqrt{x^\top A^{-1} x}$ 는 능형회귀 예측의 표준오차이자, 신뢰타원 $\{\theta : (\theta-\hat\theta)^\top A (\theta-\hat\theta) \le \beta\}$ 를 방향 $x$ 로 사영한 폭이다.

여기서 UCB1과의 결정적 차이가 나온다. UCB1의 보너스 $\sqrt{2\ln t / N_k}$ 는 팔별 방문 횟수만 본다. LinUCB의 보너스는 특징 공간의 방향을 본다 — 이미 여러 번 본 방향으로는 $A^{-1}$ 이 작아 타원이 납작해지고, 한 번도 안 본 방향으로는 여전히 뚱뚱하다. 그래서 한 번도 당기지 않은 팔이라도 그 특징이 이미 본 방향들의 조합이면 탐험할 필요가 없다. 팔이 100만 개여도 $d$ 가 작으면 학습이 되는 이유가 이것이다.

후회 한계는 $\tilde{O}(d\sqrt{T})$ 다. 원논문에는 이론 분석이 없었고, 추(Chu) 등(2011)이 변형판(SupLinUCB)에 대해 $\tilde{O}(\sqrt{Td})$ 를 증명하며 $\Omega(\sqrt{Td})$ 하한도 함께 제시했다. 일반적인 선형 밴딧에 대해 깔끔한 자기정규화 마팅게일 논법으로 $\tilde{O}(d\sqrt{T})$ 를 준 것은 압바시-야드코리 등(2011)의 OFUL이며, 오늘날 신뢰타원의 표준 구성이 이 논문에서 나온다.

$\sqrt{T}$ 가 눈에 띌 것이다. 확률적 다중 슬롯머신의 $O(\ln T)$ 와 달리 문맥 밴딧의 후회는 $T$ 의 제곱근으로 자란다. 최적 팔이 문맥마다 다르므로 “차선 팔을 유한 번만 당기면 끝”이라는 구조가 성립하지 않기 때문이다. 대신 팔 개수 $K$ 에 대한 의존이 특징 차원 $d$ 로 대체되는데, 이것이 훨씬 남는 장사다.

4. 톰슨 샘플링의 문맥판[편집]

톰슨 샘플링을 선형 모형에 얹는 것도 자연스럽다. 관측 잡음을 가우시안으로 두면 $\theta$ 의 사후분포가 정규분포이고, 매 라운드

\tilde\theta_t \sim \mathcal{N}\!\left(\hat\theta_t,\ v^2 A_t^{-1}\right), \qquad a_t = \arg\max_a\ x_a^\top \tilde\theta_t

로 한 번 뽑아 탐욕적으로 행동한다. LinUCB가 신뢰타원의 가장 낙관적인 꼭짓점을 쓴다면, 선형 톰슨은 그 타원에서 무작위로 한 점을 뽑는다. 같은 불확실성 기하를 결정론적으로 쓰느냐 확률적으로 쓰느냐의 차이일 뿐이다. 아그라왈-고얄(2013)이 $\tilde{O}(d^{3/2}\sqrt{T})$ 의 후회 한계를 증명했다 — 이론상으로는 LinUCB보다 $\sqrt{d}$ 만큼 나쁘지만, 실측에서는 대체로 대등하거나 더 낫다.

실무에서 톰슨을 고르는 이유는 후회 상수보다 운영 편의다. 첫째, $\alpha$ 같은 탐험 폭 손잡이 대신 사후분포의 스케일이 자동으로 그 역할을 한다. 둘째, 지연 피드백과 배치 갱신에 강하다 — 보상이 몇 시간 뒤에 돌아오는 광고 시스템에서 UCB는 같은 팔을 계속 당기며 굳어지는데, 톰슨은 매 요청마다 다시 뽑으므로 자연스럽게 분산된다. 셋째, 선택 확률 $\pi(a \mid x)$ 를 그대로 로그에 남길 수 있어(아래 오프폴리시 평가에 필수) 감사가 쉽다. 결정론적 정책인 LinUCB는 성향점수가 0/1이라 이 지점에서 곤란해진다.

5. ε-탐욕은 왜 아직 살아 있나[편집]

문맥 밴딧의 ε-탐욕은 “회귀 모형 하나를 학습해 두고, 확률 $1-\varepsilon$ 로 예측 최대 팔을, $\varepsilon$ 로 균등 무작위 팔을 고른다”이다. 이론적으로는 촌스럽다. 탐험이 문맥과 무관하게 무차별적이고, 고정 $\varepsilon$ 이면 후회가 선형이며, 신뢰타원 같은 기하를 전혀 쓰지 않는다.

그런데 대규모 실증 비교에서 이 촌스러운 방법이 놀랄 만큼 잘 버틴다. 비에티·아가르왈·랭포드의 “문맥 밴딧 베이크오프”는 수백 개 데이터셋에 여러 알고리즘을 돌렸는데, 이론적으로 세련된 방법들이 단순한 탐욕·ε-탐욕류를 일관되게 이기지는 못했다. 이유를 뜯어보면 이렇다.

모형이 이미 틀렸다. 신뢰타원의 정당성은 선형 모형이 맞다는 가정에서 나온다. 현실의 보상은 선형이 아니고, 잘못된 모형의 신뢰구간은 잘못된 크기다.
문맥 자체가 탐험을 해 준다. 문맥이 계속 바뀌면 예측 최댓값 팔도 계속 바뀌므로, 명시적 탐험을 안 넣어도 데이터가 어느 정도 골고루 쌓인다(이른바 “공짜 탐험”).
$A^{-1}$ 유지 비용. $d$ 가 커지면 $d \times d$ 행렬을 팔마다 갱신·역행렬(혹은 셔먼-모리슨) 하는 비용이 만만치 않다. 비선형 모형(부스팅·신경망)으로 가면 신뢰타원 자체가 정의되지 않아 근사가 필요하다.

정리하면 모형이 잘 맞고 특징 차원이 작으면 LinUCB/톰슨이, 모형이 의심스럽고 특징이 크고 비선형이면 ε-탐욕 계열이 무난하다. 밴딧 문헌의 이론 상수를 현장에 그대로 대입하지 말라는 좋은 사례다.²

6. 오프폴리시 평가 — 로그로 정책을 채점하기[편집]

문맥 밴딧을 실무에 붙일 때 진짜 병목은 알고리즘이 아니라 평가다. 새 정책 $\pi$ 를 라이브 트래픽에 올려 보기 전에, 이미 쌓인 로그(과거 정책 $\mu$ 가 만든 $(x_i, a_i, r_i)$ 기록)만으로 $V(\pi) = \mathbb{E}_{x}\mathbb{E}_{a\sim\pi}[r]$ 를 추정하고 싶다. 이것이 오프폴리시 평가(off-policy evaluation, OPE)다.

가장 기본은 역성향 점수(inverse propensity scoring, IPS) 추정량이다.

\hat{V}_{\mathrm{IPS}}(\pi) = \frac{1}{n}\sum_{i=1}^{n} \frac{\pi(a_i \mid x_i)}{\mu(a_i \mid x_i)}\, r_i

로깅 정책이 잘 안 고르던 행동을 새 정책이 자주 고른다면 그 기록에 큰 가중치를 주는, 중요도 샘플링의 정책판이다. 두 조건만 있으면 불편추정량이다.

성향점수를 안다. $\mu(a\mid x)$ 를 로그에 같이 남겼어야 한다. 나중에 추정하려 들면 그때부터 편향이 들어온다. 밴딧 시스템을 만들 때 “무엇을 골랐는가”만 로깅하고 “어떤 확률로 골랐는가”를 안 남기는 것이 이 바닥 1번 실수다.
겹침(overlap, positivity). $\pi(a\mid x) > 0$ 인 모든 $(x,a)$ 에서 $\mu(a\mid x) > 0$ 이어야 한다. 로깅 정책이 절대 하지 않은 행동에 대해서는 데이터가 원리적으로 아무 말도 해 주지 않는다. 결정론적 정책으로 로깅해 놓고 나중에 다른 정책을 평가하려는 시도가 불가능한 이유이며, 탐험은 학습을 위해서만이 아니라 훗날의 평가를 위해서도 필요하다.

IPS의 약점은 분산이다. $\mu$ 가 작은 구간에서 가중치 $\pi/\mu$ 가 폭발해 추정치가 몇 개 표본에 좌우된다. 그래서 가중치 절단(clipping), 자기정규화(SNIPS) 같은 처방이 붙지만 전부 편향-분산 거래다.

다른 축은 직접법(direct method) — 보상 모형 $\hat{r}(x,a)$ 를 지도학습으로 적합하고 $\hat{V} = \frac{1}{n}\sum_i \sum_a \pi(a\mid x_i)\hat{r}(x_i,a)$ 로 계산한다. 분산은 작지만 모형이 틀리면 편향이 통째로 남는다.

두 방식을 합친 것이 이중강건(doubly robust, DR) 추정량이다(두디크·랭포드·리 2011).

\hat{V}_{\mathrm{DR}}(\pi) = \frac{1}{n}\sum_{i=1}^{n}\left[ \sum_a \pi(a\mid x_i)\,\hat{r}(x_i,a) \;+\; \frac{\pi(a_i\mid x_i)}{\mu(a_i \mid x_i)}\bigl(r_i - \hat{r}(x_i,a_i)\bigr) \right]

읽는 법은 “모형으로 일단 값을 매기고, 모형이 틀린 만큼(잔차)을 IPS로 보정한다”이다. 이름이 말하는 성질이 여기서 나온다 — 보상 모형이 맞거나 성향점수 모형이 맞거나, 둘 중 하나만 맞아도 불편이다. 게다가 $\hat{r}$ 이 대충이라도 맞으면 잔차가 작아져 IPS 항의 분산이 줄어든다. 인과추론의 AIPW 추정량과 같은 구조이며, 실제로 문맥 밴딧의 오프폴리시 문헌과 인과 추론의 처치효과 추정 문헌은 같은 수식을 다른 기호로 쓰고 있다.

주의할 점은 이중강건도 겹침 가정은 면제해 주지 않는다는 것이다. $\mu$ 가 0인 영역에서는 어떤 추정량도 외삽일 뿐이며, 그 외삽의 품질은 전적으로 보상 모형의 가정에 달려 있다.

7. 어디에 쓰나[편집]

추천·광고. LinUCB의 원논문 자체가 야후 프론트페이지 뉴스 기사 추천이었다. 기사는 계속 갈리고(팔이 짧게 살고), 사용자 특징은 풍부하며, 콜드스타트 기사에 얼마나 노출을 줄지가 정확히 탐험 문제다.
실험계획법의 적응판. 고정 배분 A/B 테스트가 “전체에 어느 안이 나은가”를 묻는다면, 문맥 밴딧은 “누구에게 어느 안이 나은가” 를 묻는다. 이질적 처치효과가 존재할 때 고정 A/B는 평균 하나를 얻고 끝나지만 문맥 밴딧은 개인화 정책을 얻는다. 대신 적응 수집 데이터의 검정이 까다로워지는 대가는 밴딧과 똑같이 치른다.
시뮬레이션 파라미터 튜닝. 해석 케이스마다(문맥 = 레이놀즈수·형상 특징·격자 크기) 어느 솔버 설정을 쓸지 고르는 문제로 읽을 수 있다. 전처리기·완화계수·시간적분 설정의 조합이 팔이고, 보상은 수렴 여부와 벽시계 시간이다. 케이스 특징이 설정 선택을 좌우한다는 점에서 문맥 밴딧의 전형이다. 반면 하나의 비싼 목적함수를 최소화하는 설계 최적화라면 밴딧이 아니라 베이지안 최적화가 맞는 도구다 — 밴딧은 누적 보상을, 베이즈 최적화는 최종 최적점을 목표로 한다.
임상·정책. 개인 특징에 따라 처치를 바꾸는 적응적 시험. 여기서는 후회보다 겹침·감사가능성·윤리적 제약이 설계를 지배한다.

비선형 보상으로 가면 커널 기반(가우시안 과정 UCB), 신경망 기반(신경망 마지막 층에만 톰슨을 얹는 Neural-Linear, 앙상블·드롭아웃으로 사후분포를 흉내 내는 방법)이 쓰인다. 공통 주제는 하나다 — 불확실성을 어떻게든 정량화해야 탐험을 설계할 수 있다. 신경망의 불확실성 추정이 여전히 어려운 문제라는 사실이, 딥 문맥 밴딧이 이론만큼 잘 안 되는 주된 이유다.³

8. 관련 문서[편집]

이 설정에 붙은 옛 이름이 연합 탐색(associative search)이다. 바르토·서턴 계열 문헌에서 “자극에 따라 다른 행동을 학습하되 미래 상태는 없는” 문제를 그렇게 불렀다. 요즘은 다들 문맥 밴딧이라 부르는데, 개인적으로는 “연합 탐색”이 더 정직한 이름 같다. “밴딧”이 붙으면 카지노 이미지 때문에 사람들이 자꾸 팔 개수만 세려 든다. ↩
밴딧 논문을 읽고 신나서 LinUCB를 붙였다가 “그냥 로지스틱 회귀 + ε=0.05” 기준선을 못 이기는 경험은 이 바닥의 통과의례에 가깝다. 대개 원인은 알고리즘이 아니라 (가) 특징이 나쁘거나 (나) 보상 지연이 며칠이거나 (다) 실은 상태 전이가 있는 문제였거나 셋 중 하나다. CFD로 치면 격자를 안 고치고 난류 모델만 바꿔 가며 실험 값에 맞추려는 짓과 같다. ↩
문맥 밴딧의 인기 문제 중 하나가 “탐험을 껐더니 성능이 올랐다” 는 보고다. 진짜로 탐험이 해로운 경우도 있지만(모형이 이미 충분히 좋고 트래픽이 많을 때), 대개는 평가 지표가 단기 클릭이라 탐험 비용은 즉시 보이고 탐험 이득은 나중에 오기 때문이다. 탐험의 가치를 재려면 오프폴리시 평가가 되는 로그가 있어야 하고, 그 로그를 남기려면 탐험을 해야 한다. 닭과 달걀. ↩