Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

기술 요약: 강건한 평균 보상 마르코프 결정 과정 (Robust Average-Reward Markov Decision Processes)

문제 정식화
본 연구는 생성 모델 설정(generative model setting) 하에서 $\epsilon$-최적 정책을 학습하기 위한 분포 강건 평균 보상 마르코프 결정 과정(Distributionally Robust Average-Reward MDPs, AMDPs)의 통계적 복잡도를 조사한다. 에이전트는 명목 전이 커널 $P^0$와 보상 함수 $r$로 정의된 명목 환경 내에서 작동한다. 그러나 실제 환경의 역학은 불확실하며, $P^0$를 중심으로 하는 규정된 불확실성 집합 $\mathcal{P}$ 내에 존재할 수 있다. 구체적으로, 본 논문은 $(s, a)$-직사각형 총 변동(total-variation, TV) 불확실성 집합과 그 반지름이 최대 $\sigma$인 경우를 고려한다.

목표는 다음과 같이 정의된 강건 평균 보상(robust average reward)을 최대화하는 것이다:
$$\rho^{\pi, \sigma} := \inf_{P \in \mathcal{P}} \lim_{T \to \infty} \mathbb{E}^\pi_P \left[ \frac{1}{T} \sum_{t=0}^{T-1} r(s_t, a_t) \right]$$
학습 목표는 $N$개의 샘플을 각 상태-행동 쌍당 사용하여 $\rho^{\star, \sigma} - \rho^{\hat{\pi}, \sigma} \leq \epsilon$을 만족하는 정책 $\hat{\pi}$를 계산하는 것이다. 여기서 $\rho^{\star, \sigma}$는 최적의 강건 평균 보상이다.

주요 파라미터 및 구조적 가정
분석은 두 가지 핵심적인 구조적 파라미터에 의존한다:

1. 명목 최적 바이어스 스팬 ($H_0$): 명목 벨만 최적 방정식을 만족하는 바이어스 함수의 스팬(span).
2. 강건 최적 바이어스 스팬 ($H_\sigma$): 강건 벨만 최적 방정식을 만족하는 바이어스 함수의 스팬.

본 논문은 $H_0$와 $H_\sigma$가 일반적으로 독립적이며, 서로를 제어하지 못한다는 점을 확립한다. 중요한 섭동 척도(perturbation scale)로 $\sigma H_0$가 식별되었으며, 이는 학습 문제를 두 가지 뚜렷한 체제로 구분한다:

• 고내성 체제 (High-Tolerance Regime, $\epsilon \gtrsim \sigma H_0$): 불확실성에 의한 섭동이 목표 정확도에 비해 작은 경우.
• 저내성 체제 (Low-Tolerance Regime, $\epsilon \lesssim \sigma H_0$): 섭동이 유의미하며, 명목 최적화만으로는 강건한 최적성을 보장하기에 불충분한 경우.

방법론: 축소 기반 플러그인 절차 (Reduction-Based Plug-in Procedures)
핵-기여 방법론은 어려운 강건 평균 보상 문제를 더 다루기 쉬운 강건 할인 MDP(robust discounted MDP, DMDP) 문제로 변환하는 축소 프레임워크이다. 저자들은 이 축소를 기반으로 한 두 가지 알고리즘을 제안한다:

1. 스팬 정보 기반 절차 (Algorithm 1): $H_0$와 $H_\sigma$를 알고 있다고 가정한다. 이는 명목 축소(경험적 커널을 사용하여 표준 DMDP를 해결)와 강건 축소(불확실성 집합 상에서 DMDP를 해결) 사이를 적응적으로 선택한다. 선택은 $H_0$와 $H_\sigma$의 순서 및 내성 체제에 따라 결정된다. 할인 인자 $\gamma$는 관련 스팬 파라미터(예: $\gamma = 1 - \epsilon/(3H_\sigma)$)를 기준으로 조정된다.
2. 스팬 무관 절차 (Algorithm 2): $H_0$ 또는 $H_\sigma$에 대한 지식 없이 작동한다. 이는 할인 인자의 이중 격자(dyadic grid)를 따라 명목 및 강건 축소로부터 얻은 후보 정책 세트를 구축한다. 그 후, 별도의 데이터 배치로부터 계산된 "앵커 인증서(anchor certificate)"를 사용하여 강건 평균 보상에 대한 하한 신뢰 구간(lower-confidence bound, LCB)을 통해 최적의 정책을 선택한다. 이를 통해 알고리즘은 데이터에 기반하여 올바른 축소 방식과 할인 인자를 적응적으로 선택할 수 있다.

저자들은 타이트한 경계(tight bounds)를 달려하기 위해 세 가지 핵심적인 기술적 정교화를 활용한다:

• 분산을 줄이기 위해 강건 할인 문제와 명목 참조 솔루션(앵커)을 비교함.
• 유효 호라이즌(effective horizon) 대신 스팬($H_\sigma$)을 통해 할인 가치 함수를 제어함.
• 스팬에 의해 제어되는 국소 집중 경계(localized concentration bounds)를 사용함.

주요 결과: 미니맥스 샘플 복잡도
본 논문은 로그 인자를 제외하고 일치하는 상한 및 하한을 제공하는 미니맥스 샘플 복잡도 $N_{SA}$ (상태-행동 쌍당 샘플 수)를 제시한다. 복잡도는 $H_0$와 $H_\sigma$의 순서 및 내성 체제에 따른 네 가지 체제 요약으로 특징지어진다:

$$N_{SA} \asymp \frac{SA}{\epsilon^2} \times \begin{cases} \min\{H_0, H_\sigma\} & \text{if } \epsilon \gtrsim \sigma H_0 \quad (\text{High Tolerance}) \\ \min\{H_0, H_\sigma\} + \sigma H_\sigma^2 & \text{if } \epsilon \lesssim \sigma H_0 \quad (\text{Low Tolerance}) \end{cases}$$

• 고내성 체제: 복잡도는 선형 스팬 항인 $\min\{H_0, H_\sigma\}$에 의해 지배된다. 만약 $H_\sigma \leq H_0$라면, 강건 축소가 명목 축소보다 더 타이트한 경계를 제공한다.
• 저내성 체제: 추가적인 "강건성 특화" 항인 $\sigma H_\sigma^2$가 나타나며, 이는 높은 정밀도가 요구될 때 분포 불확실성을 처리하는 비용을 나타낸다.
• 하한: 저자들은 상한과 일치하는 미니맥스 하한을 증명하여, $\sigma H_\sigma^2$ 항이 저내성 체제에서 근본적이며 피할 수 없음을 확립하였다. 이는 분포 강건 AMDP의 통계적 한계를 규명하는 최초의 하한이다.

의의 및 주장
본 논문은 분포 강건 AMDP에 대한 미니맥스 최적의 샘플 복잡도 특성을 제공한다고 주장한다. 주요 기여는 다음과 같다:

• 샘플 복잡도 격차 해소: 기존의 강건 상한(예: Roch et al., 2025, 2026)은 고내성과 저내성을 구분하지 않고 강건 스팬 파라미터($H_{Roch}^2$ 또는 $H_{RHI}^2$)에 이차적으로 의존했다. 본 연구는 이를 고내성 체제에서의 $\min\{H_0, H_\sigma\}$로 정교화하고, 저내성 체제에서의 정확한 $\sigma H_\sigma^2$ 비용을 식별하였다.
• 적응형 알고리즘: 제안된 스팬 무관 절차(Algorithm 2)는 스팬 파라미터에 대한 사전 지식 없이도 최적의 비율을 달성하며, $H_0$와 $H_\sigma$의 상대적 크기와 체제에 자동으로 적응한다.
• 일반성: 결과는 $H_\sigma$가 유계(bounded)라고 가정하는 것만으로도 $\tilde{\Theta}(SA(H_\sigma + \sigma H_\sigma^2)\epsilon^{-2})$의 복잡도를 갖는다.

제어된 시뮬레이션에 대한 실험 결과는 $\min\{H_0, H_\sigma\}$에 대한 선형 의존성과 저내성 체제에서의 $\sigma H_\sigma^2$에 대한 이차 의존성, 그리고 스팬 무관 알고리즘의 적응성을 검증한다. 저자들은 향후 연구가 결합된 불확실성 구조(coupled uncertainty structures) 및 온라인(regret-based) 설정을 탐구할 수 있음을 언급하지만, 현재의 연구는 엄격하게 생성 모델 설정에 집중한다.