mlsanityData to 14 Oct 2026

Demystifying Linear MDPs and Novel Dynamics Aggregation Framework

arXiv 2410.24089 ↗First posted 31 Oct 2024stat.ML cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

In this work, we prove that, in linear MDPs, the feature dimension d is lower bounded by S/U in order to aptly represent transition probabilities, where S is the size of the state space and U is the maximum size of directly reachable states. Hence, d can still scale with S depending on the direct reachability of the environment. To address this limitation of linear MDPs, we propose a novel structural aggregation framework based on dynamics, named as the "dynamics aggregation". For this newly proposed framework, we design a provably efficient hierarchical reinforcement learning algorithm in linear function approximation that leverages aggregated sub-structures. Our proposed algorithm exhibits statistical efficiency, achieving a regret of tildeO ( dpsi3/2 H3/2√ N T ), where dpsi represents the feature dimension of aggregated subMDPs and N signifies the number of aggregated subMDPs. We establish that the condition dpsi3 N ll d3 is readily met in most real-world environments with hierarchical structures, enabling a substantial improvement in the regret bound compared to LSVI-UCB, which enjoys a regret of tildeO (d3/2 H3/2 √ T). To the best of our knowledge, this work presents the first HRL algorithm with linear function approximation that offers provable guarantees.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 21 of its 46 references that are in the map. First posted on arXiv 31 Oct 2024.

Builds on

21 of 46 references.

References · 21

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  3. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  4. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  5. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  6. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  7. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  8. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  9. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  10. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  11. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  12. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
9 more
  1. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  2. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  3. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  4. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  5. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  6. 2019Provably Efficient Reinforcement Learning with Aggregated Statescited by 20
  7. 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19
  8. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 18
  9. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2
  2. 2025Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learningcited by 1
  3. 2025Homomorphic Mappings for Value-Preserving State Aggregation in Markov Decision Processescited by 0
  4. 2026Learning Kernel-Based MDPs from Episodic Preferential Feedbackcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025An Error Bound for Aggregation in Approximate Dynamic Programming ↗
  2. 2023A Data-Driven State Aggregation Approach for Dynamic Discrete Choice Models
  3. 2026One Ring to Rule Them All: Unifying Group-Based RL via Dynamic Power-Mean Geometry
  4. 2024Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions
  5. 2024Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data
  6. 2024Solving robust MDPs as a sequence of static RL problems
  7. 2024Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs
  8. 2025Recursive Reward Aggregation