Minimum delay adaptation in non stationary reinforcement learning via online high confidence change point detection

Abstract

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

Ambientes não-estacionários são desafiadores para algoritmos de aprendizado por reforço. Se as funções de transição de estado e/ou recompensa mudam com base em fatores latentes, o agente é efetivamente encarregado de otimizar um comportamento que maximize o desempenho em uma sequência aleatória possivelmente infinita de Processos de Decisão de Markov (MDPs), cada um deles amostrado de uma distribuição desconhecida. Chamamos cada MDP de um contexto. A maioria dos trabalhos relacionados faz suposições fortes, como conhecimento sobre a distribuição sobre os contextos, a existência de fases de pré-treinamento ou conhecimento a priori sobre o número, a sequência ou os limites entre os contextos. Nós introduzimos um algoritmo que eficientemente aprende políticas em ambientes não-estacionários. Ele analisa um fluxo possivelmente infinito de dados e computa, em tempo real, estatísticas de alta confiança para detecção de pontos de mudança que refletem se novas políticas especializadas precisam ser criadas para lidar com novos contextos ou se políticas previamente otimizadas podem ser reutilizadas. Nós demonstramos que este algoritmo (i) minimiza o atraso até que mudanças imprevistas em um contexto sejam detectadas, permitindo assim respostas rápidas; e (ii) que limita a taxa de alarmes falsos, o que é importante para minimizar o regret. Nosso método constrói uma mistura de modelos composta por um conjunto (possivelmente infinito) de preditores probabilísticos da dinâmica que modelam os diferentes modos de distribuição sobre MDPs latentes subjacentes. Nós avaliamos nosso algoritmo em problemas de aprendizado por reforço contínuos e de alta dimensionalidade e mostramos que ele supera algoritmos RL estado-da-arte (livre de modelo e baseado em modelo), assim como métodos de meta-aprendizado estado-da-arte especialmente projetados para lidar com a não-estacionariedade.