mlsanityData to 14 Oct 2026

Improved Algorithms for Misspecified Linear Markov Decision Processes

arXiv 2109.05546 ↗First posted 12 Sep 2021cs.LG stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

For the misspecified linear Markov decision process (MLMDP) model of Jin et al. [2020], we propose an algorithm with three desirable properties. (P1) Its regret after K episodes scales as K max varepsilonmis, varepsilontol , where varepsilonmis is the degree of misspecification and varepsilontol is a user-specified error tolerance. (P2) Its space and per-episode time complexities remain bounded as K rightarrow ∞. (P3) It does not require varepsilonmis as input. To our knowledge, this is the first algorithm satisfying all three properties. For concrete choices of varepsilontol, we also improve existing regret bounds (up to log factors) while achieving either (P2) or (P3) (existing algorithms satisfy neither). At a high level, our algorithm generalizes (to MLMDPs) and refines the Sup-Lin-UCB algorithm, which Takemura et al. [2021] recently showed satisfies (P3) for contextual bandits. We also provide an intuitive interpretation of their result, which informs the design of our algorithm.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 23 of its 42 references that are in the map. First posted on arXiv 12 Sep 2021.

Builds on

23 of 42 references.

References · 23

  1. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  2. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  3. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  4. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  5. 2017Deep Exploration via Randomized Value Functionscited by 156
  6. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  7. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  8. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  9. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  10. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  11. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  12. 2021Adapting to Misspecification in Contextual Banditscited by 81
11 more
  1. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  2. 2020Model Selection in Contextual Stochastic Bandit Problemscited by 71
  3. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  4. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  5. 2020Regret Bound Balancing and Elimination for Model Selection in Bandits and RLcited by 47
  6. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  7. 2017Misspecified Linear Banditscited by 42
  8. 2021Efficient Local Planning with Linear Function Approximationcited by 23
  9. 2019Provably Efficient Reinforcement Learning with Aggregated Statescited by 20
  10. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  11. 2016Low-rank Bandits with Latent Mixturescited by 11

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 1; 2025: 1; 2026: 2.

6 papers.

  1. 2023On the Model-Misspecification in Reinforcement Learningcited by 7
  2. 2023Does Sparsity Help in Learning Misspecified Linear Bandits?cited by 3
  3. 2024Achieving Constant Regret in Linear Markov Decision Processescited by 3
  4. 2026Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecificationcited by 3
  5. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 2
  6. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1