Treating non-stationarity as a partially observable problem: a theoretical analysis in the context of sequential decision-making

Sequential decision-making provides the formal foundation for designing autonomous agents that learn to act optimally through interaction with uncertain and possibly evolving environments. Reinforcement Learning (RL) offers a powerful set of algorithmic and theoretical tools to address such problems, typically relying on the framework of Markov Decision Processes (MDPs). While this formalism has enabled significant progress, it relies on two critical assumptions: stationarity of the environment dynamics and full observability of the state space. These assumptions are rarely satisfied in practical scenarios, where the environment may change over time and the agent may only receive partial or noisy information about the underlying state. This dissertation investigates how non-stationarity can be systematically addressed through the lens of partial observability. Specifically, we consider settings in which the evolution of the environment is driven by latent variables that are not directly observable by the agent. By modelling these latent dynamics explicitly, non-stationary environments can be reformulated as stationary but partially observable systems, enabling the use of the theoretical machinery of Partially Observable Markov Decision Processes (POMDPs). We explore this perspective across three increasingly challenging settings. In the first part of the research, we study a scenario where the non-stationarity is exogenous and evolves independently of the agent's actions. We introduce a Latent Bandit framework in which the environment switches between a finite number of Bandit instances according to an unobserved Markov process. We propose a learning algorithm that estimates the transition dynamics by using simple action selection strategies, and we provide sublinear regret guarantees for an algorithm that employs this estimation approach. In the second part, we consider a more complex setting in which the agent's actions influence the latent dynamics. We model this problem as a POMDP with a known observation model but an unknown transition model. We design provably efficient algorithms for this setting, based on both stochastic and deterministic policies, and establish sublinear regret bounds under structural assumptions on the model. Finally, we address the most general setting, where neither the transition nor the observation model is known. We develop a novel spectral estimation procedure that employs samples collected from a diverse set of belief-based policies, and we derive a learning algorithm with provable guarantees in this fully unknown POMDP scenario. Using an optimistic strategy, we achieve state-of-the-art regret bounds that scale conveniently with the relevant problem parameters. Overall, the dissertation establishes a comprehensive framework that unifies non-stationary and partially observable learning problems. Through a sequence of progressively general models and algorithms, it demonstrates that by explicitly modeling latent dynamics, non-stationary systems can be transformed into stationary but partially observable ones, thus enabling principled analysis and efficient learning with strong theoretical guarantees.

Le decisioni sequenziali forniscono le basi formali per la progettazione di agenti autonomi in grado di apprendere a comportarsi in modo ottimale attraverso l’interazione con ambienti incerti e potenzialmente in evoluzione. L’apprendimento per rinforzo (Reinforcement Learning, RL) offre un potente insieme di strumenti algoritmici e teorici per affrontare tali problemi, tipicamente basandosi sul formalismo dei Markov Decision Processes (MDP). Sebbene questo quadro abbia consentito notevoli progressi, esso si fonda su due ipotesi cruciali: la stazionarietà dell’ambiente e l'osservabilità dello stato del sistema. Tali ipotesi risultano raramente soddisfatte in scenari reali, nei quali l’ambiente può variare nel tempo e l’agente può ricevere soltanto informazioni parziali o rumorose sullo stato sottostante. Questa tesi indaga come la non-stazionarietà possa essere affrontata sistematicamente sfruttando il concetto di parziale osservabilità. In particolare, consideriamo contesti nei quali l’evoluzione dell’ambiente è guidata da variabili latenti non direttamente osservabili dall’agente. Modellando esplicitamente tali dinamiche latenti, ambienti non stazionari possono essere riformulati come sistemi stazionari ma parzialmente osservabili, consentendo così l’applicazione dell’apparato teorico dei Partially Observable Markov Decision Processes (POMDP). Esploriamo questa prospettiva in tre scenari di complessità crescente. Nella prima parte del lavoro, studiamo un caso in cui la non-stazionarietà è esogena ed evolve indipendentemente dalle azioni dell’agente. Introduciamo un modello di tipo Latent Bandit in cui le istanze di bandit con cui l'agent interagisce cambiano nel tempo in modo governato da un processo di Markov non noto. In questo contesto, proponiamo un algoritmo di apprendimento che stima le dinamiche di transizione utilizzando semplici strategie di selezione delle azioni, e forniamo garanzie di regret sublineare per un algoritmo che impiega tale approccio di stima. Nella seconda parte, consideriamo un contesto più complesso in cui le azioni dell’agente influenzano le dinamiche latenti. Modelliamo il problema come un POMDP con modello di osservazione noto ma modello di transizione non noto. Il contributo in questo contesto consiste nel proporre algoritmi efficienti che siano in grado di fornire delle garanzie teoriche rispetto alla stima del modello considerato. Tali approcci sono basati sia su politiche stocastiche sia su politiche deterministiche. In ultimo, forniamo garanzie di regret sublineare, utilizzando alcune ipotesi strutturali sul modello. Infine, affrontiamo il setting più generale, in cui né il modello di transizione né quello di osservazione sono noti. Sviluppiamo una nuova procedura di stima spettrale che utilizza campioni raccolti da un insieme diversificato di politiche, e deriviamo un algoritmo di apprendimento con garanzie teoriche in questo scenario con POMDP completamente ignoto. Adottando una strategia ottimistica, miglioriamo le garanzie di regret rispetto allo stato dell’arte e dimostriamo che il regret scala in modo conveniente con i parametri rilevanti del problema. Complessivamente, la tesi propone un quadro teorico e algoritmico unificato che connette i problemi di apprendimento in ambienti non stazionari e parzialmente osservabili. Attraverso una sequenza di modelli e algoritmi di complessità crescente, dimostriamo che modellando esplicitamente le dinamiche latenti è possibile trasformare sistemi non stazionari in sistemi stazionari ma parzialmente osservabili, consentendo così un’analisi rigorosa e un apprendimento efficiente con solide garanzie teoriche.