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 *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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyyu2019efficient

Related papers

• Near-optimal Policy Optimization Algorithms For Learning Adversarial Linear Mixture Mdps (2021)0.00
• Narrowing The Gap Between Adversarial And Stochastic Mdps Via Policy Optimization (2024)0.00
• Online Learning In Mdps With Partially Adversarial Transitions And Losses (2026)0.00
• Learning Adversarial Markov Decision Processes With Delayed Feedback (2020)0.00
• Efficient Learning In Non-stationary Linear Markov Decision Processes (2020)6.77
• Learning To Collaborate In Markov Decision Processes (2019)0.00
• Near-optimal Regret Using Policy Optimization In Online Mdps With Aggregate Bandit Feedback (2025)0.00
• Improved Algorithm For Adversarial Linear Mixture Mdps With Bandit Feedback And Unknown Transition (2024)0.00