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:
- Continuous Budgets: In digital advertising, Alessandro Nuara et al. in Online Joint Bid/Budget Optimization of Pay-per-click Advertising Campaigns factorize multi-dimensional reward functions into independent one-dimensional components to accelerate convergence.
- Graph Neighborhoods: In graph domains, Parnian Kassraie et al. show in Graph Neural Network Bandits that assuming a total reward is an additive sum of local contributions from node neighborhoods keeps learning complexity independent of the global graph size.
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:
- Reward Elicitation: Kevin Regan et al. show in Eliciting Additive Reward Functions for Markov Decision Processes that decomposing rewards into independent attributes reduces the elicitation burden from the entire state-action space to the sum of individual attribute domains, finding optimal policies with far fewer user queries.
- Offline Games: In multi-agent settings, Haozhe Jiang et al. demonstrate in Offline Congestion Games: How Feedback Type Affects Data Coverage Requirement that focusing on individual resource states rather than action combinations drastically reduces the sample complexity required to find Nash Equilibria.
- Resource Allocation: In conservation planning, Lily Xu et al. in Dual-Mandate Patrols: Multi-Armed Bandits for Green Security calculate total utility as the sum of rewards from individual targets and effort levels, avoiding exponential complexity. In network connectivity problems, XiaoJian Wu et al. in Stochastic Network Design in Bidirected Trees factor path rewards into node-specific values, allowing algorithms to maintain compact summary statistics per subtree instead of tracking every possible path.
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.