Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Certified Policy Optimisation for Nested Causal Bandits via PAC-Bayes Risk

NeurIPS 2026 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Causal and structured bandits · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Formalises nested contextual causal bandits (NCCBs), proposes NCTS (recursive Thompson sampling over a hierarchical SCM) and the PRISM causal PAC-Bayes excess-risk bound plus AEGIS per-level handover, evaluated on a synthetic hierarchical SCM benchmark against RFF-GP baselines.

Problem

Certifying the risk of a learned sequential policy on a realised environment with causal confounding across nested decision timescales, from historic off-policy data, and deciding when to hand control from a legacy controller to a learned policy level by level.

Approach

A hierarchical SCM bandit where one posterior draw per episode drives recursive meta-to-inner action selection, plus a causal PAC-Bayes bound whose KL regulariser sums only over post-intervention learnable mechanisms and whose importance weight is a product over controlled levels; per-level certificates gate progressive handover.

Key results

• Factorised SCM posterior (flat_cts) gets 113.6±4.9 vs 56.1±10.1 for joint regression under Shift-T zero-shot (Δ=+57.5, p<10^-3).
• nested_cts reaches 113.6±1.9 reward vs 69.0±5.8 for joint_cts; recursive nesting adds +44.6 over joint commit (p<10^-10).
• The PRISM certified lower bound contracts about 2.0x from k=200 to k=2000 episodes in a data-split protocol.

Surprising findings

• The naive on-policy LS estimator is about 8.7x looser than the split-based estimator and is not a valid bound on the learned policy's value.

Limitations

• Assumes i.i.d. inner steps within episodes; extension to MDP/POMDP dynamics is left open.
• Mechanism class restricted to additive-noise models; cross-level confounding is outside the model class.
• Bound is loose under one-shot full deployment due to multiplicative overlap penalty B^I.

Experimental setup

Datasets: synthetic hierarchical SCM (SCM_unified)

Benchmarks: SCM_unified hierarchical SCM bandit benchmark

Metrics: cumulative reward certified lower bound on value Welch t-test p-value

Baselines: flat_ts (RFF-GP joint regression) flat_cts joint_cts NIG-linear baseline

Builds on: Thompson sampling online PAC-Bayes logarithmic smoothing causal MDPs (C-MDPs) structural causal bandits

Closest papers by meaning

• Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits (NeurIPS 2024 · similarity 0.87)
• Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.87)
• Adversarial Causal Bayesian Optimization (ICLR 2024 · similarity 0.87)
• Cost-Aware Near-Optimal Policy Learning (AAAI 2025 · similarity 0.86)
• Robustly Improving Bandit Algorithms with Confounded and Selection Biased Offline Data: A Causal Approach (AAAI 2024 · similarity 0.86)
• Tackling Non-Stationarity in Reinforcement Learning via Causal-Origin Representation (ICML 2024 · similarity 0.85)