기술 요약: 벨만 완결성(Bellman Completeness)이 없는 적합된 점유율 비(Fitted Occupancy-Ratio) 평가

문제 정의

오프라인 정책 평가(Offline Policy Evaluation, OPE)는 행동 정책(behavior policy)으로부터 수집된 데이터를 사용하여 타겟 정책 $\pi$의 성능을 추정하는 것을 목표로 한다. 핵심적인 과제는 오프라인 데이터 분포 $\nu$와 타겟 정책의 할인된 상태-행동 점유 측도(discounted state-action occupancy measure) $d_{\pi,\gamma}$ 사이의 분포 변화(distributional shift)를 교정하는 것이다.

기존 방법론은 일반적으로 두 가지 범주로 나뉜다:

1. 가치 기반 방법 (예: Fitted Q-Evaluation, FQE): 이들은 벨만 타겟(Bellman targets)을 함수 클래스에 반복적으로 회귀시켜 가치 함수를 추정한다. 그러나 FQE에 대한 이론적 보장은 일반적으로 벨만 완결성(함수 클래스의 임의의 벨만 이미지(Bellman image)가 해당 클래스 내에 존재해야 함) 또는 투영된 벨만 연산자(projected Bellman operator)의 안정성을 요구한다. 이러한 조건이 충족되지 않으면, 벨만 연산자와 (오프라인 분포 하에서의) 투영의 합성(composition)이 수축(contractive)하지 않아 불안정성을 초래할 수 있다.
2. 비율 기반 방법 (예: Primal-Dual, Minimax): 이들은 크리틱 클래스(critic class)에 대해 균형 모멘트(balance moments)를 강제함으로써 점유율 비 $\omega_{\pi,\gamma} = d d_{\pi,\gamma} / d\nu$를 추정한다. 이러한 접근 방식은 일반적으로 이중 실현 가능성(dual realizability) 또는 수반 벨만 완결성(adjoint Bellman completeness, 즉 크리틱 클래스가 비율 클래스에 의해 생성된 잔차(residual)를 감지할 만큼 충분히 풍부해야 함)을 요구하며, 이는 근사 부담을 결합된 한 쌍의 클래스로 전이시킨다.

본 논문은 가치 함수 완결성이나 이중 완결성이 모두 성립하지 않지만, 타겟 점유율 비 자체는 가설 클래스에 의해 잘 근사되는 간극(gap) 문제를 다룬다.

방법론: 적합된 점유율 비 평가 (Fitted Occupancy-Ratio Evaluation, FORE)

저자들은 **적합된 점유율 비 평가(FORE)**를 제안하며, 이는 **수반 벨만 재귀(adjoint Bellman recursion)**를 통해 할인된 점유율 비를 추정하는 적합된 고정점(fitted fixed-point) 방법이다.

핵심 메커니즘

1. 수반 벨만 식별 (Adjoint Bellman Identification): 할인된 점유율 비는 $\omega_{\pi,\gamma} = B^\pi_\gamma \omega_{\pi,\gamma}$라는 고정점 방정식을 만족한다. 여기서 $B^\pi_\gamma$는 수반 벨만 연산자(adjoint Bellman operator)이다. 표준 벨만 연산자와 달리, $B^\pi_\gamma$는 밀도(density)에 작용한다.
2. KL-투영 반복 (KL-Projected Iteration): 미니맥스 사점(minimax saddle-point) 문제를 푸는 대신, FORE는 수반 벨만 맵(adjoint Bellman map)을 반복 수행한다. 각 단계 $k$에서, 추정치 $\omega^{(k)}$가 주어지면, 방법론은 정확한 벨만 이미지 $B^\pi_\gamma \omega^{(k)}$를 쿨백-라이블러(Kullback–Leibler, KL) 발산을 사용하여 정규화된 로그-비(log-ratios)의 가설 클래스 $\mathcal{W}$로 투영하여 다음 추정치 $\omega^{(k+1)}$를 계산한다:
   $$\omega^{(k+1)} = \Pi^{\text{KL}}_{\mathcal{W}} (B^\pi_\gamma \omega^{(k)})$$
3. 단일 수준 목적 함수 (Single-Level Objective): 결정적으로, 수반 벨만 이미지의 KL 투영은 단일 수준 밀도-비 목적 함수(Lemma 3.2)를 통해 계산될 수 있다. 이는 별도의 크리틱 클래스를 필요로 하지 않는다. 이 목적 함수는 다음을 포함한다:
   • 초기 상태 모멘트 $E_{d_0}[h(X)]$
   • 1단계 전이 모멘트 $E_\nu[\omega(X)h(X^+)]$
   • 로그-분할 정규화 항(log-partition normalization term)
     이를 통해 표준 지도 학습기(예: 그래디언트 부스팅 트리, 신경망)를 사용하여 구현할 수 있다.

이론적 토대

FORE의 안정성은 KL 발산의 기하학적 구조에 의존한다:

• KL 수축 (KL Contraction): 투영되지 않은 수반 벨만 연산자는 상대 엔트로피(KL 발산) 관점에서 계수 $\gamma$를 갖는 수축 사상이다 (Lemma 3.1).
• 호환 가능한 투영 (Compatible Projection): 투영이 동일한 KL 기하학 내에서 수행되기 때문에, 투영된 연산자는 이 수축 성질을 상속받는다.
• 근사 조건 (Approximation Condition): 핵심 요구 사항은 단순히 타겟 할인 점유율이 가설 클래스에 의해 **실현(또는 근사)**되는 것이다. 이 방법은 클래스가 수반 벨만 연산자에 대해 닫혀 있을 필요는 없다 (즉, 수반 벨만 완결성이 필요하지 않다).

제한된 커버리지 처리

타겟 정책이 오프라인 데이터에 의해 지원되지 않는 상태-행동 쌍을 방문하는 경우(절대 연속성 위반), 전체 비율을 식별할 수 없다. 저자들은 **커버리지 중단 FORE (Coverage-Stopped FORE)**를 도입하였다:

• 이는 첫 번째 미지원(uncovered) 상태-행동 쌍이 나타나기 전까지 축적된 할인 점유율을 목표로 한다.
• 학습된 **커버리지 분류기(coverage classifier)**를 사용하여 특이 성분(singular component)을 식별하고 제거한다.
• 약하게 커버된 영역에서의 추정을 정규화하기 위해 **클리핑(clipping)**을 사용한다.
• 결과적인 가치 추정치는 비음수 보상(non-negative rewards)에 대해 실제 타겟 정책 가치에 대한 보수적 하한(conservative lower bound) 역할을 한다.

주요 기여

1. 알고리즘 공식화: 할인된 점유율 비를 수반 벨만 재귀의 유일한 고정점으로 규정하고, 이를 반복적인 단일 수준 KL 밀도-비 목적 함수를 통해 추정하는 FORE를 도입하였다.
2. 모집단 이론 (Population Theory): 점유율-비 실현 가능성에 기반한 근사 이론을 개발하였다. KL-투영된 수반 벨만 연산자는 로그-비 클래스에 의한 근사 오차에 따라 실제 비율로 KL 발산 내에서 기하급수적으로 수렴하며, 이때 수반 벨만 완결성을 요구하지 않는다.
3. 유한 표본 보장 (Finite-Sample Guarantees): 경험적 적합 재귀에 대한 유한 표본 후회 경계(regret bounds)를 증명하였다. 일반화된 KL 오차는 기하급수적으로 감소하는 초기화 항, 모집단 KL 근사 항, 그리고 로그-비 및 유도된 승수(multiplier) 클래스의 국소 라데마허 복잡도(local Rademacher complexity)에 의해 결정되는 통계적 항으로 분해된다.
4. 정책 평가 응용:
   • 보상 재가중치 부여 (Reward Reweighting): 적합된 비율을 직접 사용하여 가치를 추정한다.
   • 이중 강건 추정 (Doubly Robust Estimation): 적합된 비율과 적합된 Q-함수를 결합한 곱 형태의 오차 경계를 제공한다.
   • FORE-가중 FQE: 벨만 완결성 없이도 벨만 재귀를 안정화하기 위해 적합된 비율을 FQE의 투영 가중치로 사용한다.
5. 커버리지 중단 확장: 제한된 커버리지 환경에 대한 확장으로서, 보수적 하한을 제공하고 유효한 커버리지를 진단한다.

결과

이론적 결과

• 수렴성: 점유율 비의 실현 가능성 하에서, 모집단 재귀는 KL 발산 내에서 기하급수적으로 수렴한다.
• 오차 경계: 유한 표본 오차 경계는 비율 클래스의 근사 오차와 가설 클래스의 통계적 복잡도(critical radius)에 따라 스케일링된다. 특히, 근사 오차 항은 $\sqrt{\epsilon_{KL}/(1-\gamma)}$로 스케일링되는데, 이는 벨만 완결성 가정 하의 가치 함수 경계에서 흔히 보이는 $(1-\gamma)^{-1}$ 스케일링보다 더 유리하다.
• 안정성: FQE를 가중치 메커니즘으로 사용할 때, 가치 함수 클래스가 벨만 완결적이지 않더라도 FORE는 안정성을 제공한다.

수치 실험

논문은 세 가지 실험을 통해 이론을 검증한다:

1. Baird 스타일의 유한 MRP: 선형 FQE가 오프라인 데이터 분포 하에서 불안정(확장적)할 수 있는 반면, FORE는 안정성을 유지하며 실제 비율로 수렴함을 보여준다. FORE-재가중 FQE 또한 가치 추정을 안정화한다.
2. 선형-가우시안 정책 평가: 가치 클래스가 벨만 완결적이지 않은 연속 환경에서, 선형 FQE는 실패(승수 > 1)한다. FORE는 빠르게 수렴하며(승수 $\approx 0.086$), FORE-재가중 FQE는 수축성을 회복시킨다. FORE는 MWL, DualDICE와 같은 미니맥스 방법론에 비해 더 낮은 밀도-비 오차와 경쟁력 있는 가치 RMSE를 달성한다.
3. 커버리지 중단 FORE: 불충분한 데이터 커버리지 상황에서, 표준 FORE와 사후 클리핑(post-hoc clipping)은 올바른 부분 확률 측도(sub-probability measure)를 목표로 하지 못한다. 커버리지 중단 FORE는 커버리지 중단 점유율을 성공적으로 회복하고, 다른 베이스라인보다 정확한 가치 하한을 제공한다.

의의 및 주장

본 논문은 오프라인 정책 평가를 위한 충분 조건으로 **할인된 점유율 비 실현 가능성(discounted occupancy-ratio realizability)**을 식별함으로써, 다음의 필요성을 제거한다고 주장한다:

• 가치 클래스의 벨만 완결성
• 비율 클래스의 수반 벨만 완결성
• 크리틱 클래스의 이중 완결성

그 의의는 근사 부담을 (검증하기 어렵고 제한적인) 복잡한 폐쇄 조건(closure conditions)에서 분포 변화 자체의 직접적인 표현 능력으로 전환했다는 데 있다. KL 기하학을 활용함으로써, FORE는 FQE나 미니맥스 방법론이 요구하는 구조적 조건보다 더 약하면서도 안정성과 수렴성을 보장한다. 저자들은 이를 가치 함수나 크리틱 클래스가 필요한 완결성 속성을 갖추지 못한 환경에서도 효과적인 대안으로 제시한다.