On the Convergence of Stochastic Iterative Dynamic Programming Algorithms

By Tommi S. Jaakkola, Michael I. Jordan, Satinder Singh. 1994

Recent developments in the area of reinforcement learning have yielded a number of new algorithms for the prediction and control of Markovian environments. These algorithms, including the TD() algorithm of Sutton (1988) and the Q-learning algorithm of Watkins (1989), can be motivated heuristically as approximations to dynamic programming (DP). In this paper we provide a rigorous proof of convergence of these DP-based learning algorithms by relating them to the powerful techniques of stochastic approximation theory via a new convergence theorem. The theorem establishes a general class of convergent algorithms to which both TD() and Q-learning belong.

Subfields: Reinforcement Learning, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

RUDDER: Return Decomposition for Delayed Rewards (2018, methodology): “then perform TD updates with the Bellman error using the estimated r(s;a) [95]. Q-learning [127] is an off-policy TD algorithm which is proved to converge [128, 14]. The proofs were later generalized [53,120]. Q-learning uses E s0;a0[^q ˇ(s0;a0)] ˇmax a q^(S t+1;a) : (A27) The action-value function ”
Sample-Efficient Reinforcement Learning via Counterfactual-Based Data Augmentation (2020, background): “Moreover, it has been shown that Q-learning on the data generated from the MDP converges to the optimal value function, under the listed conditions [35, 36].”
Reinforcement learning in robotics: A survey (2013, background): “Modeling exploration models with probability distributions has surprising implications, e.g. stochastic policies have been shown to be the optimal stationary policies for selected problems (Jaakkola et al., 1993; Sutton et al., 1999) and can even break the curse of dimensionality (Rust, 1997).”
Efficient Communication in Multi-Agent Reinforcement Learning via Variance Based Control (2019, background): “erforming equation 2 iteratively, we have jjQk tot (o t;a ) Q tot (o t;a )jjNG8o ;a , as k!1, where Gsatisﬁes jj @Var(f enc(ct i )) @Qk tot (o t;a t) jjG;8i;k;t;o ;a . Proof. The proof is based on [21] and [22]. If we subtract Q tot (o t;a ) from equation 2 in the paper, and rearrange the equation, ”
Mean Field Multi-Agent Reinforcement Learning (2018, background): “See Theorem 1 in Jaakkola et al. (1994) and Corol-lary 5 Szepesvári & Littman (1999) for detailed derivation.”
Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition (1999, methodology): “Proof: The proof follows an argument similar to those introduced to prove the convergence of Q learning and SARSA(0) (Bertsekas & Tsitsiklis, 1996; Jaakkola et al., 1994).”
Reinforcement Learning with Replacing Eligibility Traces (2005, methodology): “First, we show that these methods converge underrepeated presentations of the training set to the same predictions as two well known Monte Carlomethods.”
Context-Aware Policy Reuse (2018, methodology): “The learning rule of QO can be seen as the iterative process of Theorem 1 in [32].”
MDPs: Learning in Varying Environments (2002, background): “It is easy to see that Equation 7 is a Robbins-Monro-like iterated averaging (Robbins and Monro, 1951, Jaakkola et al., 1994).”
Reinforcement Learning: An Introduction (1998, methodology): “In addition, Jaakkola, Jordan, and Singh (1994) proved convergence under online updating.”
Multiobjective Reinforcement Learning: A Comprehensive Overview (2015, background): “If in the limit the Q values of all admissible state-action pairs are updated infinitely often, and α decays in a way satisfying the usual stochastic approximation conditions, then the Q values will converge to the optimal value Q* with probability 1 [20].”