Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses

Abstract

Policy optimization is a widely-used method in reinforcement learning. Due to its local-search nature, however, theoretical guarantees on global optimality often rely on extra assumptions on the Markov Decision Processes (MDPs) that bypass the challenge of global exploration. To eliminate the need of such assumptions, in this work, we develop a general solution that adds dilated bonuses to the policy update to facilitate global exploration. To showcase the power and generality of this technique, we apply it to several episodic MDP settings with adversarial losses and bandit feedback, improving and generalizing the state-of-the-art. Specifically, in the tabular case, we obtain $\tilde{\mathcal{O}}(\sqrt{T})$ regret where $T$ is the number of episodes, improving the $\tilde{\mathcal{O}}(T^{2/3})$ regret bound by Shani et al. (2020). When the number of states is infinite, under the assumption that the state-action values are linear in some low-dimensional features, we obtain $\tilde{\mathcal{O}}(T^{2/3})$ regret with the help of a simulator, matching the result of Neu and Olkhovskaya (2020) while importantly removing the need of an exploratory policy that their algorithm requires. When a simulator is unavailable, we further consider a linear MDP setting and obtain $\tilde{\mathcal{O}}(T^{14/15})$ regret, which is the first result for linear MDPs with adversarial losses and bandit feedback.

References in corpus (12)

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• Online Convex Optimization in Adversarial Markov Decision Processes
• On the Sample Complexity of Reinforcement Learning with a Generative Model
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
• Online learning in MDPs with linear function approximation and bandit feedback
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Improved Regret Bound and Experience Replay in Regularized Policy Iteration