Near-optimal Policy Optimization Algorithms For Learning Adversarial Linear Mixture Mdps

Abstract

Learning Markov decision processes (MDPs) in the presence of the adversary is a challenging problem in reinforcement learning (RL). In this paper, we study RL in episodic MDPs with adversarial reward and full information feedback, where the unknown transition probability function is a linear function of a given feature mapping, and the reward function can change arbitrarily episode by episode. We propose an optimistic policy optimization algorithm POWERS and show that it can achieve \(\tilde\{O\}(dH\sqrt\{T\})\) regret, where \(H\) is the length of the episode, \(T\) is the number of interactions with the MDP, and \(d\) is the dimension of the feature mapping. Furthermore, we also prove a matching lower bound of \(\tilde\{Ω\}(dH\sqrt\{T\})\) up to logarithmic factors. Our key technical contributions are two-fold: (1) a new value function estimator based on importance weighting; and (2) a tighter confidence set for the transition kernel. They together lead to the nearly minimax optimal

Stats

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

Related papers

• Improved Algorithm For Adversarial Linear Mixture Mdps With Bandit Feedback And Unknown Transition (2024)0.00
• Efficient Policy Learning For Non-stationary Mdps Under Adversarial Manipulation (2019)0.00
• Narrowing The Gap Between Adversarial And Stochastic Mdps Via Policy Optimization (2024)0.00
• Nearly Minimax Optimal Reinforcement Learning For Linear Markov Decision Processes (2022)0.00
• A Theoretical Analysis Of Optimistic Proximal Policy Optimization In Linear Markov Decision Processes (2023)0.00
• Optimistic Policy Optimization Is Provably Efficient In Non-stationary Mdps (2021)0.00
• Towards Optimal Regret In Adversarial Linear Mdps With Bandit Feedback (2023)0.00
• Efficient Learning In Non-stationary Linear Markov Decision Processes (2020)6.77