A Convergent Reinforcement Learning Algorithm in the Continuous Case Based on a Finite Difference Method

Rémi Munos

Abstract

In this paper, we propose a convergent Reinforcement Learning algorithm for solving optimal control problems for which the state space and the time are continuous variables. The problem of computing a good approximation of the value function is a difficult task in the continuous case. We show that classical algorithms, like Q-learning, used with a simple look-up table built on a regular grid, may fail to converge because the discretization of the state space implies a loss of the Markov property. We propose to approximate the value function with a convergent numerical scheme based on a Finite Difference approximation of the Hamilton-Jacobi-Bellman equation. We present a model-free reinforcement learning algorithm, called Finite Difference Reinforcement Learning (FDRL), and prove its convergence to the value function of the continuous problem.

The Discretization Dilemma

Reinforcement Learning (RL) has seen significant success in discrete environments; however, applying these methods to the "real world"—which is inherently continuous in both state and time—presents a fundamental challenge. A common approach is to discretize the continuous state space into a grid or look-up table.

Discretization of a continuous state space leading to non-Markovian behavior.

As illustrated in Figure 1, this discretization destroys the Markov property. In a continuous system, the future state depends on the exact current coordinates. When these coordinates are grouped into a single grid cell $X$, the exit point (e.g., $y_1$ or $y_2$) depends on the entry point ($x_1$ or $x_2$). Since a grid-based agent only perceives the state as "cell $X$", it loses the information necessary to predict the next state accurately. This non-Markovian nature causes standard algorithms like Q-learning to diverge or produce suboptimal results.

The Finite Difference Reinforcement Learning (FDRL) Framework

To address this, we introduce Finite Difference Reinforcement Learning (FDRL). Rather than relying on the discrete Bellman equation, FDRL is grounded in the Hamilton-Jacobi-Bellman (HJB) equation, the continuous-time counterpart used in optimal control theory.

Finite Difference scheme for approximating the HJB equation.

The core of FDRL is a Finite Difference (FD) scheme that discretizes the HJB equation. As shown in Figure 2, the algorithm updates the value of a state $\xi$ by considering the system's dynamics $f(\xi, u)$. Instead of simple averaging, FDRL uses weights ($\delta p$) derived from the FD scheme to distribute the value update among neighboring grid points. This ensures that the resulting discrete process satisfies the requirements of a finite Markov Decision Process (MDP) that accurately approximates the continuous system.

Key Insights and Theoretical Results

The primary contribution of this work is the bridge it builds between classical Optimal Control and modern Reinforcement Learning.

  • Dynamics-Based Averaging: Unlike Q-learning, which estimates values based on transition frequencies, FDRL uses the underlying physics (state dynamics) to determine how values propagate across the grid.
  • Convergence Proof: We provide a rigorous mathematical proof that FDRL converges to the unique viscosity solution of the HJB equation as the grid size approaches zero. This guarantees that the algorithm finds the true optimal value function for the continuous problem.
  • Model-Free HJB: FDRL demonstrates that one can solve complex continuous differential equations using a model-free, experience-based reinforcement learning approach.

Limitations and Future Directions

While FDRL provides a robust theoretical foundation for continuous RL, it faces the "curse of dimensionality." The number of grid cells required grows exponentially with the number of state variables, making simple look-up tables impractical for high-dimensional systems like complex robotics.

Future work will focus on extending the convergence proofs to handle stochastic systems and implementing adaptive multi-resolution grids to focus computational resources on critical areas of the state space.

Summary updated

Abstract

In this paper, we propose a convergent Reinforcement Learning algorithm for solving optimal control problems for which the state space and the time are continuous variables. The problem of computing a good approximation of the value function, which is essential because this provides the optimal control, is a difficult task in the continuous case. Indeed, as it has been pointed out by several authors, the use of parameterized functions such as neural networks for approximating the value function may produce very bad results and even diverge. In fact, we show that classical algorithms, like Q-learning, used with a simple look-up table built on a regular grid, may fail to converge. The main reason is that the discretization of the state space implies a lost of the Markov property even for deterministic continuous processes. We propose to approximate the value function with a convergent numerical scheme based on a Finite Difference approximation of the Hamilton-Jacobi-Bellman equation. Then we present a model-free reinforcement learning algorithrn, called Finite Difference Reinforcement Learning, and prove its convergence to the value function of the continuous problem.
BibTeX
@inproceedings{munos1997convergent,
  author = {Rémi Munos},
  title = {{A Convergent Reinforcement Learning Algorithm in the Continuous Case Based on a Finite Difference Method}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1997},
}
Figure