Research map / Probabilistic and scientific modeling / Causal discovery
Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learning
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.
Proposes C-PSRL, a hierarchical posterior sampling method for factored MDPs whose prior is a partial causal graph, with a Bayesian regret bound that improves as prior knowledge grows.
Problem
Posterior sampling for RL requires specifying priors as parametric distributions over transition dynamics, which is cumbersome; partial causal graph knowledge is easier to specify but unsupported by PSRL when the full factorization is unknown.
Approach
A hierarchical Bayesian posterior sampling procedure samples a factorization (parent sets for each state variable) consistent with a partial causal graph prior from a hyper-prior, then samples factored transition parameters conditioned on it, and runs PSRL on the sampled FMDP.
Key results
- On Random FMDPs (d_X=9, d_Y=6, H=100), C-PSRL achieves regret significantly smaller than PSRL and close to the oracle F-PSRL over 500 episodes (mean and 95% c.i. over 20 runs).
- On Taxi 5x5, PSRL still suffers linear regret after 400 episodes while C-PSRL finds a good policy efficiently.
- Theorem gives Bayesian regret of order tilde-O((H^{5/2} N^{1+Z/2} d_Y + sqrt(H 2^{d_X-eta})) sqrt(K)), i.e. a second term scaling as sqrt(K/2^eta).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a partial causal graph prior instead of an uninformative prior | PSRL (C-PSRL vs. PSRL) · Random FMDP | regret | Helped |
| Use a partial causal graph prior instead of the true causal graph prior | PSRL (C-PSRL vs. F-PSRL) · Random FMDP | regret | Mixed |
| Use a partial causal graph prior instead of an uninformative prior | PSRL (C-PSRL vs. PSRL) · Taxi 3 × 3 | regret | No clear effect |
| Use a partial causal graph prior instead of an uninformative prior | PSRL (C-PSRL vs. PSRL) · Taxi 5 × 5 | regret | Helped |
Surprising findings
- C-PSRL is surprisingly close to the oracle F-PSRL on random FMDPs despite only partial graph knowledge.
Limitations
- Requires exact planning in FMDPs, which is intractable in general
- Only weak causal discovery: recovers a super-graph rather than the minimal causal graph
- Experiments limited to simple illustrative domains
Experimental setup
Datasets: Random FMDP (synthetic) Taxi (Gym)
Benchmarks: Random FMDP Taxi 3x3 Taxi 5x5
Metrics: Bayesian regret l1 model error
Baselines: PSRL F-PSRL
Builds on: PSRL factored PSRL mixture Thompson sampling causal minimality
Closest papers by meaning
- Sample Efficient Bayesian Learning of Causal Graphs from Interventions (NeurIPS 2024 · similarity 0.90)
- Hierarchical Reinforcement Learning with Targeted Causal Interventions (ICML 2025 · similarity 0.88)
- A Meta-Learning Approach to Bayesian Causal Discovery (ICLR 2025 · similarity 0.87)
- Estimating Interventional Distributions with Uncertain Causal Graphs through Meta-Learning (NeurIPS 2025 · similarity 0.87)
- Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits (NeurIPS 2024 · similarity 0.87)
- Causal Information Prioritization for Efficient Reinforcement Learning (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.