Transductive Reward Inference on Graph

Bohao Qu, Xiaofeng Cao, Qing Guo, Yi Chang, Ivor W. Tsang, Chengqi Zhang

TL;DR

The TRAIN (Transductive RewArds INference) framework addresses a major bottleneck in offline reinforcement learning: the scarcity of reward labels. By modeling state-action pairs as nodes in a graph and propagating rewards from a small set of human-annotated samples to the rest of the dataset, TRAIN enables effective policy learning in "reward-blind" scenarios.

What Problem Does This Paper Address?

Offline Reinforcement Learning (RL) aims to learn optimal behaviors from fixed, pre-recorded datasets without further environment interaction. This is crucial for fields like healthcare or autonomous driving, where "trial and error" is dangerous or unethical.

However, there is a catch: most real-world datasets are "unlabelled"—they contain sequences of states and actions but lack the reward signals needed to tell the agent what it's doing right. Manually annotating millions of data points is prohibitively expensive. Existing methods often rely on binary "success/failure" labels for entire episodes, which provides too little information, or require expert demonstrations, which aren't always available. The authors tackle the challenge of reward inference: how can we accurately estimate rewards for a massive unlabelled dataset using only a tiny fraction of human-annotated samples?

Methods

The authors introduce TRAIN, which stands for Transductive RewArds INference with Propagation Graph. The approach consists of three main steps:

  1. Reward Propagation Graph Construction: Every state-action pair $(s, a)$ in the dataset is treated as a node in a graph. To determine how "similar" two nodes are (the edge weight), the authors decompose states and actions into multiple sub-factors (e.g., joint angles, torso height, specific motor torques). A learnable reward-shaping function $f_\Theta$ tunes the contribution of these factors to the edge weights.
  2. Transductive Inference: Unlike inductive learning (which learns a general rule to apply to new data), transductive learning reasons directly from observed training cases to specific "test" cases (the unlabelled data already in the dataset). Rewards are propagated from labelled nodes to unlabelled ones through an iterative message-passing process. The authors mathematically prove that this process converges to a unique fixed point.
  3. Policy Learning: Once the rewards are inferred, the "completed" dataset is plugged into a standard offline RL algorithm—in this case, Critic-Regularized Regression (CRR)—to train the final policy.

Datasets

The researchers evaluated TRAIN on two major benchmarks for continuous control:

  • Meta-World: A suite of over 40 robotic manipulation tasks (e.g., opening a drawer, pressing a button, using a hammer).
  • DeepMind Control Suite (DMC): A set of locomotion tasks (e.g., Cheetah Run, Walker Walk, Humanoid).
  • Image-based variants: They also tested the model's ability to handle raw pixel inputs by treating RGB channels and frames as distinct factors in the graph construction.

Key Insights and Ideas

  • Multi-Factor Decomposition is Key: One of the "aha" moments is that treating a state as a single vector is less effective than breaking it down. By looking at sub-components (like the velocity of a specific joint vs. the height of the torso), the graph can more accurately capture the "contextual properties" that lead to rewards.
  • Inherent Smoothness: Because graph propagation aggregates information from neighbors, the resulting reward function is naturally "smooth." This prevents the RL agent from over-fitting to noisy or sparse signals, making the training process significantly more stable.
  • Mathematical Guarantee: The authors provide a proof of convergence. By showing that the transition matrix $W_{UU}$ (weights between unlabelled nodes) has values less than 1, they demonstrate that the iterative inference formula eventually settles into a stable solution.

Key Results

TRAIN consistently outperformed several strong baselines, including Behavior Cloning (BC), Time-guided rewards (TGR), and Unlabelled Data Sharing (UDS):

  • Superior Success Rates: In Meta-World tasks like "Box Close" and "Pick Place," TRAIN achieved success rates and returns that were often double or triple those of the baselines (e.g., 3897 vs 1371 for Box Close).
  • Label Efficiency: The authors found that annotating only 10% to 15% of the data was sufficient to achieve high performance on most tasks.
  • Robustness to Modality: The system worked remarkably well on image-based tasks, showing that the graph-based approach can scale from low-dimensional state vectors to high-dimensional visual data.

Limitations and Future Work

  • Computational Complexity: Constructing a graph for a dataset with millions of points is computationally heavy. The authors currently mitigate this by "slicing" the dataset into smaller segments (e.g., 10,000 to 40,000 pairs at a time). While effective, this is a heuristic.
  • Sequential Slicing: The current slicing method assumes that "similar" data points are located near each other in the recorded sequence. Future work could explore more sophisticated ways to cluster data before graph construction.
  • Human-in-the-loop: While the paper uses ground-truth rewards to simulate human labels, real human annotations are often noisier. Testing TRAIN with actual, imperfect human "sketches" or preferences is a logical next step.

Summary updated

Abstract

In this study, we present a transductive inference approach on that reward information propagation graph, which enables the effective estimation of rewards for unlabelled data in offline reinforcement learning. Reward inference is the key to learning effective policies in practical scenarios, while direct environmental interactions are either too costly or unethical and the reward functions are rarely accessible, such as in healthcare and robotics. Our research focuses on developing a reward inference method based on the contextual properties of information propagation on graphs that capitalizes on a constrained number of human reward annotations to infer rewards for unlabelled data. We leverage both the available data and limited reward annotations to construct a reward propagation graph, wherein the edge weights incorporate various influential factors pertaining to the rewards. Subsequently, we employ the constructed graph for transductive reward inference, thereby estimating rewards for unlabelled data. Furthermore, we establish the existence of a fixed point during several iterations of the transductive inference process and demonstrate its at least convergence to a local optimum. Empirical evaluations on locomotion and robotic manipulation tasks validate the effectiveness of our approach. The application of our inferred rewards improves the performance in offline reinforcement learning tasks.
BibTeX
@article{qu2024transductive,
  author = {Bohao Qu and Xiaofeng Cao and Qing Guo and Yi Chang and Ivor W. Tsang and Chengqi Zhang},
  title = {{Transductive Reward Inference on Graph}},
  journal = {IEEE Transactions on Knowledge and Data Engineering},
  year = {2024},
  url = {https://openreview.net/forum?id=0SZnXMWOI9},
}
Figure