Research map / Bandits and online learning / RL theory and MDPs

Demystifying Linear MDPs and Novel Dynamics Aggregation Framework

ICLR 2024 · Bandits and online learning › RL theory and MDPs · approach: Linear function approximation in RL · 0 citations (OpenAlex)

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.

Shows that linear MDP feature dimension is lower bounded by S/U, then proposes dynamics aggregation and a model-based hierarchical RL algorithm (UC-HRL) with linear function approximation achieving regret O~(d_psi^{3/2} H^{3/2} sqrt(N T) + TH eps_p).

Problem

Linear MDPs are usually assumed to give state-space-independent regret, but the feature dimension d may need to scale with the state space size S when the number of directly reachable states is small; existing provable RL with linear function approximation lacks hierarchical structure exploitation.

Approach

Dynamics aggregation groups subMDPs with similar dynamics into a small set of aggregated subMDPs whose linear transition models are learned once and reused; a model-based UCB planner (UC-HRL) with transition-targeted ridge regression exploits this to get regret depending on the aggregated feature dimension rather than the full d.

Key results

• Proves feature dimension d is lower bounded by floor(S/U) for linear MDPs with finite state space, and extends to infinite/continuous state spaces (d infinite or d > 2^p Vol(S)/Vol(U) - 1).
• Proposed UC-HRL regret bound O~(d_psi^{3/2} H^{3/2} sqrt(N T) + TH eps_p), improving on LSVI-UCB's O~(d^{3/2} H^{3/2} sqrt(T)) when d_psi^3 N << d^3.
• On Block-RiverSwim, UC-HRL learns the optimal policy far more quickly than baselines as the number of repeated blocks grows, per the authors' experiments (no numeric values in the extract).

Measured effects reported in the paper

Surprising findings

• Linear MDP feature dimension must scale with the state space size S whenever the maximum number of directly reachable states U is o(S), so linear MDPs do not invariably give S-independent regret.

Limitations

• Regret bound includes an aggregation error term TH·eps_p that requires precise aggregation mappings, which are assumed known.
• Assumes the reward function is known and the dynamics aggregation mapping is given a priori.
• Experiments are limited to a single toy environment (Block-RiverSwim).

Experimental setup

Datasets: Block-RiverSwim (synthetic environment)

Benchmarks: Block-RiverSwim

Metrics: regret learning curves

Baselines: UC-MatrixRL UCRL-VTR LSVI-UCB LSVI-PHE UC-HRL (N=M variant without aggregation)

Builds on: linear MDP LSVI-UCB UC-MatrixRL UCRL-VTR equivalent subMDPs (Thompson sampling HRL)

Closest papers by meaning

• Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs (NeurIPS 2024 · similarity 0.86)
• No-Regret Reinforcement Learning in Smooth MDPs (ICML 2024 · similarity 0.86)
• Structural Information-based Hierarchical Diffusion for Offline Reinforcement Learning (NeurIPS 2025 · similarity 0.86)
• Linear Mixture Distributionally Robust Markov Decision Processes (NeurIPS 2025 · similarity 0.86)
• Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback (ICML 2024 · similarity 0.85)
• Transfer Q-Learning with Composite MDP Structures (ICML 2025 · similarity 0.85)