Finite-Time Convergence of Distributionally Robust Q-Learning with Linear Function Approximation

기술 요약: 선형 함수 근사를 이용한 분포 강건 Q-러닝의 유한 시간 수렴성

문제 정의
본 논문은 훈련 환경(명목상 환경)과 배포 환경이 서로 다른 상황에서 분포 강건 강화학습(Distributionally Robust Reinforcement Learning, DRRL)을 수행할 때 발생하는 과제를 다룹니다. 저자들은 특히 $(s, a)$-직사각형 카이제곱(chi-square) 불확실성 집합 하에서의 **모델 프리(model-free), 할인된 강건 Q-러닝(discounted robust Q-learning)**에 초점을 맞춥니다.

설정상 학습자는 알려지지 않은 명목 전이 커널 $P_0$와 행동 정책 $\pi_b$에 의해 생성된 단일 마르코프 궤적(Markovian trajectory) 상에서 동작합니다. 학습자는 생성적 접근(generative access, 임의의 상태-행동 쌍을 샘플링할 수 있는 능력)을 가질 수 없으며, $P_0$를 알지 못합니다. 목표는 불확실성 집합에 대해 최악의 할인된 가치를 최대화하는 최적의 강건 Q-함수 $Q^\star_\chi$를 학습하는 것입니다.

이 문제는 두 가지 결합된 어려움을 제시합니다:

1. 함수 근사 문제: 정확한 강건 벨만 연산자(robust Bellman operator)는 $\ell_\infty$에서 축약 사상(contraction)이지만, 선형 함수 근사에 의해 유도된 투영된(projected) 강건 벨만 연산자는 일반적인 할인 인자 $\gamma \in (0, 1)$에 대해 축약 사상임이 알려져 있지 않습니다.
2. 강건 추정 문제: 카이제곱 강건 벨만 업데이트는 전이 분포에 대한 내부 최소화를 포함합니다. 이의 쌍대 그래디언트(dual gradient)는 단일 궤적으로부터 추정되어야 하는 조건부 모멘트(구체적으로 벨만 갭의 양의 부분 및 그 제곱)에 의존합니다. 표준적인 테이블형(tabular) 강건 Q-러닝 또는 선형 Q-러닝 분석은 이 설정으로 직접 확장되지 않습니다.

방법론
저자들은 타겟 네트워크 외곽 루프(target-network outer loop)와 쌍대 함수 근사 기법을 결합한 다단계 확률 근사 알고리즘인 알고리즘 1을 제안합니다. 이 알고리즘은 타겟 Q-함수가 고정되는 외곽 블록(outer blocks) 단위로 작동합니다. 각 블록 내에서는 세 단계가 진행됩니다:

1. 1단계: 모멘트 추적을 포함한 쌍대 최적화(Dual Optimization with Moment Tracking).
   알고리즘은 카이제곱 강건 벨만 업데이트의 스칼라 쌍대 형태를 통해 내부 최소화 문제를 해결합니다. 모든 상태-행동 쌍에 대해 별도의 쌍대 문제를 푸는 대신, 쌍대 변수 $\eta$를 선형적으로 근사합니다 ($\eta_\nu(i) = \psi(i)^\top \nu$).
   • 두 가지 시간 척도 체계(Two-Time-Scale Scheme): 쌍대 변수 $\nu$는 느린 시간 척도에서 업데이트되는 반면, 두 개의 "모멘트 추적 비평가(moment-tracking critics)"($\omega_1, \omega_2$)는 필요한 조건부 모멘트($Z_1$ 및 $Z_2$)를 더 빠른 시간 척도에서 추정합니다.
   • 스무딩(Smoothing): 카이제곱 쌍대 목적 함수의 전역적 매끄러움(global smoothness) 결여(이는 마르코프 노이즈 분석에서 문제를 일으킴)를 처리하기 위해, 저자들은 조절 가능한 파라미터 $\tau > 0$를 사용하는 **스무딩된 대리 목적 함수(smoothed surrogate objective)**를 최적화합니다. 이를 통해 쌍대 그래디언트가 리프시츠 연속(Lipschitz continuous)이 되도록 보장합니다.
   • 접미사 평균화(Suffix Averaging): 안정적인 추정치 $\bar{\nu}_t$를 얻기 위해 쌍대 반복값들을 접미사 평균화합니다.
2. 2단계: 신선한 평가(Fresh Evaluation).
   Q-함수를 업데이트하기 전, 알고리즘은 평균화된 쌍대 파라미터 $\bar{\nu}_t$를 사용하여 분산 유사 모멘트($Z_1$)에 대한 "신선한 평가"를 수행합니다. 이 단계는 모멘트의 추정을 최적화 궤적으로부터 격리함으로써, 1단계의 비평가( $\nu$가 움직이는 동안 학습된 것)를 직접 재사용할 때 발생할 수 있는 편향 축적을 방지합니다.
3. 3단계: Q-업데이트.
   알고리즘은 고정되고 평가된 타겟(2단계에서 도출됨)에 대해 강건 Q-함수 파라미터 $\theta$에 대한 느린 차분(temporal difference) 업데이트를 수행합니다.

주요 기여

1. 유한 시간 수렴 보장: 저자들은 작은 할인 인자 제한 없이, 단일 궤적 데이터로부터 선형 함수 근사를 사용하는 할인된 모델 프리 강건 Q-러닝에 대한 최초의 유한 시간 수렴 경계를 제공합니다.
2. 강건 RL을 위한 타겟 네트워크 분석: (비강건 딥 RL에서 흔히 쓰이는) 타겟 네트워크 기법을 강건 설정에 맞게 변형했습니다. 외곽 블록 내에서 타겟 Q-함수를 고정함으로써, 투영된 강건 벨만 연산자의 비축약성(non-contractivity) 문제를 우회하고, 블록 간의 비투영 연산자의 축약성에 기반하여 분석할 수 있도록 했습니다.
3. 확장 가능한 쌍대 추정: 쌍대 변수 자체를 선형 함수 클래스를 사용하여 근사하는 방법을 도입하며, 이를 모멘트 추적 비평가와 결합합니다. 이는 큰 상태 공간에 대해 독립적인 쌍대 문제를 푸는 데 따르는 확장성 문제를 피하게 해줍니다.
4. 스무딩 및 편향 제어: 저자들은 카이제곱 쌍대 목적 함수를 위한 스무딩된 대리 함수를 도입합니다. 이는 카이제곱 공식에 내재된 비-리프시츠 그래디언트 문제를 해결하여, 마르코프 노이즈 하에서도 엄밀한 유한 시간 확률 근사 경계를 가능하게 합니다. 저자들은 기존의 테이블형 강건 Q-러닝 증명들이 전역 매끄러움 가정을 사용했으나 이는 적절하지 않음을 지적하며, 본 연구가 이 간극을 바로잡았다고 명시합니다.

결과
주요 이론적 결과(정리 1)는 다음과 같은 형태의 엔드-투-엔드 수렴 경계를 확립합니다:
$$\mathbb{E}[\| \hat{Q}_T - Q^\star_\chi \|_\infty] \leq \gamma^T \| \hat{Q}_0 - Q^\star_\chi \|_\infty + \frac{E_{stat}(N, M, K, \tau) + E_{app}(\tau)}{1 - \gamma}$$
여기서:

• 첫 번째 항은 타겟 네트워크의 축약 오차를 나타냅니다.
• $E_{stat}$는 Q-업데이트, 쌍대 최적화, 스무딩 편향, 그리고 신선한 평가로부터 발생하는 유한 샘플 오차를 포착합니다.
• $E_{app}$는 함수 근사와 스무딩으로 인한 근사 오차를 포착합니다.

FrozenLake MDP에 대한 실험은 이론을 검증하며, 강건 참조 값(robust reference value)으로의 수렴을 보여주고 스무딩 파라미터 $\tau$가 도입하는 트레이드오프(작은 $\tau$는 편향을 줄이지만 분산/최적화 오차를 증가시킴)를 보여줍니다.

의의 및 주장
본 논문은 강건 RL 알고리즘의 경험적 성공과 비강건 대응 모델들의 가용 가능한 이론적 보장 사이의 상당한 간극을 메운다고 주장합니다. 기존의 모델 프리 강건 RL 연구는 테이블형 설정에 국한되었거나, 생성적 접근을 요구하거나, 능동적 탐색을 가정하거나, 혹은 제한적인 할인 인자 조건을 부과했습니다.

저자들은 본 연구가 작은 할인 인자 가정을 하지 않고 단일 궤적 데이터로부터 선형 함수 근사를 사용하는 할인된 모델 프리 강건 Q-러닝에 대한 최초의 유한 시간 수렴 보장을 제공한다고 밝힙니다. 또한, 카이제곱 경우(테이블 한계에서도)에 대한 본 연구의 증명이 이전의 분석들이 간과하거나 가정해버린 쌍대 목적 함수의 전역 매끄러움 결여 문제를 다루고 있으므로, 가장 올바른 수렴 증명이라고 주장합니다. 이 프레임워크는 대규모 신경망 구현으로 확장 가능한 분석 가능한 템플릿으로 제시됩니다.