Stable Fitted Reinforcement Learning

Geoffrey J. GordonNeurIPS 1995 · OpenReview

Abstract

Standard Q-learning is guaranteed to converge for small, discrete problems, but it often diverges or "blows up" when paired with function approximation for large-scale tasks. This paper proves that by using a specific class of function approximators—max-norm non-expansions (such as state aggregation)—reinforcement learning can remain stable and converge to a predictable solution.

Introduction

In Reinforcement Learning (RL), an agent learns to act optimally by estimating a "Q-function," which represents the expected long-term cost of taking a specific action in a specific state. For simple environments, this Q-function can be stored as a lookup table. However, real-world problems possess near-infinite state spaces, necessitating function approximation—using a parameterized model to represent the Q-function instead of an exhaustive table.

The "deadly triad" challenge arises when combining Bellman equations (the mathematical foundation of Q-learning) with function approximation. This combination often leads to divergence, where value estimates spiral toward infinity or oscillate endlessly. This paper identifies the mathematical conditions under which "fitted" Q-learning—where a model is fit to the data at each step—is guaranteed to remain stable.

Methodology: Fitted Q-Learning

The author introduces and analyzes Fitted Q-learning. The core mechanism involves taking the standard Bellman update and immediately following it with a function approximation step, denoted as $M_A$.

The paper focuses on two primary scenarios:

  1. Offline Discounted Problems: Here, the agent has access to a full model of the environment. The author proves that if the approximator $M_A$ is a max-norm non-expansion (meaning the approximation step never increases the maximum distance between any two value functions), the entire learning process becomes a "contraction mapping." This geometric property ensures the algorithm will always settle on a single, unique solution.
  2. Online Discounted Problems (Sarsa): In this scenario, the agent learns by actively navigating the environment. The author analyzes a generalization of TD(0) known as Sarsa.

The "gold standard" example of a safe, non-expanding approximator used in this work is state aggregation, where multiple similar states are grouped together and treated as a single state.

The Counterexample: Sarsa Oscillation

Because this is a theoretical paper, it relies on synthetic Markov Decision Processes (MDPs) rather than large-scale datasets to prove its points. A key contribution is a hand-crafted counterexample demonstrating that even with "safe" state aggregation, an online agent can fail to converge.

Sarsa Oscillation Counterexample

As illustrated in the counterexample, Sarsa can get stuck in an infinite loop of oscillation. This occurs because the frequency of updates to certain states changes as the agent's policy changes. This creates a destructive feedback loop: the agent updates its policy, which alters the state distribution it observes, which in turn changes the Q-function estimates, leading to further policy changes and permanent oscillation.

Key Insights and Results

  • Stability is Geometric: The stability of RL is not solely dependent on the learning rate; it relies heavily on the "shape" of the function approximator. A max-norm non-expansion effectively "tames" potentially unstable Bellman updates.
  • Fixed Exploration is Safer: The paper demonstrates that if the exploration policy remains fixed (rather than constantly optimizing it during learning), the online algorithm becomes significantly more stable and provably converges.
  • Convergence Proofs and Bounds: The paper provides formal proofs that fitted offline Q-learning and online Sarsa (with a fixed policy) are guaranteed to converge when using max-norm non-expanding approximators. Furthermore, for linear approximators, the author provides mathematical bounds on the final approximation error.
  • Contraction Factors: The author derives a specific contraction factor, $(1 - b(1 - \gamma))$, which quantifies exactly how fast the algorithm will converge based on the discount factor ($\gamma$) and the state visit weights ($b$). For cases where Sarsa does oscillate, the algorithm is proven to eventually remain within a bounded "region" around the optimal solution.

Limitations and Future Work

  • Restrictive Approximators: The requirement for approximators to be "max-norm non-expansions" is quite strict. Many popular modern techniques, such as deep neural networks, do not inherently satisfy this condition, shedding light on why Deep RL can suffer from severe instability.
  • On-Policy vs. Off-Policy Tension: The paper highlights a fundamental tension in online learning: attempting to learn the optimal policy while simultaneously using that same policy to collect data is the root cause of the observed oscillations.
  • Broader Models: The author notes that this specific work focuses on a narrow class of approximators, pointing to subsequent research for results on a broader range of models.

Summary updated

Abstract

We describe the reinforcement learning problem, motivate algo(cid:173) rithms which seek an approximation to the Q function, and present new convergence results for two such algorithms. 1 INTRODUCTION AND BACKGROUND Imagine an agent acting in some environment. At time t, the environment is in some state Xt chosen from a finite set of states. The agent perceives Xt, and is allowed to choose an action at from some finite set of actions. The environment then changes state, so that at time (t + 1) it is in a new state Xt+1 chosen from a probability distribution which depends only on Xt and at. Meanwhile, the agent experiences a real-valued cost Ct, chosen from a distribution which also depends only on Xt and at and which has finite mean and variance. Such an environment is called a Markov decision process, or MDP. The reinforce(cid:173) ment learning problem is to control an MDP to minimize the expected discounted cost Lt ,tCt for some discount factor, E [0,1]. Define the function Q so that Q(x, a) is the cost for being in state x at time 0, choosing action a, and behaving optimally from then on. If we can discover Q, we have solved the problem: at each step, we may simply choose at to minimize Q(xt, at). For more information about MDPs, see (Watkins, 1989, Bertsekas and Tsitsiklis, 1989). We may distinguish two classes of problems, online and offline. In the offline prob(cid:173) lem, we have a full model of the MDP: given a state and an action, we can describe the distributions of the cost and the next state. We will be concerned with the online problem, in which our knowledge of the MDP is limited to what we can dis(cid:173) cover by interacting with it. To solve an online problem, we may approximate the transition and cost functions, then proceed as for an offline problem (the indirect approach); or we may try to learn the Q function without the intermediate step (the direct approach). Either approach may work better for any given problem: the Stable Fitted Reinforcement Learning
BibTeX
@inproceedings{gordon1995stable,
  author = {Geoffrey J. Gordon},
  title = {{Stable Fitted Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1995},
  url = {https://openreview.net/forum?id=S1ZQMdW_ZS},
}
Figure