Non-Markovian Reward Modelling from Trajectory Labels via Interpretable Multiple Instance Learning

Joseph Early, Tom Bewley, Christine Evers, Sarvapali D. Ramchurn

Abstract

Standard Reward Modelling (RM) assumes the Markov property, where rewards depend only on the current state and action. However, human evaluations often incorporate historical context, leading to non-Markovian reward signals. This paper addresses the challenge of learning these rewards from trajectory-level labels by framing RM as a Multiple Instance Learning (MIL) problem. We propose LSTM-based MIL architectures, specifically the Concatenated Skip Connection (CSC) model, to reconstruct hidden temporal dependencies from simple trajectory-level labels. Our results demonstrate that these models can accurately recover per-step rewards and enable RL agents to match or even exceed the performance of those trained on ground-truth oracle rewards.

Introduction

In standard Reinforcement Learning (RL), the reward function is typically assumed to be Markovian: the reward for an action depends only on the current state and action. However, real-world human feedback often violates this assumption. Human psychology is influenced by memory and context—for instance, a robot's action might be judged based on whether it previously completed a necessary prerequisite. If the agent's state representation lacks this history, the reward becomes non-Markovian.

The core difficulty lies in learning a per-step reward function when only a single label (the total return of a trajectory) is available. This paper bridges this gap by identifying a structural isomorphism between Reward Modelling and Multiple Instance Learning (MIL), where trajectories are treated as "bags" of instances (timesteps).

Comparison of Markovian (left) and Non-Markovian (right) Reward Modelling frameworks.

Methodology: Reward Modelling as MIL

In the MIL framework, data is organized into "bags" of instances. A label is provided for the entire bag, but the labels for individual instances are hidden. By mapping trajectories to bags and state-action pairs to instances, the total return becomes the bag label.

To solve this, the authors propose several architectures, focusing on capturing temporal dependencies. The standout model is the Concatenated Skip Connection (CSC) Instance Space LSTM. This model uses an LSTM to maintain a hidden state ($h$) that accumulates historical information. Crucially, the reward-predicting head receives both this hidden state (the past) and the current state-action pair (the present). This allows the model to "disentangle" what is happening now from the historical context required to evaluate it.

Proposed MIL architectures for reward modelling, ranging from simple NN to the CSC Instance Space LSTM.

Experimental Setup and Tasks

The approach was validated on five custom non-Markovian RL environments requiring memory:

  • Timer/Moving: Tasks requiring tracking of elapsed time to receive rewards.
  • Key: A sequential task where a "key" must be collected before a "treasure" zone provides any reward.
  • Charger: A task where reward scales based on how long the agent spent in a previous "charging" zone.
  • Lunar Lander (Modified): A complex control task where the lander must stay on a pad for a set duration before taking off.

Key Results and Insights

1. Accuracy and Interpretability

The CSC Instance Space LSTM consistently achieved the lowest error in reconstructing both trajectory returns and hidden per-step rewards. Furthermore, the model's internal representations are interpretable. When the LSTM's hidden state was constrained to 2D, visualizations showed the model naturally "discovering" latent variables like "has key" or "timer status," even though these were never explicitly provided in the input data.

2. The "Better-than-Oracle" Phenomenon

Surprisingly, RL agents trained on these learned MIL rewards often outperformed those trained on ground-truth oracle rewards. This is attributed to "reward shaping": the MIL model tends to create smoother reward gradients (funnels) that guide the agent toward the goal more effectively than the potentially sparse or "stiff" oracle rewards.

3. Robustness to Noise

The models demonstrated significant resilience to label noise. In experiments, the CSC model could still accurately predict rewards even when 30% of the trajectory labels in the training set were swapped or noisy.

Conclusion

This work demonstrates that non-Markovian rewards can be effectively recovered from trajectory-level labels using interpretable MIL architectures. By leveraging LSTMs with skip connections, the models can reconstruct missing state information and provide high-quality reward signals for RL. Future work includes scaling these methods to high-dimensional state spaces, such as raw pixels, and exploring online training regimes where the reward model and policy are co-optimized.

Summary updated

Abstract

We generalise the problem of reward modelling (RM) for reinforcement learning (RL) to handle non-Markovian rewards. Existing work assumes that human evaluators observe each step in a trajectory independently when providing feedback on agent behaviour. In this work, we remove this assumption, extending RM to capture temporal dependencies in human assessment of trajectories. We show how RM can be approached as a multiple instance learning (MIL) problem, where trajectories are treated as bags with return labels, and steps within the trajectories are instances with unseen reward labels. We go on to develop new MIL models that are able to capture the time dependencies in labelled trajectories. We demonstrate on a range of RL tasks that our novel MIL models can reconstruct reward functions to a high level of accuracy, and can be used to train high-performing agent policies.
BibTeX
@inproceedings{early2022non,
  author = {Joseph Early and Tom Bewley and Christine Evers and Sarvapali D. Ramchurn},
  title = {{Non-Markovian Reward Modelling from Trajectory Labels via Interpretable Multiple Instance Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=aBHyxGcmFP},
}
Figure