3
$\begingroup$

In reinforcement learning, temporal difference seem to update the value function in each new iteration of experience absorbed from the environment.

What would be the conditions for temporal-difference learning to converge in the end? How is it guaranteed to converge?

Any intuitive understanding of those conditions that lead to the convergence?

$\endgroup$
2
$\begingroup$

There are different TD algorithms, e.g. Q-learning and SARSA, whose convergence properties have been studied separately (in many cases).

In some convergence proofs, e.g. in the paper Convergence of Q-learning: A Simple Proof (by Francisco S. Melo), the required conditions for Q-learning to converge (in probability) are the Robbins-Monro conditions

  1. $\sum_{t} \alpha_t(s, a) = \infty$
  2. $\sum_{t} \alpha_t^2(s, a) < \infty,$

where $\alpha_t(s, a)$ is the learning rate at time step $t$ (that can depend on the state $s$ and action $a$), and that each state is visited infinitely often.

(The Robbins-Monro conditions (1 and 2) are due to Herbert Robbins and Sutton Monro, who started the field of stochastic approximation in the 1950s, with the paper A Stochastic Approximation Method. The fields of RL and stochastic approximation are related. See this answer for more details.)

However, note again that the specific required conditions for TD methods to converge may vary depending on the proof and the specific TD algorithm. For example, the Robbins-Monro conditions are not assumed in Learning to Predict by the Methods of Temporal Differences by Richard S. Sutton (because this is not a proof of convergence in probability but in expectation).

Moreover, note that the proofs mentioned above are only applicable to the tabular versions of Q-learning. If you use function approximation, Q-learning (and other TD algorithms) may not converge. Nevertheless, there are cases when Q-learning combined with function approximation converges. See An Analysis of Reinforcement Learning with Function Approximation by Francisco S. Melo et al. and SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation by Bo Dai et al.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Hi, thanks for the reply! Is there any requirement on the environment? What if the environment is totally random, and for each state, action, there is not even a fixed value in essence? $\endgroup$ – MJeremy May 26 at 2:55
  • $\begingroup$ @MJeremy I don't know what you mean exactly by "totally random". There are some restrictions on the environment in certain proofs. For example, in the paper Convergence of Q-learning: A Simple Proof, F. Melo e.g. assumes that the reward function is deterministic. So, the assumptions probably vary from one proof to the other. It's probably a better idea that you read the specific papers that provide the proofs, if you want to know more details. $\endgroup$ – nbro Jun 2 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.