평균 보상 마르코프 결정 과정(Average-Reward MDP)에서의 단일 궤적을 통한 정책 학습

할인 누적 보상(discounted cumulative-reward) MDP의 샘플 복잡도(sample complexity)를 규명하는 광범위한 연구들이 존재하지만, 평균 보상(average-reward) MDP에 대한 유한 샘플 분석(finite sample analyses)은 제한적이었으며, 기존의 대부분의 연구는 에르고드성(ergodicity)이나 생성 모델(generative model)에 대한 접근과 같은 제한적인 가정에 의존해 왔습니다. 본 연구에서는 약한 통신(weakly communicating) 평균 보상 MDP에 대해 단일 궤적(single trajectory)으로부터 얻을 수 있는 최초의 유한 샘플 복잡도 보장(finite sample complexity guarantees)을 확립합니다. 이를 위해, 우리는 약한 통신 MDP에서의 단일 궤적 역학(dynamics)을 연구하며, 이 분석을 바탕으로 새로운 모델 프리(model-free) 방법론을 개발합니다. 특히, 우리의 가치 기반(value-based) 및 정책 기반(policy-based) 방법은 약한 통신 MDP의 단일 궤적으로부터 각각 $\widetilde{O}(1/\varepsilon^2)$ 및 $\widetilde{O}(1/\varepsilon^4)$의 유한 샘플 복잡도 보장을 제공합니다. 나아가, 우리는 통신(communicating) MDP에 대해 문제 의존적 양(problem-dependent quantities)에 대한 사전 지식이 필요 없는 최초의 모델 프리(model-free) 방법을 소개합니다.