Abstract: We propose empirical dynamic programming algorithms for Markov decision processes (MDPs). In these algorithms, the exact expectation in the Bellman operator in classical value iteration is replaced by an empirical estimate to get 'empirical value iteration' (EVI). Policy evaluation and policy improvement in classical policy iteration are also replaced by simulation to get 'empirical policy iteration' (EPI). Thus, these empirical dynamic programming algorithms involve iteration of a random operator, the empirical Bellman operator. We introduce notions of probabilistic fixed points for such random monotone operators. We develop a stochastic dominance framework for convergence analysis of such operators. We then use this to give sample complexity bounds for both EVI and EPI. We then provide various variations and extensions to asynchronous empirical dynamic programming, the minimax empirical dynamic program, and show how this can also be used to solve the dynamic newsvendor problem. Preliminary experimental results suggest a faster rate of convergence than stochastic approximation algorithms.
Introduction
Dynamic programming (DP) serves as the foundational framework for sequential decision-making under uncertainty. However, its practical application is often hindered by the "curse of dimensionality." In standard Markov Decision Processes (MDPs), the Bellman operator requires the calculation of exact expectations over all possible future states. As state and action spaces grow, these calculations become computationally prohibitive.
While Reinforcement Learning (RL) and stochastic approximation methods, such as Q-learning, offer alternatives by learning from samples, they often suffer from slow convergence rates and require specific mathematical properties, like the recurrence property, to ensure stability. In "Empirical Dynamic Programming," Haskell, Jain, and Kalathil propose a middle ground: Empirical Dynamic Programming (EDP). By replacing exact expectations with empirical sample averages within a batch or off-line framework, EDP aims to provide the robustness of traditional DP with the sample-based flexibility of RL.
The Empirical Dynamic Programming Framework
The core innovation of EDP lies in the substitution of the exact Bellman operator with an empirical counterpart. The authors introduce two primary algorithmic variants:
- Empirical Value Iteration (EVI): In classical value iteration, the value function is updated using the exact expected future cost. EVI instead utilizes $n$ independent samples of the next state to construct an empirical estimate of the Bellman operator. This transforms the deterministic iteration into a sequence of random operator applications.
- Empirical Policy Iteration (EPI): Similar to EVI, EPI adapts the policy evaluation and policy improvement steps of classical policy iteration. Both steps are performed using simulation-derived empirical expectations rather than analytical ones.
Unlike incremental RL methods, EDP operates in a "batch" manner. It does not require visiting states in a specific trajectory or satisfying strict recurrence properties; rather, it requires sufficient sampling at each iteration to maintain the accuracy of the empirical operator.
Theoretical Foundations: Probabilistic Fixed Points
Because EDP involves random operators, the standard fixed-point theorems used in classical DP do not directly apply. To address this, the authors introduce the concept of probabilistic fixed points. They define both "strong" and "weak" versions of fixed points for random monotone operators, providing a language to describe the behavior of algorithms that converge toward a distribution rather than a single point.
To prove convergence, the authors develop a stochastic dominance framework. They construct a "dominating Markov chain" that tracks the distance between the empirical estimate and the true optimal value. By showing that this simpler, dominating chain converges to zero, they establish that the more complex empirical algorithm must also converge to the optimal solution with high probability.
Key Insights and Results
A significant theoretical contribution of the paper is the proof of asymptotic coincidence. The authors demonstrate that as the sample size $n$ increases, the probabilistic fixed points of the empirical operators coincide with the unique fixed point of the classical Bellman operator. This ensures that EDP is consistent with classical theory in the limit.
Sample Complexity and Convergence
The research provides explicit sample complexity bounds, defining the number of samples ($n$) and iterations ($k$) required to reach within $\epsilon$ of the optimal value function with a confidence level of $1-\delta$.
In numerical evaluations using synthetic MDPs (e.g., a 10-state, 5-action model), EVI and EPI demonstrated significantly faster convergence than traditional stochastic approximation algorithms like Actor-Critic and Q-learning. While Actor-Critic methods often required a vast number of iterations to stabilize, EDP methods reached low error rates rapidly.
Extension to Continuous Spaces
The utility of EDP extends beyond discrete grid worlds. The authors applied the framework to the Dynamic Newsvendor Problem, a classic inventory management challenge with continuous state and action spaces. By exploiting Lipschitz continuity, they showed that EDP can effectively solve complex, continuous-space problems that are traditionally difficult for standard DP.
Conclusion and Future Directions
Empirical Dynamic Programming offers a promising bridge between the theoretical guarantees of DP and the practical sample-based nature of RL. Its "off-line" nature makes it highly parallelizable, suggesting high scalability on modern hardware through asynchronous implementations.
While EDP mitigates the difficulty of calculating expectations, it still requires iterating over the state space, meaning the curse of dimensionality is not entirely eliminated. Future research directions include extending this framework to average-cost MDPs and Partially Observable MDPs (POMDPs), as well as integrating state aggregation techniques to further enhance scalability in massive state spaces.
Summary updated