Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs

Jiafan He, Dongruo Zhou, Quanquan Gu
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:4259-4280, 2022.

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 ˜O(dH√T) regret, where H is the length of the episode, T is the number of interaction with the MDP, and d is the dimension of the feature mapping. Furthermore, we also prove a matching lower bound of ˜Ω(dH√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 regret.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-he22a, title = { Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs }, author = {He, Jiafan and Zhou, Dongruo and Gu, Quanquan}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {4259--4280}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/he22a/he22a.pdf}, url = {https://proceedings.mlr.press/v151/he22a.html}, 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 interaction with the MDP, and $d$ is the dimension of the feature mapping. Furthermore, we also prove a matching lower bound of $\tilde{\Omega}(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 regret. } }
Endnote
%0 Conference Paper %T Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs %A Jiafan He %A Dongruo Zhou %A Quanquan Gu %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-he22a %I PMLR %P 4259--4280 %U https://proceedings.mlr.press/v151/he22a.html %V 151 %X 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 interaction with the MDP, and $d$ is the dimension of the feature mapping. Furthermore, we also prove a matching lower bound of $\tilde{\Omega}(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 regret.
APA
He, J., Zhou, D. & Gu, Q.. (2022). Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:4259-4280 Available from https://proceedings.mlr.press/v151/he22a.html.

Related Material