A convergent reinforcement learning algorithm in the continuous case based on a finite difference method
Rémi Munos · HAL (Le Centre pour la Communication Scientifique Directe) · 1997
In this paper, we propose a convergent reinforcement learning algorithm for solving optimal control problems for which state space and time are continuous variables. The problem of computing a good approximation of the value function, which is essential because this provides 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 rectangular grid, may fail to converge. The main reason is that the discretization of the state space implies a loss 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 algorithm, called "Finite difference reinforcement learning" and prove its convergence to the value function of the continuous problem. / Dans cet article nous proposons un algorithme d'apprentissage par renforcement convergent, pour résoudre des problèmes de contrôle optimal pour lesquels l'espace d'état et le temps sont des variables continues. Nous montrons que les algorithmes habituellement utilisés, comme le Q-learning, utilisant les propriétés statistiques des successions d'états de l'espace discrétisé, ne convergent pas. La principale raison en est la perte du caractère Markovien des états successifs. Nous proposons ici d'utiliser une méthode aux différences finies, permettant de prendre en considération les propriétés géométriques de la dynamique d'état. Il en résulte un algorithme, appelé "Finite difference reinforcement learning", et la preuve de convergence vers la solution optimale est donnée.