Value Iteration for Long-run Average Reward in Markov Decision Processes
This work provides practical algorithms for a previously unsolved problem in MDP analysis, benefiting researchers and practitioners in probabilistic verification and reinforcement learning.
The authors tackle the problem of computing long-run average rewards in Markov decision processes (MDPs) using value iteration (VI). They present two practical VI-based algorithms that provide approximation guarantees and outperform standard approaches on benchmarks, with experimental results showing significant improvements.
Markov decision processes (MDPs) are standard models for probabilistic systems with non-deterministic behaviours. Long-run average rewards provide a mathematically elegant formalism for expressing long term performance. Value iteration (VI) is one of the simplest and most efficient algorithmic approaches to MDPs with other properties, such as reachability objectives. Unfortunately, a naive extension of VI does not work for MDPs with long-run average rewards, as there is no known stopping criterion. In this work our contributions are threefold. (1) We refute a conjecture related to stopping criteria for MDPs with long-run average rewards. (2) We present two practical algorithms for MDPs with long-run average rewards based on VI. First, we show that a combination of applying VI locally for each maximal end-component (MEC) and VI for reachability objectives can provide approximation guarantees. Second, extending the above approach with a simulation-guided on-demand variant of VI, we present an anytime algorithm that is able to deal with very large models. (3) Finally, we present experimental results showing that our methods significantly outperform the standard approaches on several benchmarks.