Constrained bandit learning under time-varying stochastic constraints

We study constrained online learning with bandit feedback in a hybrid regime in which losses are adversarial (possibly adaptive but non-anticipating), while constraints are stochas- tic and described through conditional means that may vary over time. At each round, the learner observes only the loss and constraint feedback of the played arm, and must simultaneously minimize regret and control constraint violations. To quantify time variation in the constraint means, we adopt an anchor-based ℓ1 corrup- tion budget C, which measures cumulative deviation from a best static reference vector. To guarantee robust feasibility under bandit feedback, we assume a pure Slater condition, implemented as the existence of a uniformly safe arm with margin ρ > 0. The proposed algorithm follows a modular two-phase design. It first performs forced exploration, so that each arm is sampled at least L times and the constraint means can be estimated with high probability. It then constructs moving optimistic feasible sets by shifting the em- pirical constraint estimates downward through confidence bonuses, and runs within these sets a moving-set regret minimizer based on projected EXP3-IX with Kullback-Leibler projection. We establish high-probability guarantees for both performance and feasibility. In par- ticular, we bound the regret with respect to the best static strategy that is feasible on average, prove a bound on realized signed cumulative violations, and derive a bound on positive mean cumulative violations. The resulting guarantees make explicit the role of the exploration length L: larger values increase the direct exploration cost, but improve the quality of the post-exploration constraint estimates and reduce the history-averaging component induced by time variation in the constraints.

Questa tesi studia l’apprendimento online con vincoli in regime bandit, in un modello ibrido in cui le perdite sono avversarie (eventualmente adattive ma non anticipanti), mentre i vincoli sono stocastici e descritti tramite medie condizionate che possono variare nel tempo. A ogni round, l’algoritmo osserva soltanto la perdita e il feedback sui vincoli dell’azione giocata, e deve contemporaneamente minimizzare il regret e controllare le violazioni dei vincoli. Per quantificare la variazione temporale delle medie dei vincoli, adottiamo un budget di corruzione ℓ1 basato su un’ancora, denotato con C, che misura la deviazione cumulativa rispetto al miglior vettore di riferimento statico. Per garantire feasibility robusta in pre- senza di feedback bandit, assumiamo una condizione di Slater in forma pura, implemen- tata come l’esistenza di un’azione uniformemente sicura con margine ρ > 0. L’algoritmo proposto segue una struttura modulare in due fasi. Nella prima fase esegue esplorazione forzata, in modo che ogni braccio venga campionato almeno L volte e le medie dei vincoli possano essere stimate con alta probabilità. Successivamente costruisce insiemi ammis- sibili ottimistici mobili, ottenuti spostando verso il basso le stime empiriche dei vincoli tramite bonus di confidenza, ed esegue al loro interno un minimizzatore di regret su insiemi variabili nel tempo basato su EXP3-IX con proiezione di Kullback–Leibler. Dimostriamo garanzie ad alta probabilità sia per le prestazioni sia per la feasibility. In particolare, otteniamo un bound sul regret rispetto alla migliore strategia statica am- missibile in media, un bound sulle violazioni cumulate realizzate con segno e un bound sulle violazioni cumulate positive in media. I risultati mettono in evidenza il ruolo della lunghezza di esplorazione L: valori più grandi aumentano il costo diretto dell’esplorazione, ma migliorano la qualità delle stime post-esplorazione dei vincoli e riducono la componente di media storica indotta dalla variazione temporale nei vincoli.