Off-Policy Learning in Large Action Spaces: Optimization Matters More Than Estimation

기술 요약: 대규모 행동 공간에서의 오프폴리시 학습: 추정보다 최적화가 더 중요하다

문제 정의
오프라인 컨텍스추얼 밴딧(offline contextual bandits)에서의 오프폴리시 학습(off-policy learning, OPL)은 로그 데이터 $D_n = \{(X_i, A_i, R_i)\}$로부터 기대 보상 $V(\pi)$를 최대화하는 정책 $\hat{\pi}$를 학습하는 것을 목표로 한다. 지배적인 패러다임은 역확률 가중치(Inverse Propensity Scoring, IPS)에 기반한 오프폴리시 평가(off-policy evaluation, OPE) 추정치, 즉 $\hat{\pi} = \arg\max_\pi \hat{V}_{IPS}(\pi)$를 최적화하는 것이다. 최근의 연구들은 $V(\pi)$를 더 정확하게 근사하기 위해 통계적 특성(예: 분산 감소 또는 편향 감소)을 개선한 정교한 추정기를 개발하는 데 집중해 왔으나, 본 논문은 이러한 추정기 중심의 접근 방식이 결정적인 실질적 장애물인 '최적화 지형(optimization landscape)'을 간과하고 있다고 주장한다.

대규모 행동 공간(행동의 수 $K$가 수백만 개에 달할 수 있는 경우)에서, IPS 기반 목적 함수와 표준 정책 파라미터화(예: softmax)를 결합하면 심각한 최적화 병리 현상이 나타난다. 여기에는 경사 상승법(gradient ascent)이 정체되는 긴 고원(plateau) 현상과 수많은 좋지 않은 지역 최적해(local maxima)가 포함된다. 본 논문은 우수한 통계적 보증을 가진 추정기라 할지라도, 근본적인 최적화 문제가 $K$가 증가함에 따라 난해해지기 때문에 좋은 정책을 도출하는 데 실패한다고 상정한다.

방법론 및 분석
저자들은 대규모 행동 공간에서 최적화 안정성이 추정 정확도보다 더 중요하다는 주장을 뒷받침하기 위해 이론적 분석과 경험적 증거를 모두 제공한다.

1. IPS 기반 목적 함수의 이론적 분석:

   • 본 논문은 표준 IPS, Clipped IPS (cIPS), Exponential Smoothing (ES), Doubly Robust (DR), Marginalized IPS (MIPS), OffCEM, POTEC, 그리고 Policy Convolution (PC)을 포함한 다양한 IPS 기반 추정기의 "오라클 정책(oracle policies, 이론적 기대 목적 함수의 극대값)"을 분석한다.
   • 최적화 병리 현상: 저자들은 softmax 정책을 사용하는 linear-in-$\pi$ 추정기에 대해, 경사 상승법이 유효 행동 공간의 크기인 $K_{eff}$에 비례하는 $O(K_{eff})$번의 반복 횟수 동안 부적절한 영역에 갇혀 있을 수 있음을 증명한다. 또한, 이 지형에는 $K_{eff}$에 대해 지수적으로 많은 지역 최적해가 존재한다.
   • $K_{eff}$의 역할: MIPS나 OffCEM과 같이 대규모 행동 공간을 위해 설계된 방법들도 만약 전체 행동 공간 $A$에 대해 최적화를 수행한다면 ($K_{eff} = K$), 이를 완화하는 데 실패하는 경우가 많다. 식별된 유일한 예외는 클러스터 수준으로 최적화를 제한하여 $K_{eff}$를 효과적으로 줄이는 POTEC이다.
   • 목적 함수 인지적 파라미터화(Objective-Aware Parametrization): 저자들은 정책 클래스를 추정기의 귀납적 편향(inductive bias)과 일치시키도록 제안한다. 예를 들어, IPS 기반 방법의 경우 정책의 서포트(support)를 로깅 정책의 서포트 $S_0$로 제한하거나, 클러스터 기반 방법의 경우 2단계 분해를 사용하는 것은 통계적 타겟을 변경하지 않으면서도 $K_{eff}$를 줄이고 학습 가능성을 높일 수 있다. 그러나 이는 증상을 완화할 뿐이며, IPS 기반 목적 함수의 근본적인 비볼록성(non-concavity)을 치료하지는 못한다.

2. 정책 가중 로그 가능도(Policy-Weighted Log-Likelihood, PWLL) 목적 함수:

   • 근본적인 대안으로서, 본 논문은 $\hat{U}_g(\pi) = \frac{1}{n} \sum g(R_i, \pi_0(A_i|X_i)) \log \pi(A_i|X_i)$ 형태를 취하는 PWLL 목적 함수를 탐구한다.
   • 볼록성(Concavity): IPS 목적 함수와 달리, PWLL 목적 함수는 linear-softmax 정책을 사용할 때 본질적으로 볼록하며($\ell_2$ 정규화를 통해 강볼록성 확보), 이는 점수(scores)에서 로그 확률로의 사상이 오목하기 때문이다.
   • 최적화 보증: 저자들은 PWLL 목적 함수에 대한 확률적 경사 상승법(stochastic gradient ascent)이 일반적으로 $O(1/\sqrt{T})$의 전역 수렴 속도를 달성하며, 정규화를 사용할 경우 기하급수적인 속도로 가속됨을 입증한다.
   • 변형 모델: 본 연구는 Local Policy Improvement (LPI), Clipped LPI (cLPI), Regularized KL (RegKL)을 포함한 특정 PWLL 변형들을 평가한다. 특히, cLPI는 cIPS와 동일한 탐욕적 결정 규칙(greedy decision rule)을 유도하면서도 볼록 최적화 문제를 통해 이를 수행함을 보여준다.

주요 기여

1. 행동 공간에 따른 최적화 이론의 스케일링: 본 논문은 최적화 병리 현상(고원 및 지역 최적해)이 행동의 수 $K$에 따라 어떻게 확장되는지를 공식화하여, 왜 IPS 기반 목적 함수가 $K$가 커짐에 따라 최적화하기 점점 더 어려워지는지를 설명한다.
2. 목적 함수 인지적 파라미터화: 저자들은 다양한 목적 함수(오라클 정책으로부터 유도된)에 대한 최소 충분 정책 구조를 식별하고, 정책을 이러한 구조에 맞게 제한하거나 분해하는 것이 학습 가능성과 성능을 향상시킨다는 것을 입증한다.
3. 최적화 친화적 목적 함수로서의 PWLL: 본 논문은 linear-softmax 정책에 대해 PWLL 목적 함수가 잘 다루어지는 볼록한 최적화 지형을 제공하며, 가치 극대화의 강력한 대안이 됨을 보여준다 가치 극대화의 직접적인 대안이 된다.
4. 대규모 실험적 스트레스 테스트: MovieLens ($K=60k$), Twitch ($K=200k$), GoodReads ($K=1M$)의 세 가지 대규모 데이터셋에 대한 광범위한 실험을 통해, IPS 기반 방법들은 하이퍼파라미터(배치 크기, 학습률 스케줄)에 매우 민가한 반면, PWLL 방법들은 견고하며 지속적으로 더 높은 보상을 달성함을 보여준다.
5. 실행 가능한 가이드라인: 대규모 행동 공간을 위한 설계 규칙을 정리한다: 목적 함수 인지적 파라미터화를 사용하여 최적화 안정성을 우선시하고, 정책 학습을 위해 복잡한 IPS 추정기보다 PWLL 스타일의 목적 함수를 선호하라.

결과

• 최적화 민감도: 통제된 스윕 실험에서, IPS 기반 목적 함수(POTEC과 같은 최첨단 방법 포함)는 하이퍼파라미터가 최적이 아닐 경우 높은 분산과 성능 붕괴를 보였다. 반면, PWLL 방법(특히 cLPI)은 모든 설정에서 높은 성능을 유지했다.
• 추정 vs. 학습: 본 논문은 흥미로운 역설적 발견을 강조한다: 가치 추정기로서 낮은 평균 제곱 오차(MSE)를 가진 방법(예: MIPS)이 반드시 더 좋은 정책을 생성하는 것은 아니었다. 반대로, 가치 추정기로서는 MSE가 높은(즉, 성능이 낮은) PWLL 방법들이 가장 좋은 정책을 생성했다. 이는 대규모 행동 공간에서 목적 함수를 최적화하는 능력이 가치 추정의 통계적 정확도보다 정책 품질을 결정하는 더 강력한 예측 변수임을 시사한다.
• 파라미터화의 영향: 목적 함수의 귀납적 편향에 맞춰 유효 행동 공간을 제한하는 것(예: IPS를 위한 서포트 제한 정책 사용)은 IPS 방법의 안정성과 성능을 크게 개선했지만, 여전히 PWLL 방법에는 미치지 못했다.
• 견고성: PWLL 방법은 IPS 기반 접근 방식에 비해 보상 노이즈와 서로 다른 로깅 정책 서포트에 대해 우수한 견고성을 보였다.

의의 및 주장
본 논문은 오프폴리시 학습 분야가 추정기를 정교화하는 데 지나치게 집중한 나머지, 대규모 행동 공간에서 결정적인 병목 구간인 최적화 지형을 간과해 왔다고 주장한다. 저자들의 주장은 다음과 같다:

• 최적화가 병목이다: 대규모 행동 공간에서, 비볼록한 IPS 목적 함수를 최적화하는 어려움은 가장 정교한 통계적 추정기조차 실질적인 효용성을 떨어뜨린다.
• 단순함이 승리한다: PWLL(특히 cLPI)과 같이 최적화 친화적인 단순한 목적 함수는 복잡한 분산 감소 IPS 추정기보다 뛰어난 성능을 보이는데, 이는 이들이 안정적이고 신뢰할 수 있는 수렴을 허용하기 때문이다.
• 설계의 전환: 대규모 행동 공간을 위한 OPL 알고리즘 개발은 명시적으로 최적화 고려 사항을 다루어야 한다. 본 논문은 "추정기 중심" 설계에서 "최적화 중심" 설계로의 전환을 옹호하며, 정책 학습을 목적으로 할 때는 고정밀 가치 추정을 달성하는 것보다 다루기 쉬운 최적화 지형을 확보하는 것이 더 중요하다고 제안한다.

저자들은 한계점도 언급한다: PWLL 목적 함수는 정확한 가치 추정이 필요한 오프폴리시 평가(OPE)나 정책 선택에는 적합하지 않다. 또한, PWLL에 대한 볼록성 보증은 엄격하게 linear-softmax 정책에 적용된다. 딥 네트워크를 사용할 경우 형식적인 볼록성은 상실될 수 있으나, 경사 구조는 IPS 기반 목적 함수보다 훨씬 양호한 상태를 유지한다.