Abstract
Focused Real-Time Dynamic Programming (FRTDP) is an evolution of the classic RTDP algorithm that significantly speeds up MDP planning by maintaining both upper and lower bounds on the value function. By prioritizing search in areas of the state space with the highest uncertainty and using an adaptive trial depth, FRTDP converges up to six times faster than previous state-of-the-art methods while providing much better "anytime" performance.
Introduction
The challenge of planning in Markov Decision Processes (MDPs) involves decision-making where actions have uncertain outcomes. Traditional heuristic search algorithms like Real-Time Dynamic Programming (RTDP) explore the state space by running "trials" from a start state. However, RTDP has two major weaknesses: it only tracks one-sided (upper) bounds on rewards, making it difficult to assess policy optimality, and it relies on stochastic exploration, which often wastes computational resources on irrelevant or well-understood parts of the state space.
Methodology
To address these limitations, the authors introduce Focused RTDP (FRTDP), which incorporates three key innovations:
- Two-Sided Bounds: FRTDP maintains both a lower bound ($V^L$) and an upper bound ($V^U$). The agent’s policy is based on the lower bound, which is more stable and provides a "regret bound"—a guarantee of how much reward might be missed.
- Priority-Based Outcome Selection: Instead of picking the next state in a trial stochastically, FRTDP calculates a priority for each outcome based on an approximation of "occupancy times uncertainty." This forces the search to follow the most impactful outcomes for reducing ignorance about the best path.
- Adaptive Maximum Depth (AMD): To prevent the algorithm from getting stuck in deep, irrelevant parts of the search graph, FRTDP caps the depth of each trial. It uses a feedback loop to increase this depth limit only when the updates at the end of a trial are as "high quality" as those at the beginning.
Experimental Setup
The algorithm was evaluated using the Racetrack benchmark, a standard in the MDP community, using the large-b and large-ring maps. To test robustness, noise variants were added: a -3 suffix for increased skidding probability and a -w (Wind) variant where errors result in random accelerations. FRTDP was compared against RTDP, Labeled RTDP (LRTDP), and Heuristic Dynamic Programming (HDP).
Key Results and Discussion
FRTDP demonstrated significant performance gains across all benchmarks. In terms of "backups" (the fundamental computational unit of value iteration), FRTDP was 2.9x to 6.4x faster than the state-of-the-art HDP algorithm.
As shown in the performance plots, FRTDP reaches high-quality solutions much faster. For example, on the large-ring-w problem, FRTDP reached a specific quality threshold with 40 times fewer backups than HDP. While calculating lower bounds adds approximately 10% overhead to wall-clock time per update, the massive reduction in the total number of updates required makes the algorithm much faster overall.
The authors found that policies derived from the lower bound perform significantly better "anytime" than those derived from the upper bound. Because FRTDP uses a finite trial depth and two-sided bounds, it can theoretically solve a broader class of problems than RTDP, such as those with infinite state spaces or "one-way doors" where a bad early choice makes the goal unreachable.
Conclusion and Future Work
FRTDP represents a substantial improvement in MDP planning efficiency. However, some limitations remain: the priority calculation assumes the search graph is a tree (which is an approximation for general graphs), and the Adaptive Maximum Depth (AMD) mechanism is currently somewhat ad-hoc. Future work may focus on more theoretically grounded depth adjustment and direct comparisons with other bounded methods like BRTDP.
Summary updated