Linear Markov Decision Processes

Ask about this topic

Overview

Linear Markov decision processes (MDPs) represent rewards or transition dynamics with unknown parameters that are linear in known features, making learning possible without enumerating every state and action. Researchers develop methods such as optimistic least-squares value iteration, model-based planning, actor-critic, and primal-dual algorithms for episodic, constrained, and changing environments. Guarantees are commonly measured by regret or the samples needed to learn a near-optimal policy, including settings with large or continuous state and action spaces. A central tension is that strong guarantees often rely on realizability or access to computational oracles, while lower bounds reveal unavoidable costs in feature dimension, horizon, and reward gaps.

Latest papers

CardsList

16 papers4 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

  1. A Computationally Efficient and Rate-Optimal Algorithm for Adversarial Linear MDPs with (Aggregate) Bandit Feedback

    Oct 22, 2026Haolin Liu, Chen-Yu Wei, Hanbin ZhouLinear Markov Decision Processes

    University of Virginia · Hong Kong University of Science and Technology

  2. Confessions of a Masked MDP

    Oct 20, 2026Sebastian Reboul, Lorenzo Croissant, Hélène HalconruyReinforcement LearningConstrained RL

    SAMOVAR, Télécom SudParis, Institut Polytechnique de Paris · Modal’X, Université Paris-Nanterre · Wiremind Cargo, AI & ML Group +1

  3. Rate-Optimal Algorithm for Adversarial Linear CMDPs

    Oct 1, 2026Kihyun Yu, Honghao Wei, Dabeen LeeRegret Minimization in RLMarkov Decision Processes

    KAIST · Washington State University · Seoul National University

  4. Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy

    Sep 30, 2026Han Zhong, Yinyu YeMarkov Decision ProcessesPolicy Iteration

    Shanghai Jiao Tong University. · Shanghai Jiao Tong University, SIMIS, and Stanford University.

  5. A Decentralized Partially Observable Team Decision Methodology with Delayed Information Sharing

    Sep 22, 2026Xiaoxing Ren, Thomas Parisini, Andreas A. MalikopoulosMarkov Decision ProcessesLinear Markov Decision Processes

    School of Civil and Environmental Engineering, Cornell University, Ithaca, NY, USA · Dept. of Electrical and Electronic Engineering, Imperial College London, London SW7 2AZ, UK · Dept. of Electronic Systems, Aalborg University, Denmark +2

  6. Active Inference as a Convex Markov Decision Process

    Jul 22, 2026Nikola Milosevic, Nicolás Hinrichs, Nico ScherfMarkov Decision ProcessesReinforcement Learning

    Max Planck Institute for Human Cognitive and Brain Sciences, Stephanstraße. 1A, 04103 Leipzig, Germany

  7. Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPs

    May 2, 2026Ruiquan Huang, Donghao Li, Yingbin Liang +1Markov Decision ProcessesReinforcement Learning

    University of Kentucky. · University of Virginia. · Ohio State University..

  8. Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation

    May 1, 2026Haichen Hu, Jian Qian, David Simchi-LeviRegret Minimization in RLMarkov Decision Processes

    Laboratory for Information and Decision Systems · Department of AI and Data Science

  9. DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees

    Apr 17, 2026Argyrios Gerogiannis, Yu-Han Huang, Venugopal V. VeeravalliNon-Stationary RLRegret Minimization in RL

    ECE and CSL, The Grainger College of Engineering University of Illinois at Urbana-Champaign

  10. When Can You Poison Rewards? A Tight Characterization of Reward Poisoning in Linear MDPs

    Apr 11, 2026Jose Efraim Aguilar Escamilla, Haoyang Hong, Jiawei Li +4Markov Decision ProcessesAdversarial Attacks

    Oregon State University, OR, USA · University of Illinois Urbana–Champaign, IL, USA · Princeton University, NJ, USA +1

  11. Provable Multi-Task Reinforcement Learning: A Representation Learning Framework with Low Rank Rewards

    Apr 4, 2026Yaoze Guo, Shana MoothedathMulti-Task RLRepresentation Learning for RL

    Electrical and Computer Engineering, Iowa State University

  12. Optimistic Actor-Critic with Parametric Policies for Linear Markov Decision Processes

    Mar 30, 2026Max Qiushi Lin, Reza Asad, Kevin Tan +3Actor-Critic MethodsPolicy Learning

    Simon Fraser University · University of Pennsylvania · Mila, McGill University +1

  13. End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions

    Mar 24, 2026Zakaria Mhammedi, Alexander Rakhlin, Nneka OkoloReinforcement LearningLinear Markov Decision Processes

    Google Research, NYC · MIT

  14. Frozen Policy Iteration: Computationally Efficient RL under Linear QπQ^π Realizability for Deterministic Dynamics

    Feb 28, 2026Yijing Ke, Zihan Zhang, Ruosong WangRegret Minimization in RLPolicy Iteration

    School of EECS, Peking University · Department of Computer Science and Engineering, HKUST · CFCS and School of Computer Science, Peking University

  15. Understanding Gap-Dependent Regret for Optimism-Based Reinforcement Learning with Linear Function Approximation

    Feb 23, 2026Haochen Zhang, Zhong Zheng, Lingzhou XueRegret Minimization in RLReinforcement Learning

    Department of Statistics, The Pennsylvania State University · Department of Applied and Computational Mathematics and Statistics, University of Notre Dame

  16. Learning Sequential Decisions from Multiple Sources via Group-Robust Markov Decision Processes

    Feb 2, 2026Mingyuan Xu, Zongqi Xia, Tianxi Cai +2Robust Markov Decision ProcessesOffline RL

    Department of Statistics and Data Science, National University of Singapore · Department of Neurology, University of Pittsburgh · Department of Biostatistics, Harvard T.H. Chan School of Public Health +2