Minimum-Delay Adaptation in Non-Stationary Reinforcement Learning via Online High-Confidence Change-Point Detection

Non-stationary environments are challenging for reinforcement learning\nalgorithms. If the state transition and/or reward functions change based on\nlatent factors, the agent is effectively tasked with optimizing a behavior that\nmaximizes performance over a possibly infinite random sequence of Markov\nDecision Processes (MDPs), each of which drawn from some unknown distribution.\nWe call each such MDP a context. Most related works make strong assumptions\nsuch as knowledge about the distribution over contexts, the existence of\npre-training phases, or a priori knowledge about the number, sequence, or\nboundaries between contexts. We introduce an algorithm that efficiently learns\npolicies in non-stationary environments. It analyzes a possibly infinite stream\nof data and computes, in real-time, high-confidence change-point detection\nstatistics that reflect whether novel, specialized policies need to be created\nand deployed to tackle novel contexts, or whether previously-optimized ones\nmight be reused. We show that (i) this algorithm minimizes the delay until\nunforeseen changes to a context are detected, thereby allowing for rapid\nresponses; and (ii) it bounds the rate of false alarm, which is important in\norder to minimize regret. Our method constructs a mixture model composed of a\n(possibly infinite) ensemble of probabilistic dynamics predictors that model\nthe different modes of the distribution over underlying latent MDPs. We\nevaluate our algorithm on high-dimensional continuous reinforcement learning\nproblems and show that it outperforms state-of-the-art (model-free and\nmodel-based) RL algorithms, as well as state-of-the-art meta-learning methods\nspecially designed to deal with non-stationarity.\n