Additive Reward Decomposition for Combinatorial Optimization

24 concepts18 papers1 proposal

In many real-world sequential decision-making problems, an "action" is not a single discrete choice, but a combination of choices. For instance, in web recommendation, an algorithm must select a "slate" or list of items to display. If a system chooses $k$ items out of a catalog of size $N$, the number of possible actions scales combinatorially. Similarly, in network routing or multi-agent congestion games, an action corresponds to a path through a graph—a specific subset of edges or shared facilities.

If we treat each unique combination as an independent choice (or "arm" in a multi-armed bandit framework), learning becomes impossible. The system suffers from an exponential explosion of the action space, meaning it rarely encounters the exact same combination twice. This "curse of dimensionality" severely hinders sample efficiency in domains ranging from wireless channel access, as discussed by Pan Zhou 0001 et al. in Toward Optimal Adaptive Wireless Communications in Unknown Environments, to large-scale infrastructure routing, as explored by Qiwen Cui et al. in Learning in Congestion Games with Bandit Feedback.

The Core Mechanism: Additive Decomposition

To bypass this combinatorial explosion, researchers leverage a powerful structural assumption: additive reward decomposition. Instead of learning a monolithic value function for an entire combination, the global reward is modeled as the sum of independent, component-level rewards.

Mathematically, if an agent selects a subset or path $A$, the total reward $R(A)$ is expressed as:

$$R(A) = \sum_{e \in A} r(e)$$

where $r(e)$ represents the reward, cost, or utility of an individual component $e$ (such as a network edge, a specific item, or a shared resource).

By shifting the target of learning from the combination level to the component level, the parameter space collapses from exponential to polynomial. For example, in network optimization, Yi Gai et al. demonstrate in On the Combinatorial Multi-Armed Bandit Problem with Markovian Rewards and Online Learning for Combinatorial Network Optimization with Restless Markovian Rewards that tracking statistics for individual user-resource pairs or edges enables polynomial time and space complexity while guaranteeing near-logarithmic regret over time.

Why It Works: Information Sharing and Variance Reduction

The intuition behind why additive decomposition works so effectively lies in information sharing. In an unstructured model, observing the outcome of a specific slate or path tells the system nothing about other slates or paths. Under an additive model, however, components are shared across different combinations. If two distinct paths share a subset of edges, feedback from traversing the first path immediately updates and improves the system's estimates for the second path.

This capability is exceptionally valuable in Off-Policy Evaluation (OPE), where researchers evaluate new policies using historical logs. Because the probability of observing an identical combinatorial action in historical data is vanishingly small, standard importance sampling fails due to extreme variance.

To solve this, Adith Swaminathan et al. introduce the Pseudoinverse estimator in Off-policy evaluation for slate recommendation. By modeling the total reward of a recommendation list as the sum of individual item-position pairs, the authors show that whole-page metrics can be accurately estimated using only aggregate rewards, bypassing the need for item-level labels. Taking this a step further, David Arbour et al. in Distributional Off-Policy Evaluation for Slate Recommendations decompose the total reward of a slate into a sum of latent functions associated with individual slots, allowing the system to estimate the entire distribution of potential rewards rather than just the mean.

Managing Complex Interactions and Structure

While strict additivity assumes components do not interact, real-world systems often feature dependencies. To maintain scalability without sacrificing accuracy, researchers incorporate structured interaction models or residual terms.

In ranking systems, for instance, user clicks on lower items depend heavily on whether higher items caught their attention. To address this, Matej Cief et al. in Pessimistic Off-Policy Optimization for Learning to Rank and Shuai Li et al. in Offline Evaluation of Ranking Policies with Click Models utilize structured click models. This allows the decomposition of list-level rewards into item-level attraction probabilities, enabling the computation of tight uncertainty bounds at the item level that aggregate into robust, pessimistic lower confidence bounds for entire sequences.

For more general combinatorial actions, Koichi Tanaka et al. propose in Effective Off-Policy Evaluation and Learning in Contextual Combinatorial Bandits to decompose rewards into a primary "main effect" component representing key actions and a "residual component" representing interaction effects, surgically balancing bias and variance.

This additive framework also extends naturally to continuous and graph-structured environments:

Simplifying Optimization, Elicitation, and Games

Decomposing rewards does more than accelerate learning; it fundamentally simplifies downstream optimization, preference elicitation, and game-theoretic analysis.

When a reward function is additive, selecting the optimal subset of items reduces to evaluating each item independently and sorting them. As demonstrated by Alexander Rakhlin et al. in Top-k eXtreme Contextual Bandits with Arm Hierarchy, this linearity transforms a complex combinatorial selection problem into a highly scalable top-k ranking task. Similarly, in reinforcement learning with preference feedback, Joongkyu Lee et al. in Combinatorial Reinforcement Learning with Preference Feedback decompose the value of an assortment into individual item-level Q-values, enabling agents to track long-term utility efficiently.

This structural exploitation manifests across several other domains:

Key Foundational Work

On the Combinatorial Multi-Armed Bandit Problem with Markovian Rewards (2010) — contributed 2 concept elements to this direction.
Eliciting Additive Reward Functions for Markov Decision Processes (2011) — contributed 2 concept elements to this direction.
Online Learning for Combinatorial Network Optimization with Restless Markovian Rewards (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_additive_reward_decomposition_9a459fe5,
  title = {additive reward decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/additive-reward-decomposition/rdr_9a459fe586e24d8a8c025ce1476e70e4},
  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_additive_reward_decomposition_9a459fe5_v1,
  title = {additive reward decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/additive-reward-decomposition/rdr_9a459fe586e24d8a8c025ce1476e70e4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake