Online Convex Optimization in Adversarial Markov Decision Processes

Abstract

We consider online learning in episodic loop-free Markov decision processes (MDPs), where the loss function can change arbitrarily between episodes, and the transition function is not known to the learner. We show $\tilde{O}(L|X|\sqrt{|A|T})$ regret bound, where $T$ is the number of episodes, $X$ is the state space, $A$ is the action space, and $L$ is the length of each episode. Our online algorithm is implemented using entropic regularization methodology, which allows to extend the original adversarial MDP model to handle convex performance criteria (different ways to aggregate the losses of a single episode) , as well as improve previous regret bounds.

Cited by in corpus (29)

• Game-Theoretic Multiagent Reinforcement Learning
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Logarithmic Regret for Adversarial Online Control
• Exploration-Exploitation in Constrained MDPs
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Corruption-robust exploration in episodic reinforcement learning
• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
• Constrained episodic reinforcement learning in concave-convex and knapsack settings
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
• Optimistic Policy Optimization with Bandit Feedback
• Online learning in MDPs with linear function approximation and bandit feedback
• No-Regret Exploration in Goal-Oriented Reinforcement Learning
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
• Minimax Regret for Stochastic Shortest Path
• Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case
• Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Improved Corruption Robust Algorithms for Episodic Reinforcement Learning
• Active Model Estimation in Markov Decision Processes
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall
• Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses
• Reward is enough for convex MDPs
• Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits
• Adaptive Sampling for Estimating Distributions: A Bayesian Upper Confidence Bound Approach
• Online Learning in Unknown Markov Games
• The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition
• Refined Analysis of FPL for Adversarial Markov Decision Processes