Research map / Reinforcement learning / MDPs and planning
Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits
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.
Develops model-free online RL algorithms that learn from outcome-only (trajectory-level) rewards with general function approximation, with sample complexity scaling with coverability, plus a simpler deterministic-MDP variant, preference-based extension, and an exponential separation lower bound versus per-step feedback.
Problem
Online exploration in RL when rewards are observed only at trajectory endpoints (outcome-based feedback), under general function approximation; when is it statistically tractable and how does it compare to per-step rewards.
Approach
Jointly optimize value functions and proxy outcome-reward models via an optimistic max-min objective with a Bellman loss and a reward-model loss, avoiding separate reward fitting; for deterministic MDPs, the value difference itself serves as the outcome reward model, yielding a simple Bellman-residual-minimization optimism algorithm.
Key results
- Model-free algorithm with outcome rewards achieves O~(C_cov H^3 / eps^2) sample complexity under realizability and completeness, matching GOLF up to O~(H).
- Deterministic MDP variant (BRM with optimism) needs only realizability and achieves a bound scaling with C'_cov H^4 / eps^2 for episodes; preference-based extension retains O~(C_cov H^2/eps^2) episodes scaling.
- Lower bound: for H=2 known-transition MDPs with d-dimensional generalized linear rewards, outcome-only learning requires e^{Omega(d)} episodes while process-reward learning needs O~(d^2/eps^2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use joint optimization of value functions and reward models instead of fitting a reward model separately | Online RL with outcome reward · MDPs with bounded coverability | sample complexity: \widetilde{O}({C_{\rm cov} H^3}/{\varepsilon^2}) | Helped |
| fit the reward model separately before optimizing the value function | Outcome-Based Exploration with Optimism · Worst-case outcome-based online RL | sample complexity | Hurt |
| replace the general algorithm with Bellman residual minimization in deterministic MDPs | Outcome-Based Exploration with Optimism · Deterministic MDPs | computational efficiency | Helped |
| use preference feedback rather than outcome reward feedback | Outcome-Based Exploration with Optimism · Preference-based RL under the BTR model | sample complexity: T\geq \tbO{\frac{\ccov H^2}{\varepsilon^2}\cdot \log(\NT{TH^2}/\delta)} | No clear effect |
| use outcome reward feedback instead of process reward feedback | Online RL with generalized linear reward models · Two-layer MDPs with known transitions and horizon $H=2$ | episodes: \tbO{d^2/\varepsilon^2} versus \Omega(e^{c_1d}) | Hurt |
Surprising findings
- Decoupling reward model fitting from value optimism can make sample complexity infinite in the worst case due to reward model mismatch.
- Outcome-based feedback can be exponentially harder than per-step feedback even when transitions are known and horizon is 2.
Limitations
- Main algorithm requires max-min optimization over a comparator class G, which is computationally expensive.
- Results depend on Bellman completeness and coverability assumptions; general-case bound carries an extra H factor relative to GOLF.
- Preference extension assumes the Bradley-Terry-Luce model.
Experimental setup
Metrics: sample complexity bound suboptimality gap
Baselines: GOLF trajectory eluder dimension methods per-step reward algorithms with eluder dimension
Builds on: GOLF coverability Bradley-Terry-Luce model
Closest papers by meaning
- A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning (ICLR 2023 · similarity 0.89)
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.88)
- Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning (ICLR 2024 · similarity 0.88)
- Provable Offline Preference-Based Reinforcement Learning (ICLR 2024 · similarity 0.88)
- The Power of Resets in Online Reinforcement Learning (NeurIPS 2024 · similarity 0.88)
- Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds (ICLR 2025 · similarity 0.88)
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.