Online Algorithms via Minimax and Posterior Matching

arXiv:2608.01616v1 Announce Type: new 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.

Source: arXiv cs.LG | 2026-08-04