Research map / Reinforcement learning / RL from feedback
A Theoretical Framework for Partially-Observed Reward States in RLHF
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.
Models RLHF as partially-observed reward-state MDPs (PORRL/PORMDP) with cardinal and dueling feedback, gives model-based (POR-UCRL, POR-UCBVI) and model-free (GOLF with a history-aware Bellman-eluder dimension) regret guarantees, and a reduction from dueling to cardinal regret.
Problem
RLHF models ignore partially observed, evolving human internal states and intermediate (snippet-level) feedback, and naive history-summarization yields exponential dependence on horizon H.
Approach
Model reward as a function of latent deterministic internal reward-states that evolve via a generator, with Markovian observed transitions; exploit this with optimistic model-based methods and a history-aware Bellman-eluder dimension for GOLF, and give a whitebox reduction from dueling to optimistic cardinal regret.
Key results
- POR-UCRL achieves regret Õ((pS√(HA) + Σ√(d_E,h d_C,h))√T), avoiding the (SA)^Ω(H) dependence of naive history-summarization.
- GOLF with the α-HABE dimension achieves regret O(pH√(d_HABE d_C T)), which on the combination lock can be exponentially smaller than the Bellman-eluder dimension A^H.
- Dueling regret is achieved via a reduction to optimistic cardinal algorithms, with corollary regret matching POR-UCRL's bound; the naive reduction is shown to incur linear dueling regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use POR-UCRL or POR-UCBVI instead of naive history-summarization | Cardinal PORRL · Cardinal PORRL | regret | Helped |
| Use POR-UCRL instead of naive history-summarization | Cardinal PORRL · Cardinal PORRL | sample complexity | Helped |
| Use a history-aware Bellman-eluder dimension to analyze GOLF | GOLF with history-summarization · Combination lock, dense intermediate feedback | Bellman-eluder dimension: A vs at least $A^H-2$ | Helped |
| Use dense rather than sparse intermediate feedback | GOLF with history-summarization · Combination lock | regret: polynomial guarantees vs \Omega(\sqrt{A^H T}) | Helped |
| Reduce dueling PORRL using confidence-set optimism while restricting both played policies to possible optimizers | Dueling PORRL · Dueling PORRL | dueling regret | Helped |
| Apply a cardinal PORRL algorithm naively to paired policies to maximize dueling feedback | Dueling PORRL · Dueling PORRL | dueling regret: \Theta(T) | Hurt |
| Restrict the policy class to possibly time-dependent Markovian policies | PORRL · PORMDP with partially observed reward-states | regret: \frac{T}{4} | Hurt |
| Use a shared Q-function or critic network across timesteps rather than a different network for each timestep | Model-free methods for recursive internal states · PORRL with recurrent feedback structure | statistical efficiency | Helped |
Surprising findings
- Any Markovian (possibly time-dependent) policy is at least 1/4-suboptimal in a constructed PORMDP, so traditional RL methods incur linear regret.
- The naive blackbox reduction from dueling to cardinal feedback always yields linear dueling regret.
Limitations
- Results are theoretical, with tabular transitions in main text and no experiments.
- Improvement for GOLF requires dense intermediate feedback; sparse feedback yields Omega(sqrt(A^H T)) regret for any algorithm.
Experimental setup
Metrics: cardinal regret dueling regret sample complexity
Baselines: naive history-summarization P-OMLE linear RLHF models
Builds on: UCRL UCBVI GOLF Bellman-eluder dimension POMDP lower bounds
Closest papers by meaning
- Uni-RLHF: Universal Platform and Benchmark Suite for Reinforcement Learning with Diverse Human Feedback (ICLR 2024 · similarity 0.92)
- Greedy Sampling Is Provably Efficient For RLHF (NeurIPS 2025 · similarity 0.91)
- Provably Efficient Online RLHF with One-Pass Reward Modeling (NeurIPS 2025 · similarity 0.91)
- Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference (ICLR 2025 · similarity 0.91)
- Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferences (ICML 2024 · similarity 0.91)
- Personalizing Reinforcement Learning from Human Feedback with Variational Preference Learning (NeurIPS 2024 · similarity 0.90)
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.