이 논문은 유한 상태 및 행동 마르코프 결정 과정(MDP) 및 강화학습(RL)을 위한 새로운 종료 기준인 "advantage gap function"을 제안합니다. 이 함수를 스텝 사이즈 규칙 설계에 통합하고 최적 정책의 정상 상태 분포에 독립적인 새로운 선형 수렴 속도를 도출함으로써, 정책 경사 방법이 MDP를 강 다항 시간(strongly-polynomial time) 내에 해결할 수 있음을 증명합니다. 또한, 확률적 환경에서도 advantage gap function이 각 상태의 최적성 간극(optimality gap)을 근사하고 하위 선형 수렴 속도를 보이며, 이를 통해 정책 경사 방법의 해결책을 검증하는 편리한 방법을 제공합니다.
