Approximate Q-learning and SARSA(0) under the ε-greedy Policy: a Differential Inclusion Analysis

Aditya Gopalan, Gugan Thoppe

Abstract

Q-learning and SARSA with $\epsilon$-greedy exploration are leading reinforcement learning methods. Their tabular forms converge to the optimal Q-function under reasonable conditions. However, with function approximation, these methods exhibit strange behaviors such as policy oscillation, chattering, and convergence to different attractors (possibly even the worst policy) on different runs, apart from the usual instability. A theory to explain these phenomena has been a long-standing open problem, even for basic linear function approximation (Sutton, 1999). Our work uses differential inclusion to provide the first framework for resolving this problem. We also provide numerical examples to illustrate our framework's prowess in explaining these algorithms' behaviors.

Introduction

In Reinforcement Learning (RL), tabular Q-learning is the gold standard for convergence, guaranteed to find the optimal strategy given sufficient exploration. However, modern RL relies on Deep Q-Networks (DQN), which combine Q-learning with neural networks, $\epsilon$-greedy exploration, experience replay, and target networks. Despite DQN's success in complex domains like Atari games, it often exhibits "pathological" behaviors such as policy oscillation or convergence to sub-optimal solutions.

This paper demonstrates that DQN frequently fails to satisfy the most basic requirement of RL: improving upon an initial policy. By applying Differential Inclusion (DI) theory, the authors provide a rigorous theoretical framework to explain why DQN with linear function approximation can be "trapped" by sub-optimal fixed points, sometimes even converging to the worst possible policy.

Methodology

The authors bridge the gap between empirical observation and theory using two main approaches:

Numerical Experiments on Random MDPs

Instead of testing on a few hand-picked environments, the researchers ran DQN on a population of 100 randomly generated Markov Decision Processes (MDPs). Each MDP consisted of 10 states and 10 actions, with rewards and transitions sampled uniformly from $[0, 1]$. This setup allowed for a statistical view of how often the algorithm actually improves the policy.

Linear DQN Analysis via Differential Inclusions

To make the mathematics tractable, the study analyzed "Linear DQN"—a version using linear function approximation while retaining key components like replay buffers and target networks. The core of the analysis uses:

  • Differential Inclusions (DIs): Unlike standard Ordinary Differential Equations (ODEs) that define a single "velocity" for a system's state, DIs allow for a set of possible velocities. This is crucial for handling the "mode switches" that occur at boundaries where one greedy policy becomes better than another.
  • Filippov Convexification: This technique was used to "stitch together" the discontinuous dynamics at policy boundaries, creating a continuous-time model of parameter evolution.

Key Results and Insights

The most significant finding is that DQN is not a monotonic improver. In over 50% of runs on random MDPs, the final policy was worse than the initial random guess.

Performance comparison of initial vs final policies across 100 random MDPs. Points above the red dashed line represent cases where the algorithm converged to a policy worse than the initial random one.

The "Worst Policy" Attractor and Chattering

The authors prove that the limit points of DQN are fixed points of "projected Bellman operators." These fixed points are determined by the geometry of the function approximation and the exploration policy, often having no relation to the optimal policy. In some configurations, sub-optimal fixed points act as "global attractors," leading the algorithm to converge to the worst possible solution.

Furthermore, DI theory explains policy oscillation as a "sliding mode" where the algorithm gets stuck on the boundary between policies, bouncing back and forth—a phenomenon known as "chattering."

Visualizing pathologies: (a) Parameter trajectories in 2D space showing convergence to different sub-optimal attractors. (b) Greedy policy evolution over iterations, illustrating the 'chattering' phenomenon.

Formal Convergence

The paper provides a formal answer to a question posed by Rich Sutton in 1999 regarding the chattering behavior of approximate RL. Theorem 6 proves that the parameters of linear DQN converge to an invariant set of its limiting DI, and Corollary 10 shows that every limit point is a projected Bellman fixed point.

Discussion and Future Work

While techniques like experience replay and target networks help stabilize training by preventing parameters from exploding, they do not ensure that the stable point reached is a high-performing policy.

The theoretical proofs in this work are currently limited to linear function approximation. While numerical results show similar failures in deep neural networks, extending DI analysis to non-linear architectures remains a significant challenge. Future RL algorithm design should focus on ensuring that the attractors of the associated Differential Inclusions lie in regions corresponding to high-value policies, perhaps through new regularization techniques.

Summary updated

Abstract

Q-learning and SARSA with $\epsilon$-greedy exploration are leading reinforcement learning methods. Their tabular forms converge to the optimal Q-function under reasonable conditions. However, with function approximation, these methods exhibit strange behaviors such as policy oscillation, chattering, and convergence to different attractors (possibly even the worst policy) on different runs, apart from the usual instability. A theory to explain these phenomena has been a long-standing open problem, even for basic linear function approximation (Sutton, 1999). Our work uses differential inclusion to provide the first framework for resolving this problem. We also provide numerical examples to illustrate our framework's prowess in explaining these algorithms' behaviors.
BibTeX
@misc{gopalan2022approximate,
  author = {Aditya Gopalan and Gugan Thoppe},
  title = {{Approximate Q-learning and SARSA(0) under the ε-greedy Policy: a Differential Inclusion Analysis}},
  year = {2022},
  eprint = {2205.13617},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2205.13617},
}
Figure