An Empirical Dynamic Programming Algorithm for Continuous MDPs

William B. Haskell, Rahul Jain, Hiteshi Sharma, P. L. YuarXiv 2017 · DOI · arXiv

Abstract

We propose universal randomized function approximation-based empirical value iteration (EVI) algorithms for Markov decision processes (MDPs). The 'empirical' nature of these algorithms stems from the fact that each iteration is performed using samples available from simulations of the next state, effectively rendering the Bellman operator a random operator. We introduce two distinct approaches: a parametric method using random basis functions and a non-parametric method utilizing Reproducing Kernel Hilbert Spaces (RKHS). Both function spaces possess the universal function approximation property. Convergence analysis is conducted using a random operator framework and techniques from the theory of stochastic dominance, allowing for the derivation of finite-time sample complexity bounds. Numerical experiments on classic control benchmarks support the versatility and effectiveness of this approach.

Introduction

In the fields of Reinforcement Learning (RL) and Dynamic Programming (DP), transitioning from discrete "grid" worlds to continuous state spaces—such as those found in robotics or autonomous vehicle control—presents significant challenges. Traditional methods, most notably Fitted Value Iteration (FVI), typically rely on human experts to hand-pick "basis functions" to estimate value functions. If these mathematical building blocks are poorly chosen, the algorithm fails to converge to an optimal policy. This reliance on manual feature engineering makes designing RL agents more of an art than a science. Furthermore, many existing methods lack non-asymptotic bounds, leaving practitioners without clear guidance on the sample complexity required for specific accuracy levels.

Empirical Value Iteration and Function Approximation

This paper introduces Empirical Value Learning (EVL), which treats the Bellman operator as a random operator by utilizing samples from simulations. To address the continuous nature of the state space without manual feature engineering, the authors combine EVL with two types of universal function approximation:

  1. EVL + Random Parametric Basis Functions (RPBF): Instead of hand-tuning features, the algorithm randomly samples parameters for a large family of functions (e.g., cosines in a Fourier series). This approach transforms a potentially difficult non-convex optimization problem into a simple convex one for the weights, significantly improving computational efficiency.
  2. EVL + Reproducing Kernel Hilbert Space (RKHS): This non-parametric approach uses kernels to find the best fit in a high-dimensional space. It is "universal" because it can approximate any continuous function to arbitrary precision given sufficient data.

Theoretical Framework: Stochastic Dominance

A core contribution of this work is the Random Operator Framework. The authors utilize stochastic dominance to analyze the error propagation within the iterative process. By demonstrating that the complex error process of the algorithm is stochastically smaller than a simpler, easy-to-analyze Markov chain, they provide a clean methodology for analyzing convergence in both $L_p$ and supremum norms. This theoretical rigor allows for the derivation of explicit formulas for the number of states ($N$), samples of next states ($M$), and basis functions ($J$) required to reach a target error $\epsilon$ with high probability.

Experimental Evaluation

The proposed methods were evaluated on several classic control benchmarks:

  • Optimal Replacement Problem: A benchmark involving the maintenance of a durable good. EVL+RPBF achieved a relative error of less than 10% within 20 iterations, outperforming standard FVI when using generic polynomial bases.
  • Cart-Pole Balancing: A 4-dimensional continuous state space problem. EVL+RPBF maintained high rewards while demonstrating superior computational speed.
  • Acrobot: A 6-dimensional problem involving a two-link pendulum. In this test, the EVL+RPBF method was significantly faster than the RKHS version, averaging 3.67 minutes faster per iteration while maintaining performance.

Key Insights and Results

  • Randomization as a Shortcut: Picking basis functions randomly bypasses the non-convexity issues often associated with training neural networks. A "random kitchen sink" of features is frequently sufficient to approximate complex value functions.
  • Efficiency vs. Complexity: While the RKHS method is highly flexible, it involves matrix inversions that scale quadratically with the number of samples. The parametric RPBF approach offers a more computationally efficient alternative for large-scale problems.
  • Universality: Unlike many Approximate Dynamic Programming (ADP) methods restricted to specific problem types, these algorithms are theoretically guaranteed to work for any continuous state MDP with finite actions, provided the cost and transitions are sufficiently smooth.

Limitations and Future Work

While the results are promising, the current framework assumes a finite action space. Extending these universal approximation techniques to continuous action spaces remains a primary challenge for future research. Additionally, while the benchmarks are standard in the literature, further testing on higher-dimensional, real-world problems will be necessary to fully explore the scaling limits of the RKHS and RPBF approaches.

Summary updated

Abstract

We propose universal randomized function approximation-based empirical value iteration (EVI) algorithms for Markov decision processes. The `empirical' nature comes from each iteration being done empirically from samples available from simulations of the next state. This makes the Bellman operator a random operator. A parametric and a non-parametric method for function approximation using a parametric function space and the Reproducing Kernel Hilbert Space (RKHS) respectively are then combined with EVI. Both function spaces have the universal function approximation property. Basis functions are picked randomly. Convergence analysis is done using a random operator framework with techniques from the theory of stochastic dominance. Finite time sample complexity bounds are derived for both universal approximate dynamic programming algorithms. Numerical experiments support the versatility and effectiveness of this approach.
BibTeX
@misc{haskell2017empirical,
  author = {William B. Haskell and Rahul Jain and Hiteshi Sharma and P. L. Yu},
  title = {{An Empirical Dynamic Programming Algorithm for Continuous MDPs}},
  year = {2017},
  eprint = {1709.07506},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1709.07506},
}
Figure