Apprendimento per rinforzo vincolato: un nuovo approccio

L'apprendimento per rinforzo (RL) è una tecnica potente, ma la sua applicazione in ambienti reali, come la robotica e la guida autonoma, richiede particolare attenzione alla sicurezza. I processi decisionali di Markov vincolati (CMDP) sono uno strumento per imporre vincoli di sicurezza durante l'ottimizzazione delle prestazioni.

Un recente studio presenta un nuovo algoritmo per CMDP che affronta i limiti dei metodi esistenti, spesso caratterizzati da violazioni significative della sicurezza o da un'elevata complessità campionaria. L'algoritmo proposto, di tipo primal-duale, bilancia il rimpianto e le violazioni dei vincoli, basandosi su tecniche di RL online e ottimizzazione vincolata.

Dettagli dell'algoritmo e risultati

L'algoritmo è stato analizzato in due contesti: fattibilità rilassata (dove sono ammesse piccole violazioni) e fattibilità rigorosa (nessuna violazione ammessa). I risultati dimostrano che, in caso di fattibilità rilassata, l'algoritmo restituisce una policy ε-ottimale con una violazione ε-limitata, richiedendo un numero di episodi di apprendimento dell'ordine di $\tilde{O}\left(\frac{SAH^3}{\varepsilon^2}\right)$. In caso di fattibilità rigorosa, l'algoritmo garantisce una policy ε-ottimale senza violazioni, con una complessità campionaria di $\tilde{O}\left(\frac{SAH^5}{\varepsilon^2\zeta^2}\right)$, dove ζ è una costante di Slater dipendente dal problema.

Questi risultati suggeriscono che l'apprendimento di CMDP in un contesto online può essere paragonabile all'apprendimento con un modello generativo e non è più complesso dell'apprendimento di MDP non vincolati quando sono consentite piccole violazioni.