표본 마르코프 결정 과정 (MDP) 의 최적 후속 샘플링을 통한 정책 식별

우리는 유한 시간 간격의 episodic Markov Decision Processes(MDP) 에서 $(\varepsilon, \delta)$-PAC 정책 식별 문제를 연구합니다. 기존 접근 방식은 근사 설정 ($\varepsilon>0$) 에 대해 유한 시간 보장을 제공하지만, 높은 계산 비용으로 인해 구현이 어렵고, 또한 $\log(1/\delta)$ 의 최적 의존성을 갖지 못합니다. 우리는 MDP 에서 탐색을 안내하기 위해 후속 샘플링과 온라인 학습 알고리즘을 결합한 무작위적이고 계산 효율적인 최선의 정책 식별 알고리즘을 제안합니다. 우리의 방법은 샘플 복잡성 측면에서, 또한 후속 수축률 (posterior contraction rate) 측면에서도 점근적 최적성을 달성하며, 에피소드 당 $O(S^2AH)$ 의 실행 속도를 가지며 표준 모델 기반 접근 방식과 일치합니다. 이전 알고리즘들 (예: MOCA 와 PEDEL) 과 달리, 우리의 보장은 점근적 영역에서 의미 있는 것으로 유지되며 $\log(1/\delta)$ 에 대한 비최적 다항식 의존성을 피합니다. 우리의 결과는 표본 MDP 에서 효율적인 정책 식별을 위한 이론적 통찰과 실용적인 도구를 제공합니다.