The certainty equivalent heuristic solves online linear programs by pretending the future is known — replacing stochastic constraints with their expected values and solving the resulting deterministic problem. It's simple, fast, and the natural first guess. In classical analysis, it works well under non-degeneracy conditions: when the optimal solution sits at a vertex of the feasible region with a unique optimal basis. When the problem is degenerate — multiple bases tie for optimal — the heuristic was thought to fail.
Chen and Wang (arXiv:2501.01716) prove that the certainty equivalent works even in degenerate cases. The regret bound interpolates flexibly between O(log²T) and O(√T) depending on a property of the conditional reward distribution called probability mass accumulation — not on whether the linear program is degenerate or not.
The structural insight: non-degeneracy was a sufficient condition, not a necessary one. The actual requirement is milder — the reward distribution just needs to avoid extreme concentration near the degeneracy boundary. The distinction between discrete and continuous reward distributions matters more than the presence or absence of degeneracy. A degenerate problem with a smooth reward distribution performs better than a non-degenerate problem with a point-mass reward distribution.
The algorithm doesn't need the geometry to be clean. It needs the randomness to be gentle. The obstruction everyone feared was geometric (degenerate vertices); the actual obstruction is distributional (probability mass piling up at critical values). A simpler condition governs a more general case.