📊 statistics

On-Policy and Off-Policy Learning for Large Action Spaces

본 논문은 탐색과 후회 상한(regret bounds)을 개선하기 위해 온폴리시(on-policy) 학습을 위한 구조적 베이지안 방법을 제안함으로써 거대 행동 공간을 가진 컨텍스추얼 밴딧(contextual bandits)에서의 정책 학습 문제를 다루며, 이와 더불어 최적화된 목적 함수와 미분 가능한 비관적 접근법을 통해 추정 오차를 완화하고 편향-분산 트레이드오프를 조절하는 새로운 오프폴리시(off-policy) 기법을 제안한다.

원저자: Imad Aouali

게시일 2026-07-31

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Imad Aouali

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 수백만 개의 별이 있는 은하계에서 최적의 경로를 찾으려는 거대한 우주선의 선장이라고 상상해 보십시오. 당신이 방문할 별을 하나씩 고를 때마다, 그 선택이 좋았는지 나빴는지를 알려주는 아주 작고 희미한 신호를 받게 됩니다. 이것이 바로 컴퓨터가 아직 게임의 규칙을 모를 때 결정을 내리도록 돕는 인공지능의 한 분야인 **컨텍스추얼 밴딧(contextual bandits)**의 세계입니다. 여기서 "컨텍스트(context)"는 상황(예: 날씨나 기분)을, "액션(action)"은 당신이 하는 행동(예: 별을 선택하는 것)을, 그리고 "보상(reward)"은 결과(예: 보물을 찾거나 소행성에 부딪히는 것)를 의미합니다.

까다로운 점은 선택지의 개수가 엄청나다는 것입니다. 만약 백만 개의 별 중 어떤 것이 최선인지 추측해야 하는데, 한 번에 몇 개씩만 확인할 수 있다면, 당신은 잘못된 곳을 탐험하며 평생을 보낼 수도 있습니다. 이것이 바로 "거대 액션 공간(large action space)" 문제입니다. 이는 마치 도시 크기만한 건초더미에서 단 하나의 특정 바늘을 찾는 것과 같습니다. 그런데 당신은 한 번에 지푸라기 하나만을 뽑아볼 수 있고, 그것이 바늘이기를 바라야만 합니다. 과학자들이 이 문제에 관심을 갖는 이유는 이것이 영화 추천, 적절한 광고 노출, 혹은 새로운 약물 설계와 같은 기술의 핵심 엔진이기 때문입니다. 컴퓨터가 무작정 무작위로 추측하는 데 머물러 있다면, 시간과 비용을 낭비하게 됩니다.

이 논문은 컴퓨터가 수백만 개의 선택지에 직면했을 때 어떻게 똑똑한 결정을 내리도록 가르칠 것인가라는 문제를 다루며, 두 가지 서로 다른 전략, 즉 '진행하며 배우는 방식(on-policy)'과 '과거의 기록으로부터 배우는 방식(off-policy)'을 사용합니다.

온-폴리시(On-Policy) 모험: 지도를 들고 직접 해보며 배우기

먼저, 저자는 컴퓨터가 실시간으로 세상과 상호작용하며 배우는 "온-폴리시(on-policy)" 시나리오를 살펴봅니다. 수백만 권의 책이 있는 거대한 도서관을 탐험하고 있는데, 어떤 책이 좋은지는 모르는 상황을 상상해 보십시오. 일반적인 탐험가는 책 한 권을 골라 한 페이지를 읽고, 내용이 지루하면 처음부터 다시 시작하여 완전히 다른 책으로 옮겨갑니다. 이는 느리고 비효율적입니다.

이 논문은 **혼합 효과 톰슨 샘플링(Mixed-Effect Thompson Sampling, meTS)**을 사용하여 더 똑똑한 탐험가를 소개합니다. 모든 책을 각각의 독특한 미스터리로 취급하는 대신, 이 탐험가는 책들이 '장르'에 속한다는 사실을 알아차립니다. 탐험가는 "SF" 책들이 공통된 특성을 공유한다는 것을 학습합니다. 책들을 카테고리(예: 액션, 로맨스, 미스터리)로 그룹화함으로써, 탐험가는 단 몇 권의 책만으로도 해당 장르 전체에 대해 배울 수 있습니다. 만약 재미있는 SF 책 한 권을 읽었다면, 탐험가는 다른 SF 책들도 좋을 수 있다는 힌트를 얻게 됩니다. 이러한 "정보의 공유"는 학습 속도를 획기적으로 높여줍니다. 수학적으로 보면, 컴퓨터는 수백만 개의 개별 책을 일일이 배울 필요 없이, 몇십 개의 "장르(잠재 효과)"와 그 장르 내 각 책의 고유한 특징만을 배우면 됩니다.

그 다음, 저자는 이 아이디어를 **확산 톰슨 샘플링(Diffusion Thompson Sampling, dTS)**으로 한 단계 더 발전시킵니다. 첫 번째 방법이 책을 장르별로 묶는 것이었다면, 이 새로운 방법은 책들 사이의 깊고 복잡한 연결 고리를 이해하는 초능력을 가진 사서와 같습니다. 어떤 책은 "사이버펑크"와 "역사 소설"이 섞여 있을 수도 있고, 혹은 다른 세기의 책과 특정한 문체를 공유할 수도 있습니다. "확산 모델(diffusion model)"(일부 이미지 생성 기술의 기반이 되는 AI 기술)을 사용하여, 컴퓨터는 모든 책이 서로 어떻게 연관되어 있는지에 대한 풍부하고 깊은 지도를 학습합니다. 이를 통해 컴퓨터는 도서관이 아무리 거대하더라도 훨씬 빠르게 탐험할 수 있습니다. 시뮬레이션 결과, 이 방법들은 모든 책을 낯선 존재로 취급했던 기존 방식보다 훨씬 빠르게 좋은 책들을 찾아냈습니다.

오프-폴리시(Off-Policy) 도전: 엉망진창인 일기장에서 배우기

다음으로, 논문은 "오프-폴리시(off-policy)" 시나리오를 다룹니다. 이제 당신은 더 이상 도서관을 직접 탐험할 수 없습니다. 대신, 취향이 매우 달랐던 이전 탐험가가 남긴 엉망진창인 일기를 통해 배워야 합니다. 예를 들어, 그 탐험가는 공포 영화만 읽었는데, 이제 당신은 최고의 로맨스 영화를 찾아야 하는 상황입니다. 이것이 바로 "오프-폴리시" 문제입니다. 즉, 다른 사람에 의해 수집된 데이터로부터 배우는 것입니다.

저자는 이 분야의 흔한 믿음에 도전합니다. 즉, 가장 중요한 것이 가장 정확한 "보상 추정기(reward estimator, 선택이 얼마나 좋을지 예측하는 수정구슬)"를 만드는 것이라는 믿음 말입니다. 논문은 거대한 도서관에서는 최적화(optimization)가 실제로 더 큰 문제라고 주장합니다. 이는 완벽한 지도(추정기)를 가지고 있지만, 고장 난 나침반(최적화 알고리즘)으로 길을 찾으려는 것과 같습니다. 수학적으로 볼 때, 이 지도를 사용하는 표준적인 방식들은 종종 "평탄한 고원(flat plateaus)"이나 국소적 함정에 빠지게 되어, 지도가 아무리 좋아도 최적의 경로를 찾는 것을 불가능하게 만듭니다.

이를 해결하기 위해 저자는 새로운 접근 방식인 **정책 가중 로그 가능도(Policy-Weighted Log-Likelihood, PWLL)**를 제안합니다. 이 방법은 정확한 보상을 예측하려고 애쓰는 대신, 최적화 경로를 매끄럽고 걷기 쉽게 만드는 데 집중합니다. 이는 울퉁불퉁하고 험난한 산길을 걷는 것에서 완만하고 구불구불한 도로로 바꾸는 것과 같습니다. 비록 도로가 완벽하게 직선은 아닐지라도, 정상에 도달하기는 훨씬 쉽습니다. 실험 결과, 이 단순하고 매끄러운 접근 방식은 길을 잃고 헤매던 복잡하고 "똑똑한" 추정기들을 지속적으로 이겼습니다.

또한, 논문은 오래된 일기 속에 존재하는 "노이즈"를 처리하는 새로운 방법을 소개합니다. 이전 탐험가가 특정 구역을 거의 방문하지 않았다면, 그 데이터는 신뢰하기 어렵습니다. 저자는 **지수 평활법(Exponential Smoothing)**과 "원칙적인 비관주의(principled pessimism)"를 결합할 것을 제안합니다. 이것은 일기를 신뢰하되 안전 장치를 추가하는 신중한 탐험가와 같습니다. 만약 일기에는 어떤 경로가 훌륭하다고 적혀 있지만 데이터가 불안정하다면, 탐험가는 재앙을 피하기 위해 그 경로가 보고된 것보다 약간은 더 나쁠 것이라고 가정합니다. 논문은 이 방법이 탐험가를 안전하게 지키면서도 효과적으로 학습할 수 있게 한다는 것을 수학적으로 증명하며, 데이터가 부족한 상황에서도 잘 작동함을 보여줍니다.

결론

요약하자면, 이 논문은 선택지가 수백만 개일 때 단순히 힘으로 밀어붙이는 방식(brute-force)으로는 안 된다는 것을 보여줍니다. 배운 것을 공유하기 위해 숨겨진 구조(장르나 깊은 연결 고리 등)를 찾아내야 하며, 학습 경로를 실제로 찾아낼 수 있을 만큼 매끄럽게 만들어야 합니다. 실시간으로 배우든 과거의 기록을 파헤치든, 핵심은 정보를 어떻게 그룹화하고 수학적 경로를 어떻게 항해하느냐에 달려 있습니다. 가공의 데이터와 실제 영화 추천 데이터셋 모두에서 테스트된 이 결과들은, 새로운 방법론들이 AI의 의사결정을 확장 가능하고 효율적으로 만드는 데 있어 중요한 진전임을 시사합니다.

기술 요약: 대규모 행동 공간을 위한 온-폴리시(On-Policy) 및 오프-폴리시(Off-Policy) 학습

문제 정의

본 논문은 상호작용 시스템, 특히 행동 공간 $K$ 가 매우 큰(수천에서 수백만 개에 이르는) 컨텍스트 밴딧(contextual bandits)에서 발생하는 근본적인 과제를 다룹니다. 이러한 설정에서 표준적인 온-폴리시(온라인) 및 오프-폴리시(오프라인) 학습 알고리즘은 심각한 확장성 병목 현상에 직면합니다:

온-폴리시: 톰슨 샘플링(Thompson Sampling, TS)이나 상한 신뢰 구간(Upper Confidence Bound, UCB)과 같은 표준 탐사 전략은 일반적으로 각 행동이 독립적인 파라미터를 갖는 분리된 모델에 의존합니다. 대규모 행동 공간에서 각 파라미터를 독립적으로 학습하는 것은 통계적으로 비효율적이며, 높은 누적 후회(cumulative regret)를 초래합니다. 반대로, 모든 행동 간에 파라미터를 공유하는 결합 모델(joint models)은 전체 공분산 행렬을 유지하고 업데이트하기 위한 $O(K^2)$ 또는 $O(K^3)$ 의 복잡도 때문에 계산적으로 다루기 어렵습니다.
오프-폴리시: 로깅 정책 $\pi_0$ $π_{0}$ 에 의해 수집된 정적 로그 데이터로부터 학습하는 것은 세 가지 주요 문제에 직면합니다:
1. 통계적 비효율성: 직접법(Direct Methods, DM)은 행동이 드물게 관찰될 때 높은 편향(bias)을 가집니다.
2. 분산: 역 성향 점수(Inverse Propensity Scoring, IPS) 추정치는 로깅 확률 $\pi_0(a|x)$ 가 작을 때 분산이 폭발하는 문제를 보입니다.
3. 최적화 불가능성: 본 논문은 대규모 행동 공간에서 표준 IPS 기반 목적 함수의 최적화 지형(optimization landscape)이 평탄한 고원(plateau)과 기하급수적으로 많은 지역 최적해(local maxima)를 가진 고도로 비볼록(non-concave)한 형태가 되어, 추정기의 통계적 품질과 관계없이 경사 하강법 기반 최적화 도구가 실패하게 된다고 주장합니다.

방법론 및 기여

본 논문은 두 부분으로 나뉘며, 각 학습 패러다임을 위한 새로운 방법을 제안합니다.

파트 I: 온-폴리시 학습 (톰슨 샘플링의 확장)

핵심 통찰은 분리된 보상 모델의 유연성을 유지하면서, 행동 간의 정보 공유를 가능하게 하는 **구조화된 베이지안 사전 분포(structured Bayesian priors)**를 도입하는 것입니다.

1. 혼합 효과 톰슨 샘플링 (Mixed-Effect Thompson Sampling, meTS) - 제3장

방법론: 저자들은 $L$ 개의 공유된 잠재 효과 파라미터 $\Psi = (\psi_\ell)_{\ell \in [L]}$ 를 통해 행동 파라미터 $\theta_a$ 가 결합되는 계층적 베이지안 모델을 도입합니다. 생성 과정은 $\theta_a | \Psi \sim p_0(\cdot|\Psi)$ 를 가정합니다.
알고리즘: meTS는 계층적 샘플링을 수행합니다. 먼저 사후 분포로부터 글로벌 효과 $\Psi_t$ 를 샘플링한 다음, $\Psi_t$ 가 조건이 된 개별 행동 파라미터 $\theta_{t,a}$ 를 샘플링합니다.
이론적 결과: 선형 가우시안 모델에 대해 저자들은 정확한 폐쇄형(closed-form) 사후 업데이트를 도출합니다. 저자들은 베이지안 후회(Bayesian regret) 바운드가 $\tilde{O}(\sqrt{Td K_{eff}})$ 임을 증명하며, 여기서 $K_{eff}$ 는 유효 행동 수입니다. $L \ll K$ 일 때 $K_{eff} \ll K$ 가 되어, 표준 TS에 비해 곱셈적 개선을 제공합니다.
복잡도: 이 방법은 메모리 복잡도를 $O(K^2d^2)$ 에서 $O((L^2 + K)d^2)$ 로, 실행 시간을 $O(K^3d^3)$ 에서 $O((L^3 + K)d^3)$ 로 줄입니다.
확장: 이 프레임워크는 다루기 쉬운 라플라스 근사(Laplace approximations)를 사용하여 일반화 선형 모델(GLM)로 확장됩니다.

2. 확산 톰슨 샘플링 (Diffusion Thompson Sampling, dTS) - 제4장

방법론: 행동 간의 더 복나 복잡하고 비선형적인 의존성을 포착하기 위해, 저자들은 단일 계층 잠재 구조를 사전 학습된 **확산 모델(diffusion models)**에 의해 제어되는 심층 잠재 변수 계층으로 대체합니다. 사전 분포는 비선형 연결 함수 $f_\ell$ 에 의해 연결된 잠재 변수의 마르코프 체인 $\psi_L \to \dots \to \psi_1 \to \theta_a$ 로 정의됩니다.
알고리즘: dTS는 재귀적 추론 절차를 사용합니다. 신경망을 통한 역전파 없이 (사전 정밀도와 데이터 정밀도를 결합하여) 연결 함수와 공분산을 가우시안 방식의 업데이트로 업데이트함으로써, 다루기 어려운 사후 분포를 근사합니다.
이론적 결과: 선형 가우시안 설정에서, 후회 바운드는 유효 행동 수와 $L$ 개 층 전체의 분산 합에 따라 스케일링됩니다. 복잡도는 $L$ 에 대해 선형적으로 스케일링되어, 즉 $O((L+K)d^2)$ 가 되어 meTS보다 개선되었습니다.
의의: 이는 딥 생성 모델이 단순히 표현(representation)을 위해서뿐만 아니라, 효율적인 탐사에 필요한 불확실성을 구조화하는 데에도 사용될 수 있음을 보여줍니다.

파트 II: 오프-폴리시 학습 (추정과 최적화 문제 해결)

본 논문은 기존의 "추정 중심(estimation-centric)" 패러다임에 이의를 제기하며 세 가지 상호 보완적인 접근 방식을 제안합니다.

1. 구조화된 직접법 (Structured Direct Method, sDM) - 제6장

방법론: meTS와 유사하게, sDM은 오프-폴리시 설정에서 행동 파라미터를 결합하기 위해 공유된 잠재 벡터 $\psi$ 를 도입합니다. 이는 잠재 효과에 대한 사후 분포와 행동 파라미터에 대한 조건부 사후 분포를 계산합니다.
결과: 저자들은 sDM이 제한적인 "전체 로깅 서포트(full logging support)" 가정을 요구하지 않고도 베이지안 하위 최적성(Bayesian suboptimality)에서 $O(1/\sqrt{n})$ 수렴을 달성함을 증명합니다. 이 바운드는 로깅 정책과 최적 정책 사이의 정렬(alignment)에 따라 달라집니다.
통찰: 고려된 베이지안 하위 최적성 기준 하에서, 탐욕적 정책(greedy policies)은 최적임이 입증되었으며, 비관적 정책(pessimistic policies)보다 우수할 수 있습니다. 이는 비관주의가 흔히 필요한 빈도주의(frequentist) 설정과 대조됩니다.

2. 최적화가 추정보다 중요하다 (Optimization Matters More Than Estimation) - 제7장

방법론: 저자들은 대규모 행동 공간에서 최적화 오차가 추정 오차보다 지배적임을 입증합니다. 표준 IPS 기반 목적 함수는 최적화 도구를 가두는 비볼록 지형을 유도합니다.
제안: 가치를 추정한 다음 최적화하는 대신, 본 논문은 정책 가중 로그 가능도(Policy-Weighted Log-Likelihood, PWLL) 목적 함수를 옹호합니다:
$\hat{U}_g(\pi) = \frac{1}{n} \sum_{i=1}^n g(R_i, \pi_0(A_i|X_i)) \log \pi(A_i|X_i)$
결과: 선형 소프트맥스 정책에 대해 PWLL 목적 함수는 볼록(concave)하며 ( $\ell_2$ 규제를 통해 강볼록(strongly concave)함), 유일한 전역 최적해를 보장합니다. 최대 100만 개의 행동이 있는 데이터셋에 대한 실험에서, 이 단순하고 안정적인 목적 함수는 정교한 가치 추정 기반 방법들을 일관되적으로 능가했습니다.

3. 지수 평활법을 위한 원칙적인 비관주의 (Principled Pessimism for Exponential Smoothing) - 제8장

방법론: IPS의 분산을 해결하기 위해, 저자들은 규제 없음과 강력한 분산 감소 사이를 보간하는 미분 가능한 지수 평활(Exponential Smoothing, ES) 추정기를 도입합니다.
이론: 이 규제된 추정기에 대해 양방향 PAC-Bayesian 일반화 바운드를 도출합니다. 이 바운드는 오차를 발산(divergence), 규제 편향(regularization bias), 그리고 남은 분산으로 분해합니다.
응용: 이 바운드는 확률적 경사 상승법(stochastic gradient ascent)을 통해 최적화할 수 있는 완전 미분 가능한 비관적 학습 목적 함수를 산출합니다. 이 프레임워크는 클리핑(clipping)이나 암묵적 탐사와 같은 다른 규제 기법을 포함하도록 통합됩니다.
확장: 또한 저자들은 클리핑의 부드럽고 미분 가능한 대안인 **로그 평활(Logarithmic Smoothing, LS)**을 도입하여 더 타이트한 집중 바운드(concentration bounds)를 달성합니다.

실험 결과

제안된 방법들은 합성 데이터 및 실제 데이터셋을 통해 검증되었습니다:

온-폴리시: 합성 선형 및 로지스틱 밴딧에서 meTS와 dTS는 베이스라인(LinTS, GLM-TS, HierTS)을 크게 능가하며, 행동 공간 $K$ 가 증가함에 따라 성능 격차가 더 커집니다. MovieLens 실험(추천 시스템)에서 meTS는 실제 보상 모델이 잘못 지정된 경우에도 가장 낮은 후회를 달성하여 강건성을 입증했습니다.
오프-폴리시:
- sDM은 표준 직접법보다 우수한 성능을 보이며, $K$ 가 커질수록 그 이득이 증가합니다.
- PWLL 목적 함수(제7장)는 최대 100만 개의 행동이 있는 데이터셋에서 최신 IPS 기반 방법들을 일관되게 능가하며, 하이퍼파라미터 튜닝에 대한 탁월한 강건성을 보여줍니다.
- PAC-Bayesian 비관적 목적 함수(제8장)는 다양한 로깅 정책의 품질(특히 로깅 정책이 균등하지 않을 때)에 걸쳐 베이스라인(London et al. 및 Sakhi et al. 포함)보다 더 나은 보상을 달성합니다.

의의 및 주장

본 논문은 이론적 밴딧 알고리즘과 현대 산업 시스템(예: 수백만 개의 아이템이 있는 추천 시스템)의 제약 사이의 간극을 메운다고 주장합니다. 핵심 주장은 대규모 행동 공간으로 확장하기 위해서는 다음이 필요하다는 것입니다:

불확실성의 구조화: 행동 간에 통계적 강점을 공유하기 위해 계층적 및 확산 기반 사전 분포를 사용함 (온-폴리시).
목적 함수의 재평가: 대규모 공간에서는 추정기의 통계적 정확도만큼이나 최적화 지형의 트랙터빌리티(tractability)가 중요하다는 것을 인식함 (오프-폴리시).
미분 가능한 비관주의: 다루기 힘든 상수들에 의존하지 않고 분산과 편향을 제어하는, 이론적으로 근거 있으면서도 계산적으로 실행 가능한 비관적 목적 함수를 개발함.

본 연구는 행동을 독립적으로 모델링하고 표준적인 가치 추정에 의존하는 방식에서 벗어남으로써, 컨텍스트 밴딧이 행동 공간이 수천 또는 수백만 개에 달하는 환경에서도 효과적으로 배치될 수 있음을 단언합니다.