# Refined Regret for Adversarial MDPs with Linear Function Approximation

arXiv: https://arxiv.org/abs/2301.12942 · HTML: https://mlsanity.com/paper/2301.12942/

## Key facts

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

## Builds on (most cited first, 19 of 19)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning](https://mlsanity.com/paper/2007.08459/) (2020)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Online Convex Optimization in Adversarial Markov Decision Processes](https://mlsanity.com/paper/1905.07773/) (2019)
- [Optimistic Policy Optimization with Bandit Feedback](https://mlsanity.com/paper/2002.08243/) (2020)
- [Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation](https://mlsanity.com/paper/2103.12923/) (2021)
- [Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses](https://mlsanity.com/paper/2107.08346/) (2021)
- [Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2007.11849/) (2020)
- [Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2002.00287/) (2020)
- [Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design](https://mlsanity.com/paper/2207.02575/) (2022)
- [Online learning in MDPs with linear function approximation and bandit feedback](https://mlsanity.com/paper/2007.01612/) (2020)
- [Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2102.08940/) (2021)
- [Scale Free Adversarial Multi Armed Bandits](https://mlsanity.com/paper/2106.04700/) (2021)
- [Equipping Experts/Bandits with Long-term Memory](https://mlsanity.com/paper/1905.12950/) (2019)

## Built on by (most cited first, 19 of 19)

- [A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes](https://mlsanity.com/paper/2305.08841/) (2023)
- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimization](https://mlsanity.com/paper/2302.06834/) (2023)
- [Imitation Learning in Discounted Linear MDPs without exploration assumptions](https://mlsanity.com/paper/2405.02181/) (2024)
- [Rate-Optimal Policy Optimization for Linear Markov Decision Processes](https://mlsanity.com/paper/2308.14642/) (2023)
- [Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback](https://mlsanity.com/paper/2310.11550/) (2023)
- [Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning](https://mlsanity.com/paper/2502.13900/) (2025)
- [Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2305.07911/) (2023)
- [Adversarial Contextual Bandits Go Kernelized](https://mlsanity.com/paper/2310.01609/) (2023)
- [Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback](https://mlsanity.com/paper/2311.07876/) (2023)
- [Enhancing PPO with Trajectory-Aware Hybrid Policies](https://mlsanity.com/paper/2502.15968/) (2025)
- [An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction](https://mlsanity.com/paper/2508.11931/) (2025)
- [Refined Sample Complexity for Markov Games with Independent Linear Function Approximation](https://mlsanity.com/paper/2402.07082/) (2024)
- [Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback](https://mlsanity.com/paper/2411.06739/) (2024)
- [An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs](https://mlsanity.com/paper/2510.08882/) (2025)
- [Optimal Regret for Policy Optimization in Contextual Bandits](https://mlsanity.com/paper/2602.13700/) (2026)
- [Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts](https://mlsanity.com/paper/2606.14929/) (2026)
- [Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses](https://mlsanity.com/paper/2605.11535/) (2026)
- [Follow the Perturbed Leader for Linear Bandits: √T Regret over General Convex Sets](https://mlsanity.com/paper/2610.17818/) (2026)

## 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.