Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs

Abstract

We study episodic reinforcement learning (RL) in non-stationary linear kernel Markov decision processes (MDPs). In this setting, both the reward function and the transition kernel are linear with respect to the given feature maps and are allowed to vary over time, as long as their respective parameter variations do not exceed certain variation budgets. We propose the \underline{p}eriodically \underline{r}estarted \underline{o}ptimistic \underline{p}olicy \underline{o}ptimization algorithm (PROPO), which is an optimistic policy optimization algorithm with linear function approximation. PROPO features two mechanisms: sliding-window-based policy evaluation and periodic-restart-based policy improvement, which are tailored for policy optimization in a non-stationary environment. In addition, only utilizing the technique of sliding window, we propose a value-iteration algorithm. We establish dynamic upper bounds for the proposed methods and a minimax lower bound which shows the (near-) optimality of the proposed methods. To our best knowledge, PROPO is the first provably efficient policy optimization algorithm that handles non-stationarity.

References in corpus (21)

• Trust Region Policy Optimization
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Robust Adversarial Reinforcement Learning
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• On the Global Convergence Rates of Softmax Policy Gradient Methods
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Weighted Linear Bandits for Non-Stationary Environments
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• On Lower Bounds for Regret in Reinforcement Learning
• Online Convex Optimization in Adversarial Markov Decision Processes
• A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Hedging the Drift: Learning to Optimize under Non-Stationarity
• A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitions
• A Simple Approach for Non-stationary Linear Bandits
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Nonstationary Reinforcement Learning with Linear Function Approximation
• Dynamic Regret of Policy Optimization in Non-stationary Environments