Instance-Optimal Best Policy Identification in Decoupled Causal MDPs with a Known Graph

We quantify the value of a known causal graph for fixed-confidence best-policy identification. Actions intervene on graph variables and rewards are Gaussian with a known variance and unknown means. A graph-aware learner can ignore every intervention on a variable that cannot influence the reward, whereas a graph-blind learner with the same feedback must rule each one out. The blind characteristic time, which governs sample complexity, grows linearly in the number of reward-irrelevant actions, while the graph-aware time does not. This separation follows from a lower bound on the number of samples any correct learner needs. In de- coupled layered causal Markov decision processes (MDPs), the characteristic time is the largest stage time under episodic sampling and the sum under per-stage sampling. An intervention-aware Track-and-Stop algorithm is correct and attains these times whenever no reward-ancestral intervention is worse than the null intervention. Simulations on synthetic causal-bandit and layered-MDP instances match the predicted times and the composition law. Both learners identified the best policy in every run at the target confidence, and with two or more reward-irrelevant actions the graph-aware learner needed 1.4 to 6.8 times fewer samples, a speed-up 15 to 43 percent larger than the leading-order prediction. All code is released at https://anonymous.4open.science/r/iats-crl-AC81.