Learning to Cover: Online Learning and Optimization with Irreversible Decisions

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 but a finite planning horizon. We prove that, under statistical conditions, the online classifier converges to the Bayes-optimal classifier at the standard square-root rate. Thus, we formulate our online learning and optimization problem with a generalized learning rate and a residual classification error. We derive an asymptotically optimal algorithm and an asymptotically tight lower bound. The regret grows sublinearly under perfect learning and remains sublinear more generally; in particular, the regret 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.

Supplemental Material: The online appendices and data files are available at https://doi.org/10.1287/mnsc.2025.01729.