Dealing with non-stationarity in Constrained Markov Decision Processes

In constrained Markov decision processes (CMDPs) with adversarial rewards and constraints, a well-known impossibility result prevents any algorithm from attaining both sublinear regret and sublinear constraint violation, when competing against a best-in-hindsight policy that satisfies constraints on average. In this thesis, we show that this negative result can be eased in CMDPs with non-stationary rewards and constraints, by providing algorithms whose performances smoothly degrade as non-stationarity increases. Specifically, we propose algorithms attaining Õ(√T + C) regret and positive constraint violation under bandit feed-back, where C is a corruption value measuring the environment non-stationarity. This can be Θ(T ) in the worst case, coherently with the impossibility result for adversarial CMDPs. First, we design an algorithm with the desired guarantees when C is known. Then, in the case C is unknown, we show how to obtain the same results by embedding such an algorithm in a general meta-procedure. This is of independent interest, as it can be applied to any non-stationary constrained online learning setting. Finally we design an algorithm that under the same condition, with known C, attains Õ(√T ) regret and Õ(√T + C) positive constraint violation.

Nei Processi Decisionali di Markov Vincolati (Constrained Markov Decision Processes o CMDP) con ricompense e vincoli avversari, un noto risultato di impossibilità impedisce a qualsiasi algoritmo di ottenere sia un regret sublineare che una violazione dei vincoli sublineare, quando si compete contro una politica ottimale in retrospettiva che soddisfa i vincoli in media. In questa tesi, mostriamo che questo risultato negativo può essere attenuato nei CMDP con ricompense e vincoli non stazionari, fornendo algoritmi le cui prestazioni degradano gradualmente con l’aumentare della non stazionarietà. In particolare, proponiamo algoritmi che ottengono un regret di Õ(√T + C) e una violazione dei vincoli positiva con un feedback di tipo bandit, dove C è un valore di corruzione che misura la non stazionarietà dell’ambiente. Nel peggiore dei casi, questo valore può essere Θ(T ), in coerenza con il risultato di impossibilità per i CMDP avversari. Innanzitutto, progettiamo un algoritmo con le garanzie desiderate quando C è noto. Successivamente, nel caso in cui C sia sconosciuto, mostriamo come ottenere gli stessi risultati incorporando tale algoritmo in una meta-procedura generale. Questa è di per sé interessante, poiché può essere applicata a qualsiasi contesto di apprendimento online vincolato non stazionario. Infine, progettiamo un algoritmo che, nelle stesse condizioni, con C noto, ottiene un regret di Õ(√T ) e una violazione positiva dei vincoli di Õ(√T + C).