Convergence of Stochastic Iterative Dynamic Programming Algorithms

Tommi S. Jaakkola, Michael I. Jordan, Satinder P. SinghNeurIPS 1993 · OpenReview

Introduction

In the early 1990s, reinforcement learning (RL) was gaining significant traction, but its theoretical foundations remained fragmented. While researchers observed empirical success with algorithms like Q-learning (for control) and TD($\lambda$) (for prediction), proving their convergence was notoriously difficult.

The primary mathematical hurdle was a mismatch in analytical tools. Standard stochastic approximation theory (such as the Robbins-Monro algorithm) was designed for Euclidean norms, essentially minimizing mean squared error. Conversely, Dynamic Programming (DP) and RL rely on Bellman equations, which act as contraction mappings in the maximum norm (meaning they reduce the maximum error across all states). Before this paper, there was no general "off-the-shelf" theorem capable of handling stochastic updates under the maximum norm, forcing researchers to write complex, algorithm-specific proofs. This seminal paper bridges that gap, providing a unified theoretical framework that extends classical stochastic approximation to handle the maximum norm.

The "Master Theorem" Framework

To resolve this mismatch, the authors introduce a "master theorem" (Theorem 1) that extends Dvoretzky’s (1956) stochastic approximation formulation.

This framework defines a random iterative process:

$$\Delta_{n+1}(x) = (1-\alpha_n(x))\Delta_n(x) + \beta_n(x)F_n(x)$$

Here, $\Delta_n$ represents the error between the current estimate and the optimal value. The theorem introduces relaxed conditions, allowing for asynchronous updates—which is crucial for real-world RL agents that visit states sequentially rather than updating all states simultaneously. The core requirement for convergence under this theorem is that the expected value of the noise-perturbed update ($F_n$) must act as a contraction mapping under a weighted maximum norm.

Key Insights and Convergence Results

By establishing this master theorem, the authors demonstrate that Q-learning and TD($\lambda$) are not just heuristically related; they are specific instances of a broader class of convergent stochastic processes. Once the master theorem is established, proving the convergence of a new RL algorithm becomes a matter of checking a few statistical properties rather than building a proof from scratch.

  • Q-learning (Theorem 2): The paper proves that Q-learning converges to the optimal $Q^*$ values with probability 1. This holds provided the state and action spaces are finite, the variance of costs is bounded, and the learning rates ($\alpha_n$) satisfy standard stochastic approximation conditions (an infinite sum, but a finite sum of squares).
  • TD($\lambda$) (Theorem 3): The authors provide the first rigorous proof for the on-line version of TD($\lambda$). A major insight is that the "noise" introduced by updating on-line (after every step) rather than in batches (after a full sequence) vanishes in the limit. The theorem proves convergence to optimal predictions for any finite absorbing Markov chain, provided $\gamma\lambda < 1$.

Limitations and Future Directions

As a foundational theoretical work, the paper operates on abstract, finite Markov Decision Processes (MDPs) rather than empirical datasets. Consequently, the proofs strictly rely on the assumption of finite state and action spaces. They do not address convergence when these algorithms are combined with function approximation (such as neural networks)—a significantly harder problem where convergence is not always guaranteed.

Furthermore, the TD($\lambda$) proof assumes an absorbing Markov chain (one that eventually terminates), though the authors note the theorem could potentially be extended. Finally, they suggest that future work could extend Theorem 1 to cover iterative processes that do not satisfy the standard contraction property, which would broaden its applicability to even more complex algorithms.

Summary updated

Abstract

Increasing attention has recently been paid to algorithms based on dynamic programming (DP) due to the suitability of DP for learn(cid:173) ing problems involving control. In stochastic environments where the system being controlled is only incompletely known, however, a unifying theoretical account of these methods has been missing. In this paper we relate DP-based learning algorithms to the pow(cid:173) erful techniques of stochastic approximation via a new convergence theorem, enabling us to establish a class of convergent algorithms to which both TD(") and Q-Iearning belong.
BibTeX
@inproceedings{jaakkola1993convergence,
  author = {Tommi S. Jaakkola and Michael I. Jordan and Satinder P. Singh},
  title = {{Convergence of Stochastic Iterative Dynamic Programming Algorithms}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1993},
  url = {https://openreview.net/forum?id=rkbHrDb_WS},
}
Figure