Online Algorithms via Minimax and Posterior Matching
2026-08-03 • Machine Learning
Machine LearningData Structures and Algorithms
AI summaryⓘ
The authors propose a new way to analyze online algorithms by linking worst-case scenarios to a Bayesian framework using an idea called posterior matching. This means at each step, their method picks the best action based on the expected optimal solution given what has happened so far. They show this approach works well for many classic problems like set cover and load balancing, often matching or improving the best known results. Their method also extends to more practical problems through randomized rounding. Overall, their work connects Bayesian strategies with traditional competitive analysis using advanced probability tools.
online algorithmscompetitive analysisYao's principleBayesian online designposterior matchingset coverload balancingmartingalesrandomized roundingresource allocation
Authors
Thomas Kesselheim, Marco Molinaro, Kalen Patton, Sahil Singla
Abstract
Competitive analysis is central to the study of online algorithms, but upper bounds are often highly problem-specific. We develop a more unifying methodology via the minimax viewpoint. Guided by Yao's principle, we reduce worst-case competitive analysis to Bayesian online design under an arbitrary correlated prior over arrival sequences. For such a prior, let $X^*$ be the hindsight-optimal fractional solution for the realized instance, and let $X^{(t)}=\mathbb E[X^*\mid \mathcal F_t]$ be its posterior process. Our guiding rule is posterior matching: at each time $t$, choose the feasible online action that tracks the current posterior $X^{(t)}$ as closely as the online constraints permit. We show that this single principle yields optimal or near-optimal guarantees for several classical online fractional problems, including set cover, load balancing, matching and more general resource-allocation problems, recovering or improving state-of-the-art bounds in these settings with norm/concave objectives. Via known rounding reductions, it also yields randomized integral guarantees for weighted paging, MTS on star metrics, and ski-rental. At a technical level, our analysis reduces competitive guarantees to key probabilistic inequalities for the vector martingales generated by the posterior of the offline optimum. The resulting framework gives a reusable route from Bayesian online design under arbitrary correlated priors to information-theoretic worst-case competitive guarantees.