Efficient Policy Learning for Non-Stationary MDPs under Adversarial Manipulation

Abstract

A Markov Decision Process (MDP) is a popular model for reinforcement learning. However, its commonly used assumption of stationary dynamics and rewards is too stringent and fails to hold in adversarial, nonstationary, or multi-agent problems. We study an episodic setting where the parameters of an MDP can differ across episodes. We learn a reliable policy of this potentially adversarial MDP by developing an Adversarial Reinforcement Learning (ARL) algorithm that reduces our MDP to a sequence of \emph{adversarial} bandit problems. ARL achieves $O(\sqrt{SAT{H}^3})$ regret, which is optimal with respect to $S$, $A$, and $T$, and its dependence on $H$ is the best (even for the usual stationary MDP) among existing model-free methods.

There is a problem in the Theorem 1. We will try to fix it and update a new version

References in corpus (10)

• Robust Adversarial Reinforcement Learning
• Multiagent Bidirectionally-Coordinated Nets: Emergence of Human-level Coordination in Learning to Play StarCraft Combat Games
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• On Lower Bounds for Regret in Reinforcement Learning
• Adversarial Attacks on Stochastic Bandits
• Variational Regret Bounds for Reinforcement Learning
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Policy Certificates: Towards Accountable Reinforcement Learning

Cited by in corpus (1)

• Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learning