We study a network revenue management (NRM) problem, where the seller irrevocably accepts or rejects customers’ requests to maximize the total revenue over a finite time horizon subject to limited resources. We consider the setting where customer arrivals are dependent and follow a Markov chain choice model. We propose a deterministic linear program (DLP) which serves as an upper bound of this problem, based on which randomized allocation policies are designed. Specifically, when the customer’s arrival distribution is known, we design a static probabilistic allocation (SPA) policy and show that the regret, measured by the difference between its expected revenue and the DLP’s optimal value, scales as the square root of the time horizon. When the customer’s arrival distribution is unknown, we design an online probabilistic allocation (OPA) policy by sequentially learning the parameters, achieving a similar regret under mild conditions. We show that the asymptotic regrets of our algorithms are optimal in the respective settings. Furthermore, we conduct numerical experiments to validate the superior performance of the proposed algorithms. Finally, we extend our model when customers have finite patience and design an adaptive probabilistic allocation (APA) policy with similar theoretical guarantees.