Research map / Reinforcement learning / RL from feedback
Provable Reward-Agnostic Preference-Based Reinforcement Learning
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.
Proposes REGIME, a reward-agnostic PbRL framework that first collects exploratory trajectory pairs without human feedback (via experimental design), then queries preferences and runs MLE, reducing human feedback complexity; extends to linear MDPs and action-based comparisons.
Problem
Existing provable PbRL methods interleave environment interaction with human feedback and need many human preference queries; the practical decoupled pipeline (as in InstructGPT/PEBBLE) lacks sample-efficiency guarantees for choosing which trajectories to query.
Approach
Decouple exploration from human feedback: a reward-agnostic experimental design picks trajectory pairs that cover the feature space (elliptical potential over policy-pair feature differences) before any preferences are collected; then MLE on BTL preferences and offline planning. Action-based comparisons over advantage functions remove exponential dependence on the reward bound.
Key results
- Human feedback complexity of REGIME is O~(kappa^2 d^2/epsilon^2), independent of |S| and |A|, versus O~((|S|^2|A|d+kappa^2d^2)/epsilon^2) for the prior tabular online method, while trajectory complexity is matched.
- For linear MDPs, REGIME-lin gets polynomial trajectory complexity independent of |S| with log-linear policy classes.
- Action-based comparison reduces dependence from kappa (exponential in r_max) to kappa_adv (exponential in the advantage bound B_adv, typically much smaller than H).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Decouple reward-free trajectory collection from collecting human preference feedback | REGIME versus the prior online PbRL algorithm · Tabular MDPs | human feedback sample complexity: \Nh=\TO\bigg(\frac{|\mathcal{S}|^2|\mathcal{A}|d+\kappa^2d^2}{\epsilon^2}\bigg) -> \Nh=\TO\bigg(\frac{\kappa^2d^2}{\epsi | Helped |
| Decouple reward-free trajectory collection from collecting human preference feedback | REGIME versus the prior online PbRL algorithm · Tabular MDPs | trajectory-pair sample complexity: \Nt=\TO\bigg(\frac{|\mathcal{S}|^2|\mathcal{A}|d+\kappa^2d^2}{\epsilon^2}\bigg) | No clear effect |
| Use action-based comparisons instead of trajectory-based comparisons | REGIME-action · Action-based comparison | human feedback sample complexity dependence: \kadv instead of \kappa | Helped |
Limitations
- Analysis is theoretical; no empirical experiments reported.
- Sample complexity of the trajectory-based setting scales exponentially with r_max through kappa under the BTL model.
- Linear MDP extension depends on covering number of the policy class, and the reward-free oracle assumption is strong for general MDPs.
Experimental setup
Metrics: sample complexity (trajectory pairs and human feedback) suboptimality gap
Baselines: Pacchiano et al. (2021) online PbRL with tabular transitions Chen et al. (2022) Eluder-dimension PbRL
Builds on: reward-free RL LSVI-UCB Bradley-Terry-Luce model PEBBLE
Closest papers by meaning
- RA-PbRL: Provably Efficient Risk-Aware Preference-Based Reinforcement Learning (NeurIPS 2024 · similarity 0.92)
- Decoding Global Preferences: Temporal and Cooperative Dependency Modeling in Multi-Agent Preference-Based Reinforcement Learning (AAAI 2024 · similarity 0.92)
- Provable Offline Preference-Based Reinforcement Learning (ICLR 2024 · similarity 0.91)
- Listwise Reward Estimation for Offline Preference-based Reinforcement Learning (ICML 2024 · similarity 0.91)
- Query-Policy Misalignment in Preference-Based Reinforcement Learning (ICLR 2024 · similarity 0.91)
- Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options (NeurIPS 2025 · similarity 0.91)
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.