로깅 데이터만으로는 못 잰다, OPE의 지수적 어려움

오프라인 데이터만으로는 정책품질을 못 잰다, 그 증명이 나왔어요

오프 정책 평가(Off-Policy Evaluation, OPE)는 다른 정책이 미리 모아 둔 궤적 로그만으로, 새로운 목표 정책이 얼마나 좋은 보상을 얻을지 추정하는 강화학습의 핵심 과제예요. 실제 환경을 반복 실행하기 어려운 추천, 헬스케어, 자율주행 같은 영역에서 특히 중요한 문제죠.

그런데 2026년 9월 arXiv에 올라온 논문이, 겉보기에 완벽히 건강해 보이는 로깅 데이터조차 목표 정책의 가치를 지수적으로 추정하기 어렵게 만들 수 있음을 이론과 실험으로 증명했어요.

부분 관측 환경과 커버리지 조건이라는 배경

OPE를 어렵게 만드는 첫 번째 벽은 환경이 부분 관측(POMDP)이라는 점이에요. 부분 관측 Markov 결정 과정은 에이전트가 현재 상태를 완전히 알고 행동하는 게 아니라, 관측 신호만으로 상태를 짐작해야 하는 조건부 환경을 뜻해요.

상태가 안 보이니, 로거가 남긴 궤적이 목표 정책의 가치를 담보할 만큼 상태 공간을 잘 '뒤덮는지'가 결정적이 돼요. 이걸 액션 커버리지·신념 커버리지·revealing(상태를 드러내는 정보성) 조건이라 부르는데, 기존 이론들은 이런 상수들이 유한하게 묶여 있으면 다항식 샘플 복잡도로 평가가 가능하다고 보장해 줬어요.

Zhang·Jiang이 남긴 미해결 빈칸

이 논문이 정면으로 잇는 건 Zhang과 Jiang이 2025년 ICLR에서 발표한 관련 연구의 빈칸이에요. 그분들은 로거가 단순히 현재 상태만 보는 게 아니라 과거 이력에 의존해 행동하는(history-dependent) 경우를 분석했는데, 모델 프리(model-free) 방식은 성립하기 어렵다는 하한을 보여 줬어요.

반면 모델 기반(model-based) 접근은 아직 열려 있다고 표에 남겨 두면서, 사실은 역시 어려울 것이라고 추측했어요. 새 논문은 바로 그 '모델 기반 + 과거 의존 로거'라는 조합에 대해 지수적 어려움을 완성한 거예요.

두 개의 레인과 하나의 리셋으로 만든 함정

구성은 놀랍게도 아주 단순해요. 두 개의 후보 환경(M0, M1)이 두 레인(0번·1번)으로 이뤄진 방향성 격자를 공유해요. agent는 관찰자에게 똑같이 보이는 복도를 지나가고, 첫 전이에서 continue 액션이 어느 레인으로 진입할지 결정하는데, 오직 이 첫 전이 하나만 두 모델이 달라요.

문제는 이후 등장하는 '게이트' 액션이 레인을 확정적으로 리셋한다는 점이에요. 리셋이 일어나면 처음에 어느 레인에 있었는지에 대한 정보가 통째로 지워져요. 목표 정책은 매 순간 continue만 하므로 리셋되지 않고, 결과적으로 목표 가치를 결정짓는 첫 전이 정보만 데이터에서 사라져요.

여기에 로거는 세 가지 메모리 상태(리셋 없음, 마지막 리셋 0, 마지막 리셋 1)를 갖는 과거 의존 정책이에요. 같은 물리적 상태에 도달했더라도 이력에 따라 다음 행동 분포가 달라져요. 예를 들어 M0에서 첫 continue과 첫 위쪽 게이트는 둘 다 에이전트를 0번 레인에 놓지만, 그 뒤 로거의 행동 분포는 (2/3, 1/6, 1/6)과 (1/6, 2/3, 1/6)로 갈라져요.

즉 상태만 아는 행렬 하나로 로거의 미래 법칙을 재현할 수가 없어요. 이 과거 의존성이 곧 '상태 커버리지는 충분한데 데이터는 무의미한' 상황을 만들어 내는 핵심 장치예요.

지수적으로 폭발하는 필요 샘플 수

이 구성 위에서 논문은 엄밀한 하한을 얻어요. 목표 정책을 1/8 오차 안에서 평가하려면, 신뢰도 1-δ에 대해 Θ((3/2)^H · log(1/δ))개의 로깅 궤적이 필요하다고 증명해요. 여기서 H는 에피소드 길이(수평)인데, (3/2)^H가 지수라 H가 조금만 길어져도 필요 샘플이 폭발해요.

게다가 이 하한은 두 후보 모델을 완전히 알고, 목표 정책에 원하는 만큼 질의할 수 있고, 계산 제약이 전무한 상태에서도 적용돼요. 보기 좋은 커버리지·revealing 상수들이 모두 H와 무관하게 유계여도 말이죠.

실험은 이 예측을 정확히 재현했어요. 90% 성공에 필요한 에피소드 수가 H=4에서 43개인데, H=24에서는 143,982개로 급증해요. 방향성 이중 레인 그리드월드 시뮬레이션의 실패율은 8.6%~10.2%로 이론 예측(약 10%)에 들어맞았어요.

참고로 같은 문제에서 처음부터 레인을 알려 주는 통제 실험은 어떤 H에서도 에피소드 4개면 충분해요. 어려움의 원인은 환경 자체가 아니라 '그 정보가 로그에서 사라지는 것'이라는 점이 확인되는 대목이에요.

실무에서 어떻게 받아들여야 할까

이 결과는 'OPE가 항상 어렵다'는 뜻은 아니에요. 정확히는, 특정한 behavior-marginal 방식의 보장에 대항하는 음성 결과로, 모든 POMDP가 이렇게 어렵다는 주장은 아니에요. 논문도 긍정적 보장을 얻으려면 로거의 지속이 실제 관측 이력에 묶인 추가 구조, 즉 상태와 로거 메모리를 함께 커버하는 joint coverage나 기억을 잊는(forgetting) 조건 같은 게 필요하다고 지적해요.

실용 관점의 시사점은 분명해요. 데이터 품질 지표가 겉보기에 좋다고 해서 목표 정책 평가가 쉬워지는 것은 아니라는 점이에요. 모든 상태를 자주 방문했고 커버리지 상수가 작다고 해도, 로깅 정책이 과거에 의존해 정보를 지우는 방식이라면 평가 비용이 기하급수적으로 커질 수 있어요.

그래서 로깅 정책과 목표 정책이 어떻게 갈라지는지, 특히 그 차이가 정말로 평가에 필요한 정보를 남기는지를 함께 점검해야 해요.

참고 링크

• 논문 원문 · Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging
• Zhang·Jiang 2025 · Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs
• Lean 4로 기계 검증한 공식화 저장소