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 .