Reward Decomposition for High Dimensional Action Spaces

This direction is split into other directions: additive reward decomposition. Its last version stays readable and citable here.

Version 1 of 170 papers89 conceptsfrozen 2026-10-04

In most reinforcement learning and bandit settings, an agent receives a single scalar reward—a "score" that summarizes the quality of its actions. While simple, this scalar is often too blunt a tool for complex environments. If an agent chooses a "slate" of ten movies to show a user, or performs a thousand steps to solve a puzzle, a single reward number doesn't explain which movie the user liked or which step was the breakthrough.

To overcome this, a growing body of research focuses on reward decomposition: the practice of breaking a global reward into constituent parts. By modeling rewards as sums or products of underlying factors, researchers are bypassing the "curse of dimensionality" and making intractable problems solvable.

Breaking the Combinatorial Explosion

The most immediate benefit of decomposition is in combinatorial optimization. When an agent must choose a subset of items (like network edges or ad placements), the number of possible combinations grows exponentially. Treating every combination as a unique "arm" to pull is impossible.

Yi Gai, Rahul Jain, and Bhaskar Krishnamachari demonstrated in Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards that if the reward of a complex action is simply the sum of its parts, we only need to learn the properties of those individual parts. This turns an exponential search space into a linear one.

This "additive" assumption is a powerful inductive bias. For instance, in Distributional Off-Policy Evaluation for Slate Recommendations, David Arbour and colleagues show that even if the world isn't perfectly additive, assuming it is allows for much more efficient evaluation of "slates" (grids of items) by focusing on slot-level interactions rather than every possible item combination.

Isolating Signal from Artifacts

Decomposition is also a defense mechanism against "reward hacking," where models exploit superficial features to get high scores. In the context of Large Language Models (LLMs), a reward model might mistakenly reward a response just because it is long or well-formatted, rather than helpful.

Jie Ren, Tianqi Liu, and Wei Xiong address this in RRM: Robust Reward Model Training Mitigates Reward Hacking. Their Robust Reward Model (RRM) framework decomposes the reward into:

  1. Contextual signals: How well the response matches the specific prompt.
  2. Context-free artifacts: Superficial features like length or formatting.

By explicitly decoupling these, the model can be trained to ignore the artifacts, leading to higher-quality alignment. Similarly, Liyuan Mao and Chenjia Bai use information-theoretic objectives in Information-Theoretic Reward Decomposition for Generalizable RLHF to ensure the reward model actually "reads" the prompt instead of relying on internal response-only biases.

Solving the Credit Assignment Problem

In long-horizon tasks, the reward often arrives only at the very end. This makes it difficult to know which of the many preceding actions was actually responsible for the success.

Researchers have used decomposition to "redistribute" this final reward back through time. In Synthetic Returns for Long-Term Credit Assignment, Adam Santoro and Greg Wayne propose modeling the total reward as a sum of contributions from previously visited states. This allows the agent to skip over irrelevant events and assign credit directly to the critical actions that happened much earlier.

A similar logic applies to Randomized Return Decomposition (RRD) by Ruihan Guo and Jian Peng. By training on random subsequences, they decompose episodic feedback into dense, step-wise rewards, providing the agent with a constant stream of training signals rather than a single, sparse terminal reward.

Beyond Addition: Multiplicative and Residual Models

While additive decomposition is common, other structures are emerging for specific problems:

By moving away from the monolithic scalar reward and toward these structured decompositions, machine learning systems can finally tackle environments where the number of possible choices—and the paths to reach them—are otherwise overwhelming.

Papers in this version

Showing 60 of 70 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_reward_decomposition_for_high_dimensiona_432cf341,
  title = {Reward Decomposition for High Dimensional Action Spaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/reward-decomposition-for-high-dimensional-action-spaces/rdr_432cf341dae94e659e1f0bad5768f7d6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_reward_decomposition_for_high_dimensiona_432cf341_v1,
  title = {Reward Decomposition for High Dimensional Action Spaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/reward-decomposition-for-high-dimensional-action-spaces/rdr_432cf341dae94e659e1f0bad5768f7d6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}