# Robust Causal Bandits for Linear Models

**Authors:** Zirui Yan, Arpan Mukherjee, Burak Varıcı, Ali Tajer  
**arXiv:** [2310.19794](https://arxiv.org/abs/2310.19794)  
**Date:** 2023-10-30  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/2310.19794v1/

## Key points

- The paper addresses the problem of optimizing a reward function in causal systems through sequential design of interventions in causal bandits (CBs)
- Existing literature assumes constant causal models over time, but this may not hold in complex systems with temporal model fluctuations
- Focuses on robustness of CBs to model fluctuations in linear structural equation models (SEMs)
- Both SEMs and pre/post-interventional statistical models are unknown
- Design criteria based on cumulative regret, measuring deviation between expected rewards obtained by an algorithm and those obtained by an oracle aware of the entire causal model and its fluctuations
- Objective is to design interventions that minimize cumulative regret
- Existing approaches fail to maintain sub-linear regret even with a few instances of model deviation
- Proposed robust CB algorithm is introduced and its regret is analyzed
- Upper and lower bounds on regret established for graphs with N nodes and maximum degree d under measure of model deviation denoted as C
- Cumulative regret upper bounded by $\tilde{\mathcal{O}}(d^{L-\frac{1}{2}}(\sqrt{NT} + NC))$ and lower bounded by $\Omega(d^{\frac{L}{2}-2}\max\{\sqrt{T},d^2C\})$
- Proposed algorithm achieves nearly optimal $\tilde{\mathcal{O}}(\sqrt{T})$ regret when C is $o(\sqrt{T})$, maintains sub-linear regret for broader range of C
- Contributes to sequential design of experiments in causal systems by addressing robustness of CBs to model fluctuations
- Proposed algorithm provides improved performance compared to existing approaches, especially in scenarios with temporal model deviations

## Summary

The paper titled "Robust Causal Bandits for Linear Models" addresses the problem of optimizing a reward function in causal systems through sequential design of interventions in causal bandits (CBs). The existing literature on CBs assumes that the causal models remain constant over time, but this assumption may not hold in complex systems that undergo temporal model fluctuations. This paper focuses on the robustness of CBs to such model fluctuations, specifically in causal systems with linear structural equation models (SEMs). In this study, both the SEMs and the time-varying pre- and post-interventional statistical models are unknown. The design criteria is based on cumulative regret, which measures the deviation between the expected rewards obtained by an algorithm and those obtained by an oracle aware of the entire causal model and its fluctuations. The objective is to design a sequence of interventions that minimizes cumulative regret. The authors first establish that existing approaches fail to maintain regret sub-linearity even with a few instances of model deviation. When there are as few as $T^\frac{1}{2L}$ instances of model deviation, where $T$ is the time horizon and $L$ is the longest causal path in the graph, existing algorithms exhibit linear regret in $T$. To address this limitation, a robust CB algorithm is proposed and its regret is analyzed. Upper and information-theoretic lower bounds on the regret are established for graphs with $N$ nodes and maximum degree $d$, under a general measure of model deviation denoted as $C$. The cumulative regret is shown to be upper bounded by $\tilde{\mathcal{O}}(d^{L-\frac{1}{2}}(\sqrt{NT} + NC))$ and lower bounded by $\Omega(d^{\frac{L}{2}-2}\max\{\sqrt{T},d^2C\})$. By comparing these bounds, it is demonstrated that the proposed algorithm achieves nearly optimal $\tilde{\mathcal{O}}(\sqrt{T})$ regret when $C$ is $o(\sqrt{T})$, and maintains sub-linear regret for a broader range of $C$. Overall, this paper contributes to the field of sequential design of experiments in causal systems by addressing the robustness of CBs to model fluctuations. The proposed robust CB algorithm provides improved performance compared to existing approaches, particularly in scenarios with temporal model deviations. It demonstrates that it can achieve near optimal $\tilde{\mathcal{O}}(\sqrt{T})$ regret when there are only a few instances of temporal model deviations present.