# Online Algorithms via Minimax and Posterior Matching

arXiv: https://arxiv.org/abs/2608.01616 · HTML: https://mlsanity.com/paper/2608.01616/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 44 references that are in the map.
- First posted on arXiv 3 Aug 2026.

## Builds on (most cited first, 14 of 14)

- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Adaptive Online Learning](https://mlsanity.com/paper/1508.05170/) (2015)
- [Subspace Embedding and Linear Regression with Orlicz Norm](https://mlsanity.com/paper/1806.06430/) (2018)
- [Online Learning: Sufficient Statistics and the Burkholder Method](https://mlsanity.com/paper/1803.07617/) (2018)
- [k-server via multiscale entropic regularization](https://mlsanity.com/paper/1711.01085/) (2017)
- [Efficient Symmetric Norm Regression via Linear Sketching](https://mlsanity.com/paper/1910.01788/) (2019)
- [Robust Algorithms for the Secretary Problem](https://mlsanity.com/paper/1911.07352/) (2019)
- [Submodular Norms with Applications To Online Facility Location and Stochastic Probing](https://mlsanity.com/paper/2310.04548/) (2023)
- [ZigZag: A new approach to adaptive online learning](https://mlsanity.com/paper/1704.04010/) (2017)
- [k-Servers with a Smile: Online Algorithms via Projections](https://mlsanity.com/paper/1810.07508/) (2018)
- [Supermodular Approximation of Norms and Applications](https://mlsanity.com/paper/2406.15180/) (2024)
- [The Online Submodular Assignment Problem](https://mlsanity.com/paper/2412.03826/) (2024)
- [Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives](https://mlsanity.com/paper/2508.18383/) (2025)

## Abstract (arXiv)

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 Ft] 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.