Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs

기술적 요약: 제약된 평균 보상 MDP에 대한 근사 최적 샘플 복잡도 경계

문제 정의
본 논문은 생성 모델(generative model) 하에서 $\epsilon$-최적 정책을 학습하기 위한 제약된 평균 보상 마르코프 결정 과정(Constrained Average-Reward MDPs, CAMDPs)의 샘플 복잡도를 조사한다. CAMDP는 튜플 $\mathcal{M} = \langle S, A, P, r, c, b, s \rangle$로 정의되며, 여기서 에이전트는 평균 제약 조건 $\rho^\pi_c(s) \geq b$를 만족하면서 정상 상태 평균 보상 $\rho^\pi_r(s)$를 최대화하는 것을 목표로 한다. 벤치마크 정책 $\pi^*$는 정적 결정론적 정책들의 외부 혼합(external mixture)이다. 저자들은 두 가지 가용성 체제(feasibility regimes)를 고려한다:

1. 완화된 가용성(Relaxed Feasibility): 출력 정책이 제약을 최대 $\epsilon$만큼 위반할 수 있음 (즉, $\rho^{\hat{\pi}}_c(s) \geq b - \epsilon$).
2. 엄격한 가용성(Strict Feasibility): 출력 정책이 제약을 정확히 만족해야 함 (즉, $\rho^{\hat{\pi}}_c(s) \geq b$).
   분석은 구조적 파라미터인 $S$와 $A$ (상태 및 행동 수), $H$ (보상 및 제약 함수의 편향 스팬(bias spans)에 대한 균등 상한), $B$ (과도 시간(transient time)에 대한 균등 상한), 그리고 $\zeta$ (가용 영역의 크기를 특징짓는 슬레이터 마진(Slater margin)의 하한)에 의존한다. 본 연구는 정책별 할인 분산 조건(Assumption 1)을 가정한다.

방법론
저자들은 일련의 섭동된 경험적 할인 MDP(perturbed empirical discounted MDPs)를 해결함으로써 작동하는 모델 기반 프라이멀-듀얼 알고리즘(Algorithm 1)을 제안한다. 주요 방법론적 구성 요소는 다음과 같다:

• 프라이멀-듀얼 프레임워크: 알고리즘은 라그랑주 승수 $\lambda_t$를 유지하며, 현재 정책의 제약 위반에 따라 이를 업데이트한다. 프라이멀 단계는 경험적 할인 설정에서 라그랑주 보상 $r_p + \lambda_t c$를 최대화하는 결정론적 정책 $\hat{\pi}_t$를 구한다.
• 섭동 및 반올림(Perturbation and Rounding): 최적 행동의 유일성을 보장하고 집중 분석(concentration analysis)을 용이하게 하기 위해, 보상 신호는 확률 변수 $Z$에 의해 섭동된다. 라그랑주 승수는 격자 $\Lambda$ 위에서 이산화된다.
• 교차 신호 집중(Cross-Signal Concentration): 핵심적인 기술적 기여는 유한한 경험적 라그랑주 오라클 정책 군에 대한 새로운 집중 정리(Theorem 2)이다. 전체 정책 클래스에 대한 표준적인 균등 집중과 달리, 이 결과는 알고리즘에 의해 생성된 특정 정책들에 대한 추정 오차를 제어한다. 이는 행(row)을 분리하기 위해 "상태-행동 흡수 구성(state-action absorbing construction)"을 활용하며, 인스턴스 의존적 분산 항을 유지하기 위해 조건부 번스타인 계층(conditional Bernstein hierarchy)을 사용한다.
• 평균 보상으로의 전이: 섭동된 할인 문제에서 도출된 보증은 편향 스팬 $H$를 통해 할인 값을 평균 보상과 연결하는 브리지 렘마(bridge lemmas)를 사용하여 원래의 평균 보상 문제로 전이된다.

주요 기여 및 결과
본 논문은 평균 보상 설정의 CAMDP에 대한 최초의 근사 최적 샘플 복잡도 경계를 확립하며, 완화된 가용성과 엄격한 가용성을 구분한다:

1. 완화된 가용성 상한: 알고리즘은 완화된 제약 만족을 가진 $\epsilon$-최적 정책을 $\tilde{O}\left(\frac{SA(B + H)}{\epsilon^2}\right)$ 샘플을 사용하여 달성한다. 주목할 점은 이 비율이 슬레이터 마진 $\zeta$와 무관하다는 것이다.
2. 엄격한 가용성 상한: 엄격한 제약 만족을 위한 샘플 복잡도는 $\tilde{O}\left(\frac{SA(B + H)}{\epsilon^2 \zeta^2}\right)$로 증가한다. $\zeta^{-2}$에 대한 의존성은 위반 없이 정확한 가용성을 보장하는 것의 어려움을 반영한다.
3. 하한(Lower Bounds):
   • 약하게 통신하는(weakly communicating) CAMDP의 경우, 저자들은 지름 $D$ (여기서 $H = \Theta(D)$)를 가진 어려운 패밀리를 구성하여 엄격한 가용성에 대해 $\tilde{\Omega}\left(\frac{SAH}{\epsilon^2 \zeta^2}\right)$의 적응적 미니맥스 하한을 증명한다.
   • 일반적인 CAMDP의 경우, 별도의 과도(transient) 패밀리가 균형 잡힌 샘플링(balanced sampling) 하에서 $\tilde{\Omega}\left(\frac{SAB}{\epsilon^2 \zeta^2}\right)$의 하한을 나타낸다.
   • 이러한 서브패밀리들을 결합하면, 균형 잡힌 알고리즘에 대한 최악의 경우 하한은 $\tilde{\Omega}\left(\frac{SA(B + H)}{\epsilon^2 \zeta^2}\right)$이며, 이는 로그 인자를 제외하고 엄격한 가용성 상한과 일치한다.

의의 및 주장
저자들은 본 연구가 평균 보상 설정의 CAMDP에 대한 최초의 샘플 복잡도 특성화를 제공한다고 주장한다. 결과는 장기 제약 조건 하에서의 학습의 통계적 난이도가 편향 스팬($H$), 과도 동작($B$), 그리고 가용 영역 마진($\zeta$)에 의해 공동으로 결정됨을 보여준다.

본 논문은 완화된 가용성과 엄격한 가용성이 할인된 CMDP에서는 연구되었으나(예: Vaswani et al., 2022), 벨만 수축(Bellman contraction)과 같은 성질이 성립하지 않기 때문에 평균 보상 설정은 독특한 과제를 제시한다고 명시한다. 일치하는 상한과 하한을 확립함으로써, 본 연구는 엄격한 가용성을 위해 필요한 추가적인 $\zeta^{-2}$ 의존성이 피할 수 없는 것임을 입증하고, 완화된 체제와 엄격한 체제 사이의 증명 가능한 분리를 확립한다. 제안된 알고리즘과 분석 프레임워크는 생성 모델 하의 제약된 평균 보상 강화 학습에 대해 근사 미니맥스 최적성(near-minimax optimality)을 달성하는 첫 사례로 제시된다.