Research map / Reinforcement learning / Visual and representation RL
How Does Goal Relabeling Improve Sample Efficiency?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical analysis of why goal relabeling improves sample efficiency: a constructed MDP example shows exponential gains for goal-conditioned value functions, and the GOALIVE algorithm with a GOAL-BE dimension gives polynomial sample complexity.
Problem
Hindsight experience replay and goal relabeling work empirically, but there is no theory explaining why they improve sample efficiency or how to design provably efficient goal-conditioned model-free RL with relabeling.
Approach
Goal-conditioned value functions let the learner eliminate hypotheses using Bellman errors across many goals (relabeling) rather than only the target goal, yielding denser feedback; this is formalized in a new goal-conditioned Bellman-Eluder dimension and an OLIVE-style algorithm, GOALIVE.
Key results
- In the constructed example, goal-conditioned model-free algorithms (GOALIVE) need poly(H, 1/eps, log(1/delta)) trajectories while model-free algorithms without multiple goals need Omega(2^H).
- GOAL-BE dimension equals 1 in the example while the original BE dimension is at least 2^d - 1.
- GOALIVE's sample complexity is O~(H^3 d^2 / eps^2) in terms of the GOAL-BE dimension d, and GOAL-BE dimension is never larger than the original BE dimension.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use goal-conditioned value functions and relabel goals instead of using only the target goal | Model-free RL in the constructed MDP · Constructed goal-conditioned MDP | sample complexity: o(2H) trajectories; poly(H, 1/ϵ, log(1/δ)) trajectories | Helped |
| Use goal-conditioned value functions over multiple goals rather than value functions for g* only | Model-free value-function methods · Constructed example, target goal g* | Bellman-Eluder dimension: ≥ 2d − 1; 1 | Helped |
| Use Bellman errors across multiple goals for hypothesis elimination | GOALIVE · Constructed example | hypotheses eliminated | Helped |
| Use GOAL-BE dimension instead of the original BE dimension to characterize complexity | Goal-conditioned RL problems · Goal-conditioned RL | complexity dimension | Helped |
Surprising findings
- Relabeling as used in existing methods (achieved goals) is shown to be equivalent to the goal maximizing Bellman error in the constructed deterministic example.
Limitations
- Purely theoretical; no empirical experiments on standard goal-conditioned benchmarks.
- Requires realizability of Q* in the hypothesis class and a finite or covered goal space with log-covering cost.
- Algorithm favors sample efficiency over computation: evaluating max over the goal space is expensive, unlike practical achieved-goal relabeling.
Experimental setup
Metrics: sample complexity Bellman-Eluder dimension
Baselines: original Bellman-Eluder dimension (Jin et al. 2021) OLIVE (Jiang et al. 2017) model-free algorithms without multiple goals
Builds on: OLIVE Bellman-Eluder dimension GOLF Sun et al. 2019 model-free vs model-based sample complexity
Closest papers by meaning
- EfficientZero V2: Mastering Discrete and Continuous Control with Limited Data (ICML 2024 · similarity 0.85)
- Null Counterfactual Factor Interactions for Goal-Conditioned Reinforcement Learning (ICLR 2025 · similarity 0.84)
- Cluster-Based Sampling in Hindsight Experience Replay for Robotic Tasks (Student Abstract) (AAAI 2024 · similarity 0.84)
- When Does Non-Uniform Replay Matter in Reinforcement Learning? (NeurIPS 2026 · similarity 0.84)
- Demonstration-Regularized RL (ICLR 2024 · similarity 0.84)
- Goal-Conditioned On-Policy Reinforcement Learning (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.