Sequential and Adaptive Decision-Making — From Bandits to Dynamic Treatment Regimes

대부분의 실전 의사결정은 한 번으로 끝나지 않는다. 환자의 1차 치료가 다음 달의 상태를 바꾸고, 그 상태가 2차 치료의 선택지를 다시 규정한다. 광고 입찰 한 건이 예산을 깎고, 남은 예산이 이후 모든 입찰의 여유를 결정한다. 결정이 시간 축을 따라 연쇄(cascade) 하고, 더 까다롭게는 각 선택이 우리가 앞으로 무엇을 배울지를 바꾼다. 이런 세계에서 한 번 학습해 고정해 둔 정적(static) 정책은 빠르게 무너진다. 이 글은 bandits에서 출발해 off-policy evaluation을 거쳐 dynamic treatment regimes로 이어지는 하나의 척추(spine) 를 따라가며, 임상 adaptive trial과 real-time bidding이 왜 같은 수학을 공유하는지를 정리한다.

통합 아이디어: 학습과 행동이 얽힐 때

정적 supervised learning의 암묵적 전제는 “데이터는 외생적으로 주어지고, 모델은 그것을 수동적으로 적합한다”이다. 순차적 의사결정은 이 전제를 깬다. 우리가 선택한 행동이 곧 다음 데이터를 생성한다. 여기서 두 가지 본질적 난점이 생긴다.

• Exploration–exploitation 긴장. 지금 최선으로 보이는 행동만 반복하면(exploit) 더 나은 대안을 영영 못 볼 수 있고, 정보를 모으려 낯선 행동을 시도하면(explore) 단기 보상을 희생한다.
• 분포 이동(distribution shift)과 counterfactual. 우리가 실제로 시도한 행동의 결과만 관측되고, 시도하지 않은 행동의 결과는 영영 결측이다. 이는 off-policy evaluation과 인과추론을 같은 문제의 두 얼굴로 만든다 — “관측된 로그로 다른 정책의 가치를 추정”하는 것은 본질적으로 counterfactual 질문이다.

이 두 난점을 관통하는 한 줄의 통합 원리는 이렇다: 불확실성을 정량화하고, 그 불확실성에 비례해 탐색하며, 행동이 미래를 바꾸는 구조를 명시적으로 모델링하라. 이 원리가 아래의 방법 아크 전체를 관통한다.

방법 아크

1. Bandits — 가장 순수한 형태의 탐색-활용

Multi-armed bandit(MAB)은 순차 의사결정을 가장 앙상하게 추린 모델이다. $K$개의 arm 중 매 라운드 하나를 당겨 보상을 관측하고, 누적 후회(cumulative regret)

$R_T = T\mu^\* - \mathbb{E}\Big[\sum_{t=1}^T \mu_{A_t}\Big],\qquad \mu^\* = \max_k \mu_k$

를 최소화한다. 여기엔 상태 전이도, 맥락도 없다 — 오직 explore–exploit의 균형만 있다. 두 정전(canonical) 전략이 이 균형을 푼다.

• UCB (Upper Confidence Bound). “불확실성 앞에서 낙관하라(optimism in the face of uncertainty).” 각 arm의 추정 평균에 신뢰 보너스를 더해 $A_t = \arg\max_k(\hat\mu_k + \sqrt{2\log t / N_k})$를 당긴다. 이 결정론적 규칙이 Lai–Robbins 하한에 닿는 $O(\log T)$ regret을 달성한다.
• Thompson Sampling. 베이지안 관점 — 각 arm의 보상 파라미터에 대한 사후분포에서 표본을 뽑아, 표본이 가장 큰 arm을 당긴다. “arm이 최적일 사후확률에 비례해 선택”하는 probability matching으로, 불확실한 arm은 가끔 큰 표본을 뽑아 자연스럽게 탐색된다. 구현이 단순하고 실증 성능이 강건해 산업 현장에서 널리 쓰인다.

맥락이 들어오면 contextual bandit으로 확장된다. 매 라운드 맥락 $x_t$(환자 특성, 사용자 프로필)를 먼저 관측하고, 그 맥락에 조건부로 최적 행동을 학습한다. 후회는 $\text{Regret}_T = \sum_t [r^*(x_t) - r(x_t, a_t)]$로, 보상을 맥락의 함수로 모델링한다(LinUCB는 선형 가정 + UCB의 대표 사례). 이 단계에서 의사결정은 이미 개인화(personalization) 다 — “이 맥락에 무엇이 최적인가”를 묻기 때문이다.

2. 상태가 행동에 반응할 때 — MDP

Bandit의 결정적 한계는 각 결정이 독립이라는 점이다. 하지만 현실에서 오늘의 행동은 내일의 상태를 바꾼다 — 재고가 줄고, 환자의 병기가 진행하고, 예산이 소진된다. 이 동역학을 명시하는 틀이 MDP(Markov Decision Process)다. 5-튜플 $(S, A, P, R, \gamma)$로 상태·행동·전이확률·보상·할인을 규정하고, Bellman 최적방정식

$V^*(s) = \max_a \Big[ R(s,a) + \gamma \sum_{s'} P(s'|s,a)\, V^*(s') \Big]$

으로 장기 가치를 정의한다. Contextual bandit은 사실상 전이가 없는 MDP의 특수 케이스($\gamma=0$ 또는 단일 스텝)이고, 반대로 MDP는 bandit에 시간 결합(temporal coupling)을 더한 일반화다. 여기서부터 강화학습(RL)의 영토가 시작된다.

3. 한 번 가본 길을 다시 평가하기 — Off-Policy Evaluation

순차 정책을 실제 환경에서 시험하는 건 비싸고, 임상에서는 비윤리적일 수도 있다. 그래서 핵심 질문이 바뀐다: 이미 모은 로그(behavior policy $\pi_b$로 수집)만으로, 아직 배포하지 않은 새 정책 $\pi_e$의 가치를 추정할 수 있는가? 이것이 off-policy evaluation(OPE)이며, 세 가지 정전 추정량이 bias–variance 스펙트럼을 가른다.

• Direct Method (DM). 보상 모델 $\hat Q$를 적합해 plug-in. 분산은 낮지만 모델 오설정(misspecification)에 취약.
• Inverse Propensity Scoring (IPS). 중요도 가중 $\hat V = \frac1n\sum \frac{\pi_e(a|x)}{\pi_b(a|x)} r$. 무편향이지만 가중치가 폭발하면 고분산.
• Doubly Robust (DR). DM의 plug-in에 IPS 보정을 결합 — 보상 모델과 propensity 모델 둘 중 하나만 맞아도 일치성(consistency)을 얻는다. 이는 doubly-robust 추정과 AIPW의 정책 평가판이다.

여기서 인과추론과 의사결정이 정식으로 만난다. OPE의 핵심 가정인 policy overlap(positivity)은 인과식별의 positivity와 같은 조건이고, 시도하지 않은 행동의 결측 결과를 추정하는 일은 곧 counterfactual 추론이다. 정책을 평가에서 학습으로 밀면 policy learning에 닿는다 — 추정된 개인별 효과를 입력으로 받아, 결정 트리 형태의 해석 가능한 정책 규칙 $\pi^*(x)=\arg\max_a E[Y(a)\mid X=x]$를 학습하고, 정책 가치 $V(\pi)=E[\tau(X)\,\mathbf 1\{\pi(X)=1\}]$를 최대화한다(Athey–Wager). 블랙박스 효과 추정과 달리 “왜 이 맥락에 이 행동인가”를 규제·임상 검토에 설명할 수 있다.

4. 시간 축의 개인화 — Dynamic Treatment Regimes

마지막 단계는 위의 조각들을 임상 시계열로 통합한다. Dynamic treatment regime(DTR)은 누적 이력 $H_t$(공변량·이전 처치·중간 결과)를 처치로 사상하는 결정규칙의 열 $\{d_t(H_t)\}_{t=1}^T$이고, optimal treatment regime(OTR)은 기대 장기결과 $E[Y^d]$를 최대화하는 규칙 열이다. “지금까지의 모든 것을 보고, 다음에 무엇을 할지”를 정해 최종 결과를 최적화한다 — 본질적으로 시간 축으로 확장된 personalization이다. 추정 도구는 RL과 인과추론의 합류점에 있다.

• Q-learning — Q-함수를 후진귀납(backward induction)으로 회귀 적합.
• A-learning — contrast/advantage만 모델링해 baseline 오설정에 강건.
• G-estimation — Robins의 structural nested mean model.
• OWL (outcome-weighted learning) — 정책 학습을 가중 분류 문제로 환원.

핵심 식별 가정은 sequential ignorability(매 시점, 관측 이력 조건부로 처치가 미래 잠재결과와 독립)로, 이는 단일 시점 무교란(no unmeasured confounding)을 시간 축으로 일반화한 것이다. DTR은 결국 bandit의 explore–exploit, MDP의 시간 결합, OPE/policy learning의 counterfactual 평가를 하나의 순차적 임상 의사결정 안에 모두 담는다.

왜 도메인을 가로질러 중요한가

이 척추가 단일하다는 점이 실용적 핵심이다. 표면 도메인은 달라도 수학 코어는 같다.

• 임상 adaptive trial. 환자가 순차 등록되고, 중간 결과가 다음 배정 확률을 갱신한다. response-adaptive randomization은 사실상 bandit이고, 다단계 치료 최적화는 DTR/OTR이며, 새 프로토콜을 환자에게 노출하기 전 기존 시험 로그로 평가하는 것은 OPE다.
• Real-time bidding (RTB). 광고 경매가 초당 수만 건 흐르고, 맥락(사용자·페이지·시간)에 조건부로 입찰가를 정한다 — contextual/linear bandit. 예산은 시간에 걸쳐 소진되는 상태 변수이므로 MDP의 시간 결합이 작동하고, 배포 전 새 입찰 정책의 가치는 budget OPE로 추정한다.

같은 네 단계 — 탐색-활용, 상태 동역학, off-policy 평가, 시간 축 개인화 — 가 두 도메인 모두를 받친다. 한쪽에서 얻은 regret bound나 doubly-robust 추정량은 다른 쪽으로 직접 옮겨간다. 이것이 “personalized decision-making under uncertainty”를 임상과 산업의 양면(duality) 으로 보는 관점의 방법론적 근거다.

한 가지 정직한 경계: 이 모든 보증(regret bound, consistency, coverage)은 가정에 의존한다 — overlap/positivity, sequential ignorability, 모델 적합성. 가정이 깨지면 추정은 조용히 편향된다. 그래서 분포자유 보증(anytime-valid OPE, conformal 류)과 민감도 분석은 부가물이 아니라, 순차 의사결정을 실전에 배치할 때의 필수 안전층이다.

Related Concepts

• Decision-Making Overview — 이 글이 압축한 전체 지형의 허브
• Multi-Armed Bandits · Contextual Bandits · Thompson Sampling — 탐색-활용
• MDP — 상태가 행동에 반응하는 순차 결정
• Off-Policy Evaluation · Policy Trees — counterfactual 정책 평가·학습
• Dynamic Treatment Regimes — 시간 축의 개인화 치료규칙