Data to 7 Oct 2026

Learning Adversarial MDPs with Bandit Feedback and Unknown Transition

arXiv 1912.01192 ↗First posted 3 Dec 2019cs.LG stat.MLcited by 84

Not on the map. Why?

Abstract (arXiv)

We consider the problem of learning in episodic finite-horizon Markov decision processes with an unknown transition function, bandit feedback, and adversarial losses. We propose an efficient algorithm that achieves mathcaltildeO(L|X|√|A|T) regret with high probability, where L is the horizon, |X| is the number of states, |A| is the number of actions, and T is the number of episodes. To the best of our knowledge, our algorithm is the first to ensure mathcaltildeO(√T) regret in this challenging setting; in fact it achieves the same regret bound as (Rosenberg & Mansour, 2019a) that considers an easier setting with full-information feedback. Our key technical contributions are two-fold: a tighter confidence set for the transition function, and an optimistic loss estimator that is inversely weighted by an textitupper occupancy bound.

Key facts. Cited by 84 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Dec 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 21; 2022: 10; 2023: 21; 2024: 16; 2025: 12; 2026: 4.

84 papers.

Sort:

By area:

2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
2021Corruption-Robust Offline Reinforcement Learningcited by 51
2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 34
2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
2021Robust Policy Gradient against Strong Data Corruptioncited by 30
2021Minimax Regret for Stochastic Shortest Pathcited by 30
2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30

38 more

2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
2021Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recallcited by 21
2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
2022Online Policy Optimization for Robust MDPcited by 19
2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 18
2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
2023Best of Both Worlds Policy Optimizationcited by 17
2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 16
2022Robust Anytime Learning of Markov Decision Processescited by 16
2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
2023A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPscited by 15
2024Learning Adversarial MDPs with Stochastic Hard Constraintscited by 15
2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
2022Dynamic Regret of Online Markov Decision Processescited by 13
2022Socially Fair Reinforcement Learningcited by 13
2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 13
2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
2021Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximationcited by 11
2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimizationcited by 11
2021Online Markov Decision Processes with Aggregate Bandit Feedbackcited by 10
2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
2023A Best-of-Both-Worlds Algorithm for Constrained MDPs with Long-Term Constraintscited by 9
2023Semi-Bandit Learning for Monotone Stochastic Optimizationcited by 8
2024Markov Persuasion Processes: Learning to Persuade from Scratchcited by 8
2024Beyond Worst-case Attacks: Robust RL with Adaptive Defense via Non-dominated Policiescited by 8
2024Uncertainty-based Offline Variational Bayesian Reinforcement Learning for Robustness under Diverse Data Corruptionscited by 8
2023Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learningcited by 7
2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
2024Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transitioncited by 6
2023Non-stationary Reinforcement Learning under General Function Approximationcited by 5
2024Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraintscited by 5
2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5

50 most cited of 84 All 84 (JSON)