mlsanityData to 7 Oct 2026

Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs

arXiv 2102.08940 ↗First posted 17 Feb 2021cs.LG math.OC stat.MLcited by 28

Not on the map. Why?

Abstract (arXiv)

Learning Markov decision processes (MDPs) in the presence of the adversary is a challenging problem in reinforcement learning (RL). In this paper, we study RL in episodic MDPs with adversarial reward and full information feedback, where the unknown transition probability function is a linear function of a given feature mapping, and the reward function can change arbitrarily episode by episode. We propose an optimistic policy optimization algorithm POWERS and show that it can achieve tildeO(dH√T) regret, where H is the length of the episode, T is the number of interactions with the MDP, and d is the dimension of the feature mapping. Furthermore, we also prove a matching lower bound of tildeOmega(dH√T) up to logarithmic factors. Our key technical contributions are two-fold: (1) a new value function estimator based on importance weighting; and (2) a tighter confidence set for the transition kernel. They together lead to the nearly minimax optimal regret.

Key facts. Cited by 28 papers in the map (data through 7 Oct 2026). Builds on 23 of its 54 references that are in the map. First posted on arXiv 17 Feb 2021.

Builds on

23 of 54 references.

References · 23

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  6. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  7. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  8. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  9. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  10. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  11. 2017A unified view of entropy-regularized Markov decision processescited by 174
  12. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
11 more
  1. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  2. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  3. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  4. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  5. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  6. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  7. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  8. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  9. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 75
  10. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
  11. 2020Adaptive Approximate Policy Iterationcited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 1; 2023: 11; 2024: 8; 2025: 2; 2026: 5.

28 papers.

Sort:

By area:

  1. 2024Reinforcement Learning from Human Feedback with Active Queriescited by 39
  2. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  3. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  4. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  5. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 18
  6. 2023Best of Both Worlds Policy Optimizationcited by 17
  7. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  8. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 15
  9. 2024Imitation Learning in Discounted Linear MDPs without exploration assumptionscited by 15
  10. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
  11. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  12. 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Banditscited by 9
16 more
  1. 2024Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transitioncited by 6
  2. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  3. 2024Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPscited by 5
  4. 2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4
  5. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  6. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Banditscited by 3
  7. 2023Policy Optimization via Adv2: Adversarial Learning on Advantage Functionscited by 2
  8. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
  9. 2025Reinforcement Learning in Switching Non-Stationary Markov Decision Processes: Algorithms and Convergence Analysiscited by 2
  10. 2023Online Resource Allocation in Episodic Markov Decision Processescited by 1
  11. 2024Provably Efficient Off-Policy Adversarial Imitation Learning with Convergence Guaranteescited by 1
  12. 2026Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewardscited by 1
  13. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 1
  14. 2024Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimizationcited by 0
  15. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0
  16. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0