A Competitive Strategy for Function Approximation in Q-Learning

TL;DR

This paper introduces a "Competitive Function Approximation" (CFA) strategy for Reinforcement Learning (RL) in continuous domains. Instead of a single, complex function approximator, CFA uses many simpler "competitor" approximators, each specialized for a region of the state-action space, and a "relevance" function to select the best one for any given input. This approach leads to faster learning and more stable convergence compared to traditional methods.

What Problem Does This Paper Address?

Reinforcement Learning (RL) agents need to learn how to make decisions in complex environments to maximize rewards. When the environment's state and action spaces are continuous (meaning they can take on an infinite number of values, like positions or velocities), RL agents must use function approximation (FA) to generalize their knowledge from experienced states to unseen ones. However, traditional FA methods in RL face significant challenges:

  • Non-stationarity: The target function (e.g., the value of taking an action in a state) changes as the agent learns and improves its policy.
  • Biased Sampling: Data collected by the agent often comes from trajectories dictated by its current policy, leading to some regions of the state-action space being sampled much more frequently than others. This can cause the FA to become inaccurate in sparsely sampled but potentially important regions.
  • Scalability: Creating a single function approximator complex enough to accurately represent the entire continuous domain can be computationally expensive and difficult to train.

These issues make it hard for RL agents to learn effectively and generalize well in real-world applications.

Methods

The core innovation is the Competitive Function Approximation (CFA) strategy. Here's how it works:

  • Competitors: Instead of one large function approximator, CFA employs a set of simpler "competitor" functions, denoted as $\Phi_i(x, \xi_i)$. Each competitor is designed to approximate the target function within a specific, potentially overlapping, region of the domain ($X_i$).
  • Relevance Function: For each competitor, a "relevance function," $\Gamma_i(x, v_i)$, is defined. This function quantifies how "good" or "relevant" a particular competitor is at a given input point $x$. The relevance is based on two key factors:
  • Accuracy: Estimated variance of the function's output in that region. Lower variance means higher confidence in the approximation.
  • Confidence: Density of samples in that region. More samples mean higher confidence.
  • Winner Selection: At any given input point $x$, the "winner" competitor is selected by finding the one with the highest relevance score: $w = \text{argmax}_i \Gamma_i(x, v_i)$.
  • Output: The final output of the CFA system for input $x$ is the output of the selected winner competitor: $y = \Phi_w(x, \xi_w)$.
  • Gaussian Mixture Models (GMMs): The paper proposes using GMMs to represent each competitor function $\Phi_i$. A GMM is defined in the joint input-output space, allowing it to simultaneously approximate the function's mean (the estimated value) and its variance (the accuracy/confidence measure) from a single probabilistic model. This is crucial for calculating the relevance function.
  • Competitor Management: The system dynamically manages the set of competitors. New competitors are generated when the approximation error is too high and existing competitors lack sufficient confidence. Competitors can also be eliminated if they become redundant with others.

Datasets

The paper does not introduce new datasets. Instead, it uses two standard benchmarks for evaluating RL algorithms:

  • Pendulum Swing-up and Stabilization: A classic control problem where the goal is to swing a pendulum to an upright position and maintain it there.
  • Cart-Pole Balancing: Another well-known control task where the agent must balance a pole on a cart by moving the cart.

Key Insights and Ideas

  • Divide and Conquer for FA: The core idea of using multiple specialized, simpler approximators that compete is a powerful way to handle complex, continuous domains, avoiding the need for a single, monolithic, and potentially brittle approximator.
  • Relevance as a Guiding Principle: The relevance function is critical. By quantifying both accuracy and confidence, it allows the system to intelligently select the best local expert, effectively addressing the biased sampling problem.
  • GMMs as Unified Models: Using GMMs in the joint input-output space elegantly provides all the necessary information (mean, variance, density) for both function approximation and relevance calculation from a single model per competitor.
  • Dynamic Competitor Generation: The ability to dynamically create new competitors as needed makes the approach non-parametric and adaptable to arbitrary functions, rather than being limited by a fixed number of approximators.
  • Improved Generalization and Stability: The localized nature of updates and the intelligent selection of competitors lead to more stable learning and better generalization, especially in higher-dimensional spaces.

Key Results

The paper demonstrates the effectiveness of CFA through experiments on the pendulum and cart-pole benchmarks.

  • Faster Convergence: CFA achieved convergence significantly faster than a standard GMM approach. For the pendulum task, CFA converged in about 23 episodes, compared to 45 episodes for a GMM with 10 Gaussians and worse performance for a GMM with 100 Gaussians.
  • More Stable Convergence: The learning curves for CFA were generally smoother and more stable.
  • Superior Performance in Higher Dimensions: In the cart-pole balancing task (a 5-dimensional state-action space), CFA showed a much larger performance advantage over both GMM and Variable Resolution methods, highlighting its better generalization capabilities.
  • Computational Cost: While CFA has a higher computational cost than a single GMM, the increase was less than an order of magnitude in their experiments.

Limitations and Future Work

  • Computational Cost: The paper acknowledges that CFA has a higher computational cost than a single global GMM. While the increase was manageable in their experiments, it could become a factor in extremely complex or real-time critical applications.
  • Parameter Tuning: The CFA system has user-defined thresholds (e.g., $n_g$ for minimum samples, $e_g$ for maximum error) that influence competitor generation. Finding optimal values for these parameters might require tuning.
  • Future Work: The authors suggest that it's possible to make the approach non-parametric not only by varying the number of competitors but also by varying the number of Gaussians within each competitor. This could further enhance adaptability. They also mention that the GMM instantiation is just one possibility, and other function approximators could be used as competitors.

Summary updated

BibTeX
@inproceedings{2011competitive,
  title = {{A Competitive Strategy for Function Approximation in Q-Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
}
Figure