EasyDeepLearn

When does tabular Q-learning provably converge?

hard

Answer

  • (1) All (s, a) visited infinitely often (adequate exploration), (2) Learning rate α satisfies Robbins-Monro: Σα = ∞, Σα2{\Sigma}{\alpha}^{2} < ∞, (3) Bounded rewards.
  • Under these, QkQ_{k} → Q* almost surely.
  • Real deep-RL breaks (1) severely (state space huge) and mostly ignores (2).
  • Classical theory guides intuition but doesn't guarantee anything in modern deep RL — that's why empirical care matters.
Check yourself — multiple choice
  • Random
  • Requires: (s, a) visited infinitely often + Robbins-Monro rates (Σα  =  ∞,  Σα2  <  ∞)  +  bounded({\Sigma}{\alpha}\; = \; \infty , \;{\Sigma}{\alpha}^{2}\; < \; \infty )\; + \;\mathrm{bounded} rewards; then QkQ_{k} → Q* a.s.; deep RL breaks these — empirical care
  • Never converges
  • Not proven

Tabular Q-learning convergence: infinite (s,a) visits + Robbins-Monro rates.

#theory

Practise Reinforcement Learning

214 interview questions in this topic.

Read the lessonFlashcardsTake the quiz

Related questions