# Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 47 references that are in the map.
- First posted on arXiv 14 Oct 2022.

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

- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Simple and Fast Algorithm for Binary Integer and Online Linear Programming](https://mlsanity.com/paper/2003.02513/) (2020)
- [Online Stochastic Optimization with Wasserstein Based Non-stationarity](https://mlsanity.com/paper/2012.06961/) (2020)
- [Uniformly bounded regret in the multi-secretary problem](https://mlsanity.com/paper/1710.07719/) (2017)
- [A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management](https://mlsanity.com/paper/1802.06192/) (2018)
- [Primal Beats Dual on Online Packing LPs in the Random-Order Model](https://mlsanity.com/paper/1311.2578/) (2013)
- [Online Allocation and Pricing: Constant Regret via Bellman Inequalities](https://mlsanity.com/paper/1906.06361/) (2019)
- [The Bayesian Prophet: A Low-Regret Framework for Online Decision Making](https://mlsanity.com/paper/1901.05028/) (2019)
- [Online Resource Allocation with Stochastic Resource Consumption](https://mlsanity.com/paper/2012.07933/) (2020)
- [Prophet Secretary](https://mlsanity.com/paper/1507.01155/) (2015)
- [Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards](https://mlsanity.com/paper/1809.02016/) (2018)
- [Overbooking with bounded loss](https://mlsanity.com/paper/2204.11148/) (2022)
- [Uniformly Bounded Regret in Dynamic Fair Allocation](https://mlsanity.com/paper/2205.12447/) (2022)

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

- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming](https://mlsanity.com/paper/2501.02761/) (2025)
- [Online Pricing and Allocation with Demand Learning and Fulfillment Cost](https://mlsanity.com/paper/2501.18049/) (2025)
- [Contextual Decision-Making with Knapsacks Beyond the Worst Case](https://mlsanity.com/paper/2211.13952/) (2022)
- [Decoupling Learning and Decision-Making: Breaking the O(√T) Barrier in Online Resource Allocation with First-Order Methods](https://mlsanity.com/paper/2402.07108/) (2024)
- [Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices](https://mlsanity.com/paper/2501.14155/) (2025)
- [Cross-Epoch Adaptive Rollout Optimization for RL Post-Training](https://mlsanity.com/paper/2606.05606/) (2026)
- [Non-Stationary Online Resource Allocation: Learning from a Single Sample](https://mlsanity.com/paper/2602.18114/) (2026)
- [Adaptive Resolving Methods for Markov Decision Processes with Function Approximations](https://mlsanity.com/paper/2505.12037/) (2025)
- [Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates](https://mlsanity.com/paper/2607.02150/) (2026)
- [Prediction-Assisted Pricing and Admission for LLM APIs with Stochastic Token Consumption](https://mlsanity.com/paper/2609.00710/) (2026)
- [A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret](https://mlsanity.com/paper/2609.05895/) (2026)
- [Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving](https://mlsanity.com/paper/2609.28263/) (2026)

## Abstract (arXiv)

We study the classical Network Revenue Management (NRM) problem with accept/reject decisions and T IID arrivals. We consider a distributional form where each arrival must fall under a finite number of possible categories, each with a deterministic resource consumption vector, but a random value distributed continuously over an interval. We develop an online algorithm that achieves O(log2 T) regret under this model, with the only (necessary) assumption being that the probability densities are bounded away from 0. We derive a second result that achieves O(log T) regret under an additional assumption of second-order growth. To our knowledge, these are the first results achieving logarithmic-level regret in an NRM model with continuous values that do not require any kind of "non-degeneracy" assumptions. Our results are achieved via new techniques including a new method of bounding myopic regret, a "semi-fluid" relaxation of the offline allocation, and an improved bound on the "dual convergence".