Learning Adversarial MDPs with Bandit Feedback and Unknown Transition

Abstract

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 $\tilde{\mathcal{O}}(L|X|\sqrt{|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 $\tilde{\mathcal{O}}(\sqrt{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 $\text{upper occupancy bound}$.

arXiv commentFix a bug

References in corpus (8)

• Empirical Bernstein Bounds and Sample Variance Penalization
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• Online Convex Optimization in Adversarial Markov Decision Processes
• Minimax Regret Bounds for Reinforcement Learning
• Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• Explore no more: Improved high-probability regret bounds for non-stochastic bandits
• Deterministic MDPs with Adversarial Rewards and Bandit Feedback

Cited by in corpus (22)

• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Exploration-Exploitation in Constrained MDPs
• Corruption-robust exploration in episodic reinforcement learning
• Near-Optimal Reinforcement Learning with Self-Play
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss
• Dynamic Regret of Policy Optimization in Non-stationary Environments
• Optimistic Policy Optimization with Bandit Feedback
• Online learning in MDPs with linear function approximation and bandit feedback
• Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model
• Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
• Minimax Regret for Stochastic Shortest Path
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Bandit Linear Control
• Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits
• Confidence-Budget Matching for Sequential Budgeted Learning
• Online Boosting with Bandit Feedback
• Online Learning in Unknown Markov Games
• Reinforcement Learning in Reward-Mixing MDPs
• Towards Fundamental Limits of Multi-armed Bandits with Random Walk Feedback
• Refined Analysis of FPL for Adversarial Markov Decision Processes