Efficient Policy Learning for Non-Stationary MDPs under Adversarial Manipulation
This addresses the challenge of adversarial and non-stationary environments in reinforcement learning, which is crucial for applications like multi-agent systems, but the approach is incremental as it builds on existing bandit reduction methods.
The paper tackles the problem of learning policies in non-stationary MDPs with adversarial changes across episodes by developing an Adversarial Reinforcement Learning algorithm, achieving optimal regret bounds of O(√SATH³) with respect to state, action, and time parameters.
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{SATH^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.