마르코프 결정 과정 (Markov decision processes, MDPs)은 비결정론적 선택과 확률적 불확실성을 모두 나타내는 불확실성 하에서의 의사결정을 위한 고전적인 모델입니다. 전통적으로는 기저에 깔린 확률에 대한 정확한 지식이 있다고 가정합니다. 그러나 사이버 물리 시스템 (cyber-physical systems)이나 생물학적 과정을 모델링할 때와 같이, 이는 종종 비현실적입니다. 여기서 통계적 방법은 의미 있는 보장을 얻기 위한 방법을 제공합니다. 고전적인 접근 방식은 MDP에서 샘플을 수집하고, 이를 사용하여 전이 확률 (transition probabilities)에 대한 통계적 결론을 도출하며, 이를 통해 실제 값에 대한 경계 (bounds)를 얻는 것입니다. 만약 이 경계가 너무 넓다면, 이 과정을 반복합니다. 그러나 이러한 접근 방식의 기존 구현체들은 미묘하게 부정확하거나 최적화되지 않았으며, 종종 두 가지 문제 모두를 가지고 있습니다. 우리는 이러한 "온라인 (online)" 설정에 특화되어 설계된 여러 "신뢰 구간 시퀀스 (confidence sequences)"를 제시하고, 이를 효율적인 도구로 모두 구현하며, 그 실질적인 적용 가능성을 보여줍니다. 특히, 우리는 이것들이 고전적인 "합집합 경계 (union-bound)" 스타일의 접근 방식보다 성능이 뛰어남을 보여주며, 전반적으로 우리의 구현은 기존의 최첨단 (state of the art) 기술보다 평균적으로 50배 적은 샘플을 필요로 합니다.