# Linear Combinatorial Semi-Bandit with Causally Related Rewards

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 37 references that are in the map.
- First posted on arXiv 25 Dec 2022.

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

- [OSQP: An Operator Splitting Solver for Quadratic Programs](https://mlsanity.com/paper/1711.08013/) (2017)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Causal Bandits: Learning Good Interventions via Causal Inference](https://mlsanity.com/paper/1606.03203/) (2016)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Identifying Best Interventions through Online Importance Sampling](https://mlsanity.com/paper/1701.02789/) (2017)
- [Multi-armed Bandits with Application to 5G Small Cells](https://mlsanity.com/paper/1510.00627/) (2015)
- [Networked Stochastic Multi-Armed Bandits with Combinatorial Strategies](https://mlsanity.com/paper/1503.06169/) (2015)
- [Analysis of Thompson Sampling for Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms](https://mlsanity.com/paper/1809.02707/) (2018)

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

- [Meta Learning in Bandits within Shared Affine Subspaces](https://mlsanity.com/paper/2404.00688/) (2024)
- [Non-stationary Delayed Combinatorial Semi-Bandit with Causally Related Rewards](https://mlsanity.com/paper/2307.09093/) (2023)
- [Piecewise-Stationary Combinatorial Semi-Bandit with Causally Related Rewards](https://mlsanity.com/paper/2307.14138/) (2023)
- [Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals](https://mlsanity.com/paper/2606.14650/) (2026)

## Abstract (arXiv)

In a sequential decision-making problem, having a structural dependency amongst the reward distributions associated with the arms makes it challenging to identify a subset of alternatives that guarantees the optimal collective outcome. Thus, besides individual actions' reward, learning the causal relations is essential to improve the decision-making strategy. To solve the two-fold learning problem described above, we develop the 'combinatorial semi-bandit framework with causally related rewards', where we model the causal relations by a directed graph in a stationary structural equation model. The nodal observation in the graph signal comprises the corresponding base arm's instantaneous reward and an additional term resulting from the causal influences of other base arms' rewards. The objective is to maximize the long-term average payoff, which is a linear function of the base arms' rewards and depends strongly on the network topology. To achieve this objective, we propose a policy that determines the causal relations by learning the network's topology and simultaneously exploits this knowledge to optimize the decision-making process. We establish a sublinear regret bound for the proposed algorithm. Numerical experiments using synthetic and real-world datasets demonstrate the superior performance of our proposed method compared to several benchmarks.