기술 요약: 샘플 복잡도 분석을 포함한 모델 프리 강건 평균 보상 강화 학습

1. 문제 정의

본 논문은 평균 보상 기준(average-reward criterion) 하에서의 강건한 강화 학습(Robust Reinforcement Learning, RL) 문제를 다룹니다. RL은 통제된 환경에서 큰 성공을 거두었으나, 실제 배포 시에는 모델 불일치, 환경적 섭동 또는 적대적 공격으로 인한 "Sim-to-Real" 간극 문제를 겪게 됩니다. 강건한 RL은 불확실성 집합 내의 최악의 성능을 최적화함으로써 이를 완화합니다.

구체적인 초점은 **분포 강건 평균 보상 MDP(Distributionally Robust Average-Reward MDPs, RAMDPs)**에 있습니다. 할인 보상(discounted reward) 설정과 달리, 평균 보상 기준은 큐잉 제어(queuing control)나 포트폴리오 최적화와 같은 응용 분야에서 장기적인 정상 상태(steady-state) 성능을 위해 필수적입니다. 그러나 강건한 평균 보상 RL은 다음과 같은 이유로 할인된 경우보다 훨씬 더 까다롭습니다:

1. 비수축 연산자(Non-contractive operators): 강건한 벨만 연산자는 일반적으로 수축(contractive)이 아닌 비팽창(non-expansive) 성질을 가지므로, 표준적인 반복 수렴 보장을 무효화합니다.
2. 이중 미지수(Dual unknowns): 강건한 벨만 방정식은 가치 함수(또는 편향, $Q$)와 최적 평균 보상 $g^*_P$라는 두 개의 미지수 변수를 포함합니다.
3. 비선형성(Non-linearity): 명목상(nominal) 샘플로부터 최악의 기대값(서포트 함수)을 추정하는 과정은, 특히 모델 프리(model-free) 설정에서 편향(bias)을 유발합니다.

기존 문헌은 주로 점근적 보장에 의존하거나, 문제 파라미터(예: 편향 스팬 $H$)에 대한 사전 지식을 요구하는 모델 기반 접근 방식, 또는 하위 최적의 샘플 복잡도를 갖거나 특정 수축 계수를 가진 기약성(irreducibility)과 같은 강력한 구조적 가정을 요구하는 축소 기반(reduction-based) 방식에 의존합니다.

2. 방법론: 강건한 할픈 반복(Robust Halpern Iteration, RHI)

저자들은 문제의 MDP 파라미터에 대한 사전 지식 없이 강건한 벨만 방정식을 해결하도록 설계된 모델 프리 알고리즘인 **강건한 할픈 반복(RHI)**을 제안합니다.

2.1. 알고리즘 핵심

RHI 알고리즘은 최적화 문헌의 **할픈 반복(Halpern Iteration)**에서 영감을 얻었으며, 강건한 평균 보상 RL의 특정 과제들을 처리하도록 조정되었습니다:

• 몫 공간 공식화(Quotient Space Formulation): "이중 변수의 저주"(미지수인 $g^*_P$)를 해결하기 위해, 저자들은 벡터가 상수 이동에 의해서만 차이가 나는 경우 동등하게 취급하는 몫 공간 $\mathbb{R}^{SA} / \sim$에 문제를 임베딩합니다. 이를 통해 $g^*_P$를 명시적으로 알지 못해도 근사 방정식 $T_P(Q) - Q = ce$를 풀 수 있습니다.
• 할픈 업데이트(Halpern Update): 표준 가치 반복 대신, RHI는 초기값과 연산자 업데이트의 볼록 조합을 사용합니다:
  $$[Q_{k+1}] = [(1 - \beta_{k+1})Q_0 + \beta_{k+1} T_P(Q_k)]$$
  여기서 $\beta_k = k/(k+2)$입니다. 이 접근 방식은 수축 계수에 의존하지 않고 비팽창 연산자에 대한 수렴 보장을 제공합니다.

2.2. 블랙박스 샘플링 오라클(R-SAMPLE)

강건한 연산자 $T_P$는 비선형이며 최악의 기대값을 포함하므로, 저자들은 명목 커널(nominal kernel)로부터의 샘플만을 사용하여 연속적인 반복 사이의 강건한 서포트 함수 차이를 추정하는 블랙박스 샘플링 오라클인 R-SAMPLE을 도입합니다.

• 이 오라클은 기대값이 강건한 벨만 연산자 값의 차이를 근사하는 무작위 증분 $D_k$를 반환합니다.
• 알고리즘의 샘플 복잡도는 이 오라클의 특성(립시츠 상수, 편향, 샘플 비용)을 기반으로 도출됩니다.

2.3. K-차수 다층 몬테카를로(K-order Multi-Level Monte-Carlo, MLMC) 추정기

낮은 편향을 가진 R-SAMPLE 오라클을 구체적으로 구현하기 위해, 저자들은 K-차수 MLMC 추정기를 제안합니다.

• 동기: 강건한 서포트 함수에 대한 표준 플러그인 추정기와 일반적인 MLMC 추정기는 $O(1/N)$의 편향을 겪으며, 이는 $\tilde{O}(\epsilon^{-3})$의 샘플 복-잡도로 이어집니다.
• 메커니즘: K-차수 추정기는 서로 다른 샘플 크기($N_\ell = 2^\ell N_0$)를 가진 단일 레벨 추정기들의 선형 조합을 구성합니다. 가중치 $w^{(K)}_\ell$를 신중하게 선택함으로써, 이 추정기는 편향 전개의 처음 $K$개 항을 상쇄합니다.
• 결과: 이는 편향을 $\tilde{O}(N_0^{-(K+1)})$로 줄여주어, 훨씬 더 타이트한 전체 샘플 복잡도를 가능하게 합니다.

3. 주요 기여

1. 보편적인 모델 프리 알고리즘: RHI는 강건한 최적 스팬 $H$나 혼합 시간(mixing time)에 대한 사전 지식을 요구하지 않는 최초의 강건 평균 보상 RL용 모델 프리 알고리즘으로, 축소 기반 접근 방식의 한계를 극복합니다.
2. K-차수 MLMC 추정기: 저자들은 이전 MLMC 방식에 비해 편향을 크게 줄이는 새로운 추정기를 설계했습니다. 이는 비선형 강건 서포트 함수가 존재하는 상황에서 거의 최적의 샘플 복잡도를 달ach하기 위해 매우 중요합니다.
3. 유한 샘플 복잡도 분석: 본 논문은 생성 모델(generative model) 설정 하에서 RHI에 대한 엄밀한 유한 샘플 분석을 제공합니다.
   • KL 및 $\chi^2$ 다이버전스 불확실성 집합의 경우, $\epsilon$-최적 정책을 찾기 위한 샘플 복잡도는 $\tilde{O}\left(SAH^2 \epsilon^{-(2+o(1))}\right)$입니다.
   • $\ell_p$-노름 및 오염(contamination) 집합의 경우, 복잡도는 $\tilde{O}\left(SAH^2 \epsilon^{-2}\right)$입니다.
   • 여기서 $S$와 $A$는 상태와 행동의 수이며, $H$는 강건 최적 스팬입니다.
4. 파라미터 프리 변형(PF-RHI): 저자들은 알려지지 않은 파라미터 $H$에 기반한 호라이즌을 미리 지정할 필요 없이 더블링 트릭(doubling trick)을 사용하여 반복 횟수를 동적으로 결정하는 RHI의 변형을 제안하며, 동일한 샘플 복잡도를 유지합니다.

4. 결과 및 이론적 보장

• 수렴성: 정확한 RHI 알고리즘은 반복이 증가함에 따라 벨만 잔차(Bellman residual)의 스팬과 부최적 갭(sub-optimality gap)이 소멸하며 수렴함이 증명되었습니다.
• 샘플 복잡도: KL 및 $\chi^2$ 집합에 대한 샘ple 복잡도는 모델 기반 접근 방식(예: Roch et al., 2025; Chen et al., 2025)의 가장 잘 알려진 경계와 점근적으로 일치합니다. 지수의 $o(1)$ 항은 $\epsilon \to 0$일 때 사라지는 아다항(sub-polynomial) 패널티를 나타내며, 이는 표준 MLMC를 사용하는 방법의 $\epsilon^{-3}$ 복잡도와 구별되는 점입니다.
• 실험적 검증: Garnet 문제와 다양한 불확실성 집합(오염, $\ell_\infty$, $\ell_2$)에 대한 수치 실험은 RHI가 최적의 강건 평균 보상으로 수렴하며, K-차수 MLMC 추정기가 표준 방식에 비해 편향을 효과적으로 줄임을 보여줍니다.

5. 의의 및 주장

본 논문은 RHI를 강건 평균 보상 RL을 위한 최첨단(state-of-the-art) 모델 프리 알고리즘으로 확립한다고 주장합니다. 그 의의는 다음과 같습니다:

• 간극 해소: 강건 평균 보상 RL에서 점근적 보장과 유한 샘플 분석 사이의 간극을 메웁니다.
• 실용성: 모델 프리 방식이며 $H$에 대한 사전 지식을 요구하지 않으므로, 이러한 파라미터를 알 수 없는 실제 환경 배포에 더 실용적입니다.
• 최적성: 샘플 복잡도가 모델 기반 방법론에서 알려진 가장 타이트한 경계와 점근적으로 일치함을 보여줌으로써, 모델 구축의 오버헤드 없이도 모델 프리 접근 방식이 유사한 효율성을 달 achieves 할 수 있음을 입증합니다.
• 편향 감소: K-차수 MLMC 설계는 이전의 강건 RL 추정기들에 비해 근본적인 개선을 제공하며, 비선형 함수 추정에서 발생하는 높은 샘플 복잡도 문제를 해결합니다.

저자들은 분석이 통계적 복잡도를 격리하기 위해 생성 모델(시뮬레이터 접근 권한)을 가정하고 있음을 언급합니다. 온라인(탐색-활용) 또는 오프라인(데이터셋 기반) 설정으로의 확장은 향후 과제로 식별되었습니다. 또한, KL/$\chi^2$ 집합의 샘플 복잡도에서 나타나는 아다항(sub-polynomial) 갭은 비선형 범함수(functional) 추정의 내재적인 편향-분산 트레이드오프 때문이며, 이는 모델 프리 설정에서 완전히 제거하기 어려운 미해결 과제로 남아 있습니다.