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

• URL: http://arxiv.org/abs/2210.07996v4
• Date: Thu, 8 Feb 2024 07:09:23 GMT
• Title: Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions
• Authors: Jiashuo Jiang, Will Ma and Jiawei Zhang
• Abstract summary: We study the classical Network Revenue Management (NRM) problem with accept/reject decisions and $T$ IID arrivals. We develop an online algorithm that achieves $O(log2 T)$ regret under this model. We derive a second result that achieves $O(log T)$ regret under an additional assumption of second-order growth.
• Score: 14.959412298776199
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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(\log^2 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''.

Related papers

• Gradual Domain Adaptation via Manifold-Constrained Distributionally Robust Optimization [0.4732176352681218]
  This paper addresses the challenge of gradual domain adaptation within a class of manifold-constrained data distributions. We propose a methodology rooted in Distributionally Robust Optimization (DRO) with an adaptive Wasserstein radius. Our bounds rely on a newly introduced it compatibility measure, which fully characterizes the error propagation dynamics along the sequence.
  arXiv  Detail & Related papers  (2024-10-17T22:07:25Z)
• A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints [87.08677547257733]
  Neuro-symbolic AI bridges the gap between purely symbolic and neural approaches to learning. We show how to maximize the likelihood of a symbolic constraint w.r.t the neural network's output distribution. We also evaluate our approach on Sudoku and shortest-path prediction cast as autoregressive generation.
  arXiv  Detail & Related papers  (2023-12-06T20:58:07Z)
• $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits [29.966828248335972]
  We study the regret minimization problem when $epsilon$ and $u$ are unknown to the learner. AdaR-UCB is the first algorithm that enjoys regret guarantees nearly matching those of the non-adaptive heavy-tailed case.
  arXiv  Detail & Related papers  (2023-10-04T17:11:15Z)
• Classification of Data Generated by Gaussian Mixture Models Using Deep ReLU Networks [28.437011792990347]
  This paper studies the binary classification of data from $math RMs. generated under Gaussian Mixture networks. We obtain $d2013x neural analysis rates for the first time convergence rates. Results provide a theoretical verification of deep neural networks in practical classification problems.
  arXiv  Detail & Related papers  (2023-08-15T20:40:42Z)
• Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models [49.81937966106691]
  We develop a suite of non-asymptotic theory towards understanding the data generation process of diffusion models. In contrast to prior works, our theory is developed based on an elementary yet versatile non-asymptotic approach.
  arXiv  Detail & Related papers  (2023-06-15T16:30:08Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret. We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
  arXiv  Detail & Related papers  (2023-02-21T00:17:24Z)
• Constrained Online Two-stage Stochastic Optimization: Near Optimal Algorithms via Adversarial Learning [1.994307489466967]
  We consider an online two-stage optimization with long-term constraints over a finite horizon of $T$ periods. We develop online algorithms for the online two-stage problem from adversarial learning algorithms.
  arXiv  Detail & Related papers  (2023-02-02T10:33:09Z)
• Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis [121.9821494461427]
  We show how to significantly reduce the number of neurons required for two-layer ReLU networks. We also prove new lower bounds that improve upon prior work, and that under certain assumptions, are best possible.
  arXiv  Detail & Related papers  (2022-06-26T06:51:31Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  We study the problem of learning revenue-optimal multi-bidder auctions from samples when the samples of bidders' valuations can be adversarially corrupted or drawn from distributions that are adversarially perturbed. We propose new algorithms that can learn a mechanism whose revenue is nearly optimal simultaneously for all true distributions'' that are $alpha$-close to the original distribution in Kolmogorov-Smirnov distance.
  arXiv  Detail & Related papers  (2021-07-13T17:37:21Z)
• Sparse network asymptotics for logistic regression [0.0]
  Asymptotic normality of the logistic regression is shown using a martingale central limit theorem (CLT) for triangular arrays. Sparse networks may lead to better inference since they suggest variances which incorporate additional sources of sampling variation and (ii) are valid under varying degrees of dyadic dependence.
  arXiv  Detail & Related papers  (2020-10-09T17:46:29Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  We consider the fundamental problem of ReLU regression. The goal is to output the best fitting ReLU with respect to square loss given to draws from some unknown distribution.
  arXiv  Detail & Related papers  (2020-05-26T16:26:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.