기술 요약: 단일 궤적으로부터의 평균 보상 마르코프 결정 과정 학습

문제 정의

본 논문은 **평균 보상 마르코프 결정 과정(average-reward MDPs)**에서 **단일 궤적(single trajectory)**으로부터 유도된 **유한 샘플 복잡도 보장(finite sample complexity guarantees)**을 사용하여 $\epsilon$-최적 정책을 찾는 과제를 다룹니다.

할인 누적 보상(discounted cumulative-reward) MDP의 샘플 복잡도에 관한 광범위한 문헌이 존재하지만, 평균 보상 MDP에 대한 분석은 역사적으로 제한적인 가정들에 의존해 왔습니다. 기존 연구들은 일반적으로 다음 중 하나를 요구합니다:

1. 생성 모델(Generative models) (임의의 상태로 리셋할 수 있는 시뮬레이터에 대한 접근).
2. i.i.d. 오프라인 데이터.
3. 강한 구조적 가정, 예를 들어 에르고디시티(ergodicity) (모든 정책이 단일 재귀 클래스를 유도함) 또는 행동 정책에 대한 특정 커버리지 조건.

본 연구가 목표로 하는 구체적인 공백은 약하게 통신하는(weakly communicating) 설정입니다. 약하게 통신하는 MDP에서는, 어떤 "잘 정의된" 정책 하에서도 상태 공간이 하나의 재귀 클래스(recurrent class)와 일련의 일시적 상태(transient states) 집합으로 분해되지만, 시스템이 반드시 에르고디시적이지는 않습니다(즉, 일시적 상태가 존재함). 본 연구 이전에는 이 설정에서 단일 궤적으로부터의 평균 보상 RL에 대한 유한 샘플 복잡도 분석은 탐구되지 않았습니다.

방법론

저자들은 약하게 통신하는 MDP의 구조적 특성, 특히 **재귀-일시적 분류(recurrent-transient classification)**를 활용하는 이론적 프레임워크와 새로운 모델 프리(model-free) 알고리즘을 개발합니다.

1. 단일 궤적의 구조적 분석

핵심적인 기술적 기여는 행동 정책 $\pi_b$에 의해 생성된 단일 궤적에 대한 확률적 분석입니다. 저자들은 다음을 확립합니다:

• 재귀-일시적 불변성(Recurrent-Transient Invariance): 정책 공간의 내부($\Pi_+$)에 있는 정책들에 대해, 상태를 단일 재귀 클래스($R$)와 일시적 집합($T$)으로 분류하는 것은 전이 커널 $P$에 의해서만 결정되며, 특정 정책 선택에 의해 결정되지 않고 불변합니다.
• 일시적 상태 탈출(Escaping Transient States): 마르코프 부등식과 강한 마르코프 성질을 사용하여, 일시적 상태에서 시작하는 궤적이 높은 확률로 유한한 도달 시간(hitting time, $t_{hit}$) 내에 재귀 클래스 $R$에 도달함을 증명합니다.
• 재귀 클래스 커버(Covering the Recurrent Class): 일단 $R$에 도달하면, 궤적은 유한한 커버링 시간(covering time, $t_{cov}$) 내에 $R$의 모든 상태를 커버합니다.
• 정지 시간을 통한 i.i.d. 샘플링: 정지 시간(특히 궤적이 특정 상태 $s$로 돌아오는 시점)을 활용하여, 저자들은 단일 궤적으로부터의 샘플이 농축 부등식(concentration inequalities)을 적용하기 위한 목적(Lemma 2.3)으로 독립 항등 분포(i.i.d.)로 취급될 수 있음을 보여줍니다. 이는 혼합 시간(mixing time) 가정을 요구하지 않고 단일 궤적 분석에 내재된 의존성 문제를 해결합니다.

2. 가치 기반 방법: SAVIC

**확률적 앵커드 가치 반복(Stochastic Anchored Value Iteration, SAVIC)**은 약하게 통신하는 MDP를 위해 설계된 모델 프리 가치 기반 알고리즘입니다. 이는 세 단계로 작동합니다:

1. 재귀 상태 식별: 에이전트는 행동 정책을 실행하여 일시적 상태를 탈출하고, **알고리즘 1 (RECUR)**을 사용하여 모든 재귀 상태($R$)의 목록을 수집합니다.
2. 앵커를 이용한 반복 및 분산 감소: 재귀 클래스 내에서, 알고리즘은 **앵커드 가치 반복(Anchored Value Iteration, Anc-QI)**을 수행합니다. 표준 VI와 달리, Anc-QI는 다음 반복값(iterate)을 벨만 업데이트와 초기 지점($Q_0$)의 볼록 결합(convex combination)으로 계산합니다. 이 "앵커" 항은 비점근적 수렴을 보장합니다.
   • 효율적인 샘플 복잡도를 달성하기 위해, 이 방법은 재귀적 샘플링 기법을 사용합니다. 각 단계에서 전체 벨만 연산자 $T(Q_k)$를 추정하는 대신, 분산이 감소된 샘플링을 사용하여 차이 $T(Q_k) - T(Q_{k-1})$를 추정합니다.
3. 정책 섭동(Policy Perturbation): 알고리즘은 재귀 클래스 $R$에 대해서만 최적화를 수행하므로, 최종 정책은 일시적 상태를 포함한 전체 상태 공간 $S$에 대해 $\epsilon$-최적임을 보장하도록 섭동됩니다.

3. 사전 지식 없는 모델 프리 방법: SAVIC+

통신하는 MDP(여기서 $S=R$, 즉 일시적 상태가 없음)를 위해, 저자들은 **SAVIC+**를 도입합니다.

• 이 변형은 문제 의존적 상수(예: $t_{hit}$, $t_{cov}$, 또는 최소 정상 분포 확률 $d_{min}$)에 대한 사전 지식 없이 작동합니다.
• **더블링 트릭(doubling trick)**과 경험적 벨만 잔차 오차($\|Q - TQ\|_{sp}$)에 기반한 명시적인 정지 규칙을 사용합니다.
• 모든 상태-행동 쌍에 대해 충분한 횟수의 샘플이 수집될 때까지 자동으로 샘플을 수집하기 위해 **알고리즘 4 (SAMPLE+)**를 사용합니다.

4. 정책 기반 방법: SCPMA

**확량적 $\alpha$-클리핑드 정책 미러 어센트(Stochastic $\alpha$-clipped Policy Mirror Ascent, SCPMA)**는 약하게 통신하는 MDP를 위한 정책 경사(policy gradient) 방법입니다.

• 이는 SAVIC와 동일한 앵커링 및 분산 감소 메커니즘을 사용하여 상태-행동 가치 함수를 근사하는 새로운 **정책 평가 알고리즘(SAVIPE)**을 활용합니다.
• 정책 업데이트는 정책 미러 어센트(Policy Mirror Ascent) 프레임워크를 따르지만, 정책이 정책 공간의 내부($\Pi_\alpha$)에 머물도록 $\alpha$-클리핑을 적용합니다. 이 클리핑은 샘플 복잡도 분석에서 계수를 제한하는 데 매우 중요합니다.
• 이 방법은 상수 및 적응형 단계 크기(step size)를 모두 지원합니다.

주요 결과

본 논문은 약하게 통신하는 설정에서 단일 궤적으로부터의 평균 보상 MDP에 대한 최초의 유한 샘플 복잡도 보장을 확립합니다.

1. SAVIC (가치 기반):

   • $\epsilon$-최적 정책을 찾는 데 $\tilde{O}(1/\epsilon^2)$의 샘플 복잡도를 달성합니다.
   • 이 경계는 도달 시간($t_{hit}$), 커버링 시간($t_{cov}$), 최적 가치 함수의 스팬($\|Q^*\|_{sp}$), 그리고 최소 정상 분포 확률의 역수($1/d_{min}^\pi$)에 의존합니다.

2. SAVIC+ (모델 프리, 사전 지식 없음):

   • 통신하는 MDP에 대해, SAVIC+는 $\tilde{O}(1/\epsilon^2)$ 샘플 복잡도를 달성합니다.
   • 결정적으로, 매개변수를 설정하기 위해 문제 의존적 양(예: $t_{cov}$ 또는 $d_{min}$)에 대한 사전 지식이 필요하지 않습니다.

3. SCPMA (정책 기반):

   • 상수 단계 크기를 사용할 경우 $\tilde{O}(1/\epsilon^4)$의 샘플 복잡도를 달성하거나, 적응형 단계 크기를 사용하여 개선된 비율을 달성합니다.
   • 이는 약하게 통신하는 MDP에서 단일 궤적으로부터의 정책 경사 방법을 위한 최초의 유한 샘플 복잡도 보장입니다.

의의 및 주장

저자들은 본 연구가 약하게 통하는 설정의 단일 궤적으로부터 평균 보상 MDP를 학습하는 것에 대한 최초의 유한 샘플 복잡도 보장을 제공한다고 주장합니다.

• 에르고디시티 가정의 타파: 에르고디시티(모든 상태가 재귀적임)를 요구했던 이전 연구들과 달리, 본 연구는 일시적 상태가 존재하는 더 일반적인 약하게 통하는 경우를 다룹니다.
• 단일 궤적의 현실성: 본 결과는 비현실적인 생성 모델이나 i.i.d. 데이터 가정을 넘어, 에이전트가 순차적으로 환경과 상호작용하는 표준적인 온라인 학습 설정에 대한 보장을 제공합니다.
• 모델 프리 효율성: 제안된 방법들은 모델 프리 방식이며, SAVIC+의 경우 문제의 혼합 특성이나 정상 분포에 대한 사전 지식을 요구하지 않아 미지의 환경에 더 실용적입니다.
• 이론적 도구: 본 논문은 단일 궤적으로부터 i.i.d. 샘플을 생성하기 위해 정지 시간과 강한 마르코프 성질을 사용하는 새로운 이론적 도구를 도입하며, 이를 통해 이전에 i.i.d. 설정에만 국한되었던 농축 부등식을 적용할 수 있게 합니다.

저자들은 가치 기반 방법이 정책 기반 방법의 $\tilde{O}(1/\epsilon^4)$에 비해 더 타이트한 $\tilde{O}(1/\epsilon^2)$ 경계를 달성한다는 점을 언급하며, 이 간극을 좁히고 이러한 결과를 매개변수화된 함수 근사 설정으로 확장하는 것이 향로의 과제로 남아 있다고 결론짓습니다.