Constrained Contextual Markov Decision Processes

This thesis addresses the topic of online learning in environments that simultaneously exhibit context-dependent characteristics and constraints that must be respected. It introduces the framework of Constrained Contextual Markov Decision Processes, a theoretical model in which rewards, costs, and transition dynamics depend on the observed context, and where policies must maintain adherence to the constraints imposed by the system. The research proposes EBOPT-CCMDP, an optimistic algorithm based on the Eluder dimension, which extends to contextual environments the optimistic linear-programming approach developed for CMDPs. The algorithm constructs confidence sets for rewards, costs, and dynamics using regression oracles, and introduces optimism through exploration bonuses that encourage the discovery of less known states and transitions. At each episode, it selects a policy by solving an optimistic and constrained linear program that maximizes predicted reward while keeping costs within limits compatible with the constraints. The thesis provides high-probability guarantees, showing that both cumulative regret and constraint violation grow sublinearly. The study also includes an implementation of the algorithm, together with a discussion of experimental results in simulated contextual environments. The experiments show behavior consistent with expectations in terms of both cumulative rewards and constraint violations, offering empirical support to the theoretical guarantees. The work also presents a sensitivity analysis evaluating the impact of the number of contextual features and the size of the action space on the algorithm’s performance, highlighting how these factors influence the quality of the learned policies and the stability of the constraints. The thesis concludes by outlining possible future developments, including extending the model to richer classes of functions, improving the algorithm to reduce computational requirements, and addressing scenarios in which no feasible policy exists for certain contexts.

Questa tesi affronta il tema dell’online learning in ambienti che presentano allo stesso tempo caratteristiche dipendenti da informazioni esterne (contesto) e vincoli da rispettare. Viene introdotto il modello dei Constrained Contextual Markov Decision Processes, un modello teorico in cui ricompense, costi e dinamiche di transizione dipendono dal contesto osservato e in cui le policy devono mantenere l’aderenza ai vincoli imposti dal sistema. La ricerca propone EBOPT-CCMDP, un algoritmo ottimistico basato sulla dimensione di Eluder, che estende agli ambienti contestuali l’approccio di programmazione lineare ottimistica sviluppato per i CMDP. L’algoritmo costruisce insiemi di confidenza per ricompense, costi e dinamiche utilizzando oracoli di regressione, e introduce ottimismo tramite bonus di esplorazione che favoriscono la scoperta di stati e transizioni meno noti. Ad ogni episodio seleziona una policy risolvendo un programma lineare ottimistico e vincolato, che massimizza la ricompensa prevista mantenendo i costi entro limiti compatibili con i vincoli. La tesi fornisce garanzie con alta probabilità, mostrando che sia il regret cumulativo sia la violazione dei vincoli crescono in modo sublineare. Lo studio comprende inoltre una proposta di implementazione dell'algoritmo, della quale vengono mostrati e discussi i risultati dei test in ambienti simulati. Gli esperimenti mostrano un comportamento atteso sia in termini di ricompense cumulative, che di violazioni dei vincoli, dando supporto empirico alle garanzie teoriche. Il lavoro include un’analisi di sensibilità che valuta l’impatto del numero di feature contestuali e della dimensione dello spazio delle azioni sulle prestazioni dell’algoritmo, evidenziando come questi fattori influenzino la qualità delle policy apprese e l'aderenza ai vincoli. La tesi si conclude delineando possibili sviluppi futuri, tra cui l’estensione del modello ad altre classi di funzioni, l'efficientamento dell'algoritmo per ridurre il numero di computazioni e l'estensione a casi in cui nessuna policy sia ammissibile per alcuni contesti.