Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes
Not on the map. Why?
Abstract (arXiv)
We study minimax optimal reinforcement learning in episodic factored Markov decision processes (FMDPs), which are MDPs with conditionally independent transition components. Assuming the factorization is known, we propose two model-based algorithms. The first one achieves minimax optimal regret guarantees for a rich class of factored structures, while the second one enjoys better computational complexity with a slightly worse regret. A key new ingredient of our algorithms is the design of a bonus term to guide exploration. We complement our algorithms by presenting several structure-dependent lower bounds on regret for FMDPs that reveal the difficulty hiding in the intricacy of the structures.
Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 Jun 2020.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 5; 2022: 2; 2023: 4; 2024: 0; 2025: 2.
13 papers.
Sort:
- 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 20
- 2022Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalizationcited by 12
- 2022Learning in Congestion Games with Bandit Feedbackcited by 10
- 2021Factored Policy Gradients: Leveraging Structure for Efficient Learning in MOMDPscited by 8
- 2021Causal Markov Decision Processes: Learning Good Interventions Efficientlycited by 7
- 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learningcited by 6
- 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learningcited by 5
- 2023Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learningcited by 5
- 2021Polynomial Time Reinforcement Learning in Factored State MDPs with Linear Value Functionscited by 4
- 2023Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Spacecited by 2
- 2025From Pixels to Factors: Learning Independently Controllable State Variables for Reinforcement Learningcited by 2
- 2021Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?cited by 1
1 more
- 2025Tail Distribution of Regret in Optimistic Reinforcement Learning23 Nov 2025
- 2025From Pixels to Factors: Learning Independently Controllable State Variables for Reinforcement Learning2 Oct 2025
- 2023Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learning11 Oct 2023
- 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning15 Jun 2023
- 2023Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space21 Feb 2023
- 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learning8 Feb 2023
- 2022Learning in Congestion Games with Bandit Feedback4 Jun 2022
- 2022Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalization14 Feb 2022
- 2021Polynomial Time Reinforcement Learning in Factored State MDPs with Linear Value Functions12 Jul 2021
- 2021Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?16 Jun 2021
- 2021Factored Policy Gradients: Leveraging Structure for Efficient Learning in MOMDPs20 Feb 2021
- 2021Causal Markov Decision Processes: Learning Good Interventions Efficiently15 Feb 2021
1 more
- 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 20
- 2022Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalizationcited by 12
- 2022Learning in Congestion Games with Bandit Feedbackcited by 10
- 2021Factored Policy Gradients: Leveraging Structure for Efficient Learning in MOMDPscited by 8
- 2021Causal Markov Decision Processes: Learning Good Interventions Efficientlycited by 7
- 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learningcited by 6
- 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learningcited by 5
- 2023Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learningcited by 5
- 2021Polynomial Time Reinforcement Learning in Factored State MDPs with Linear Value Functionscited by 4
- 2023Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Spacecited by 2
- 2025From Pixels to Factors: Learning Independently Controllable State Variables for Reinforcement Learningcited by 2
- 2021Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?cited by 1
12 most cited of 13 All 13 (JSON)
- 2025Tail Distribution of Regret in Optimistic Reinforcement Learning23 Nov 2025
- 2025From Pixels to Factors: Learning Independently Controllable State Variables for Reinforcement Learning2 Oct 2025
- 2023Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learning11 Oct 2023
- 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning15 Jun 2023
- 2023Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space21 Feb 2023
- 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learning8 Feb 2023
- 2022Learning in Congestion Games with Bandit Feedback4 Jun 2022
- 2022Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalization14 Feb 2022
- 2021Polynomial Time Reinforcement Learning in Factored State MDPs with Linear Value Functions12 Jul 2021
- 2021Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?16 Jun 2021
- 2021Factored Policy Gradients: Leveraging Structure for Efficient Learning in MOMDPs20 Feb 2021
- 2021Causal Markov Decision Processes: Learning Good Interventions Efficiently15 Feb 2021
12 newest of 13 All 13 (JSON)