# Non-stationary Delayed Combinatorial Semi-Bandit with Causally Related Rewards

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 41 references that are in the map.
- First posted on arXiv 18 Jul 2023.

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

- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [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)
- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [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)
- [Contextual-Bandit Based Personalized Recommendation with Time-Varying User Interests](https://mlsanity.com/paper/2003.00359/) (2020)
- [Combinatorial Semi-Bandit in the Non-Stationary Environment](https://mlsanity.com/paper/2002.03580/) (2020)
- [Multi-Armed Bandit for Energy-Efficient and Delay-Sensitive Edge Computing in Dynamic Networks with Uncertainty](https://mlsanity.com/paper/1904.06258/) (2019)
- [Linear Combinatorial Semi-Bandit with Causally Related Rewards](https://mlsanity.com/paper/2212.12923/) (2022)
- [Networked Stochastic Multi-Armed Bandits with Combinatorial Strategies](https://mlsanity.com/paper/1503.06169/) (2015)

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

- [Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals](https://mlsanity.com/paper/2606.14650/) (2026)

## Abstract (arXiv)

Sequential decision-making under uncertainty is often associated with long feedback delays. Such delays degrade the performance of the learning agent in identifying a subset of arms with the optimal collective reward in the long run. This problem becomes significantly challenging in a non-stationary environment with structural dependencies amongst the reward distributions associated with the arms. Therefore, besides adapting to delays and environmental changes, learning the causal relations alleviates the adverse effects of feedback delay on the decision-making process. We formalize the described setting as a non-stationary and delayed combinatorial semi-bandit problem with causally related rewards. We model the causal relations by a directed graph in a stationary structural equation model. The agent maximizes the long-term average payoff, defined as a linear function of the base arms' rewards. We develop a policy that learns the structural dependencies from delayed feedback and utilizes that to optimize the decision-making while adapting to drifts. We prove a regret bound for the performance of the proposed algorithm. Besides, we evaluate our method via numerical analysis using synthetic and real-world datasets to detect the regions that contribute the most to the spread of Covid-19 in Italy.