C-Learning: Learning to Achieve Goals via Recursive Classification

Benjamin Eysenbach, Ruslan Salakhutdinov, Sergey Levine

Introduction

In goal-conditioned reinforcement learning (RL), an agent is tasked with reaching a specific state or "goal." Traditionally, this requires a manually designed reward function, often a sparse indicator (1 if the goal is reached, 0 otherwise) or a hand-crafted distance metric like Euclidean distance. However, in continuous environments, the probability of exactly hitting a specific coordinate is zero. This makes the standard Q-function mathematically problematic.

While techniques like Hindsight Experience Replay (HER) mitigate this by relabeling past experiences as goals, they often lack a clear theoretical target—leaving ambiguity around what the resulting Q-function actually represents. C-Learning (Classification-learning) bridges this gap by reframing goal-conditioned RL as a density estimation problem. Instead of learning a traditional Q-function, it trains a classifier to distinguish between states that will be visited in the future and states sampled at random, providing a principled foundation for common RL heuristics.

The C-Learning Approach

The core innovation of C-Learning is replacing the value function estimator with a classifier, $C(s, a, s_+)$. This classifier predicts whether a future state $s_+$ was sampled from the agent's actual future trajectory (positive examples) or from a random marginal distribution of states (negative examples).

Key Technical Mechanisms

  • Recursive Classification: The authors derive a "Bellman Equation for Classifiers." Much like how Q-learning updates values based on the next state's value, C-Learning updates the classifier based on its own predictions for the next state.
  • Bayes' Rule Transformation: By applying Bayes' rule to the classifier's output, the algorithm can recover the actual probability density of reaching a future state.
  • Off-Policy Training: C-Learning includes a bootstrapping variant that allows the agent to predict where a new policy would go using data collected by an old policy, utilizing importance weighting to correct for the distribution shift.
  • Goal-Conditioned Control: To turn this density estimation into a control algorithm, the agent simply learns a policy that maximizes the classifier's probability that the commanded goal is a "future state." Because it relies on state distributions, it completely bypasses the need for a reward function or distance metric.

Key Insights: Explaining RL Heuristics

A major contribution of C-Learning is its ability to theoretically explain why certain RL heuristics work.

Q-Learning as Density Estimation: The paper proves that goal-conditioned Q-learning is essentially a "broken" version of density estimation. Specifically, Q-learning tends to systematically underestimate the true density of future states.

The "Magic" Hyperparameter Explained: In HER, the ratio of "future" goals to "random" goals is a notoriously sensitive hyperparameter. C-Learning provides a theoretical derivation for the optimal ratio: $\lambda = \frac{1+\gamma}{2}$.

Error rates across different fractions of negative examples. Q-learning error is minimized exactly at the theoretically predicted ratio, while C-learning remains stable.

Experiments confirm that Q-learning performs best exactly at this predicted value. Furthermore, unlike prior methods, C-Learning does not require tuning this goal-sampling ratio, as the "correct" ratio is inherently built into the algorithm's derivation.

Empirical Results

The authors evaluated C-Learning across several continuous control benchmarks, including a diagnostic Continuous Gridworld, MuJoCo Locomotion tasks (Walker2d, Hopper, Ant), and a challenging suite of 8 Robotic Manipulation tasks (e.g., Sawyer Reach, Sawyer Push, Sawyer Drawer).

Predictive Accuracy: C-Learning estimates the future state distribution much more accurately than Q-learning or standard 1-step dynamics models. One-step models typically suffer from compounding errors over long horizons, whereas C-Learning maintains low prediction error even at high discount factors.

Prediction error comparison. 1-step models suffer from compounding errors at high discount factors, whereas C-learning maintains accurate long-horizon predictions.

Control Performance: On complex manipulation tasks, C-Learning significantly outperformed baselines like TD3 + HER. It successfully discovered complex behaviors, such as regrasping objects, which usually require carefully shaped, manual reward functions.

Limitations and Future Work

While highly effective, C-Learning has a few limitations:

  • Importance Weight Variance: The off-policy version relies on importance weights, which can become very large and lead to training instability. The authors mitigated this using weight clipping and a "mixing" strategy (combining Monte Carlo and Temporal Difference samples).
  • Marginal Distribution Dependency: The classifier requires a "marginal distribution" of states to serve as negative examples. While a uniform sample from the replay buffer worked well in these benchmarks, the choice of this distribution could impact performance in more open-ended or exploratory environments.
  • Theoretical vs. Practical Gap: Convergence is proven for the tabular case, but the use of deep neural networks (function approximation) means those strict guarantees do not perfectly carry over to the experimental results, despite strong empirical performance.

Summary updated

Abstract

We study the problem of predicting and controlling the future state distribution of an autonomous agent. This problem, which can be viewed as a reframing of goal-conditioned reinforcement learning (RL), is centered around learning a conditional probability density function over future states. Instead of directly estimating this density function, we indirectly estimate this density function by training a classifier to predict whether an observation comes from the future. Via Bayes' rule, predictions from our classifier can be transformed into predictions over future states. Importantly, an off-policy variant of our algorithm allows us to predict the future state distribution of a new policy, without collecting new experience. This variant allows us to optimize functionals of a policy's future state distribution, such as the density of reaching a particular goal state. While conceptually similar to Q-learning, our work lays a principled foundation for goal-conditioned RL as density estimation, providing justification for goal-conditioned methods used in prior work. This foundation makes hypotheses about Q-learning, including the optimal goal-sampling ratio, which we confirm experimentally. Moreover, our proposed method is competitive with prior goal-conditioned RL methods.
BibTeX
@inproceedings{eysenbach2021c,
  author = {Benjamin Eysenbach and Ruslan Salakhutdinov and Sergey Levine},
  title = {{C-Learning: Learning to Achieve Goals via Recursive Classification}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
}
Figure