기술 요약: $Q^\star$-근사와 부분적 커버리지 하에서의 오프라인 강화학습의 복잡성에 관하여

문제 정의

본 연구는 **$Q^\star$-실현 가능성(realizability)**과 부분적 커버리지(partial coverage) 조건 하에서의 **오프라인 강화학습(Offline Reinforcement Learning, RL)**의 이론적 한계를 조사한다. 이 패러다임에서 에이전트는 추가적인 환경 상호작용 없이 고정된, 사전 수집된 데이터셋으로부터 정책을 학습한다. 데이터셋은 전체 상태-행동 공간을 모두 커버하지 않을 수 있는 행동 정책(behavior policy)에 의해 생성된다(부분적 커버리지).

본 논문이 다루는 핵심적인 미해결 질문은, $Q^\star$-실현 가능성($Q^\star$가 알려진 함수 클래스 내에 존재함)이 벨만 완결성(Bellman completeness)(벨만 연산자가 해당 함수 클래스를 상위 집합으로 매핑함) 및 부분적 커버리지와 결합되었을 때, **샘플 효율적(sample-efficient)**인 학습을 보장하기에 충분한가 하는 점이다. 이러한 조건들은 참인 $Q^\star$를 포함하는 신뢰 집합(confidence set)을 구축할 수 있게 해주지만, 본 논문은 이것이 강건한 정책 선택을 보장하기에 충분한지에 대해 의문을 제기한다.

방법론

1. 정보 이론적 하한 (Information-Theoretic Lower Bound)

저자들은 먼저 앞서 언급한 조건들이 샘플 효율적 학습을 위한 충분조건이 아님을 입증한다. 이들은 다음과 같은 마르코프 결정 과정(MDP) 군(family)을 구성한다:

• $Q^\star$-실현 가능성과 벨만 완결성이 성립한다.
• 최적 정책의 커버리지는 상수($\Theta(1)$)이다.
• 참인 가치 함수(value function)가 함수 클래스 내에 잘 국소화(well-localized)되어 있음에도 불구하고, 학습자는 파멸적인 오류를 초래하는 정책과 안전한 정책을 구분할 수 없다.
• 필요한 샘클 복잡도는 $\Omega(\frac{1}{\epsilon} \min\{\sqrt{|S|}, \frac{1}{\Delta^2}\})$로 스케일링된다 (여기서 $\Delta$는 가치 격차(value gap)이다). 이는 가치 격차가 작더라도 샘플 복잡도가 매우 높을 수 있음을 나타내며, 어려움의 원인이 단순히 $Q^\star$를 추정하는 것뿐만 아니라 모호성 집합(ambiguity set) 내에서 강건한 결정을 내리는 데 있음을 시사한다.

2. 결정-추정 분해 프레임워크 (Decision-Estimation Decomposition Framework)

식별된 간극을 해결하기 위해, 저자들은 온라인 RL의 결정-추정 계수(DEC)에서 영감을 받은 일반적인 결정-추정 프레임워크를 도입한다. 이들은 오프라인 RL의 부서브옵티멀리티(suboptimality)를 두 가지 모듈형 구성 요소로 분해한다:

1. 결정 복잡도 (Decision Complexity): 가능한 모델들의 신뢰 집합으로부터 강건한 정책을 선택하는 난이도.
2. 추정 오차 (Estimation Error): 오프라인 데이터로부터 가치 함수 또는 모델 파라미터를 추정할 때 발생하는 오차.

저자들은 다음을 만족하는 혼합 정책(mixture policy) $\hat{\pi}$를 출력하는 알고리즘(E2D.OR)을 정의한다:
$$Ordec\text{-}OD_\gamma(F_{conf}) := \min_{\rho \in \Delta(\Pi)} \max_{M \in \mathcal{M}_{conf}} \mathbb{E}_{\pi \sim \rho} \left[ J_M(\pi_M) - J_M(\pi) - \gamma \max_{f \in F_{conf}} D_\pi(f \| M) \right]$$
여기서:

• $F_{conf}$는 가능한 $Q^\star$ 함수들의 신뢰 집합이다.
• $\mathcal{M}_{conf}$는 유도된 가능한 모델들의 집합이다.
• $\rho$는 정책들에 대한 분포이다.
• $D_\pi(f \| M)$은 함수와 모델 사이의 불일치 측정치(예: 벨만 오차)이며, 이는 (온라인 DEC와 달리) 학습자의 정책이 아닌 후보 모델의 최적 정책 $\pi_M$ 하에서 평가된다.

이 프레임워크는 다음을 만족하는 혼합 정책 $\hat{\pi}$를 출력한다:
$$J(\pi^\star) - \mathbb{E}[J(\hat{\pi})] \leq Ordec + \text{Estimation Error}$$

주요 기여

1. 충분성에 대한 부정적 결과 (Negative Result on Sufficiency)

본 논문은 $Q^\star$-실현 가능성, 부분적 커버리지, 그리고 벨만 완결성이 샘플 효율적인 오프라인 RL을 위한 충분조건이 아님을 증명하는 정보 이론적 하한을 제공한다. 이는 부분적 커버리지 설정에서 핵심적인 과제가 단순히 $Q^\star$를 추정하는 문제가 아니라, 신뢰 집합 내에서 안전한 정책과 안전하지 않은 정책을 구분하는 "결정(decision)" 문제임을 강조한다.

2. 통합 프레임워크 및 개선된 경계 (Unified Framework and Improved Bounds)

제안된 $Ordec$ 프레임워크는 기존의 결과들을 통합하고 개선한다:

• 가치 격차 설정 (Value-Gap Setting): Chen과 Jiang (2022)의 결과를 재현하되, 격차 값을 알 필요가 없거나 추가적인 온라인 상호작용을 수행할 필요가 없도록 개선했다. 이 경계는 실제 격차에 따라 자동으로 적응한다.
• 정규화 설정 (Regularized Setting): 부분적 커버리지 하에서의 Soft Q-learning에 대한 샘플 복잡도 경계를 $\epsilon^{-4}$ (Uehara et al., 2023)에서 $\epsilon^{-2}$로 개선하였다. 이는 정규화된 MDP를 위한 새로운 2차 성능 차이 렘마(second-order performance difference lemma)를 통해 달성되었다.
• 곡선 결정 경계 (Curved Decision Boundary): 연속적 행동 공간에서의 결정 경계 곡률에 기반한 새로운 학습 가능한 설정을 도입하여, 엄격한 가치 격차 가정에 대한 실질적인 우려를 해결한다.

3. 추정 오차를 위한 새로운 학습 가능 영역 (New Learnable Regimes for Estimation Error)

본 논문은 구조적 가정이 추정 오차 항을 제어하는 역할을 규명한다:

• 벨만 완결성 (Bellman Completeness): 일반적인 함수 근사(general function approximation) 하에서 **보수적 Q-러닝(CQL)**에 대한 최초의 샘플 복잡도 분석을 제공한다 (기존에는 테이블 형식에 국한됨).
• 낮은 벨만 랭크 (Low Bellman Rank): (전형적인 온라인 RL 설정인) 낮은 벨만 랭크를 가진 MDP의 오프라인 학습 가능성을 조사한다. 저자들은 표준적인 데이터 가정 하에서 낮은 벨만 Rank가 오프라인 학습에는 불충분함을 보여준다. 이 영역에서의 학습 가능성을 위해 두 가지 필수 조건을 도입한다:
  1. 이중 정책 샘플링 (Double Policy Sampling): 데이터가 하나의 정책을 샘플링한 후 두 개의 독립적인 전이를 샘플링하여 생성되어야 한다.
  2. 정책 특징 커버리지 (Policy Feature Coverage): 정책의 특징 공간(feature space)에 대한 특정 커버리지 조건이 필요하다.
     이 중 하나라도 완화되면 다항식 샘플 복잡도 보장이 깨진다.

결과 요약

• 하한 (Lower Bound): $Q^\star$-실현 가능성 + 벨만 완결성 + 부분적 커버리지 $\nRightarrow$ 샘플 효율적 학습임을 입증하였다.
• 상한 (Upper Bound): $Ordec$(결정 복잡도)와 추정 오차로 분해된 일반적인 서브옵티멀리티 경계를 확립하였다.
• 구체적 경계:
  • 비정규화 (가치 격차): $\tilde{O}(\frac{H^2}{\gamma \Delta^2} + \gamma \frac{C_{\pi^\star}}{n})$. 알려지지 않은 격차에 적응한다.
  • 정규화: $\tilde{O}(\sqrt{\frac{C_{\pi^\star}}{n}})$를 통해 $\epsilon^{-2}$ 샘플 복잡도를 산출한다.
  • CQL: 부분적 커버리지 하의 일반 함수 근사에 대한 최초의 일반적 함수 근사 보장을 제공한다.
  • 낮은 벨만 랭크: 표준 가정 하에서의 불가능성을 증명하였으며, 이중 정책 샘플링과 정책 특징 커버리지를 학습 가능성을 위한 필수 조건으로 식별하였다.

의의 및 주장

본 논문은 $Q^\star$-근사 및 부분적 커버리지 하에서의 오프라인 RL의 잠재력과 한계에 대해 더 포괄적인 이해를 제공한다고 주장한다. 그 의의는 다음과 같다:

1. 난이도의 근원 명확화: 이론적 초점을 순수 추정 오차에서 부분적 커버리지 설정에 내재된 결정 복잡도로 전환하여, 완벽한 추정이 있더라도 추가적인 구조적 가정이 없다면 강건한 의사결정이 불가능할 수 있음을 보여준다.
2. 통합: 결정 복잡도와 추정 복잡도를 분리함으로써 기존 결과들(Chen and Jiang, 2022; Uehara et al., 2023)을 재현, 개선 및 확장하는 모듈형 프레임워크를 제공한다.
3. 실무적 관련성: 일반적인 함수 근사 하에서의 CQL을 분석하고 낮은 벨만 랭크 문제에 대한 구체적인 구조적 요구 사항을 식별함으로써, 본 연구는 실질적인 알고리즘과 이전에 다루기 어렵거나 이해가 부족했던 설정 사이의 간극을 메운다.
4. 새로운 설정의 참신함: 낮은 벨만 랭크 MDP의 오프라인 학습 가능성 조건을 최초로 확립하였으며, 부분적 커버리지 하에서 정규화된 Soft Q-learning에 대한 최초의 $\epsilon^{-2}$ 경계를 제공한다.

저자들은 이 프레임워크가 이론적으로는 견고하지만, 미니맥스(minimax) 알고리즘을 정확히 푸는 것은 계산적으로 어려울 수 있으며, 액터-크리틱(actor-critic) 방법을 통해 근사될 수 있다고 언급한다. 본 연구의 주된 목적은 새로운 학습 가능 영역을 식별하고, 이를 위해 필요한 구조적 조건을 규명하는 것이다.