# Causal Markov Decision Processes: Learning Good Interventions Efficiently

arXiv: https://arxiv.org/abs/2102.07663 · HTML: https://mlsanity.com/paper/2102.07663/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 23 references that are in the map.
- First posted on arXiv 15 Feb 2021.

## Builds on (most cited first, 12 of 12)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Causal Bandits: Learning Good Interventions via Causal Inference](https://mlsanity.com/paper/1606.03203/) (2016)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Off-policy Policy Evaluation For Sequential Decisions Under Unobserved Confounding](https://mlsanity.com/paper/2003.05623/) (2020)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Near-optimal Reinforcement Learning in Factored MDPs](https://mlsanity.com/paper/1403.3741/) (2014)
- [Identifying Best Interventions through Online Importance Sampling](https://mlsanity.com/paper/1701.02789/) (2017)
- [Budgeted and Non-budgeted Causal Bandits](https://mlsanity.com/paper/2012.07058/) (2020)
- [Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes](https://mlsanity.com/paper/2006.13405/) (2020)
- [Regret Analysis of Bandit Problems with Causal Background Knowledge](https://mlsanity.com/paper/1910.04938/) (2019)

## Built on by (most cited first, 7 of 7)

- [Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcare](https://mlsanity.com/paper/2305.01738/) (2023)
- [Causal Multi-Agent Reinforcement Learning: Review and Open Problems](https://mlsanity.com/paper/2111.06721/) (2021)
- [A Causal Bandit Approach to Learning Good Atomic Interventions in Presence of Unobserved Confounders](https://mlsanity.com/paper/2107.02772/) (2021)
- [Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instruments](https://mlsanity.com/paper/2208.11040/) (2022)
- [Towards Generalizable Reinforcement Learning via Causality-Guided Self-Adaptive Representations](https://mlsanity.com/paper/2407.20651/) (2024)
- [Expediting Reinforcement Learning by Incorporating Knowledge About Temporal Causality in the Environment](https://mlsanity.com/paper/2510.15456/) (2025)
- [The Importance of Causality in Decision Making: A Perspective on Recommender Systems](https://mlsanity.com/paper/2410.01822/) (2024)

## Abstract (arXiv)

We introduce causal Markov Decision Processes (C-MDPs), a new formalism for sequential decision making which combines the standard MDP formulation with causal structures over state transition and reward functions. Many contemporary and emerging application areas such as digital healthcare and digital marketing can benefit from modeling with C-MDPs due to the causal mechanisms underlying the relationship between interventions and states/rewards. We propose the causal upper confidence bound value iteration (C-UCBVI) algorithm that exploits the causal structure in C-MDPs and improves the performance of standard reinforcement learning algorithms that do not take causal knowledge into account. We prove that C-UCBVI satisfies an tildeO(HS√ZT) regret bound, where T is the the total time steps, H is the episodic horizon, and S is the cardinality of the state space. Notably, our regret bound does not scale with the size of actions/interventions (A), but only scales with a causal graph dependent quantity Z which can be exponentially smaller than A. By extending C-UCBVI to the factored MDP setting, we propose the causal factored UCBVI (CF-UCBVI) algorithm, which further reduces the regret exponentially in terms of S. Furthermore, we show that RL algorithms for linear MDP problems can also be incorporated in C-MDPs. We empirically show the benefit of our causal approaches in various settings to validate our algorithms and theoretical results.