mlsanityData to 14 Oct 2026

Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimization

arXiv 2302.06834 ↗First posted 14 Feb 2023cs.LG cs.AIcited by 15

Not on the map. Why?

Abstract (arXiv)

Learning Markov decision processes (MDP) in an adversarial environment has been a challenging problem. The problem becomes even more challenging with function approximation, since the underlying structure of the loss function and transition kernel are especially hard to estimate in a varying environment. In fact, the state-of-the-art results for linear adversarial MDP achieve a regret of tildeO(K6/7) (K denotes the number of episodes), which admits a large room for improvement. In this paper, we investigate the problem with a new view, which reduces linear MDP into linear optimization by subtly setting the feature maps of the bandit arms of linear optimization. This new technique, under an exploratory assumption, yields an improved bound of tildeO(K4/5) for linear adversarial MDP without access to a transition simulator. The new view could be of independent interest for solving other MDP problems that possess a linear structure.

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). Builds on 30 of its 39 references that are in the map. First posted on arXiv 14 Feb 2023.

Builds on

30 of 39 references.

References · 30

  1. 2015Continuous control with deep reinforcement learningcited by 3,407
  2. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  3. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 721
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  5. 2018Is Q-learning Provably Efficient?cited by 487
  6. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  7. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  8. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  9. 2021Reinforcement learning based recommender systems: A surveycited by 188
  10. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  11. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  12. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
18 more
  1. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  2. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  3. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  4. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  5. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  6. 2020Q-learning with Logarithmic Regretcited by 60
  7. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  8. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  9. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  10. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 30
  11. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  12. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  13. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  14. 2020Online Sparse Reinforcement Learningcited by 25
  15. 2021Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPscited by 19
  16. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 19
  17. 2021A Survey on Reinforcement Learning for Recommender Systemscited by 18
  18. 2022Policy Optimization for Stochastic Shortest Pathcited by 13

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 5; 2024: 4; 2025: 3; 2026: 3.

15 papers.

Sort:

By area:

  1. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 29
  2. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 19
  3. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  4. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 13
  5. 2024Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transitioncited by 6
  6. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  7. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  8. 2025An Improved Algorithm for Adversarial Linear Contextual Bandits via Reductioncited by 4
  9. 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximationcited by 3
  10. 2025Decision Making in Hybrid Environments: A Model Aggregation Approachcited by 3
  11. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
  12. 2025An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPscited by 2
3 more
  1. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  2. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0
  3. 2026Follow the Perturbed Leader for Linear Bandits: √T Regret over General Convex Setscited by 0