Polynomial Time Reinforcement Learning in Factored State MDPs with Linear Value Functions

2021/07/12 by Zihao Deng, Deng, Zihao, Siddartha Devic +3 · 1 citation
Computer Science · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2107.05187

openalex publication_date 2021/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Many reinforcement learning (RL) environments in practice feature enormous state spaces that may be described compactly by a "factored" structure, that may be modeled by Factored Markov Decision Processes (FMDPs). We present the first polynomial-time algorithm for RL in Factored State MDPs (generalizing FMDPs) that neither relies on an oracle planner nor requires a linear transition model; it only requires a linear value function with a suitable local basis with respect to the factorization, permitting efficient variable elimination. With this assumption, we can solve this family of Factored State MDPs in polynomial time by constructing an efficient separation oracle for convex optimization. Importantly, and in contrast to prior work on FMDPs, we do not assume that the transitions on various factors are conditionally independent.

Cited by

• Context-Sensitive Abstractions for Reinforcement Learning with Parameterized Actions

Related

• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
• Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions
• Optimistic Initialization and Greediness Lead to Polynomial Time Learning in Factored MDPs - Extended Version
• Near-optimal Reinforcement Learning in Factored MDPs
• Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting