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

요약

이 논문은 유한 시간 간격의 에피소드 마르코프 결정 과정(MDP)에서 $(\varepsilon, \delta)$-PAC 정책 식별 문제를 다룹니다. 기존 방법들이 높은 계산 비용이나 최적 의존성 문제점을 가졌던 것과 달리, 연구진은 후속 샘플링과 온라인 학습 알고리즘을 결합한 새로운 접근 방식을 제안했습니다. 이 방법은 샘플 복잡성과 후속 수축률 측면에서 점근적 최적성을 달성하며, 계산 효율성이 높고 $\log(1/\delta)$에 대한 비최적 다항식 의존성을 피하는 것이 주요 강점입니다.

핵심 포인트

• 유한 시간 에피소드 MDP의 $(\varepsilon, \delta)$-PAC 정책 식별 문제를 해결합니다.
• 후속 샘플링과 온라인 학습을 결합하여 계산 효율적이고 무작위적인 최적 정책 식별 알고리즘을 제안했습니다.
• 샘플 복잡성 및 후속 수축률 측면에서 점근적 최적성을 달성했습니다.
• 기존 방법의 단점인 높은 계산 비용과 $\log(1/\delta)$에 대한 비최적 다항식 의존성을 극복했습니다.