Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach

Abstract

We propose a black-box reduction that turns a certain reinforcement learning algorithm with optimal regret in a (near-)stationary environment into another algorithm with optimal dynamic regret in a non-stationary environment, importantly without any prior knowledge on the degree of non-stationarity. By plugging different algorithms into our black-box, we provide a list of examples showing that our approach not only recovers recent results for (contextual) multi-armed bandits achieved by very specialized algorithms, but also significantly improves the state of the art for (generalized) linear bandits, episodic MDPs, and infinite-horizon MDPs in various ways. Specifically, in most cases our algorithm achieves the optimal dynamic regret $\tilde{\mathcal{O}}(\min \{\sqrt{LT},{\Delta }^{1/3}{T}^{2/3}\})$ where $T$ is the number of rounds and $L$ and $\Delta$ are the number and amount of changes of the world respectively, while previous works only obtain suboptimal bounds and/or require the knowledge of $L$ and $\Delta$.

References in corpus (25)

• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Efficient Contextual Bandits in Non-stationary Worlds
• Weighted Linear Bandits for Non-Stationary Environments
• Online Convex Optimization in Adversarial Markov Decision Processes
• A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
• Tracking the Best Expert in Non-stationary Stochastic Environments
• 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
• Variational Regret Bounds for Reinforcement Learning
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Deterministic MDPs with Adversarial Rewards and Bandit Feedback
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
• Nonstationary Reinforcement Learning with Linear Function Approximation
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
• Regret Bound Balancing and Elimination for Model Selection in Bandits and RL
• Algorithms for Non-Stationary Generalized Linear Bandits
• A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces
• Regret Balancing for Bandit and RL Model Selection
• Strongly Adaptive Online Learning
• Combinatorial Semi-Bandit in the Non-Stationary Environment
• Efficient Learning in Non-Stationary Linear Markov Decision Processes
• Regret Bounds for Generalized Linear Bandits under Parameter Drift

Cited by in corpus (2)

• Bandit Algorithms for Precision Medicine
• Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systems