mlsanityData to 14 Oct 2026

Online learning in MDPs with linear function approximation and bandit feedback

arXiv 2007.01612 ↗First posted 3 Jul 2020cs.LG stat.MLcited by 30

Not on the map. Why?

Abstract (arXiv)

We consider an online learning problem where the learner interacts with a Markov decision process in a sequence of episodes, where the reward function is allowed to change between episodes in an adversarial manner and the learner only gets to observe the rewards associated with its actions. We allow the state space to be arbitrarily large, but we assume that all action-value functions can be represented as linear functions in terms of a known low-dimensional feature map, and that the learner has access to a simulator of the environment that allows generating trajectories from the true MDP dynamics. Our main contribution is developing a computationally efficient algorithm that we call MDP-LinExp3, and prove that its regret is bounded by widetildeObig(H2 T2/3 (dK)1/3big), where T is the number of episodes, H is the number of steps in each episode, K is the number of actions, and d is the dimension of the feature map. We also show that the regret can be improved to widetildeObig(H2 √TdKbig) under much stronger assumptions on the MDP dynamics. To our knowledge, MDP-LinExp3 is the first provably efficient algorithm for this problem setting.

Key facts. Cited by 30 papers in the map (data through 14 Oct 2026). First posted on arXiv 3 Jul 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 2; 2023: 13; 2024: 5; 2025: 2; 2026: 4.

30 papers.

Sort:

By area:

  1. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  2. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  3. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  4. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 29
  5. 2022Proximal Point Imitation Learningcited by 26
  6. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 19
  7. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 19
  8. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 17
  9. 2023Best of Both Worlds Policy Optimizationcited by 17
  10. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPscited by 17
  11. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 15
  12. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
18 more
  1. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 13
  2. 2022No-Regret Learning in Dynamic Stackelberg Gamescited by 12
  3. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  4. 2024Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transitioncited by 6
  5. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  6. 2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4
  7. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  8. 2021Online Markov Decision Processes with Non-oblivious Strategic Adversarycited by 3
  9. 2025Multi-Step Alignment as Markov Games: An Optimistic Online Gradient Descent Approach with Convergence Guaranteescited by 3
  10. 2025Reinforcement Learning from Adversarial Preferences in Tabular MDPscited by 2
  11. 2023Online Resource Allocation in Episodic Markov Decision Processescited by 1
  12. 2024Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedbackcited by 1
  13. 2024Online Stackelberg Optimization via Nonlinear Controlcited by 1
  14. 2026Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferencescited by 1
  15. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  16. 2024packetLSTM: Dynamic LSTM Framework for Streaming Data with Varying Feature Spacecited by 0
  17. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0
  18. 2026A Geometric Perspective on Reward Function Updates in Inverse Reinforcement Learningcited by 0