Offline reinforcement learning trains a decision-making policy from a fixed log of past behavior, with no new interaction. When that log carries no numeric rewards and only human judgments such as "trajectory A was better than trajectory B," the agent must first infer which states were good. The inference is badly underdetermined. A comparison between two whole trajectories says little about any single state in them, and theory shows the learner needs the dataset to cover entire trajectories of the target policy, not just individual steps (Provable Offline Preference-Based Reinforcement Learning). The natural remedy is to share credit across trajectories that pass through the same places. Concretely, we would build a graph whose nodes are clustered states and whose edges are logged transitions, then smooth the inferred reward over it. This proposal argues that the obvious way to do that smoothing fails in a specific, predictable way.
Offline transition graphs are sparse and lopsided. Start regions and corridors are visited by thousands of trajectories and become hubs. Rare excursions leave tree-like dead ends hanging off the main graph by a single edge. On such graphs, the standard tools behind graph smoothing (eigenvectors of the Laplacian and the polynomial filters built from it) are known to pile their mass onto hubs and dead ends instead of spreading over meaningful global structure. This failure is called eigenvector localization. In offline RL those dead ends are exactly the poorly covered regions where value estimates are most prone to hallucination. We propose two linked fixes. First, run the reward-smoothing filter on the Bethe-Hessian, an operator known to resist localization, so that preference credit spreads along global structure. Second, treat the localized modes of the ordinary Laplacian as a coverage detector, and use them to make the reward pessimistic exactly where the data is thin.
Core Claim
When per-state rewards are learned from trajectory-level preferences and propagated over the offline transition graph, the choice of graph operator matters. A Chebyshev polynomial filter on a degree-corrected Bethe-Hessian, combined with a pessimism penalty equal to the reward's energy in the Laplacian's localized modes, should yield better downstream offline policies per preference query than three alternatives: graph-free neural reward models, Laplacian-based filters, and positively regularized Laplacian filters. The advantage should be largest when preferences combine objectives non-linearly, for example when a safety failure vetoes the whole trajectory. In that regime, a non-linear reward model needs structural regularity to avoid the sample-complexity blow-up that general function classes suffer.
What is new is not "a graph neural network for rewards." It is the observation that localization does two jobs in this setting. It is a defect to remove from the propagation operator, and it is also a signal to keep as an uncertainty estimate. A regularizer that simply suppresses dead ends throws the second job away.
Prior Work and Where This Sits
The localization problem and its operator-level cures supply the method. Hubs in sparse graphs produce outlier eigenvalues that drown out community structure (Community detection thresholds and the weak Ramanujan property). Rows with unusually many entries pull leading eigenvectors onto single nodes (Matrix Completion from Fewer Entries). Low-conductance dangling trees capture whole eigenvectors (Understanding Regularized Spectral Clustering via Graph Conductance). The non-backtracking matrix, which forbids a walk from immediately stepping back along the edge it came from, removes these artifacts (Non-backtracking Spectrum of Random Graphs), but it lives on directed edges and is non-symmetric.
The Bethe-Hessian is a symmetric node-sized relative,
$$H(r) = (r^2-1)I - rA + D,$$
where $A$ is the adjacency matrix, $D$ the diagonal degree matrix, and $r$ a scale parameter. With $r$ near the square root of the average degree, its informative eigenvalues fall below zero while the uninformative bulk stays positive (Spectral Clustering of graphs with the Bethe Hessian; Community detection with the Bethe-Hessian). We reuse this operator directly. Because the fixed choice of $r$ is tuned for homogeneous random graphs and offline graphs are heterogeneous, we instead set $r$ from a power-iteration estimate of the non-backtracking spectral radius, as the localization literature recommends.
The filter machinery comes from spectral graph convolution. Chebyshev polynomial filters apply a learned function of an operator using $K$ sparse matrix-vector products, with strict $K$-hop locality (Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering). Bernstein filters add non-negativity guarantees at quadratic cost in the polynomial order (BernNet). All of this work assumes a Laplacian on a static benchmark graph. We swap the operator and the application.
Two existing papers sit closest on the operator side, and both stop short of learned filtering for decision-making. Non-backtracking Graph Neural Networks brings non-backtracking ideas into message passing on edge states and doubles F1 on PascalVOC-SP, but it defines no polynomial spectral filter and never touches control. InfraredGP shifts eigenvalues negative for training-free graph partitioning and explicitly leaves open how such corrections interact with learned polynomial filters.
On the RL side, three papers motivate the gap. Spectral Decomposition Representation for Reinforcement Learning factorizes the transition operator with a singular value decomposition and is exposed to the same localization on sparse buffers. It also uses numeric rewards, not preferences. Graph-Assisted Stitching builds exactly the kind of clustered state graph we need and reports 88.3 success on OGBench AntMaze-giant-stitch, but it only runs shortest-path search over goal distances. The theory of Provable Offline Preference-Based RL constrains us: it proves the per-trajectory coverage requirement and gives a confidence-set pessimism scheme whose deep-network version needs heuristic relaxations. Our localization penalty is one such relaxation that comes with a structural justification. Preference Elicitation for Offline RL sidesteps coverage by having a learned world model invent trajectories to show the human, but it treats states as unstructured vectors and preferences as scalar.
On non-linear preferences, weighted-sum scalarization is documented to misrepresent real trade-offs (Zhou et al.; Rame et al.). Rubric work notes that a failed non-negotiable criterion should zero out utility (Chasing the Tail). Offline multi-objective methods still condition on linear preference vectors (PEDA/D4MORL; MODULI). We use this regime as the stress test, not as the mechanism.
Research Program
The pipeline has four parts: building the graph, the reward model, the pessimism penalty, and policy learning.
To build the graph, we cluster dataset states into nodes using the temporal-distance embedding and efficiency filtering of Graph-Assisted Stitching. We add an edge for every logged transition between clusters and symmetrize the edges for the Bethe-Hessian. Directed operators remain an acknowledged open problem (Complex non-backtracking matrix for directed graphs).
The reward model is
$$r_\theta = \sum_{k=0}^{K} \theta_k\, T_k(\tilde H)\, f_\phi(X),$$
where $X$ holds node state features, $f_\phi$ is a small multilayer perceptron producing per-node attribute scores, $T_k$ are Chebyshev polynomials, and $\tilde H$ is $H(r)$ rescaled to $[-1,1]$. A non-linear head then combines the attribute channels, for example a learned soft-minimum that can express a veto. We train it with a Bradley-Terry likelihood on summed node rewards along each compared trajectory.
The penalty works as follows. Let $\{v_j\}$ be the eigenvectors of the ordinary normalized Laplacian whose inverse participation ratio, a standard measure of how concentrated a vector's mass is, exceeds a threshold. We define the uncertainty $u(s) = \sum_j \langle r_\theta, v_j\rangle^2 v_j(s)^2$ and train the policy on the reward $r_\theta - \beta u$. For large graphs we compute only the few dozen extreme eigenpairs with Lanczos iterations.
Downstream policy learning uses Conservative Q-Learning, the most robust D4RL method in D4RL, applied to relabeled rewards. That way, differences come from the reward model alone.
Alongside the empirical work, we will analyze a tabular version of the method. The aim is to show that when trajectories share states, filtered propagation replaces the per-trajectory coverage coefficient with a coverage notion over graph-connected segments. We will also show that the localization penalty upper-bounds reward error on dangling sets. We treat this as a hypothesis to prove or refute, not a promised result.
Baselines
The naive reference point is a per-state multilayer-perceptron reward trained with Bradley-Terry on the same preference pairs, fed into the same Conservative Q-Learning setup. It shows whether any graph structure helps at all.
The strongest graph-free competitor is an ensemble of such reward models. It is penalized by ensemble disagreement, a practical stand-in for the confidence-set pessimism of Provable Offline Preference-Based RL. This is the method most likely to match ours, because disagreement also grows in poorly covered regions.
The strongest published method on preference-query efficiency is Sim-OPRL. It reports reaching a suboptimality gap of 20 on the Sepsis simulator in roughly 225 queries, against over 600 for the standard offline baseline, and target performance on Star MDP in 4 queries versus 30. Sim-OPRL may query invented trajectories while we query only logged ones. We will therefore run it in its native mode under the same query budget, and also run a hybrid in which our reward model replaces its reward learner. Beating it means a lower query count to the same gap on Sepsis, or matching it without a world model.
For long-horizon navigation, GAS's reported 88.3 on AntMaze-giant-stitch was obtained with goal rewards rather than preferences. We treat it as a ceiling, not a competitor.
The ablations isolate the key ingredient by keeping the architecture, polynomial order, preference data, and tuning budget identical (the same number of hyperparameter trials per method, chosen on held-out preference likelihood, never on environment return). Only the operator and the penalty change. The operator variants are the normalized Laplacian (ChebNet's operator), the positively regularized Laplacian of Zhang et al., the negatively shifted operator of InfraredGP, and the Bethe-Hessian. We also run the Bethe-Hessian filter without the penalty, the penalty with a graph-free reward, and an edge-state reward model in the style of Non-backtracking GNNs. A final variant uses fixed representations from SPEDER as features for the multilayer-perceptron reward.
Why not just…?
Why not just use a larger reward ensemble with disagreement pessimism? This is the most serious threat. Ensembles do flag uncovered states, but nothing ties their members to the dataset's connectivity. Members can agree confidently on a dead end they all extrapolate into in the same way. That is the failure the localization penalty targets, since dangling sets are identified structurally rather than through model variance. The decisive test is the planted dead-end experiment below: if ensemble disagreement correlates with true reward error on dangling nodes as well as our penalty does, the penalty adds nothing and we will say so.
Why not just regularize the Laplacian with a positive degree shift, which is known to fix dangling-set overfitting? A positive shift suppresses localized modes, which is good for propagation, but it discards them. Our method needs them as an uncertainty signal. The regularized-Laplacian filter, both with our penalty (computed on the unregularized Laplacian) and without it, is a full ablation arm. If it plus the penalty ties the Bethe-Hessian filter, the honest conclusion is that the penalty, not the operator, carries the result. The proposal would narrow accordingly.
Why not just let a non-backtracking message-passing network learn the reward? NBA-GNN removes backtracking echoes and shows large gains on sparse benchmarks, for example Wisconsin accuracy rising from 0.6059 to 0.7471. However, it stores state on directed edges and so scales with twice the edge count. It also offers no spectral handle for reading off localized modes. We run it at matched parameter count. If it wins on return, the operator insight still holds, but our filter form loses.
Why not just invent trajectories with a world model, as Sim-OPRL does? On sparse buffers, model rollouts drift out of distribution, and the human then labels trajectories the agent cannot reproduce. Graph propagation needs no model. The two are also complementary, which the hybrid arm tests.
Proposed Experiments
The first check can kill the idea early. We compute inverse participation ratios of Laplacian eigenvectors on the clustered graphs from D4RL AntMaze (medium and large, diverse and play splits) and OGBench AntMaze-giant-stitch. If those graphs show no meaningful localization after GAS-style filtering, the premise fails and we stop.
Second, in a synthetic gridworld with planted dangling corridors, we measure how strongly each method's uncertainty correlates with true reward error. We also measure how far reward hallucination spreads into the corridors under each operator.
Third, the main evaluation uses D4MORL Hopper, HalfCheetah, and Walker2d. We relabel preferences with three utility functions: a linear one, a product of objectives, and a veto in which falling below a threshold on one objective zeroes utility. We report true utility of the learned policy and hypervolume at query budgets from 100 to 5,000 pairs. For context, PEDA reports a hypervolume of 5.77 × 10⁶ on HalfCheetah under linear preferences. For the non-linear relabelings there is no reported result found on Lacuna, so all arms are run by us. The prediction is that the gap over graph-free baselines widens from the linear to the veto relabeling.
Fourth, we test preference-labeled AntMaze and OGBench stitching with synthetic preferences derived from goal progress, reporting success rate, plus the Sepsis and Star MDP environments, reporting queries to a fixed suboptimality gap against Sim-OPRL's published counts.
The proposal succeeds if the Bethe-Hessian filter with the localization penalty beats the ensemble baseline at equal query budget on the veto relabeling and on AntMaze, and if its advantage disappears on graphs that the first check finds non-localized. That second condition would show the mechanism, not just extra capacity, is doing the work.
References
- Provable Offline Preference-Based Reinforcement Learning
- Community detection thresholds and the weak Ramanujan property
- Matrix Completion from Fewer Entries: Spectral Detectability and Rank Estimation
- Understanding Regularized Spectral Clustering via Graph Conductance
- Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs
- Spectral Clustering of graphs with the Bethe Hessian
- Community detection with the Bethe-Hessian
- Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
- BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation
- Non-backtracking Graph Neural Networks
- InfraredGP: Efficient Graph Partitioning via Spectral Graph Neural Networks with Negative Corrections
- Spectral Decomposition Representation for Reinforcement Learning
- Graph-Assisted Stitching for Offline Hierarchical Reinforcement Learning
- Preference Elicitation for Offline Reinforcement Learning
- Beyond One-Preference-Fits-All Alignment: Multi-Objective Direct Preference Optimization
- Rewarded soups: towards Pareto-optimal alignment by interpolating weights fine-tuned on diverse rewards
- Chasing the Tail: Effective Rubric-based Reward Modeling for Large Language Model Post-Training
- Scaling Pareto-Efficient Decision Making via Offline Multi-Objective RL
- MODULI: Unlocking Preference Generalization via Diffusion Models for Offline Multi-Objective Reinforcement Learning
- Complex non-backtracking matrix for directed graphs
- D4RL: Datasets for Deep Data-Driven Reinforcement Learning.