Q-learning with linear function approximation gets a convergence condition: heavier discounting lets a learning policy's information extend only to nearer greedy policies
Synopsis
For Markov decision problems with infinite state spaces, where the Q-function cannot be stored entry by entry, Q-learning with linear function approximation previously lacked a convergence guarantee. The analysis gives a sufficient condition: the chain induced by the learning policy is uniformly ergodic, features are bounded and linearly independent, and the second moments of greedy-action features are dominated by those of learning-policy actions with a margin set by the discount factor; the parameter estimate then converges with probability 1 to a projected fixed point. As the discount approaches 1, the learning policy's information can be safely generalized only to nearer greedy policies.
Interpretation
Q-learning with linear function approximation converges with probability 1 under a fixed learning policy, and its limit satisfies a Bellman-like recursion with an orthogonal projection. Value-based reinforcement learning combined with function approximation generally behaves poorly, and convergence of Q-learning with approximation had been a long-standing open question; existing convergence analysis covered TD-learning, not Q-learning in stochastic control. The convergence claim rests on an explicit condition: for each discount factor, the second moments of greedy-action features must be dominated by those of actions chosen by the learning policy with a margin, while the step-size sequence meets the usual stochastic-approximation requirements.
The algorithm uses the temporal difference as its error and updates the parameter vector along the gradient of the features, representing the Q-function with a finite parameter vector in an infinite state space. Original Q-learning requires each state-action Q-value to be stored explicitly as a matrix, which is infeasible when states or actions are infinite, so a compact representation such as linear function approximation is needed. Convergence is established through an ODE argument: the algorithm's trajectories are shown to closely follow an associated ODE that contracts under the stated conditions and has a unique globally asymptotically stable equilibrium.
On-policy SARSA with linear function approximation also converges with probability 1 when the exploration policy varies smoothly with the parameters. The Q-learning result requires the learning policy to stay close enough to greedy policies, which is seldom met in practice, motivating analysis of an on-policy algorithm whose policy itself depends on the estimate. The result requires the learning policy to be Lipschitz continuous in the parameters, the induced chain to be uniformly ergodic, and the Lipschitz constant to be sufficiently small; it agrees with an existing SARSA convergence result but treats a continuing task rather than an episodic one.
Perspective
The results concern Markov decision problems with compact state spaces, finite action sets, and Q-functions in the linear span of fixed basis functions, requiring the chain induced by a fixed learning policy to be uniformly ergodic and the features bounded and linearly independent. The SARSA part further requires the learning policy to be Lipschitz continuous in the parameters with a sufficiently small constant, and the analysis is set in a continuing task.
All conditions are only sufficient, and convergence may still occur when some fail. The Q-learning condition is explicitly described as quite restrictive: if features have the same norm for all actions, it can hold only when the discount factor is 0, and it will seldom be met in practice. The SARSA guarantee relies on the exploration policy staying smooth, while decaying exploration to zero makes the smoothness condition hard to meet and removes the policy lower bound used in the analysis. Error bounds are not derived here; the authors only expect existing TD error bounds to carry over with little change.
