A Study of Reinforcement Learning in the Continuous Case by the Means of Viscosity Solutions

Rémi MunosMachine Learning 2000 · OpenReview

Abstract: This paper proposes a study of Reinforcement Learning (RL) for continuous state-space and time control problems, based on the theoretical framework of viscosity solutions (VSs). We use the method of dynamic programming (DP) which introduces the value function (VF), expectation of the best future cumulative reinforcement. In the continuous case, the value function satisfies a non-linear first (or second) order differential equation called the Hamilton-Jacobi-Bellman (HJB) equation. It is well known that there exists an infinity of generalized solutions (differentiable almost everywhere) to this equation, other than the VF. We show that gradient-descent methods may converge to one of these generalized solutions, thus failing to find the optimal control.

Introduction

While Reinforcement Learning (RL) has seen significant success in discrete environments modeled as Markov Decision Processes (MDPs), extending these methods to continuous state-space and continuous-time problems introduces substantial mathematical complexity. In such settings, the optimal value function—representing the expected total reward—is governed by the Hamilton-Jacobi-Bellman (HJB) equation, a non-linear partial differential equation. This paper, published in Machine Learning (2000), establishes a rigorous theoretical bridge between continuous-time optimal control and RL by leveraging the theory of viscosity solutions.

The Challenge of Continuous Control

Transitioning to continuous domains presents two primary hurdles for standard RL algorithms:

  1. Non-differentiability: Even in problems with smooth underlying dynamics, the optimal value function often lacks differentiability everywhere. Consequently, "classical" solutions to the HJB equation frequently do not exist.
  2. Infinite Generalized Solutions: If one searches for "generalized" solutions (functions differentiable almost everywhere), the HJB equation admits infinitely many. Standard gradient-descent methods, common in neural network training, risk minimizing the "Hamiltonian error" to zero while converging to a non-optimal solution.
Figure 3: Representation of a continuous state-space domain $O$ with trajectories $x(t)$ and boundary points, illustrating the environment for the HJB equation.

Viscosity Solutions: A Mathematical Bridge

To resolve the ambiguity of multiple generalized solutions, the author employs the framework of viscosity solutions (VS). This mathematical theory provides a way to define "weak" solutions to PDEs that ensure uniqueness. By identifying the optimal value function as the unique viscosity solution to the HJB equation, the paper establishes a definitive "ground truth" for RL algorithms.

A critical property of viscosity solutions is their stability. This ensures that if a sequence of approximate solutions satisfies specific criteria—namely monotonicity and consistency—they are guaranteed to converge to the unique viscosity solution as the discretization becomes increasingly fine.

Methods and Discretization

To bridge the gap between continuous theory and computable algorithms, the paper utilizes Finite Difference (FD) and Finite Element (FE) methods. These techniques discretize the continuous HJB equation into a structure resembling a discrete MDP.

Furthermore, the author introduces the "Weak Contraction" Property. Unlike standard Dynamic Programming, which relies on strong contractions where errors shrink predictably at every step, RL often operates with imperfect models and experience-based learning. The derived convergence theorem shows that even with this weaker property, RL algorithms can reliably find the optimal value function.

Numerical Validation: The "Car on the Hill"

The theoretical framework was tested using the "Car on the Hill" benchmark, a 2D state-space problem (position and velocity). This problem is particularly challenging because the value function is discontinuous; a marginal change in velocity can determine whether the car reaches the goal or falls back.

  • Model-based RL (RTDP): Demonstrated smooth convergence to the optimal value function.
  • Model-free RL (FERL): While the error did not reach absolute zero due to discretization limits, it remained bounded within a range defined by the discretization step $\delta$, confirming the practical validity of the weak contraction property.

Conclusion and Future Directions

The paper concludes that RL algorithms, whether model-based or model-free, can be proven to converge to the optimal value function in continuous domains if they align with convergent discretization schemes. However, challenges remain, notably the curse of dimensionality inherent in grid-based methods. Future work is suggested in the area of adaptive discretization, where grids become finer only in regions where the value function exhibits high complexity, potentially mitigating computational costs in higher-dimensional spaces.

Summary updated

Abstract

This paper proposes a study of Reinforcement Learning (RL) for continuous state-space and time control problems, based on the theoretical framework of viscosity solutions (VSs). We use the method of dynamic programming (DP) which introduces the value function (VF), expectation of the best future cumulative reinforcement. In the continuous case, the value function satisfies a non-linear first (or second) order (depending on the deterministic or stochastic aspect of the process) differential equation called the Hamilton-Jacobi-Bellman (HJB) equation. It is well known that there exists an infinity of generalized solutions (differentiable almost everywhere) to this equation, other than the VF. We show that gradient-descent methods may converge to one of these generalized solutions, thus failing to find the optimal control.
BibTeX
@article{munos2000study,
  author = {Rémi Munos},
  title = {{A Study of Reinforcement Learning in the Continuous Case by the Means of Viscosity Solutions}},
  journal = {Machine Learning},
  year = {2000},
  url = {https://openreview.net/forum?id=bnZd0ppzUU},
}
Figure