본 논문은 마르코프 체인(MCs)과 마르코프 의사결정 과정(MDPs)에 대한 확률적 시스템의 두 가지 표준 모델을 다룹니다. 제어 및 계획 문제에 대한 이러한 확률적 모델의 고전적인 목표는 도달 가능성과 확률적 최단 경로입니다. 이러한 문제에 대한 널리 연구된 알고리즘적 접근 방식은 벨만 업데이트라고 하는 지역적 업데이트를 반복적으로 적용하는 값 반복(VI) 알고리즘입니다. 문헌에는 VI에 대한 많은 실용적인 접근 방식이 있지만, 최악의 경우 MC에 대해서는 기하급수적으로 많은 벨만 업데이트가 필요합니다. 전처리 단계는 이산적이고 그래프 이론적이며 선형 공간을 필요로 하는 알고리즘입니다. 중요한 미해결 문제는 다항 시간 전처리 후 VI를 기하급수적으로 적은 벨만 업데이트로 달성할 수 있는지 여부입니다. 본 연구에서는 값 추측을 기반으로 하는 새로운 VI 접근 방식을 제시합니다. 이론적 기여는 두 가지입니다. 첫째, MC의 경우 거의 선형 시간 전처리 알고리즘을 제시하여 값 추측과 함께 VI가 기하급수적으로 적은 벨만 업데이트만 필요하도록 합니다. 둘째, MDP에 대한 VI의 수렴 속도에 대한 개선된 분석을 제시합니다. 마지막으로, 새로운 접근 방식을 기반으로 하는 MDP에 대한 실용적인 알고리즘을 제시합니다. 실험 결과는 본 접근 방식이 문헌의 여러 벤치마크 예제에서 기존 VI 기반 접근 방식보다 상당한 개선을 제공함을 보여줍니다.
