Label only a sliver of rewards: SURE multiplies successor reachability by reward uncertainty to approach full-feedback performance with far fewer labels
Synopsis
When only a tiny fraction of transitions in an offline dataset can receive reward labels, SURE multiplies two signals, which states can reach currently high-value states and where the reward model remains uncertain, to decide where the next label goes. Queried rewards are retained to fit a reward model that annotates the remaining transitions. On Maze2d-Medium, Maze2d-Large and HalfCheetah, the feedback fractions SURE needs to reach 95% of the full-feedback reference were the lowest among all methods, at 0.20%, 0.15% and 0.71% respectively.
Interpretation
Reward-label selection shifts from feeding queried rewards straight into policy learning to retaining them for reward-model training, so the chosen labels can annotate the whole offline dataset. Earlier limited-feedback reward selection treated downstream policy learning as a black box and did not retain queried rewards for reward-model training; partially labeled offline RL used a reward model to impute labels but assumed the labeled subset was passively given. In finite environments built to satisfy the linear-MDP assumptions exactly, SURE and Exact Gain, which computes the exact one-step gain, required identical label counts at every threshold in both state sizes, while Uniform needed more.
The selection rule multiplies multi-step reachability from successor features by the reward model's local uncertainty, preferring transitions that both lead to currently high-value states and remain uncertain. Reachability alone fails when current value estimates are inaccurate, and uncertainty alone spends labels in regions unrelated to high-return behavior, so the two single-factor variants each win in different domains. Across TwoRooms, Maze2d-Medium, Maze2d-Large and HalfCheetah, every method shares the same reward-free dataset and the same retained-label pipeline, with results averaged over 50 trials.
The feedback needed to match a given fraction of full-feedback performance drops to a small percentage, and the advantage does not depend on a single offline RL backbone. At the 95% level SURE required the least feedback in all four domains; on Maze2d-Medium it needed 0.20% against 0.32% for IDRL, the strongest non-SURE method there, and on HalfCheetah 0.71% against 2.49% for Uncertainty, the strongest non-SURE method there. Replacing IQL with CQL or TD3+BC on Maze2d-Medium and HalfCheetah kept SURE's required feedback fraction far below Uniform, for example 0.52% versus 2.36% on HalfCheetah under TD3+BC.
Perspective
The demonstrated setting is retained-label reward selection on a fixed reward-free offline dataset: linear-MDP environments validate label efficiency when the theoretical assumptions hold, and continuous-control experiments cover TwoRooms, Maze2d-Medium, Maze2d-Large and HalfCheetah with IQL, CQL and TD3+BC backbones. The theory requires the chosen reference measure to be admissible.
The theoretical results rest on the linear-MDP assumption and on an admissible reference measure; if the offline pool does not cover feature directions used by the optimal policy, no reward-labeling strategy can recover them from labels alone. The offline backbones considered output continuous actions only, and parameterized action spaces are listed as future work.
