mlsanityData to 7 Oct 2026

Refined Regret for Adversarial MDPs with Linear Function Approximation

arXiv 2301.12942 ↗First posted 30 Jan 2023cs.LG cs.AI stat.MLcited by 18

Not on the map. Why?

Abstract (arXiv)

We consider learning in an adversarial Markov Decision Process (MDP) where the loss functions can change arbitrarily over K episodes and the state space can be arbitrarily large. We assume that the Q-function of any policy is linear in some known features, that is, a linear function approximation exists. The best existing regret upper bound for this setting (Luo et al., 2021) is of order tildemathcal O(K2/3) (omitting all other dependencies), given access to a simulator. This paper provides two algorithms that improve the regret to tildemathcal O(√ K) in the same setting. Our first algorithm makes use of a refined analysis of the Follow-the-Regularized-Leader (FTRL) algorithm with the log-barrier regularizer. This analysis allows the loss estimators to be arbitrarily negative and might be of independent interest. Our second algorithm develops a magnitude-reduced loss estimator, further removing the polynomial dependency on the number of actions in the first algorithm and leading to the optimal regret bound (up to logarithmic terms and dependency on the horizon). Moreover, we also extend the first algorithm to simulator-free linear MDPs, which achieves tildemathcal O(K8/9) regret and greatly improves over the best existing bound tildemathcal O(K14/15). This algorithm relies on a better alternative to the Matrix Geometric Resampling procedure by Neu & Olkhovskaya (2020), which could again be of independent interest.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). Builds on 19 of its 41 references that are in the map. First posted on arXiv 30 Jan 2023.

Builds on

19 of 41 references.

References · 19

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  3. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  4. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  5. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  6. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  7. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  8. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  9. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  10. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  11. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  12. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
7 more
  1. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  2. 2020Efficient and Robust Algorithms for Adversarial Linear Contextual Banditscited by 42
  3. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  4. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 29
  5. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  6. 2021Scale Free Adversarial Multi Armed Banditscited by 12
  7. 2019Equipping Experts/Bandits with Long-term Memorycited by 9

Built on by

Cited by year (2026 to 7 Oct)

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

18 papers.

Sort:

By area:

  1. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  2. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  3. 2024Imitation Learning in Discounted Linear MDPs without exploration assumptionscited by 15
  4. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
  5. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  6. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  7. 2025Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learningcited by 12
  8. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  9. 2023Adversarial Contextual Bandits Go Kernelizedcited by 6
  10. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  11. 2025Enhancing PPO with Trajectory-Aware Hybrid Policiescited by 4
  12. 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximationcited by 3
6 more
  1. 2025An Improved Algorithm for Adversarial Linear Contextual Bandits via Reductioncited by 3
  2. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
  3. 2025An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPscited by 2
  4. 2026Optimal Regret for Policy Optimization in Contextual Banditscited by 1
  5. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  6. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0