Regret minimization in constrained Markov decision processes

Over the last years, reinforcement learning (RL) has attracted increasing interest from the AI community due to its capability of dealing with complex real-world environments in a sequential way. Standard online RL is usually modeled through the Markov decision process (MDP) framework, where an agent interacts sequentially with a multi-state environment and observes the rewards associated with its trajectory in the MDP. While online learning in classical (unconstrained) MDPs has received considerable attention in recent years, the setting of constrained Markov decision processes (CMDPs) is still largely unexplored. This is surprising, as in many real-world applications---such as autonomous driving, automated bidding, and recommender systems---there are often additional constraints and requirements that an agent needs to satisfy during the learning process. In this dissertation, we study online learning in constrained MDPs. In online CMDPs, the learner (that is, the agent) selects a policy---a distribution over actions for any state---at each step of a given time horizon. As a result, the learner traverses the CMDP and observes the rewards and the costs associated with the constraints for the resulting trajectory. We focus on designing algorithms tailored to simultaneously minimize the regret---that is, the difference in performance between the optimal safe policy and the ones selected by the algorithm during the learning process---and satisfy the constraints, according to some measures of constraints violation. Constrained MDPs have been recently studied in the simplest case, where both rewards and constraints are assumed to be stochastically sampled from fixed distributions. Nonetheless, the gap between standard MDPs and constrained settings is still far from being fully addressed. In this dissertation, we push forward the theoretical understanding of online learning in CMDPs. Specifically, we study different scenarios where rewards and costs may be either stochastic---that is, sampled from fixed distributions---or adversarial---that is, without any statistical assumptions. Moreover, we consider different notions of constraints violation. In the first part, we focus on stochastic CMDPs. We close one of the main open problems in the field by developing the first primal-dual algorithm---without relying on the linear programming formulation of CMDPs---able to achieve the optimal rate for both strong regret and strong constraints violation. These metrics do not allow negative regret (resp. violation) caused by selecting unsafe (resp. safe) policies. In the second part, we study CMDPs with adversarial rewards and stochastic constraints. In such a setting, we develop algorithms capable of attaining different (and optimal) violation rates under the necessary assumptions. In the third part, we provide algorithms capable of simultaneously handling stochastic and adversarial constraints. Specifically, we design best-of-both-worlds algorithms that attain optimal regret and violation bounds when the constraints can be either stochastic or adversarial. Finally, in the fourth and last part of this dissertation, we consider settings where rewards and constraints are sampled from non-stationary distributions, assuming that the level of non-stationarity over time is bounded. In this case, we show how specific challenges arising in adversarial settings can be overcome when the non-stationarity is sufficiently limited.

Negli ultimi anni, l’apprendimento per rinforzo (reinforcement learning, RL) ha suscitato un crescente interesse nella comunità dell’intelligenza artificiale grazie alla sua capacità di affrontare ambienti reali complessi in modo sequenziale. Il RL è solitamente modellato attraverso il framework dei processi decisionali di Markov (Markov Decision Process, MDP), in cui un agente interagisce in modo sequenziale con un ambiente a più stati e osserva le ricompense associate alla sua traiettoria nel MDP. Sebbene l’apprendimento online in MDP classici (non vincolati) abbia ricevuto notevole attenzione negli ultimi anni, l’ambito dei processi decisionali di Markov vincolati (Constrained Markov Decision Processes, CMDP) rimane in gran parte inesplorato. Questo è sorprendente, poiché in molte applicazioni reali---come la guida autonoma, le aste automatizzate e i sistemi di raccomandazione---spesso vi sono vincoli aggiuntivi e requisiti che l’agente deve rispettare durante il processo di apprendimento. In questa dissertazione, studiamo l’apprendimento online nei MDP vincolati. Nei CMDP online, il decisore (cioè l’agente) seleziona una politica (policy)---una distribuzione di probabilità sulle azioni per ogni stato---a ogni step di un dato orizzonte temporale. Di conseguenza, l’agente attraversa il CMDP e osserva le ricompense e i costi associati ai vincoli lungo la traiettoria risultante. Ci concentriamo sulla progettazione di algoritmi in grado di minimizzare il regret---cioè la differenza di performance tra la politica ottimale sicura e quelle selezionate dall’algoritmo durante l’apprendimento---e rispettare i vincoli, secondo alcune misure di violazione dei vincoli. I CMDP sono stati recentemente studiati nel caso più semplice, in cui ricompense e vincoli sono assunti come campionati in modo stocastico da distribuzioni fisse. Tuttavia, il divario tra MDP standard e ambienti vincolati è ancora lontano dall’essere completamente colmato. In questa dissertazione, approfondiamo la comprensione teorica dell'apprendimento online nei CMDP. Analizziamo diversi scenari in cui ricompense e costi possono essere di natura sia stocastica — ovvero campionati da distribuzioni fisse — sia avversaria, cioè generati in modo arbitrario senza alcuna assunzione probabilistica. Inoltre, esploriamo diverse definizioni di violazione dei vincoli. La prima parte è dedicata allo studio dei CMDP stocastici. In questo contesto, risolviamo uno dei principali problemi aperti del settore sviluppando il primo algoritmo primal-dual — che non si basa sulla formulazione tramite programmazione lineare — capace di raggiungere livelli ottimali sia per la metrica di regret forte sia per la violazione forte dei vincoli. Tali metriche non ammettono compensazioni: non è possibile, ad esempio, annullare il regret causato da una politica insicura con i benefici di una politica sicura. Nella seconda parte, esaminiamo i CMDP con ricompense avversarie e vincoli stocastici. Proponiamo una famiglia di algoritmi in grado di raggiungere diversi, e ottimali, livelli di violazione, a seconda delle ipotesi adottate. La terza parte si concentra su scenari più generali, in cui i vincoli possono essere sia stocastici sia avversari. In questo caso, sviluppiamo algoritmi best-of-both-worlds, capaci di garantire prestazioni ottimali in termini di regret e violazione, indipendentemente dalla natura del vincolo. Infine, nella quarta e ultima parte di questa dissertazione, affrontiamo contesti in cui ricompense e vincoli derivano da distribuzioni non stazionarie, ipotizzando che il grado di variazione nel tempo sia limitato. Mostriamo come, in tali ambienti, sia possibile affrontare con successo le sfide tipiche dei modelli avversari, a patto che la non stazionarietà resti entro soglie controllabili.