# Beyond Simple Sum of Delayed Rewards: Non-Markovian Reward Modeling for Reinforcement Learning

arXiv: https://arxiv.org/abs/2410.20176 · HTML: https://mlsanity.com/paper/2410.20176/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation.
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 26 Oct 2024.

## Placed in

- LLM alignment / RLHF / preference optimisation / [Reward modeling and RLHF](https://mlsanity.com/alignment/reward-modeling-and-rlhf/)
- Deep reinforcement learning methods / [Interpretable and logic-guided RL](https://mlsanity.com/deeprl/interpretable-and-logic-guided-rl/)

## Builds on (most cited first, 22 of 22)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [A Brief Survey of Deep Reinforcement Learning](https://mlsanity.com/paper/1708.05866/) (2017)
- [Reinforcement Learning in Healthcare: A Survey](https://mlsanity.com/paper/1908.08796/) (2019)
- [Stabilizing Transformers for Reinforcement Learning](https://mlsanity.com/paper/1910.06764/) (2019)
- [Deep Reinforcement Learning framework for Autonomous Driving](https://mlsanity.com/paper/1704.02532/) (2017)
- [RUDDER: Return Decomposition for Delayed Rewards](https://mlsanity.com/paper/1806.07857/) (2018)
- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [On Learning Intrinsic Rewards for Policy Gradient Methods](https://mlsanity.com/paper/1804.06459/) (2018)
- [Preference Transformer: Modeling Human Preferences using Transformers for RL](https://mlsanity.com/paper/2303.00957/) (2023)
- [Reinforcement Learning with Trajectory Feedback](https://mlsanity.com/paper/2008.06036/) (2020)
- [Align-RUDDER: Learning From Few Demonstrations by Reward Redistribution](https://mlsanity.com/paper/2009.14108/) (2020)
- [Learning Long-Term Reward Redistribution via Randomized Return Decomposition](https://mlsanity.com/paper/2111.13485/) (2021)
- [Learning Guidance Rewards with Trajectory-space Smoothing](https://mlsanity.com/paper/2010.12718/) (2020)
- [Sequence Modeling of Temporal Credit Assignment for Episodic Reinforcement Learning](https://mlsanity.com/paper/1905.13420/) (2019)
- [Synthetic Returns for Long-Term Credit Assignment](https://mlsanity.com/paper/2102.12425/) (2021)
- [Off-Policy Reinforcement Learning with Delayed Rewards](https://mlsanity.com/paper/2106.11854/) (2021)
- [Non-Markovian Reward Modelling from Trajectory Labels via Interpretable Multiple Instance Learning](https://mlsanity.com/paper/2205.15367/) (2022)
- [Exploiting Transformer in Sparse Reward Reinforcement Learning for Interpretable Temporal Logic Motion Planning](https://mlsanity.com/paper/2209.13220/) (2022)
- [Off-Policy Evaluation for Human Feedback](https://mlsanity.com/paper/2310.07123/) (2023)

## Built on by (most cited first, 2 of 2)

- [PRISM: Parallel Reward Integration with Symmetry for MORL](https://mlsanity.com/paper/2602.18277/) (2026)
- [Live LTL Progress Tracking: Towards Task-Based Exploration](https://mlsanity.com/paper/2604.17106/) (2026)

## Abstract (arXiv)

Reinforcement Learning (RL) empowers agents to acquire various skills by learning from reward signals. Unfortunately, designing high-quality instance-level rewards often demands significant effort. An emerging alternative, RL with delayed reward, focuses on learning from rewards presented periodically, which can be obtained from human evaluators assessing the agent's performance over sequences of behaviors. However, traditional methods in this domain assume the existence of underlying Markovian rewards and that the observed delayed reward is simply the sum of instance-level rewards, both of which often do not align well with real-world scenarios. In this paper, we introduce the problem of RL from Composite Delayed Reward (RLCoDe), which generalizes traditional RL from delayed rewards by eliminating the strong assumption. We suggest that the delayed reward may arise from a more complex structure reflecting the overall contribution of the sequence. To address this problem, we present a framework for modeling composite delayed rewards, using a weighted sum of non-Markovian components to capture the different contributions of individual steps. Building on this framework, we propose Composite Delayed Reward Transformer (CoDeTr), which incorporates a specialized in-sequence attention mechanism to effectively model these contributions. We conduct experiments on challenging locomotion tasks where the agent receives delayed rewards computed from composite functions of observable step rewards. The experimental results indicate that CoDeTr consistently outperforms baseline methods across evaluated metrics. Additionally, we demonstrate that it effectively identifies the most significant time steps within the sequence and accurately predicts rewards that closely reflect the environment feedback.