We define an online learning and optimization problem with irreversible
decisions contributing toward a coverage target. At each period, a
decision-maker selects facilities to open, receives information on the success
of each one, and updates a machine learning model to guide future decisions.
The goal is to minimize costs across a finite horizon under a chance constraint
reflecting the coverage target. We derive an optimal algorithm and a tight
lower bound in an asymptotic regime characterized by a large target number of
facilities $m\to\infty$ but a finite horizon $T\in\mathbb{Z}_+$. We find that
the regret grows sub-linearly at a rate
$\Theta\left(m^{\frac{1}{2}\cdot\frac{1}{1-2^{-T}}}\right)$, thus converging
exponentially fast to $\Theta(\sqrt{m})$. We establish the robustness of this
result to the learning environment; we also extend it 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 for learning purposes, and fast
exploitation later on for optimization purposes once uncertainty gets
mitigated. These findings underscore the benefits of limited online learning
and optimization, in that even a few rounds can provide significant benefits as
compared to a no-learning baseline.

通过限制在线学习和优化策略的探索次数，将不确定性减少为最低程度，从而最小化成本并实现覆盖目标。