mlsanityData to 7 Oct 2026

Sample Complexity Characterization for Linear Contextual MDPs

arXiv 2402.02700 ↗First posted 5 Feb 2024cs.LG stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

Contextual Markov decision processes (CMDPs) describe a class of reinforcement learning problems in which the transition kernels and reward functions can change over time with different MDPs indexed by a context variable. While CMDPs serve as an important framework to model many real-world applications with time-varying environments, they are largely unexplored from theoretical perspective. In this paper, we study CMDPs under two linear function approximation models: Model I with context-varying representations and common linear weights for all contexts; and Model II with common representations for all contexts and context-varying linear weights. For both models, we propose novel model-based algorithms and show that they enjoy guaranteed ε-suboptimality gap with desired polynomial sample complexity. In particular, instantiating our result for the first model to the tabular CMDP improves the existing result by removing the reachability assumption. Our result for the second model is the first-known result for such a type of function approximation models. Comparison between our results for the two models further indicates that having context-varying features leads to much better sample efficiency than having common representations for all contexts under linear CMDPs.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 35 of its 55 references that are in the map. First posted on arXiv 5 Feb 2024.

Builds on

35 of 55 references.

References · 35

  1. 2015End-to-End Training of Deep Visuomotor Policiescited by 847
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2019Introduction to Multi-Armed Banditscited by 475
  4. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 342
  5. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  6. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  7. 2015Contextual Markov Decision Processescited by 213
  8. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  9. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  10. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  11. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  12. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
23 more
  1. 2018Practical Contextual Bandits with Regression Oraclescited by 92
  2. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  3. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  4. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  5. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  6. 2017Markov Decision Processes with Continuous Side Informationcited by 54
  7. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  8. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  9. 2020Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Banditscited by 35
  10. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  11. 2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
  12. 2021Block Contextual MDPs for Continual Learningcited by 25
  13. 2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
  14. 2019√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcited by 20
  15. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  16. 2020Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Samplingcited by 15
  17. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  18. 2020Finite-Time Analysis for Double Q-learningcited by 12
  19. 2022Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDPcited by 11
  20. 2022Learning Efficiently Function Approximation for Contextual MDPcited by 10
  21. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 5
  22. 2022Provably Efficient Lifelong Reinforcement Learning with Linear Function Approximationcited by 2
  23. 2023Provably Efficient Algorithm for Nonstationary Low-Rank MDPscited by 2

Built on by

Cited by year (2026 to 7 Oct)

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

4 papers.

  1. 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 7
  2. 2025Episodic Contextual Bandits with Knapsacks under Conversion Modelscited by 1
  3. 2025Detecting Model Drifts in Non-Stationary Environment Using Edit Operation Measurescited by 0
  4. 2026Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximationcited by 0