경로 수준 감독이 오프라인 강화학습의 샘플 효율성을 보장하는 상황

오프라인 RL에서 프로세스 수준의 보상이 제공되지 않는 데이터가 흔하다. 이 논문은 경로 수준의 결과를 이용해도 정책 최적화가 가능하다는 이론적·알고리즘적 근거를 제시하고, 샘플 복원력과 하한을 분석한다. OPAC 알고리즘은 latent per-step rewards를 학습하고 offline 분포 이동에 대한 페니즘을 적용하여 성능 보장을 제공한다. 또한 선호 피드백과 일반화된 목표에 대한 확장도 제시한다.

출발점은 오프라인 RL에서 일반적으로 가정되는 프로세스 수준의 reward를 관측하지 않는 환경이다. 경로 수준 감독은 per-step reward 정보를 직접 제공하지 않으므로 latent per-step rewards를 추정하는 것이 핵심 문제이다. OPAC는 trajectory-level outcome 레이블로 latent rewards를 회귀로 추정하고, 벨만 백업에 대한 plug-in 오차를 사용해 critic를 학습하며, offline 데이터의 분포 차이를 보정하기 위해 pessimism 전략을 채택한다. 선호 피드백으로의 확장도 가능하며, 비선형 경로 목표를 다룰 때는 κµ(σ)와 χµ(σ)라는 두 정보손실 계수를 도입해 학습 가능성의 조건을 제시한다. 이 두 계수는 데이터에서의 정보손실(경로 출력으로의 압축)과 Bellman 타깃이 보존하는 reward 차이의 손실을 각각 표현한다. 계수들이 작을 때 Generalized OPAC의 샘플 복원력은 다항식적으로 증가하며, 반대로 모든-성공과 같은 특정 합성 목표는 지수적 샘플 복잡도를 가지게 될 수 있다.

• 입력: finite-horizon MDP M = (S,A,P,r⋆,H,s1)에서 경로 τ의 보상은 latent r⋆와 달리 Y(τ)로 관찰되며, E[Y(τ)|τ] = R⋆(τ) = ∑h r⋆h(sh,ah). D = {(τ(i),Yi)}ni=1은 오프라인 데이터, dπh(s,a)은 정책의 occupancy, dµh(s,a)는 행동정책 µ의 occupancy. - OPAC 알고리즘: K회 반복에서 (fk,rk) ∈ F×R를 최소화한다. LD(π,f) = ED[fh(sh,π)−fh(sh,ah)], LBE(π,r,f) = ∑h ED[(fh(sh,ah)−y r,f,π h)²], LRM(r)=ED[(Y−∑h rh(sh,ah))²]. y r,f,πh := rh(sh,ah)+fh+1(sh+1,π). 학습은 아래 세 항의 합을 최소화하는 (f,r) 쌍으로 이루어진 최적화 문제를 반복한다: LD(πk,f)+β LBE D (πk,r,f)+β LRM D (r). 다음으로 정책 개선은 πk+1,h(·|s) ∝ πk,h(·|s) exp(fk,h(s,·)/η) 로 이루어진다. 최종 deploy은 π̄ := Unif(π1,...,πK). - 선호 피드백 확장: LPref DPref(r) = 1/n ∑i [−y(i) log Cr(τi+,τi−) − (1−y(i)) log(1−Cr(τi+,τi−))], Cr(τ+,τ−) = exp(γR(τ+;r)) / (exp(γR(τ+;r)) + exp(γR(τ−;r))). β와 η는 정책-평가의 no-regret bound과 Bernstein/Hoeffding 기반 집중성 보장을 유지하도록 설정된다. - 일반화된 목표: σ : R^H → [0,Vmax]가 주어졌을 때, R(τ;r) = σ(r1(s1,a1),...,rH(sH,aH))이고 Jr(π) = Eτ∼π[R(τ;r⋆)]. κµ(σ)와 χµ(σ)로 정보손실과 Bellman 타깃의 보존정도를 정의하고, Assumption 4 하에서 GOPAC의 샘플복잡도는 Oe[ V^2 max L r κµ(σ) H^2 Csa(π⋆)/n + V^2 max L r χµ(σ) H^4 / n + ...] 로 보장된다. - 증명 기법: population_loss를 정의하고, concentration(εPerf, εBE, εRM, εapx, εPref)을 통해 샘플로 대체한 뒤, AM–GM과 Young의 불평등으로 β를 최적화한다. - 한계: σ의 일반화가 Bellman-학습 가능성(Bellman-learnable) 조건을 만족하지 않으면 exponential lower bound가 성립한다.

• Scalar-outcome 설정(OPAC): Theorem 1은 오버헤드 없이 J(π⋆)−J(π̄) = Oe(H2 Csa(π⋆)/n)으로 수렴하며, n = Oe(H4 Csa(π⋆)/ε2) trajectories가 ε-optimality에 충분함을 보인다. Theorem 2는 이 상한이 최적임을 Ω(H4/ε2) 하한으로 보인다. - Preferences 확장(Theorem 3): 선호 피드백에 대해서도 leading term H2 Csa(π⋆)/n 의 의존성을 유지하며, alpha 및 c 상수는 Bradley–Terry–Lucre 모델의 파라미터에 의해 결정된다. - 일반화된 목표(Theorem 6): 구조적 조건 하에서 Generalized OPAC가 polynomial 샘플 복잡도를 달성하며 κµ(σ)와 χµ(σ)가 정보손실의 두 축을 각각 표현한다. - 전체적으로, trajectory-level supervision의 샘플 효율성은 데이터의 분포 이동에 대응하는 pessimism 및 latent per-step reward 복원에 좌우되며, 모든-성공(all-success) 같은 특정 비선형 목표는 지수적 하한에 직면할 수 있다.

• 전체 아키텍처 구조: OPAC는 latent per-step reward 모델 f와 값함수/정책을 학습하는 이중 구조를 사용한다. - 핵심 메커니즘: LD(π,f) + β LBE(π,r,f) + β LRM(r)을 최소화하고, 정책 개선은 π <- π ∘ exp(f/η) 방식으로 수행한다. y_{r,f,π}h은 rh + fh+1의 벡터합으로 Bellman 근사치를 구성한다. - 차별점: process reward supervision 대신 trajectory-level outcome에 의존하는 학습이며, pessimism을 도입해 오프라인 데이터의 분포 이질성을 보정한다. - 구현/학습 세부사항: 드리프트를 제거하기 위한 double-sampling 보정, critic의 realizability 및 completeness 가정, K 반복의 mixture policy, 그리고 선호 피드백 및 일반화된 목표로의 확장을 포함한다.