# Learning to Cover: Online Learning and Optimization with Irreversible Decisions

arXiv: https://arxiv.org/abs/2406.14777 · HTML: https://mlsanity.com/paper/2406.14777/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2024.

## Built on by (most cited first, 1 of 1)

- [When to Commit and When to Defer: Maturing Markov Decision Processes under Refining Information and Expiring Opportunities](https://mlsanity.com/paper/2606.18820/) (2026)

## Abstract (arXiv)

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→∞ but a finite horizon T ∈ Z_+. We prove that, under statistical conditions, the online classifier converges to the Bayes-optimal classifier at a rate of at best O(1/√ 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 Thetaleft(m^frac1-r1-rTright) if p=1 (perfect learning) or in Thetaleft(maxleftm^frac1-r1-rT,√mrightright) otherwise; in particular, the regret rate is sub-linear and converges exponentially fast to its infinite-horizon limit. We extend this result to a more complicated facility location setting in a bipartite facility-customer graph with a target on customer coverage. Throughout, constructive proofs identify a policy featuring limited exploration initially and fast exploitation later on once uncertainty gets mitigated. These results uncover the benefits of limited online learning and optimization through pilot programs prior to full-fledged expansion.