[2406.14777] Learning to Cover: Online Learning and Optimization with Irreversible Decisions

Computer Science > Machine Learning arXiv:2406.14777 (cs) [Submitted on 20 Jun 2024 (v1), last revised 4 Mar 2026 (this version, v3)] Title:Learning to Cover: Online Learning and Optimization with Irreversible Decisions Authors:Alexandre Jacquillat, Michael Lingzhi Li View a PDF of the paper titled Learning to Cover: Online Learning and Optimization with Irreversible Decisions, by Alexandre Jacquillat and 1 other authors View PDF Abstract:We define an online learning and optimization problem with discrete and irreversible decisions contributing toward a coverage target. In each period, a decision-maker selects facilities to open, receives information on the success of each one, and updates a classification model to guide future decisions. The goal is to minimize facility openings under a chance constraint reflecting the coverage target, in an asymptotic regime characterized by a large target number of facilities $m\to\infty$ but a finite horizon $T \in \mathcal{Z}_+$. We prove that, under statistical conditions, the online classifier converges to the Bayes-optimal classifier at a rate of at best $\mathcal{O}(1/\sqrt n)$. Thus, we formulate our online learning and optimization problem, with a generalized learning rate $r>0$ and a residual error $1-p$. We derive an asymptotically optimal algorithm and an asymptotically tight lower bound. The regret grows in $\Theta\left(m^{\frac{1-r}{1-r^T}}\right)$ if $p=1$ (perfect learning) or in $\Theta\left(\max\left\{m^{\frac{1-r}{1-r^...