Improved Bound for Robust Causal Bandits with Linear Models

2024/05/13 by Zirui Yan, Arpan Mukherjee, Yan, Zirui +5 · 1 citation
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Machine Learning and Algorithms #Distributed Sensor Networks and Detection Algorithms

paper · pdf · doi:10.48550/arxiv.2405.07795

Abstract

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 O(d^L-(1)/(2)(√(T) + C)) and lower bounded by Ω(d^(L)/(2)-2max\√(T) , d²C\). The proposed algorithm achieves nearly optimal O(√(T)) regret when C is o(√(T)), maintaining sub-linear regret for a broad range of C.

Cited by

• Uncertainty Sets for Distributionally Robust Bandits Using Structural Equation Models

Related

• Robust Causal Bandits for Linear Models
• Causal Bandits for Linear Structural Equation Models
• Causal Bandits with General Causal Models and Interventions
• Linear Causal Bandits: Unknown Graph and Soft Interventions
• Regret Analysis of Bandit Problems with Causal Background Knowledge