본 논문은 강화 학습(RL)의 근본적인 문제인 재현 가능성을 다룬다. RL 알고리즘의 불안정성과 훈련 조건 변화에 대한 민감성 때문에, 저자들은 PAC-RL 프레임워크 내에서 'list replicability'를 연구한다. List replicability는 알고리즘이 여러 번 실행될 때, 높은 확률로 작은 'list' 내의 거의 최적의 정책을 반환하도록 요구한다. 이 list의 크기는 'list complexity'를 정의한다. 저자들은 약한 형태와 강한 형태의 list replicability를 제시한다. 약한 형태는 최종 학습된 정책이 작은 list에 속하는 것을 보장하고, 강한 형태는 전체 실행된 정책 시퀀스가 제약되는 것을 추가로 요구한다. 주요 기여는 polynomial list complexity를 보장하는 효율적인 tabular RL 알고리즘의 개발이다. 이 알고리즘은 (i) 무작위로 선택된 허용 오차 내에서 거의 최적의 선택 중에서 사전식 순서에 따라 행동을 선택하는 새로운 planning 전략, (ii) 재현 가능성을 유지하면서 확률적 환경에서 상태 도달 가능성을 테스트하는 메커니즘을 포함한다. 또한, 저자들은 새로운 planning 전략이 실제 RL 프레임워크의 안정성을 향상시킬 수 있음을 실험적으로 입증한다.
