WorksComputer Science
Uncertainty-Guided Reward Labeling for Reinforcement Learning under Limited Feedback
Abstract
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.
Introduction
Modern large-scale sequential-decision problems pose a unique challenge: data can often be generated, logged, or collected at scale, but obtaining evaluative feedback for policy learning remains costly. In RLHF, models can generate many candidate responses, while feedback requires human judgment or a separate feedback oracle [8, 28, 2]; in drug discovery settings, generative models can propose large candidate sets, while validation requires expensive simulation or experimental evaluation [32, 14, 17, 31, 11]; and in offline RL, large reward-free transition datasets may be available while reward annotation remains limited [7, 40, 15]. Thus, in learning from collected data, the bottleneck often shifts from data collection to reward acquisition. When only a small fraction of the available data can be reward-labeled, the central question is which subset to label so that learning from the resulting partially reward-labeled dataset yields a high-performing policy.
Existing work on reinforcement learning under limited feedback (RLLF) studies reward selection in a setting where queried rewards are consumed by a policy learner rather than retained for reward-model training [7]. This makes reward selection a question of which queried rewards directly improve policy learning. A complementary line of work on partially labeled offline RL shows that reward modeling is a useful way to leverage retained labels: rewards observed on a subset of transitions can be used to fit a reward model, which annotates the remaining offline dataset before policy optimization [40, 15, 23]. However, these methods assume that the labeled subset is passively available. They do not address the question of which additional transitions should be selected for reward labeling. Information-directed reward learning (IDRL) is the closest related approach, as it actively queries feedback to learn a reward model for policy optimization. However, it acquires feedback online to distinguish the returns of candidate high-performing policies, rather than to determine which transitions in an offline dataset should be reward-labeled [26]. This leaves open the problem of retained-label reward selection: actively selecting a small subset of transitions from a fixed, offline dataset for reward labeling, so that a reward model trained on those labels can annotate the remaining transitions and enable learning a high-performing policy from the resulting dataset.
In this retained-label setting, selected rewards affect policy learning through the reward model they induce. A natural way to improve such a model is to label rewards that reduce uncertainty in the reward model, but reducing uncertainty at different states can have very different effects on the performance of the learned policy. We formalize this intuition by showing that the performance gap between the policy learned from a partially reward-labeled dataset and the true-reward optimal policy is upper bounded by two terms: one determined by the fixed offline transition dataset, and one given by reward uncertainty under the state distribution induced by the true-reward optimal policy. Since reward selection cannot alter the fixed transition data, it can only reduce the latter term. If the state occupancy of an optimal policy were known, the rule would be simple: select rewards that reduce uncertainty in states with high occupancy under that policy. Since this information is unavailable during selection, we introduce Successor-Guided Uncertainty REduction (SURE): the policy learned from the current reward model provides an evolving estimate of which states are valuable, while successor features are used to identify candidate states from which those states are reachable. SURE selects rewards where reachability and uncertainty meet, i.e., states that remain uncertain and are reachable precursors to currently high-value states. Figure 1 illustrates this uncertainty–reachability tradeoff.

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.
In this work, our contributions are:
Formulate retained-label reward selection, an offline RLLF setting where selected rewards are retained for reward-model learning and used to annotate the remaining offline data for policy learning. This extends RLLF to retained reward labels and continuous state-action domains.
Establish a bound-guided acquisition principle for retained-label selection. By separating the performance gap into a fixed offline-data term and a label-dependent reward-uncertainty term, our analysis identifies the ideal selection target: reducing uncertainty on states visited by the true-reward optimal policy.
Introduce SURE, an adaptive reward-selection rule that implements this principle by combining reward-model uncertainty with successor-guided reachability to currently high-value states.
Analyze and evaluate the reward-label efficiency of SURE through theory and experiments. Our analyses relate selection quality to coverage mismatch and effective dimension. Experiments across a variety of domains and offline-RL backbones show that SURE reaches strong performance with fewer reward labels than competing selection strategies.
Related Work
Reward selection and active reward acquisition. When only a limited amount of reward feedback can be obtained, different problem settings involve learners that can query different objects. Active reward learning and preference-based RL query comparisons, demonstrations, rankings, or other types of human feedback to identify a latent reward function [9, 34, 4, 38]. Information-directed reward learning (IDRL) is closer to our motivation: these methods actively acquire feedback to learn a reward model for policy optimization [26]. However, IDRL acquires feedback online, selecting queries expected to rapidly identify which candidate high-performing policy achieves the highest return, whereas our setting focuses on selecting which transitions in a fixed offline dataset should receive reward labels. Methods for active RL with costly rewards and partially observable reward models also query reward observations while interacting with the environment, intertwining reward acquisition with exploration and data collection [21, 35, 37, 30, 29]. These directions all study how to spend limited feedback, but their queried objects and learning protocols differ from retained-label offline reward selection. Closest to our setting is RLLF [6, 7], which formulates reward selection from a reward-free offline dataset under a limited labeling budget. We build on this formulation but retain queried rewards for reward-model learning. The resulting reward-uncertainty signals guide label selection directly, avoiding the additional policy-evaluation cost of the evaluator used in RLLF.
Partially labeled offline RL. Partially labeled offline RL studies policy learning from offline datasets in which only a subset of transitions is annotated with rewards, while the remaining transitions are reward-free. The UDS method [40] studies this setting directly and shows that simply assigning zero rewards to unlabeled transitions can be surprisingly effective, despite the bias introduced by incorrect reward labels. Another strategy is to infer missing reward signals from the labeled subset and use the learned reward model to annotate reward-free transitions before applying standard offline RL [19, 45, 33]. The PDS method [15] takes a pessimistic approach to offline RL with partially labeled datasets, learning a conservative reward estimate from the labeled subset and using the full transition dataset for policy learning. Kernelized variants extend this partially labeled offline-RL framework beyond the original linear setting [23]. Related offline policy-learning settings consider additional forms of incomplete supervision, such as observation-only data with partially labeled rewards, missing actions, low-quality demonstrations, or limited coverage [25, 27].
Problem Formulation and Preliminaries
Preliminaries. An MDP is a tuple , where is the state space, is the state at time , is the action space, is the action at time , is the transition function, is the reward function, is the discount factor, and is the initial-state distribution. Specifically, we consider linear MDPs for our theoretical exposition, defined as follows.
Definition 1 (Linear MDP [39, 16]). An MDP is a linear MDP if there exists a feature map with for all , an unknown vector-valued measure over , and an unknown reward parameter such that and for all . We assume , where bounds the reward-parameter norm.
Given a policy , denotes its discounted expected return under reward function . Consider this MDP, but now with a different reward function ; we denote 's discounted expected return under by . Let be an optimal policy under reward . The discounted state–action occupancy measure of is , which satisfies the relation [36]. A closely related concept is successor features, which encode the expected discounted occupancy of future state-action features.
Definition 2 (Successor Features [10, 3]). For a policy , the successor features of a state–action pair is defined as:
Successor features represent the discounted future occupancy of the feature under a given policy. They summarize which feature directions trajectories from are expected to visit.
Retained-Label Reward Selection
We adopt the reward-selection formulation from Chaudhari et al. [7] (RLLF). An offline dataset is obtained by the interaction of a data-collecting policy with , and contains no rewards. Let denote the states in that are reward-labeled: for samples in where , reward labels are assigned; the remaining samples in are unlabeled. Given a labeling budget , a reward-selection strategy is a map . The states selected for reward labeling are . Unlike RLLF’s original setting, where queried reward labels for states in are not retained, in our setting each transition , where , receives a reward label , and the resulting labeled set, , is retained for reward-model learning. In our setting, the selected rewards are retained and used to learn a policy through the reward-modeling and offline-RL pipeline described next. Our reward-selection objective, in particular, is to identify a querying strategy , where is the return of the policy learned from the retained labels selected by .
Reward Modeling for Partially Labeled Offline RL
Given a retained labeled set , we follow the Provable Data Sharing (PDS) framework [15]: fit a conservative reward model from , use it to assign rewards to the remaining unlabeled transitions in , and run a pessimistic offline-RL on the resulting annotated dataset. Under the linear reward model, we fit the best linear reward parameter from the labeled transitions using regularization, commonly referred to as ridge regression: .
Let denote the labeled reward-design matrix. The ridge solution is . Using this estimate, PDS constructs a pessimistic conservative reward model,
where , and
Here, is the reward-model uncertainty induced by the retained labeled set , and is the corresponding confidence width, which depends on the budget and the confidence tolerance . We take , so and . Appendix § 10.§ 1 provides the full derivation.
By the self-normalized concentration inequality of Abbasi-Yadkori et al. [1] and the nonnegative-reward clipping in Definition 1, with probability at least , the following holds simultaneously for all labeled sets encountered by the learner and for all :
The derivation is provided in Appendix § 10.§ 1. Given the reward estimate , the downstream learner runs a pessimistic offline-RL algorithm on . We use the PEVI-style backbone [18] as a black box proving the following high-probability guarantee: for any pessimistic reward estimate ,
where , and is the offline confidence width. The full derivation is given in Appendix § 10.§ 3. Crucially, this upper bound depends only on the fixed transition dataset and confidence tolerance , not on which transitions are reward-labeled. This motivates the reward-selection question studied next: which rewards should be queried/labeled (and retained) so that the resulting reward model improves policy learning the most?
Successor-Guided Uncertainty Reduction
We introduce Successor-Guided Uncertainty REduction (SURE), an adaptive reward-selection method for the retained-label RLLF setting. Following RLLF’s iterative selection protocol, SURE updates the retained labeled dataset after each queried reward, refits a pessimistic estimate of the reward model, and uses the resulting policy and value estimates to choose the next label. In round , SURE fits the current pessimistic reward model from , runs the offline-RL learner to obtain , selects an unlabeled transition , queries , and updates . The score guiding this selection is derived below from a label-sensitive bound (Thm. 1) and then approximated through successor-guided reachability and reward-model uncertainty metrics (§ 4.2).
From the Suboptimality Bound to an Acquisition Objective
We first derive a label-sensitive upper bound on policy suboptimality. The bound separates the contribution of the fixed offline transition dataset from the contribution of the rewards selected so far.
Theorem 1 (Label-sensitive suboptimality decomposition). Assume that the MDP is linear, as in Definition 1, that the retained labels induce a conservative reward estimate satisfying the reward-confidence bound (Eq. (2)), and that the pessimistic offline-RL algorithm satisfies the stated offline-learning guarantee (Eq. (3)). For any strategy with budget , let denote its first selections, let denote the retained labeled set resulting from those selections, and write and . Then, with probability at least , for every round ,
where is the suboptimality of , the policy learned from the retained labeled set induced by selections.
The proof is in Appendix § 11.§ 1. Thm. 1 shows that the suboptimality bound for the policy induced by a querying strategy can be tightened by minimizing a reward-uncertainty term that depends on the optimal occupancy under the true reward function. Because is unknown during selection, we need a computable surrogate (see Section Section 4.2). Here, we first derive the corresponding selection objective for an arbitrary reference measure .
Given a retained labeled set and reference measure , define the weighted uncertainty objective as
This objective measures the squared reward uncertainty averaged over . Thm. 1 can then be written as
Since only the second term in Eq. (6) depends on the selected rewards, we can use as the objective guiding reward selection. For a fixed reference measure , we define the one-step acquisition function as the uncertainty reduction in this objective obtained by reward-labeling a candidate :
We now show (Prop. 1) that this marginal gain admits a closed form under the linear-MDP assumption.
Proposition 1 (Exact one-step marginal gain). Let . For any reference measure and candidate ,
The proof is given in Appendix § 11.§ 2. Equation (8) shows that the one-step acquisition function accounts for both the reference measure and the current labeled set: it favors candidates that reduce uncertainty in directions emphasized by , while downweighting feature directions already well represented by the current labels. For fixed , maximizing gives the largest one-step decrease of the bound in (6). Appendix § 11.§ 3 formalizes this monotonicity. We next construct a computable reference measure to replace the unavailable optimal occupancy .
Successor-Guided Surrogate Occupancy
At iteration , a pessimistic reward model is learned from the retained labels . The policy learned from the dataset annotated by provides value estimates on the offline dataset. We use these estimates to construct a computable proxy for the optimal policy’s occupancy: following RLLF’s intuition that useful rewards should help the agent remain on, or recover toward, high-return behavior, we treat the highest-valued transitions as temporary targets, or subgoals, and use successor features to score which unlabeled candidates can reach them over multiple steps.
Let be the top- transitions in the offline dataset ranked by . For a candidate and target , define the successor overlap . This overlap is large when trajectories starting from visit feature directions similar to the target under . Averaging over the target set gives
We normalize the positive scores over unlabeled candidates to obtain a successor-guided distribution ; the explicit normalization is given in Appendix § 11.§ 4. To avoid over-concentration when the current value estimates are inaccurate, we mix this distribution with the empirical behavior distribution over unlabeled samples:
We refer to as the successor-guided reachability measure.
The measure is the computable reference measure used in place of the unavailable optimal occupancy . The behavior mixture acts as a coverage safeguard: it prevents successor guidance from concentrating entirely on the current value estimate and preserves feature directions covered by the empirical behavior distribution. Appendix § 12 provides the corresponding theoretical analysis: reference measures constructed from the offline dataset transfer to the original optimal-occupancy objective, with guarantees controlled by coverage of the relevant feature directions.
In principle, one could plug the reachability measure into the exact gain and select . However, evaluating this exact gain for every candidate requires applying to each candidate feature , so that the score accounts for uncertainty reduction in feature directions emphasized by . Forming this matrix and scoring all unlabeled candidates has per-round computational complexity (Appendix § 11.§ 5). To avoid this candidate-wise matrix-vector scoring, we define the computable SURE score as
The first factor is the successor-guided reachability measure, which prioritizes candidates that can reach currently high-value targets while maintaining behavior-policy coverage. The second factor is the local uncertainty-reduction term, which prioritizes candidates that remain uncertain under the current reward model, with the same normalization used in Proposition 1. SURE combines these factors to select rewards that are both reachable to currently high-value targets and informative for reward-model learning, thereby targeting uncertainty reductions that are more likely to improve the learned policy. § 5.4 shows that either factor alone can fail: REACH, which selects only by the reachability factor, can fail when current value estimates are inaccurate, while UNCERTAINTY, which selects only by the uncertainty factor, can fail when high uncertainty lies in regions unrelated to high-return behavior. Appendix § 9 gives the full adaptive procedure.
Experiments
We evaluate SURE in the retained-label RLLF setting considered in § 3, where the learner is given a fixed reward-free offline transition dataset and can acquire rewards for only selected transitions. Our experiments address five questions: (Q1 § 5.1) when the linear-MDP assumptions of § 3 hold by construction, does the computable SURE score retain the label efficiency of the exact one-step-gain rule it approximates; (Q2 § 5.2) does SURE remain label-efficient beyond this setting, in continuous-control domains where the feature map is learned and the linear-MDP structure need not hold, and how does it compare with other reward-selection strategies across budgets; (Q3 § 5.3) how much feedback each strategy requires to approach the full-feedback performance obtained when rewards are available for all transitions in ; (Q4 § 5.4) how each component of SURE contributes to acquisition; and (Q5 § 5.5) whether the gains of SURE are specific to the IQL backbone or persist when the downstream offline-RL learner is replaced.
We evaluate on five domains with different acquisition challenges: LinearMDP, a finite linear MDP in which the assumptions of § 3 hold by construction (§ 5.1); TwoRooms, Maze2d-Medium, and Maze2d-Large, three navigation tasks with bottleneck and goal-reaching rewards; and HalfCheetah, a high-dimensional locomotion task [5]. For each domain, all strategies use the same fixed reward-free dataset : we collect the TwoRooms dataset ourselves and use the D4RL datasets [12] for Maze2d-Medium, Maze2d-Large, and HalfCheetah.
Our empirical comparison focuses on reward-selection strategies: SURE selects rewards using the acquisition score in equation (11), and we compare it against alternative rules for selecting the rewards. UNIFORM samples labels uniformly from the unlabeled pool. RLLF-GUIDED adapts the guided heuristic of RLLF [7], which biases selection toward one-step predecessors of states estimated to have high value under the current learner. IDRL [26] adapts the information-directed acquisition criterion to the fixed offline dataset by estimating policy-return information with FQE. REACH uses only the successor-guided relevance factor in equation (11), while UNCERTAINTY uses only the uncertainty-reduction factor. After rewards are selected, every method follows the retained-label PDS pipeline described in § 3: the acquired labels are used to fit a conservative reward model, which assigns rewards to the unlabeled portion of ; IQL [20] is then run on the resulting reward-labeled dataset to produce a policy (§ 5.5 replaces IQL with other offline-RL backbones).
We report the return of learned policies as a function of the absolute feedback budget in § 5.2 and the percentage feedback in § 5.3, where denotes the set of distinct states in . We also include a full-feedback reference, corresponding to percentage feedback equal to one, i.e., . Results are averaged over 50 trials for each strategy. Full domain and dataset descriptions, implementation details, hyperparameters, and evaluation protocols are provided in Appendix § 13.
Validation under Exact Linear MDPs
We first evaluate SURE in a setting where the theoretical assumptions hold exactly. We construct finite linear MDPs using the simplex-feature construction of Jin et al. [16]: each state–action pair is assigned a known 8-dimensional feature vector on the probability simplex, its transition distribution is the corresponding convex combination of eight base next-state distributions, and its reward is linear in the same feature vector. Both the reward and the transition kernel are therefore linear in a fixed feature map , which is provided to every method. We consider environments with 32 and 48 states, four actions, and low-exploration offline pools of 4,096 transitions. Because is known and the problem is small, the exact one-step gain of Proposition 1 can be computed for every candidate, so we compare SURE with EXACT GAIN, which selects the candidate maximizing equation (8), and with UNIFORM. All methods share the same four uniformly selected warm-start labels, counted toward the budget, and results are averaged over 30 paired seeds.
Table 1 shows that SURE and EXACT GAIN require identical numbers of labels at every threshold in both environments. With 48 states, both reach 90% and 95% of the full-feedback return with 12 labels, whereas UNIFORM requires 68 and 132 labels, respectively. Thus, when the theoretical assumptions hold, replacing the exact one-step gain with the computable SURE score does not sacrifice label efficiency.
| Environment | SURE | EXACT GAIN | UNIFORM |
| 8 / 12 / 12 | 8 / 12 / 12 | 20 / 20 / 36 | |
| 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.
Label Efficiency Across Domains
In continuous-control tasks, however, a feature map under which rewards and transitions are exactly linear is generally unknown and must be learned from data. We therefore test whether the conclusions of § 5.1 carry over to four continuous-control domains in which is learned rather than given. Figure 2 compares SURE with the reward-selection baselines described above. The solid curve shows the mean return over 50 trials, and the shaded region shows the standard error. The dashed line indicates the full-feedback offline-RL reference, obtained by training IQL when rewards are available for all transitions in .
Figure 2. Performance comparison across domains under limited feedback. Return is shown as a function of the absolute feedback budget . 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.
The results show that the relative performance of baselines varies across domains, while SURE remains consistently strong across all settings. Below, we highlight the main empirical findings:
SURE is the strongest overall strategy. Across all four domains, SURE achieves the best or near-best returns over the feedback range. The strongest competing baseline changes across domains, but SURE is the only method that remains consistently strong across the full evaluation suite.
Single-factor acquisition is not sufficient. The better single-factor baseline depends on the domain. In navigation tasks, REACH is often competitive because the most useful labels are those that help identify trajectories leading toward the goal. In HalfCheetah, this spatial guidance is less informative: the higher-dimensional replay dataset makes reward uncertainty the main bottleneck, so UNCERTAINTY becomes the stronger single-factor baseline. This domain dependence shows that neither reachability nor uncertainty alone is a reliable acquisition rule.
Information-directed querying depends on reliable return estimates. IDRL is competitive in the maze domains, where low-dimensional geometry and goal-reaching rewards make policy-return differences easier to estimate from limited rewards. Its performance degrades in HalfCheetah, where the higher-dimensional dataset makes the information-directed acquisition signal less reliable.
Multi-step reachability improves over one-step guidance. RLLF-GUIDED often remains close to UNIFORM, suggesting that one-step predecessor guidance alone is too local for these offline datasets. In contrast, REACH is stronger in navigation domains, indicating that successor-guided multi-step reachability provides a more useful acquisition signal than selecting only immediate predecessors of currently high-value states.
SURE combines the useful signals without choosing one in advance. The multiplicative acquisition score requires a candidate to be both relevant to promising behavior and informative for reward-model learning. As a result, SURE emphasizes reachability when useful trajectories are easier to identify from the geometry of the task, and emphasizes uncertainty when the relevant behaviors are harder to localize.
Feedback Needed to Reach Full-Feedback Performance
Table 2 converts the curves in Figure 2 into the feedback required to reach fixed fractions of the full-feedback reference. This view makes the cross-domain comparison more direct by normalizing for the size of each domain’s state set: TwoRooms has 15K transitions, Maze2d-Medium has 2M, Maze2d-Large has 4M, and HalfCheetah has 200K.
| Domain | Fraction | 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% | |
| 80% | 0.06% | 2.42% | 2.38% | 0.40% | 0.16% | 2.12% | |
| halfcheetah | 95% | 0.71% | 6.64% | 7.06% | 6.18% | 4.10% | 2.49% |
| 90% | 0.45% | 2.55% | 2.65% | 2.22% | 2.49% | 0.59% | |
| 80% | 0.30% | 0.31% | 0.36% | 2.20% | 0.32% | 0.31% |
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.
The main takeaway is that SURE reaches the same performance levels with substantially less feedback. At the 95% level, SURE requires the least feedback in every domain: 3.17% in TwoRooms, 0.20% in
Maze2d-Medium, 0.15% in Maze2d-Large, and 0.71% in HalfCheetah. Compared with the strongest non-SURE method in each domain, this corresponds to roughly 1.6×–4.3× less feedback. The gap is even larger against mismatched single-factor baselines: UNCERTAINTY requires about 18.6× more feedback than SURE on Maze2d-Large, while REACH requires about 5.8× more feedback than SURE on HalfCheetah.
Since SURE reaches the 95% level with substantially less feedback than the baselines, Figure 2 focuses on the feedback range in which SURE has largely converged. Some baselines continue to improve with larger budgets, but Table 2 shows that they require much more feedback to reach the same performance levels.
Ablation Study of Reachability and Uncertainty
Figure 3 presents an ablation on the maze domain by visualizing how different acquisition signals rank candidate states under different initial labeled sets. Each row corresponds to one initial labeled set. The first column shows the current labeled samples (black dots) together with the underlying ground-truth reward field (background color), which is not accessible to the selection strategy. The second column shows the exact one-step gain, computed by adding additional feedback from each grid cell (sampling 50 transitions from the dataset whose states fall into that cell); darker colors indicate larger gain, meaning selecting from that cell under the current labeled set leads to greater policy improvement. The remaining columns show the selection distributions induced by the Reach score, the Uncertainty score, and the SURE score. Darker colors indicate higher selection density, and the highlighted cells are the top-ranked cells, i.e., the states most likely to be selected by each acquisition rule.
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 , 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.
The results show that the alignment between each acquisition rule and the exact one-step gain depends on the structure of the current labeled set, while SURE consistently tracks the high-gain regions. When the labeled set provides broad coverage, the uncertainty field is relatively flat, and the highest-gain cells concentrate along the goal-reaching corridor; in this regime, Reach has stronger overlap with the exact gain, while Uncertainty highlights scattered regions with weaker alignment. Conversely, when the labeled set is spatially biased, the highest-gain cells shift toward previously unexplored areas; here, Uncertainty aligns better with the gain, while Reach concentrates near already-labeled regions. Across both scenarios, SURE overlaps well with the exact-gain cells by combining the two signals rather than committing to either one alone. This distinction becomes more important in higher-dimensional domains, where the labeled set cannot be easily visualized as uniformly spread or clustered, and where the labeled distribution changes as more feedback is acquired. SURE therefore provides a more robust acquisition rule by adapting to both policy relevance and reward uncertainty throughout selection.
Robustness to the Offline-RL Backbone
All preceding experiments use the same IQL backbone for every method to isolate differences due to reward-label acquisition. However, SURE is not intrinsically tied to IQL: the analysis in § 4 invokes the downstream learner only through the pessimistic offline-learning condition in equation (3). To test whether the empirical gains are specific to IQL, we replace the backbone throughout the full acquisition loop, including the policy and value estimates used to construct the SURE score, with CQL [22] and TD3+BC [13] on Maze2d-Medium and HalfCheetah. CQL provides a more theory-aligned test because it explicitly encourages conservative value estimates, whereas TD3+BC tests the acquisition rule with a behavior-regularized learner outside the formal condition.
Table 3 shows that SURE requires approximately less feedback than UNIFORM under both alternative backbones and in both domains, indicating that the acquisition benefit of SURE is not specific to IQL. The sensitivity of SURE to the size of the initial warm-start set is reported in Appendix § 13.7.
| 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.
Discussion and Conclusion
This work studies reward selection for RLLF in the retained-label setting, where queried rewards can be reused to train a reward model before downstream offline RL. Our analysis shows that, once the offline dataset is fixed, selection can only improve the reward-model uncertainty term in the suboptimality bound. This clarifies the role of reward uncertainty: uncertainty is most useful to reduce when it lies along directions that good policies are likely to use. We then propose SURE, which turns this principle into a practical acquisition rule by combining successor-guided reachability with uncertainty reduction, so that selected rewards are both connected to promising regions and useful for shrinking the reward confidence radius. The theory justifies this rule by deriving the acquisition objective from the suboptimality bound and showing how compatible reference measures can replace the unknown optimal occupancy. Empirically, SURE is consistently more label-efficient across a variety of domains and offline-RL backbones, while other selection strategies are strongest mainly in regimes favored by their respective biases.
Acknowledgments and Disclosure of Funding
This work used computational resources and services provided by the Unity Research Computing Platform and the Swarm cluster at the University of Massachusetts Amherst. We also thank the anonymous reviewers for their comments and suggestions, which helped strengthen and clarify this work.
References
SURE Algorithm
Algorithm 1 gives the full pseudocode for SURE, assembled from the SURE score (11), the reachability measure (10), the successor-guided distribution of Appendix § 11.§ 4 obtained by normalizing the per-candidate scores (9), and the pessimistic reward and backbone objects of § 3. § 4 uses single-query notation to simplify the presentation of the acquisition rule and its analysis; in the experiments, labels are acquired in batches. SURE starts from uniformly sampled warm-start labels, which are shared by all methods within each seed and counted toward the feedback budget . Each subsequent round acquires the unlabeled candidates with the largest SURE scores, after which the reward model, the offline backbone, the successor features, and the acquisition scores are recomputed. With and , round coincides with the -th query and Algorithm 1 reduces to the single-query rule of § 4. We use in all continuous-control experiments (Appendix § 13.§ 4). After the budget is exhausted, SURE refits the reward model using the final labeled set , re-runs the pessimistic backbone once more on the full dataset, and returns the resulting policy .
Algorithm 1 SURE: Successor-Guided Uncertainty REduction for reward labeling
Require: offline dataset ; budget ; warm-start size ; batch size ; top-; weights .
Draw with uniformly at random; query their rewards to form .
Set the number of acquisition rounds .
for do
Fit ridge reward estimator and build pessimistic reward from .
Run the offline backbone on with reward to obtain and .
Form target set : the top- transitions in under .
Compute per-candidate scores via (9) and the successor-guided distribution via Appendix § 11.§ 4.
Mix with behavior: .
the candidates in with the largest in (11).
Query for all ; update , .
end for
Refit from ; run backbone on with to obtain .
return .
Derivations for Section 3
This appendix collects the derivations of the constructions used in § 3: the PDS pipeline that produces the pessimistic reward estimate together with the reward-confidence bound (2), a ridge estimator for the one-step feature transition operator that supports the successor features of Definition 2, and the offline-RL error term used in equation (3).
PDS pipeline and reward-confidence bound
The “Reward Modeling for Partially Labeled Offline RL” paragraph of § 3 describes how the retained labeled set is converted into a reward signal that the downstream offline-RL backbone can consume. We restate that pipeline here in pragmatic terms, formalize the ridge regression step, derive the reward-confidence bound (2), and verify that the resulting underestimates the true reward at every state–action pair.
The PDS pipeline. The pipeline composes two ingredients. First, ridge regression on the labeled set (equation (3.2)) fits a single linear reward parameter . Because the reward model is linear in , this single estimator produces a prediction at every state–action pair—not only the queried ones—which is what allows a small number of labels to generate a reward signal everywhere the offline pool reaches. Second, PDS turns this point prediction into a lower-confidence reward
by subtracting the elliptical uncertainty radius from the ridge prediction, scaled by the width . By construction, the result underestimates the true reward, with high probability, so the downstream pessimistic backbone (e.g., PEVI [18]) inherits a clean reward-side guarantee.
Matrix-form derivation of the ridge estimator. Fix a labeled set , and let . Enumerate it as . Define the design matrix, the noise vector, and the response vector
Under the linear reward model, . In matrix form, the ridge objective (3.2) reads
Setting its gradient to zero gives the normal equation
Substituting and using , we obtain
The first term is the stochastic estimation error inherited from the noise , and the second is the deterministic ridge bias toward zero induced by . Bounding each yields the reward-confidence inequality below.
Derivation of the reward-confidence bound.
Derivation of (2). We bound the two terms of (12) separately, combine them, and apply the nonnegative-reward clipping of PDS.
Step 1: bounding the stochastic term. Fix . Using (12),
For the first term, insert and apply Cauchy–Schwarz:
using . By the self-normalized concentration inequality of Abbasi-Yadkori et al. [1] for linear regression with conditionally -sub-Gaussian noise, with probability at least , uniformly over all labeled sets the learner may encounter,
Bounding the determinant ratio by the AM–GM inequality together with (since ) gives , hence
Step 2: bounding the ridge-bias term. Insert again and apply Cauchy–Schwarz:
where the last step uses , so , and .
Step 3: combining and clipping. Adding the two bounds,
Define , so . Recall . When the un-clipped expression is nonnegative, the displayed two-sided confidence bound gives ; when it is negative, and , again yielding the same two-sided gap. This is equation (2). ∡՞
Successor-feature estimation
Under Definition 1, the successor feature of Definition 2 admits the closed form
where is the one-step feature transition operator under , characterized by with and . Given the offline transition dataset and a policy , we estimate by ridge regression of the next-feature expectation on the current feature:
whose closed form is the standard multivariate ridge estimator. We then set and use in place of in the per-candidate scores of equation (9). The estimation error contributes an additive term to the unified design bound of Appendix § 12.§ 1; because this term does not depend on the labeled subset , it does not affect the query-complexity structure of the analysis.
Form of the offline-RL error term
The backbone guarantee (3) is invoked abstractly in the analysis. Here we record the concrete instantiation we use in experiments—the pessimistic value-iteration (PEVI) backbone of Jin et al. [18] adapted to retained-reward partial labels by Hu et al. [15]—and derive the max-over- form of used in § 3.
Let be the offline value-regression design matrix built from all transitions in , with regularizer . The associated offline pessimism radius is , and the offline confidence width is
for an absolute constant inherited from the self-normalized vector concentration of Abbasi-Yadkori et al. [1]. By construction, , , and are functions of only.
Theorem 4.4 of Jin et al. [18], instantiated in the linear-MDP setting of Definition 1 and combined with the pessimistic-reward clipping of Hu et al. [15], yields, with probability at least , the PEVI suboptimality bound
The right-hand side has a residual -dependence through the integration measure , but the integrand is reward- and labeling-free: a function of only. We absorb the residual dependence by replacing the expectation with the maximum of the integrand over the transitions in . Pessimism in PEVI prevents the learned policy from leaving the support of , so effectively concentrates on the state–action pairs covers, and the chain
holds. The last equality is the definition of used in § 3: by construction it is a function of alone, with no dependence on which transitions are reward-labeled. The full PEVI / PDS derivation of equation (15) is given by Jin et al. [18], Hu et al. [15]; we do not reproduce it here.
Proofs and Auxiliary Results for Section 4
This appendix proves the formal statements introduced in § 4 and supplies the auxiliary constructions deferred from the main text. Throughout, all proofs are carried out on the intersection of the reward-confidence event of (2) and the success event of the pessimistic offline-RL backbone from (3). On this event, all displayed inequalities are deterministic.
Proof of Theorem 1
Theorem (Label-sensitive suboptimality decomposition). Under Definition 1, equation (2), and equation (3), with probability at least , for every round ,
Proof. Write for the policy produced by the pessimistic offline-RL backbone in round . By the definition of suboptimality in Theorem 1,
Add and subtract two terms involving the pessimistic reward :
We bound the three terms separately.
Step 1: bounding term . Equation (2) gives for every , and the discounted return is monotone in the reward, so for any policy . Applied to ,
Step 2: bounding term . Let be an optimal policy for the pessimistic reward. Since is optimal for , , and therefore
With , the backbone guarantee in equation (3) gives
and hence .
Step 3: bounding term . By definition of value,
Equation (2) gives for every , so
The discounted occupancy identity , applied with , yields
Step 4: assembling the pieces. Combining the three bounds gives
Since and is a probability measure, Jensen’s inequality applied to the concave square-root yields , and substitution gives the claimed bound.
Proof of Proposition 1
Proposition (Exact one-step marginal gain). For any reference measure over the pool and any candidate ,
In particular, is monotonically nonincreasing in the labeled set.
Proof. For readability, write , , , and . The design potential admits a trace form: by definition , and taking expectation over with linearity of trace gives
Applying (17) to both and ,
so
Step 1: Sherman–Morrison update. Since is positive definite, the rank-one inverse formula applies:
Substituting into (18) and using linearity of trace, the terms cancel, leaving
Step 2: simplifying the denominator. By definition of the uncertainty radius, , so the denominator is .
Step 3: simplifying the numerator. By cyclicity of trace and the existence of a symmetric positive semidefinite square root ,
Substituting yields
the claimed formula.
Step 4: monotonicity. The numerator is a squared Euclidean norm and therefore nonnegative, and , so for every . By definition of , , so is monotonically nonincreasing in the labeled set.
Marginal gain and bound decrease
The bound in equation (6) is monotone in for any fixed reference measure , so the largest one-step decrease of the bound is achieved by selecting the candidate that maximizes the marginal gain . We make this precise.
For a fixed reference measure , define the bound-side objective
and let denote the same quantity after adding to the labeled set.
Lemma 1 (Marginal gain orders bound improvement). Fix a reference measure and round . For any candidate with ,
Consequently, is strictly increasing in .
Proof. By the definition of in equation (7), . Substituting into (19) for and into the analogous expression for yields (20). Applying the elementary identity with and yields the equivalent ratio form
For strict monotonicity, fix and define for . Since , is strictly increasing on , and is a positive constant multiple of . Hence is strictly increasing in .
Normalization of the reachability measure
Section 4.2 obtains the successor-guided distribution by normalizing the positive part of the per-candidate scores of equation (9) over the unlabeled pool. We make the normalization explicit. Let denote the unlabeled set at round , and define
The successor-guided distribution is
Clipping to the positive part discards candidates whose successor overlap with the target set is negative under the current policy, so they receive no probability mass. The fallback to the uniform distribution on when —that is, when no unlabeled candidate has positive successor overlap with —keeps a well-defined probability measure on at every round. Under this definition, the mixture of equation (10) is always a probability measure on the unlabeled pool, with the behavior component controlling coverage and the successor component concentrating on candidates that can reach under .
Exact-gain scoring complexity
Section 4.2 states that, at each round , evaluating the exact gain of equation (8) for every unlabeled candidate costs when the directional operator is formed explicitly. We record the per-round cost breakdown.
By Proposition 1,
A candidate-wise evaluation therefore needs:
the symmetric square root , via one eigendecomposition of the symmetric matrix , at ;
the matrix product , at ;
one matrix–vector product per unlabeled candidate, at , followed by an squared-norm;
the scalar uncertainty , already maintained by the pessimistic reward pipeline.
Summing over the unlabeled candidates, the per-round cost is , as claimed. By contrast, the SURE score of equation (11) requires only per round to evaluate the values across the unlabeled pool—the operator construction is avoided—while reusing the per-candidate scores and the mixture weights already produced by the surrogate-occupancy step.
Theoretical Analysis
This appendix supports the discussion at the end of § 4.2. We define a coverage coefficient that measures the cost of replacing the unknown optimal occupancy by a computable reference measure on the offline pool, prove the resulting unified suboptimality bound, derive a budget-dependent design rate that exposes the dependence on coverage mismatch and effective dimension, and explain how the SURE score arises as a scalable surrogate for the exact one-step gain. Every formal statement is proved.
Coverage transfer and unified bound
Definition 3 (Coverage coefficient and query complexity). For any probability measure on the unlabeled pool, define
and the query-complexity coefficient . We call admissible if . Admissibility is a data-coverage condition on the offline pool: requires . If the pool leaves any feature direction used by the optimal policy uncovered, no reward-labeling strategy can recover it from labels alone.
Proposition 2 (Coverage transfer). For any admissible reference measure and any labeled set ,
Proof. By definition of , . Set . For any pair of positive semidefinite matrices we have , since . Therefore
For any probability measure , trace cyclicity together with gives
Substituting and yields .
Proposition 3 (Coverage preserved by the behavior mixture). Let be the round- reachability measure of equation (10). For any ,
This shows that successor guidance can concentrate mass near currently high-value targets without discarding the feature directions already covered by the empirical behavior distribution.
Proof. By construction, is a probability measure on the unlabeled pool (Appendix § 11.§ 4), so its second-moment matrix is
as a conic combination of rank-one positive semidefinite matrices. Linearity of under convex combinations gives
which is the first claim.
For the second claim, write . By definition of , . The first claim and imply . Composing the two PSD inequalities,
By minimality in the definition of , .
Combining Theorem 1 with Proposition 2 yields the structural bound under any admissible reference measure.
Theorem 2 (Unified reference-measure suboptimality bound). Under Definition 1, equation (2), and equation (3), with probability at least , for any admissible reference measure and any labeled set producing a pessimistic policy with confidence radius ,
Proof. Theorem 1, applied to and the pessimistic policy with confidence radius , gives
where is the uncertainty radius associated with . The trace-identity argument used in the proof of Proposition 2 (taking ) yields . Substituting and applying Proposition 2,
The square-root map is monotone increasing on , so substituting yields the displayed bound.
Budget-dependent rates
We translate Theorem 2 into a budget-dependent rate by tracking how fast the design potential decays under exact-gain selection against a fixed reference measure.
Theorem 3 (Fixed-measure greedy design rate). Fix an admissible probability measure on the pool with rank , and run the exact-gain rule
of Proposition 1 against this fixed reference measure. Then for every ,
Proof. Write . By Proposition 1, is monotonically nonincreasing in and the round- drop equals the exact gain at the chosen candidate:
Step 1: greedy lower bound. The rule maximizes over the unlabeled pool, and is supported on the pool, so
Step 2: lower bound on the expected gain. By Proposition 1,
Section takes so that and . Hence the denominator is at most , and
Expanding the squared norm,
using . Taking expectation over , with and trace cyclicity,
where .
Step 3: relating to . Trace cyclicity gives (the last equality is the trace identity from Step 2). The matrix has rank at most , so its eigenvalues (with the remaining eigenvalues equal to zero) satisfy, by the Cauchy–Schwarz inequality applied to the all-ones vector and ,
Therefore , and combining Steps 1–3,
Step 4: telescoping the recursion. If for some , monotonicity gives and the bound is trivial. Otherwise, dividing (21) by and using ,
Summing over and using (so ),
which gives , the claimed bound.
Combining Theorem 2 with Theorem 3 yields the budget-dependent corollary that we view as the headline rate statement: under exact-gain selection against a fixed reference measure, the label-dependent term decays at the parametric rate with a constant determined by the query complexity .
Corollary 1 (Reference-measure suboptimality rate). Under the assumptions of Theorem 2 and exact-gain selection against an admissible fixed reference measure ,
Proof. Theorem 2 applied at the terminal round with reference measure and confidence radius gives
By Theorem 3, , and the square-root map is monotone, so
using . Substituting yields the displayed bound.
Exact-gain structure and the SURE score
We finally explain why the SURE score (11) approximates the exact gain (8), and what is preserved when the directional operator is replaced by the scalar mixture weight .
For a fixed round , reference measure , and candidate , define
Define the directional relevance and the uncertainty-reduction factor
When , set both quantities to zero.
Proposition 4 (Exact-gain decomposition). For every round , every reference measure , and every candidate ,
Proof. By Proposition 1,
For any vector and PSD , . Applying this with and ,
If , the right-hand side is zero, so ; by definition as well, and the identity holds trivially. Otherwise and
Substituting,
which is the claimed factorization.
The SURE score (11) replaces the two factors of Proposition 4 by quantities already produced upstream. The directional relevance is replaced by the scalar mixture weight – which reuses the reachability scores of equation (9) and the behavior mixing of equation (10) – and the uncertainty-reduction factor is replaced by the closely related , already maintained by the pessimistic reward pipeline. The next proposition records the cost saving that this substitution buys per round.
Proposition 5 (Per-round cost of the SURE score versus the exact gain). At each round , evaluating SURE of equation (11) for every unlabeled candidate costs , whereas evaluating the exact gain of equation (8) for every unlabeled candidate costs when the directional operator is formed explicitly.
Proof. The SURE score requires only the per-candidate scalars and the mixture weights . Once is maintained incrementally by the pessimistic reward pipeline, each costs one matrix–vector product and one inner product, i.e., ; summed over the unlabeled candidates this gives .
For the exact gain, Proposition 1 requires the directional operator . Computing the symmetric square root needs one eigendecomposition of the symmetric matrix , at , and forming needs one matrix product, also at . Then for each unlabeled candidate, computing costs and the squared norm an additional . Summing the operator-construction cost and the per-candidate matrix–vector products gives per round, as claimed.
SURE thus preserves the relevance-times-uncertainty structure of the exact gain – each candidate is scored by the product of a relevance term and an uncertainty term – while avoiding the per-round operator construction. This is the structural reason why dropping either factor (REACH or UNCERTAINTY in the empirical ablation of § 5.4) breaks the score whenever the dropped factor is not nearly flat across candidates.
Experimental Details
This appendix complements § 5 with domain and dataset details, baseline implementations, the shared partially labeled offline-RL pipeline, and acquisition hyperparameters.
Domains and Datasets
We evaluate on five domains: the finite linear MDPs of § 5.1, constructed so that the assumptions of § 3 hold exactly, and four offline-RL domains chosen to span continuous navigation, continuous-control navigation at two scales, and high-dimensional locomotion. Within each domain, every reward-selection strategy and every random seed sees the same fixed reward-free transition pool ; a strategy is allowed to acquire transition-level reward labels from this pool.
Domain visualizations
Figure 4 shows one subplot per domain. The four subplots correspond to the following.
Figure 4. Visualization of the four evaluation domains. From left to right: TwoRooms, Maze2d-Medium, Maze2d-Large, and HalfCheetah-Medium-Replay.
TwoRooms. A continuous two-room gridworld in which two rectangular rooms are connected by a narrow doorway. The state is the agent’s continuous cell and the action set is the four cardinal moves; a sparse reward is given only at the goal cell, which lies in the room opposite the start. The doorway concentrates the directions an optimal policy must traverse, providing a small-scale sanity check for the reward-selection problem.
Maze2d-Medium. A continuous 2D point-mass navigation domain from the D4RL benchmark suite [12]. The state encodes the point-mass position and velocity, the action is a continuous 2D force, and a sparse reward is given upon reaching the goal. “Medium” refers to the layout size: a moderately long path between start and goal with a small number of corridors.
Maze2d-Large. The larger-layout counterpart of Maze2d-Medium, with the same continuous state and action spaces and the same sparse goal-reaching reward, but a longer required path between start and goal. The longer horizon concentrates the optimal-policy directions on a narrow corridor that occupies a smaller fraction of the offline pool, increasing the difficulty of credit assignment.
HalfCheetah-Medium-Replay. A continuous-control locomotion domain from the D4RL MuJoCo suite [5, 12]. The state encodes joint positions and velocities of the simulated half-cheetah (17-D), and the action is a continuous torque vector (6-D). The Medium-Replay dataset records the full replay buffer of a partially trained agent, so it mixes high- and low-quality transitions; together with the navigation domains it provides a higher-dimensional, non-navigation contrast for the acquisition comparison.
Dataset collection
We use the same fixed reward-free transition pool for every reward-selection strategy and every random seed within a domain.
TwoRooms. We collect the offline pool ourselves, with transitions. The data-collecting policy mixes uniform random exploration with goal-directed trajectories from a hand-coded shortest-path policy: at each step it takes a random action with probability 0.5 and a shortest-path action with probability 0.5. This mixture ensures coverage of both the corridor connecting the two rooms and the surrounding non-corridor cells.
Maze2d-Medium and Maze2d-Large. We use the standard D4RL datasets “maze2d-medium-v1” (M) and “maze2d-large-v1” (M), both collected by a hand-engineered planner that drives the point mass to repeatedly resampled goals. We strip the rewards from the released datasets to obtain the reward-free pool used as input to reward selection.
HalfCheetah-Medium-Replay. We use the D4RL dataset “halfcheetah-medium-replay-v2” (K), which records the full replay buffer of a SAC agent trained to medium-level performance. Rewards are stripped to obtain the reward-free pool used as input to reward selection.
Retained-Label Reward Selection Baselines
All baselines share the offline pool and the same partially labeled offline-RL pipeline of Appendix § 13.§ 3; they differ only in how each round’s transition is selected from the unlabeled pool. We describe the implementation of each in turn.
Uniform. At round , Uniform draws a transition uniformly at random from the unlabeled subset , without replacement across rounds. Uniform uses no value information, no reward-uncertainty information, and no policy estimate, and serves as the coverage-only baseline.
RLLF-Guided. RLLF-Guided is the guided heuristic of Chaudhari et al. [7]. At round , with the action-value function of the current pessimistic policy under reward and the current top-valued transition, each unlabeled candidate is scored by an empirical one-step transition probability of reaching from , estimated empirically from the offline transition pool. The score is then mixed with the empirical behavior visitation distribution as in Chaudhari et al. [7], and the candidate with the highest mixed score is selected. We re-run this entire procedure at every round.
IDRL. IDRL is the Information Directed Reward Learning method of Lindner et al. [26], originally proposed for online reward querying. At each round it selects the candidate label that is expected to be most informative for comparing the returns of candidate high-performing policies. To adapt IDRL to our offline setting, we replace its online rollout-based return estimation with FQE [24] on the fixed dataset , so that policy-return estimates used to compute the information-gain criterion are derived from the same offline pool used by every other baseline. The candidate set, the posterior reward distribution, and the FQE evaluation are recomputed at every round.
Reach (single-factor ablation). Reach is a single-factor ablation of SURE that drops the reward-uncertainty term. At round , it selects the candidate that maximizes the relevance weight from equation (10). Reach uses the same successor-feature reachability and behavior-mixing pipeline as SURE, but ignores how much each label would shrink the reward-confidence radius.
Uncertainty (single-factor ablation). Uncertainty is the complementary single-factor ablation: it drops the relevance weight and selects the candidate that maximizes , using the current pessimistic-reward design matrix . Uncertainty uses no policy or successor information; it queries wherever the reward model is currently most uncertain.
Partially Labeled Offline RL Implementation
After a reward-selection strategy produces the retained labeled set , every method follows the same pipeline from § 3: the retained labels are used to construct a conservative reward estimate, the reward-free transitions in are annotated with this estimate, and IQL is trained on the resulting dataset. This shared pipeline ensures that empirical differences come from the reward-selection rule rather than the offline-RL learner. All methods use the same representation and offline-RL implementation.
The IQL learner [20] hyperparameters are listed in Table 4; we follow standard IQL settings throughout.
| Hyperparameter | Value |
| Hidden sizes for , , | 256 256 MLP, ReLU |
| Optimizer | Adam |
| Learning rate | (all three networks) |
| Batch size | 256 (D4RL); 64 (TwoRooms) |
| Discount | 0.99 (HC-MR); 0.995 (Maze2d-M, Maze2d-L); 0.95 (TwoRooms) |
| Target-network Polyak rate | |
| Expectile parameter | 0.7 (D4RL); 0.5 (TwoRooms) |
| Advantage-weighting temperature | 3.0 (Maze2d-M, HC-MR); 10.0 (Maze2d-L); 1.0 (TwoRooms) |
| Reward scaling | fixed across methods |
Table 4. IQL hyperparameters.
Hyperparameters
SURE acquisition score. The acquisition-score hyperparameters are listed in Table 5. We set the top- target-set size by domain scale, using a smaller for TwoRooms and a larger for the continuous domains. We use a small constant behavior-mixing weight in all experiments; this prevents the relevance weight from concentrating on isolated outliers under low-coverage early rounds.
| Hyperparameter | Value |
| Top- target-set size | 5 (TwoRooms); 32 (Maze2d-M); 64 (Maze2d-L); 64 (HC-MR) |
| Behavior-mixing weight | 0.1 (constant across rounds) |
| Successor-feature ridge regularizer | |
| Successor-feature estimator | closed-form ridge (Appendix § 10.§ 2) |
| Warm-start labels | 64, uniformly sampled; shared across methods and counted toward the budget |
| Acquisition batch size | 64 |
| Refit cadence | every acquisition round (after each batch of labels) |
Table 5. SURE acquisition-score hyperparameters.
Evaluation Protocol
We report mean return over 50 random seeds; shaded regions in Figure 2 show standard error. Policies are evaluated with 100 rollouts per seed for the D4RL domains and 200 rollouts for TwoRooms. All methods are evaluated under the same budget grid and the same full-feedback reference. Due to hardware constraints, we run our jobs on CPUs.
Computational Cost
The methods differ in the computation required for acquisition. UNIFORM selects labels without fitting an acquisition model and is therefore substantially cheaper. UNCERTAINTY updates only the reward estimator and its uncertainty quantities, whereas RLLF-GUIDED, REACH, IDRL, and SURE additionally update policy-, value-, successor-, or policy-evaluation-related quantities. SURE’s method-specific overhead consists of recomputing successor features, constructing the high-value target set, evaluating reachability, and scoring the unlabeled candidates. As described in Appendix § 9, these components are updated once per batch of newly acquired labels rather than after every individual label.
We compare the wall-clock time of all methods under identical batch sizes, feedback budgets, hardware, and evaluation protocols. Across the evaluated domains, SURE takes on average approximately as long as RLLF-GUIDED and IDRL, and has comparable runtime to REACH and UNCERTAINTY. The successor-feature and reachability computations used by SURE and REACH, as well as the reward-uncertainty updates used by SURE and UNCERTAINTY, contribute only a small fraction of the total runtime relative to the repeated offline-learning updates. UNIFORM, which does not require adaptive model-based acquisition, remains the least computationally expensive method overall.
Relative to UNIFORM, the results expose an explicit label–compute trade-off. For example, on Maze2d-Large, SURE uses approximately more computation but reaches of the matched full-feedback return with approximately fewer reward labels. Thus, SURE is more computationally expensive than simple non-adaptive selection, but its wall-clock cost is comparable to existing informed adaptive approaches while yielding substantially greater label efficiency.
Sensitivity to the Warm-Start Size
Early in acquisition, the reward model and the reachability computed from its policy and value estimates may be unreliable. In all continuous-control experiments, adaptive acquisition therefore begins from uniformly sampled reward labels (Appendix § 9). To evaluate sensitivity to this choice, we vary the warm-start size while keeping the subsequent acquisition batch size fixed at . Table 6 reports the percentage feedback required to reach of the matched full-feedback return, averaged over 50 paired seeds.
| Domain | |||
| Maze2d-Large | 0.060% | 0.064% | 0.067% |
| HalfCheetah | 0.300% | 0.330% | 0.360% |
Table 6. Percentage feedback required by SURE to reach 80% of the matched full-feedback return under different warm-start sizes , averaged over 50 paired seeds.
The feedback required by SURE changes only marginally across the tested warm-start sizes, showing that its label efficiency is stable with respect to the initialization. This robustness is consistent with the design of the SURE score: the reachability measure in (10) mixes the successor-guided distribution with the empirical behavior distribution through , so inaccurate early value estimates cannot fully determine the acquisition distribution, and the multiplicative uncertainty factor in (11) further requires selected transitions to be informative for the reward model. The mild advantage of is also expected: fewer labels are spent on uniform initialization, allowing adaptive acquisition to begin earlier.
Limitations
Our theoretical analysis is stated under the linear-MDP model of Definition 1 and presumes that the chosen reference measure is admissible (Definition 3); when the offline pool fails to cover feature directions used by the optimal policy, no reward-labeling strategy can recover them. Finally, the offline-RL backbones considered in this work output continuous actions only; extending retained-label reward selection to more challenging settings, such as parameterized action spaces that combine discrete and continuous components, could be a direction for future work [41, 42, 44, 43].
References
- [1]Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312–2320, 2011.
- [2]Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, et al. Constitutional ai: Harmlessness from ai feedback. arXiv preprint arXiv:2212.08073, 2022.arxiv.org/abs/2212.08073
- [3]André Barreto, Will Dabney, Rémi Munos, Jonathan J. Hunt, Tom Schaul, Hado van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. In Advances in Neural Information Processing Systems, 2017.arxiv.org/abs/1606.05312
- [4]Erdem Bıyık, Malayandi Palan, Nicholas C. Landolfi, Dylan P. Losey, and Dorsa Sadigh. Asking easy questions: A user-friendly approach to active reward learning. In Proceedings of the 3rd Conference on Robot Learning, 2020.
- [5]Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAI Gym, 2016.
- [6]Shreyas Chaudhari, Renhao Zhang, Philip S. Thomas, and Bruno Castro da Silva. Which rewards matter? reward selection for reinforcement learning under limited feedback. arXiv preprint arXiv:2510.00144, 2025.arxiv.org/abs/2510.00144
- [7]Shreyas Chaudhari, Renhao Zhang, Philip S. Thomas, and Bruno Castro da Silva. Data selection for reward labeling in limited-feedback reinforcement learning. Transactions on Machine Learning Research, 2026. ISSN 2835-8856. URL https://openreview.net/forum?id=N8UIHGHSy.
- [8]Paul F. Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems, 2017.arxiv.org/abs/1706.03741
- [9]Christian Daniel, Oliver Kroemer, Malte Viering, Jan Metz, and Jan Peters. Active reward learning with a novel acquisition function. Autonomous Robots, 39(3):389–405, 2015.DOI
- [10]Peter Dayan. Improving generalization for temporal difference learning: The successor representation. Neural Computation, 5(4):613–624, 1993.DOI
- [11]Joseph A. DiMasi, Henry G. Grabowski, and Ronald W. Hansen. Innovation in the pharmaceutical industry: New estimates of R&D costs. Journal of Health Economics, 47:20–33, 2016. doi: 10.1016/j.jhealeco.2016.01.012.DOI
- [12]Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4RL: Datasets for deep data-driven reinforcement learning, 2020.arxiv.org/abs/2004.07219
- [13]Scott Fujimoto and Shixiang Shane Gu. A minimalist approach to offline reinforcement learning. In Advances in Neural Information Processing Systems, 2021.arxiv.org/abs/2106.06860
- [14]Rafael Gómez-Bombarelli, Jennifer N. Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sánchez-Lengeling, Dennis Sheberla, Jorge Aguilera-Iparraguirre, Timothy D. Hirzel, Ryan P. Adams, and Alán Aspuru-Guzik. Automatic chemical design using a data-driven continuous representation of molecules. ACS Central Science, 4(2):268–276, 2018. doi: 10.1021/acscentsci.7b00572.
- [15]Hao Hu, Yiqin Yang, Qianchuan Zhao, and Chongjie Zhang. The provable benefits of unsupervised data sharing for offline reinforcement learning. In International Conference on Learning Representations, 2023.arxiv.org/abs/2302.13493
- [16]Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Probably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory (COLT), 2020.arxiv.org/abs/1907.05388
- [17]Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In Proceedings of the 35th International Conference on Machine Learning, pages 2323–2332, 2018.arxiv.org/abs/1802.04364
- [18]Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline reinforcement learning? In Proceedings of the 38th International Conference on Machine Learning, 2021.
- [19]Ksenia Konyushkova, Konrad Zolna, Yusuf Ayter, Alexander Novikov, Scott Reed, Serkan Cabi, and Nando de Freitas. Semi-supervised reward learning for offline reinforcement learning, 2020.arxiv.org/abs/2012.06899
- [20]Ilya Kostrikov, Ashvin Nair, and Sergey Levine. Offline reinforcement learning with implicit q-learning. In International Conference on Learning Representations, 2022.arxiv.org/abs/2110.06169
- [21]David Krueger, Jan Leike, Owain Evans, and John Salvatier. Active reinforcement learning: Observing rewards at a cost, 2020.arxiv.org/abs/2011.06709
- [22]Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. In Advances in Neural Information Processing Systems, 2020.arxiv.org/abs/2006.04779
- [23]Yen-Ru Lai, Fu-Chieh Chang, and Pei-Yuan Wu. Leveraging unlabeled data sharing through kernel function approximation in offline reinforcement learning. Transactions on Machine Learning Research, 2025.arxiv.org/abs/2408.12307
- [24]Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Proceedings of the 36th International Conference on Machine Learning, pages 3703–3712, 2019.arxiv.org/abs/1903.08738
- [25]Anqi Li, Byron Boots, and Ching-An Cheng. Mahalo: Unifying offline reinforcement learning and imitation learning from observations. In Proceedings of the 40th International Conference on Machine Learning, 2023.arxiv.org/abs/2303.17156
- [26]David Lindner, Matteo Turchetta, Sebastian Tschiatschek, Kamil Ciosek, and Andreas Krause. Information directed reward learning for reinforcement learning. In Advances in Neural Information Processing Systems, 2021.arxiv.org/abs/2102.12466
- [27]Soichiro Nishimori, Xin-Qiang Cai, Johannes Ackermann, and Masashi Sugiyama. Offline reinforcement learning with domain-unlabeled data. In Reinforcement Learning Conference, 2025.arxiv.org/abs/2404.07465
- [28]Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems, 2022.arxiv.org/abs/2203.02155
- [29]Simone Parisi, Alireza Kazemipour, and Michael Bowling. Beyond optimism: Exploration with partially observable rewards. In Advances in Neural Information Processing Systems, 2024.arxiv.org/abs/2406.13909
- [30]Simone Parisi, Montaser Mohammedalamen, Alireza Kazemipour, Matthew E. Taylor, and Michael Bowling. Monitored Markov decision processes. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2024.arxiv.org/abs/2402.06819
- [31]Mariya Popova, Oxslandr Isayev, and Alexander Tropsha. Deep reinforcement learning for de novo drug design. Science Advances, 4(7):eaap7885, 2018. doi: 10.1126/sciadv.aap7885.DOI
- [32]Jean-Louis Reymond. The chemical space project. Accounts of Chemical Research, 48(3): 722–730, 2015. doi: 10.1021/ar500432k.DOI
- [33]Carlo Romeo and Andrew D. Bagdanov. Offline reinforcement learning with imputed rewards, 2024.arxiv.org/abs/2407.10839
- [34]Dorsa Sadigh, Anca D. Dragan, S. Shankar Sastry, and Sanjit A. Seshia. Active preference-based learning of reward functions. In Proceedings of Robotics: Science and Systems, 2017.DOI
- [35]Sebastian Schulze and Owain Evans. Active reinforcement learning with Monte-Carlo tree search, 2018.arxiv.org/abs/1803.04926
- [36]Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2nd edition, 2018.
- [37]Aaron David Tucker, Caleb Biddulph, Claire Wang, and Thorsten Joachims. Bandits with costly reward observations. In Conference on Uncertainty in Artificial Intelligence, 2023.
- [38]Nils Wilde, Dana Kulić, and Stephen L. Smith. Active preference learning using maximum regret. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2020.arxiv.org/abs/2005.04067
- [39]Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In Proceedings of the 37th International Conference on Machine Learning, pages 10746–10756, 2020.arxiv.org/abs/1905.10389
- [40]Tianhe Yu, Aviral Kumar, Yevgen Chebotar, Karol Hausman, Chelsea Finn, and Sergey Levine. How to leverage unlabeled data in offline reinforcement learning. In International Conference on Machine Learning, 2022.
- [41]Renhao Zhang, Haotian Fu, Yilin Miao, and George Konidaris. Model-based reinforcement learning for parameterized action spaces. In International Conference on Machine Learning, 2024.arxiv.org/abs/2404.03037
- [42]Renhao Zhang, Haotian Fu, Mingxi Jia, George Konidaris, Yilun Du, and Bruno Castro da Silva. From noise to control: Parameterized diffusion policies. In International Conference on Machine Learning, 2026.
- [43]Renhao Zhang, Mingzhe Li, and Bruno Castro da Silva. Latent barrier steering: Hierarchical safety for generative planning. In Advances in Neural Information Processing Systems, 2026.arxiv.org/abs/2611.13227
- [44]Renhao Zhang, Mingzhe Li, Yuli Li, Jiayu Zheng, and Yilin Miao. Learning what to keep: Evidence-gated parameterized skills for frozen LLM agents. In NeurIPS 2026 Workshop on Test-Time Continual Learning, 2026.
- [45]Konrad Zolna, Alexander Novikov, Ksenia Konyushkova, Caglar Gulcehre, Ziyu Wang, Yusuf Aytar, Misha Denil, Nando de Freitas, and Scott Reed. Offline learning from demonstrations and unlabeled experience, 2020.arxiv.org/abs/2011.13885


