  We study the canonical quantity-based network revenue management (NRM)
problem where the decision-maker must irrevocably accept or reject each
arriving customer request with the goal of maximizing the total revenue given
limited resources. The exact solution to the problem by dynamic programming is
computationally intractable due to the well-known curse of dimensionality.
Existing works in the literature make use of the solution to the deterministic
linear program (DLP) to design asymptotically optimal algorithms. Those
algorithms rely on repeatedly solving DLPs to achieve near-optimal regret
bounds. It is, however, time-consuming to repeatedly compute the DLP solutions
in real time, especially in large-scale problems that may involve hundreds of
millions of demand units. In this paper, we propose innovative algorithms for
the NRM problem that are easy to implement and do not require solving any DLPs.
Our algorithm achieves a regret bound of $O(\log k)$, where $k$ is the system
size. To the best of our knowledge, this is the first NRM algorithm that (i)
has an $o(\sqrt{k})$ asymptotic regret bound, and (ii) does not require solving
any DLPs.

Optimization and Control