Online learning with uncertain constraints : cumulative and replenishable violations

Learning how to act optimally in complex environments constitutes a crucial milestone in the field of artificial intelligence. In recent years, considerable attention has been directed towards investigating online learning in microeconomic settings, such as Bayesian Persuasion, Mechanism Design, and many other economic scenarios. This line of research is primarily motivated by the fact that it allows overcoming the often unrealistic assumptions of perfect knowledge regarding the exact configuration of the environment. However, most learning paradigms tend to overlook the presence of constraints that are ubiquitous in many real-world applications. These constraints are usually uncertain, and one cannot simply restrict the decision space a priori but needs to adapt online to the observed constraint violations. In this thesis, we take a step towards examining the impact of uncertain constraints on the learning process. Depending on the application, constraints may encapsulate various real-world requirements. For instance, in autonomous driving, safety prerequisites are typically demanded and can be defined by a set of constraints. Similarly, in online advertising, constraints may be imposed on the total budget to spend. Nonetheless, these constraints manifest very distinct characteristics. In safety constraints, the objective is to avoid violating the constraints entirely, while in budget constraints, some overspending in certain phases and underspending in others are permissible, as long as the overall budget constraint is satisfied. The former are referred to as per-round constraints, while the latter are termed long-term constraints. Therefore, when considering these two complementary settings, we necessitate two different measures for quantifying the effectiveness of the designed algorithms in satisfying the constraints. Namely, this thesis investigating two types of constraint violations, namely cumulative violations and replenishable violations, which are appropriate for per-round and long-term constraints, respectively. In the former, we solely consider the constraint violations incurred by the algorithm, whereas in the latter, we permit the violations to be offset by rounds in which the constraints are satisfied. In this thesis, we analyze the diverse effects of constraints on learning agents in various microeconomic settings. Particularly, in the presence of per-round constraints, we explore various sequential decision models and demonstrate that achieving zero constraint violations is impossible. However, we show that attaining asymptotically small cumulative violations is possible. Conversely, in the presence of long-term constraints, in settings resembling budget constraints, we can establish results that would otherwise be unattainable if no violations were allowed.

Apprendere come comportarsi in modo ottimale in ambienti complessi costituisce una pietra miliare cruciale nel campo dell'intelligenza artificiale. Negli ultimi anni, considerevole attenzione è stata dedicata all'indagine dell'apprendimento online in contesti microeconomici, come la Persuasione Bayesiana, il Design di Meccanismi e molti altri scenari economici. Questa linea di ricerca è principalmente motivata dal fatto che consente di superare le spesso irrealistiche ipotesi di conoscenza perfetta dell’esatta configurazione dell'ambiente. Tuttavia, la maggior parte dei paradigmi di apprendimento tende a trascurare la presenza di vincoli che sono onnipresenti in molte applicazioni del mondo reale. Questi vincoli sono di solito incerti e non è possibile semplicemente limitare lo spazio decisionale a priori, ma è necessario adattarsi online alle violazioni dei vincoli osservate. In questa tesi, compiamo un passo verso lo studio dell'impatto dei vincoli incerti sul processo di apprendimento. A seconda dell'applicazione, i vincoli possono racchiudere vari requisiti del mondo reale. Ad esempio, nella guida autonoma, sono tipicamente richiesti requisiti di sicurezza e possono essere definiti da un insieme di vincoli. Allo stesso modo, nella pubblicità online, possono essere imposti vincoli al budget totale da spendere. Tuttavia, questi vincoli manifestano caratteristiche molto distinte. Nei vincoli di sicurezza, l'obiettivo è evitare completamente di violare i vincoli, mentre nei vincoli di budget, è ammissibile un certo eccesso di spesa in alcune fasi e un certo deficit in altre, purché il vincolo di budget complessivo sia soddisfatto. I primi sono definiti vincoli per round, mentre i secondi sono definiti vincoli a lungo termine. Pertanto, considerando questi due contesti complementari, è necessario utilizzare due diverse misure per quantificare l'efficacia degli algoritmi progettati nel soddisfare i vincoli. In particolare, questa tesi investiga due tipi di violazioni dei vincoli, ovvero le violazioni cumulative e le violazioni ripristinabili, che sono appropriate per vincoli per round e vincoli a lungo termine, rispettivamente. Nelle prime, consideriamo solo le violazioni dei vincoli incorse dall'algoritmo, mentre nelle seconde permettiamo che le violazioni siano compensate dai round in cui i vincoli sono soddisfatti. In questa tesi analizziamo i diversi effetti dei vincoli sugli agenti di apprendimento in vari contesti microeconomici. In particolare, in presenza di vincoli per round, esploriamo vari modelli decisionali sequenziali e dimostriamo che raggiungere zero violazioni dei vincoli è impossibile. Tuttavia, mostriamo che è possibile ottenere violazioni cumulative asintoticamente piccole. Al contrario, in presenza di vincoli a lungo termine, in contesti simili ai vincoli di budget, possiamo stabilire risultati che altrimenti sarebbero irraggiungibili se non fossero ammesse violazioni.