A primal-dual approach for online learning in constrained tree-form sequential decision problems

Learning in constrained environments and decision making under uncertainty play a central role in many modern applications, where actions must be taken in a safety critical environment. Constrained Markov Decision Processes (CMDPs) provide a general framework for modeling such problems. However, designing algorithms that simultaneously ensure strong performance and constraint satisfaction remains a significant challenge. This work begins by presenting a comparative analysis of two established algorithms for CMDPs. The comparison highlights their theoretical guarantees, convergence behaviour and the practical trade-offs in realistic constrained scenarios. At the same time, it raises the question of whether similar results can be achieved in a more structured environment. Motivated by this challenge, the second part of this research extends the setting to account for sequential dynamics and partial observability. Formally, the setting is called a Constrained Tree-Form Sequential Decision Making (CTFSDM) problem. There are existing algorithms that can achieve optimal performance, but they typically rely on linear programming formulations, which are inefficient. These limitations motivate the development of a novel algorithm that is computationally efficient and scalable, without requiring any prior knowledge or assumptions about the environment and maintaining strong theoretical guarantees. More precisely, the proposed algorithm, called Constrained Primal-Dual Adaptive Follow the Regularized Leader (CPD-FTRL), is based on a primal-dual optimization scheme that leverages a state-of-the-art algorithm originally developed for unconstrained adversarial environments, namely the two-player zero-sum games, and adapts it to a constrained stochastic setting. A theoretical analysis is provided, demonstrating that the proposed algorithm achieves optimal guarantees while remaining computationally efficient. Overall, this work contributes a theoretically grounded framework for constrained online decision-making in complex, partially observable settings.

L’apprendimento in ambienti vincolati e il processo decisionale in condizioni di incertezza svolgono un ruolo centrale in molte applicazioni moderne, dove le decisioni devono essere prese in contesti in cui la sicurezza è cruciale. I Processi Decisionali di Markov Vincolati (CMDP) offrono una struttura generale per modellare tali problemi. Tuttavia, sviluppare algoritmi che garantiscano prestazioni elevate e rispetto dei vincoli rimane una sfida. Questo lavoro inizia presentando un’analisi comparativa di due algoritmi consolidati per i CMDP. Il confronto ne evidenzia le garanzie teoriche, la convergenza e i compromessi pratici in scenari vincolati realistici. Allo stesso tempo, solleva la questione se risultati simili possano essere ottenuti in un ambiente più strutturato. Motivata da questa sfida, la seconda parte di questa ricerca estende il contesto per tenere conto di una dinamica sequenziale e di osservabilità parziale. Formalmente, il contesto è chiamato problema di Decision Making Sequenziale in Forma ad Albero Vincolato (CTFSDM). Esistono algoritmi in grado di raggiungere prestazioni ottimali, ma tipicamente si basano su formulazioni di programmazione lineare, che risultano inefficienti. Queste limitazioni motivano lo sviluppo di un nuovo algoritmo che sia computazionalmente efficiente e scalabile, senza richiedere alcuna conoscenza o assunzione sull’ambiente e mantenendo al contempo simili garanzie teoriche. Più precisamente, l’algoritmo proposto, denominato Constrained Primal-Dual Adaptive Follow the Regularized Leader (CPD-FTRL), si basa su uno schema di ottimizzazione primale-duale che sfrutta un algoritmo allo stato dell’arte originariamente sviluppato per ambienti avversari non vincolati, in particolare i giochi a somma zero tra due giocatori, adattandolo ad un contesto stocastico vincolato. Viene fornita un’analisi teorica che dimostra come l’algoritmo proposto raggiunga garanzie ottimali mantenendo al contempo efficienza computazionale. Nel complesso, questo lavoro contribuisce con un nuovo approccio teoricamente fondato per il processo decisionale sequenziale vincolato in contesti complessi e parzialmente osservabili.