In reinforcement learning from limited feedback (RLLF), only a small fraction of an offline dataset can be labeled with rewards, and the central question is which samples should be labeled to learn a high-performing policy from the resulting partially labeled dataset. Prior work formalized this as a reward-selection problem by focusing on the selection stage while treating downstream policy learning as a black box, in a regime where queried rewards are not retained for reward-model training. We instead study the retained-label setting, where queried rewards can be stored and used to fit a reward model before policy learning. We bound the suboptimality of the learned policy in terms of two sources of error: one arising from offline RL on a fixed, offline dataset, and the other from uncertainty in the reward model. Since reward selection cannot change the offline dataset, the limited labeling budget must be used to strategically reduce reward uncertainty. Motivated by RLLF's observation that useful rewards tend to keep the agent on high-return trajectories, we introduce Successor-Guided Uncertainty REduction (SURE), a novel method that uses successor features to select rewards that are both uncertain and associated with states from which high-valued states are reachable. We formally derive SURE from a bound-induced design objective and characterize its exact one-step marginal gain. Empirically, SURE reaches near full-feedback performance with few reward labels across a variety of domains and offline-RL backbones, yielding an effective method for feedback-efficient reinforcement learning.
Figures & tables
Figure 1: Illustrative retained-label reward-selection example in a navigation task. The agent must reach the goal while avoiding a central obstacle. With the initial reward labels, the policy learned from the current reward model takes a long detour, while a more direct path remains possible. Uncertainty-only selection chooses a state where the reward model is uncertain, but the selected state may be far from trajectories that lead to high return. Reachability-only selection chooses a state that can lead toward regions assigned high value by the current reward model, but this estimate can be misleading when the reward model is inaccurate. SURE combines both signals, selecting for labeling a reward that is uncertain under the current reward model and lies on a reachable path toward currently high-value states, yielding a better policy with fewer reward labels.
Environment
SURE
Exact Gain
Uniform
∣S∣=32
8 / 12 / 12
8 / 12 / 12
20 / 20 / 36
∣S∣=48
8 / 12 / 12
8 / 12 / 12
12 / 68 / 132
Table 1: Number of reward labels required to reach 80% / 90% / 95% of the matched full-feedback return in exact linear MDPs, averaged over 30 paired seeds. Full feedback corresponds to labeling all 4,096 transitions in the offline pool.
Figure 2: Performance comparison across domains under limited feedback. Return is shown as a function of the absolute feedback budget B . We compare SURE with Uniform , Reach , Uncertainty , IDRL , and RLLF-Guided . Solid lines show the mean over 50 trials and shaded regions show the standard error. The dashed line indicates the full-feedback reference .
Domain
Fraction
Percentage feedback required
SURE
RLLF -Guided
Uniform
IDRL
Reach
Uncertainty
maze2d-medium
95%
0.20%
1.74%
2.25%
0.32%
1.46%
1.96%
90%
0.12%
1.45%
1.79%
0.26%
0.50%
1.47%
80%
0.05%
0.94%
1.22%
0.11%
0.06%
0.50%
maze2d-large
95%
0.15%
3.28%
2.88%
0.64%
2.51%
2.79%
90%
0.09%
2.92%
2.70%
0.62%
2.10%
2.52%
Table 2: Percentage feedback needed to reach different fractions of the full-feedback reference . The “Fraction” column specifies the target return as a fraction of the full-feedback reference ; “Percentage feedback required” reports the fraction of distinct states that must be labeled to reach that target. Bold indicates the smallest percentage feedback in each row.
Figure 3: Ablation of the SURE score on representative maze rounds. Each row shows a different stage of selection. From left to right: acquired feedback locations, exact one-step gain Δ(s,a;Y[b],ρb) , Reach-only score, Uncertainty-only score, and SURE score. Red boxes mark the highest-scoring cells under each criterion, and the green star denotes the goal region.
Backbone
Domain
SURE
Uniform
TD3+BC
Maze2d-Medium
0.14%
1.92%
HalfCheetah
0.52%
2.36%
CQL
Maze2d-Medium
0.16%
2.00%
HalfCheetah
0.55%
2.44%
Table 3: Percentage feedback required to reach 90% of each backbone’s own matched full-feedback reference, averaged over 50 paired seeds.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Visualization of the four evaluation domains. From left to right: TwoRooms, Maze2d-Medium, Maze2d-Large, and HalfCheetah-Medium-Replay.
64 , uniformly sampled; shared across methods and counted toward the budget
Acquisition batch size M
64
Appendix
Table 5: SURE acquisition-score hyperparameters.
Domain
B0=64
B0=200
B0=400
Maze2d-Large
0.060%
0.064%
0.067%
HalfCheetah
0.300%
0.330%
0.360%
Appendix
Table 6: Percentage feedback required by SURE to reach 80% of the matched full-feedback return under different warm-start sizes B0 , averaged over 50 paired seeds.
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
Large Language Models (LLMs) have achieved remarkable advancements in reasoning capabilities empowered by Reinforcement Learning with Verifiable Rewards (RLVR). Nonetheless, RLVR intrinsically relies on ground-truth labels for reward computation, the acquisition of which is often prohibitively expensive in real-world scenarios. While unsupervised RLVR paradigms attempt to circumvent this by training on pseudo-labels, they are notoriously susceptible to training collapse. Moreover, different samples often exhibit varying annotation values. In this paper, we propose Reinforcement Learning with Active Verifiable Rewards (RLAVR), which actively acquires ground-truth labels for a small set of selected samples and integrates them with pseudo-labels, thereby stabilizing training dynamics and improving performance under limited annotation budgets. To identify valuable samples, we propose the Corrective Advantage Gap (CAG) metric and analyze the sample-level supervision value. Building on this, we introduce Correction-Aware Reliability Estimation for RLAVR (CARE), which translates the oracle CAG criterion into a practical pre-query acquisition policy to substantially improve training stability. Extensive experiments across diverse domains, model families, and model scales demonstrate the effectiveness and generality of our approach. Our code is available at https://github.com/Lumina04/CARE.
Li Wang, Xiaodong Lu, Xiaohan Wang +5
Meituan · Beihang University · Nanyang Technological University
Reinforcement learning from human feedback (RLHF) is bottlenecked by reward hacking, where the policy exploits errors in a proxy reward model (RM) and produces high RM scores without genuine quality gains. A natural mitigation is pessimism: lowering rewards in regions where the RM is uncertain. However, standard scalar RMs provide no principled notion of uncertainty. We argue that the right object is a distributional reward model p(r∣x,y). Under either a Bayesian inference or a KL-distributionally robust optimization (KL-DRO) lens, the KL-regularized RLHF objective admits a closed-form effective reward r~(x,y)=±βlogEp[e±r/β]. The pessimistic branch unifies the prior heuristics for RM ensemble aggregation: mean aggregation, worst-case optimization (WCO), and uncertainty-weighted optimization (UWO) all emerge as limits or truncations of this single expression. This also clarifies the implicit assumptions of each existing rule.
Ely Hahami, Yoel Zimmermann, Ray Zhou +1
Harvard College, Harvard University, Cambridge, MA, USA · John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA
Inverse reinforcement learning (IRL) typically assumes demonstrations from a single optimal demonstrator, but in many applications data come from multiple imperfect demonstrators with heterogeneous suboptimality levels. We study reward learning in this setting through a feasible-reward-set framework: for each demonstrator, we encode its declared suboptimality level as a linear constraint and intersect the resulting feasible sets across demonstrators. Our theoretical analysis shows that the joint feasible set shrinks monotonically as data are added, and we give an exact characterization of when a new demonstrator strictly tightens it. We further establish two recovery guarantees for the feasible reward set of the ground-truth optimal demonstrator: one bound depends on closeness to the optimal occupancy, while the other requires only sufficient coverage and no near-optimal demonstrator. On the practical side, we introduce strategies to address the inherent reward ambiguity in the obtained reward set and provide an offline algorithm with function approximation for high-dimensional environments. Experiments in tabular grid-world and large language model (LLM) fine-tuning settings are consistent with the theoretical predictions and demonstrate the effectiveness of the proposed framework over baselines.
Kihyun Kim, Shripad Deshmukh, Nikos Vlassis +1
MIT LIDS · University of Massachusetts, Amherst · Adobe Research +1