# Beyond Non-Degeneracy: Revisiting Certainty Equivalent Heuristic for Online Linear Programming

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jan 2025.

## Built on by (most cited first, 3 of 3)

- [Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy](https://mlsanity.com/paper/2607.02196/) (2026)
- [Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates](https://mlsanity.com/paper/2607.02150/) (2026)
- [Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving](https://mlsanity.com/paper/2609.28263/) (2026)

## Abstract (arXiv)

The Certainty Equivalent heuristic (CE) is a widely-used algorithm for various dynamic resource allocation problems in OR and OM. Despite its popularity, existing theoretical guarantees of CE are limited to settings satisfying restrictive fluid regularity conditions, particularly, the non-degeneracy conditions, under the widely held belief that the violation of such conditions leads to performance deterioration and necessitates algorithmic innovation beyond CE. In this work, we conduct a refined performance analysis of CE within the general framework of online linear programming. We show that CE achieves uniformly near-optimal regret (up to a polylogarithmic factor in T) under only mild assumptions on the underlying distribution, without relying on any fluid regularity conditions. Our result implies that, contrary to prior belief, CE effectively beats the curse of degeneracy for a wide range of problem instances with continuous conditional reward distributions, highlighting the distinction of the problem's structure between discrete and non-discrete settings. Our explicit regret bound interpolates between the mild (log T)2 regime and the worst-case √T regime with a parameter β quantifying the minimal rate of probability accumulation of the conditional reward distributions, generalizing prior findings in the multisecretary setting. To achieve these results, we develop novel algorithmic analytical techniques. Drawing tools from the empirical processes theory, we establish strong concentration analysis of the solutions to random linear programs, leading to improved regret analysis under significantly relaxed assumptions. These techniques may find potential applications in broader online decision-making contexts.