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

• URL: http://arxiv.org/abs/2210.07996v5
• Date: Thu, 02 Jan 2025 16:07:08 GMT
• Title: Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions
• Authors: Jiashuo Jiang, Will Ma, 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: 13.310272407473809
• License:
• 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)
• Contextual Decision-Making with Knapsacks Beyond the Worst Case [5.65888994172721]
  We study the framework of a dynamic decision-making scenario with resource constraints. In this framework, an agent selects an action in each round upon observing a random request. We prove that our algorithm maintains a near-optimal $widetildeO(sqrtT)$ regret even in the worst cases.
  arXiv  Detail & Related papers  (2022-11-25T08:21:50Z)
• 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)
• An Infinite-Feature Extension for Bayesian ReLU Nets That Fixes Their Asymptotic Overconfidence [65.24701908364383]
  A Bayesian treatment can mitigate overconfidence in ReLU nets around the training data. But far away from them, ReLU neural networks (BNNs) can still underestimate uncertainty and thus be overconfident. We show that it can be applied emphpost-hoc to any pre-trained ReLU BNN at a low cost.
  arXiv  Detail & Related papers  (2020-10-06T13:32:18Z)

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.