Improved Bound for Robust Causal Bandits with Linear Models
<|reference_start|>Improved Bound for Robust Causal Bandits with Linear Models: This paper investigates the robustness of causal bandits (CBs) in the face of temporal model fluctuations. This setting deviates from the existing literature's widely-adopted assumption of constant causal models. The focus is on causal systems with linear structural equation models (SEMs). The SEMs and the time-varying pre- and post-interventional statistical models are all unknown and subject to variations over time. The goal is to design a sequence of interventions that incur the smallest cumulative regret compared to an oracle aware of the entire causal model and its fluctuations. A robust CB algorithm is proposed, and its cumulative regret is analyzed by establishing both upper and lower bounds on the regret. It is shown that in a graph with maximum in-degree $d$, length of the largest causal path $L$, and an aggregate model deviation $C$, the regret is upper bounded by $\tilde{\mathcal{O}}(d^{L-\frac{1}{2}}(\sqrt{T} + C))$ and lower bounded by $\Omega(d^{\frac{L}{2}-2}\max\{\sqrt{T}\; ,\; d^2C\})$. The proposed algorithm achieves nearly optimal $\tilde{\mathcal{O}}(\sqrt{T})$ regret when $C$ is $o(\sqrt{T})$, maintaining sub-linear regret for a broad range of $C$.<|reference_end|>
@article{yan2024improved,
    title={Improved Bound for Robust Causal Bandits with Linear Models},
    author={Zirui Yan, Arpan Mukherjee, Burak Var{i}c{i}, Ali Tajer},
    journal={arXiv preprint arXiv:2405.07795},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.07795},
    primaryClass={stat.ML cs.LG}
}