2025-11-10T02:43:59.651588

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

Jiang, Ma, Zhang
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".
academic

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

基本信息

  • 论文ID: 2210.07996
  • 标题: Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions
  • 作者: Jiashuo Jiang (HKUST), Will Ma (Columbia University), Jiawei Zhang (NYU Stern)
  • 分类: cs.LG math.PR
  • 发表时间: 2025年1月2日 (arXiv v5)
  • 论文链接: https://arxiv.org/abs/2210.07996

摘要

本文研究经典的网络收益管理(NRM)问题，涉及接受/拒绝决策和T个独立同分布到达。我们考虑一种分布形式，其中每个到达必须属于有限数量的可能类别，每个类别具有确定性的资源消耗向量，但价值在区间上连续分布。我们开发了一个在线算法，在此模型下实现O(log⁡2T)O(\log^2 T)后悔，唯一(必要)假设是概率密度远离0。我们得出第二个结果，在二阶增长的额外假设下实现O(log⁡T)O(\log T)后悔。据我们所知，这些是在具有连续值的NRM模型中实现对数级后悔的首批结果，不需要任何"非退化"假设。

研究背景与动机

问题定义

网络收益管理(NRM)是一个容量控制问题，需要在长度为T的有限时间范围内分配有限资源。在每个时间步t，一个查询到达，需要资源向量a~t\tilde{a}_t并提供奖励r~t\tilde{r}_t。决策者必须立即做出不可撤销的决定是否服务该查询。

研究动机

  1. 实际重要性: NRM在航空、酒店等行业具有重要应用价值
  2. 理论挑战: 现有文献在处理连续分布时需要强"非退化"假设
  3. 方法局限: 传统方法要么假设离散分布(小N假设)，要么需要非退化条件

现有方法的局限性

  • 小N假设: 限制为有限离散分布，无法处理连续奖励
  • 非退化假设: 要求流体松弛的最优解唯一且满足严格互补松弛条件
  • 扰动方法: 传统LP退化处理方法会导致Ω(T)\Omega(\sqrt{T})后悔

核心贡献

  1. 首次实现对数后悔: 在连续分布NRM中首次实现对数级后悔，无需非退化假设
  2. 新的半流体松弛: 提出介于离线最优和流体松弛之间的新松弛方法
  3. 改进的近视后悔界: 开发新的近视后悔分析技术
  4. 双重结果:
    • O(log⁡2T)O(\log^2 T)后悔(仅需密度下界)
    • O(log⁡T)O(\log T)后悔(额外二阶增长条件)

方法详解

任务定义

  • 输入: T个独立同分布查询，每个查询(rt,at)(r_t, a_t)包含奖励和资源需求
  • 约束: 初始容量C∈R≥0mC \in \mathbb{R}^m_{\geq 0}，容量约束∑t=1Tat,i⋅xt≤Ci\sum_{t=1}^T a_{t,i} \cdot x_t \leq C_i
  • 目标: 最大化总收集奖励，最小化与离线最优的后悔

模型架构

分布假设(Assumption 1)

对于每个类型j∈[n]j \in [n]:

  • 需求向量ata_t从离散分布{a1,…,an}\{a_1, \ldots, a_n\}中抽取
  • 条件奖励rtr_t在区间[lj,uj][l_j, u_j]上连续分布
  • 密度函数满足f(r∣aj)≥α>0f(r|a_j) \geq \alpha > 0

半流体松弛

对于给定的类型计数d=(d1,…,dn)d = (d_1, \ldots, d_n):

VcSemi(d)=max⁡x∑j=1ndj⋅Er∼Fj[r⋅xj(r)]V^{\text{Semi}}_c(d) = \max_x \sum_{j=1}^n d_j \cdot \mathbb{E}_{r \sim F_j}[r \cdot x_j(r)]

受约束: ∑j=1ndj⋅aj,i⋅Er∼Fj[xj(r)]≤ci,∀i∈[m]\sum_{j=1}^n d_j \cdot a_{j,i} \cdot \mathbb{E}_{r \sim F_j}[x_j(r)] \leq c_i, \quad \forall i \in [m]

算法设计

算法1: M^\hat{M}-估计器策略

  1. 观察查询(rt,at)(r_t, a_t)
  2. 计算估计器M^ct,at\hat{M}_{c_t, a_t}
  3. 如果rt≥M^ct,atr_t \geq \hat{M}_{c_t, a_t}且ct≥atc_t \geq a_t，则接受
  4. 否则拒绝

算法2: O(log⁡2T)O(\log^2 T)后悔算法

  • 求解优化问题(13)得到{q^j,t∗}\{\hat{q}^*_{j,t}\}
  • 根据q^jt,t∗\hat{q}^*_{j_t,t}的值设置边界吸引策略:
    • 如果q^jt,t∗≥1−2κ1log⁡(T−t+1)T−t+1\hat{q}^*_{j_t,t} \geq 1 - 2\kappa_1 \sqrt{\frac{\log(T-t+1)}{T-t+1}}，设置M^=ljt\hat{M} = l_{j_t}(总是接受)
    • 如果q^jt,t∗≤2κ1log⁡(T−t+1)T−t+1\hat{q}^*_{j_t,t} \leq 2\kappa_1 \sqrt{\frac{\log(T-t+1)}{T-t+1}}，设置M^=ujt+1\hat{M} = u_{j_t} + 1(总是拒绝)
    • 否则设置M^=Fjt−1(1−q^jt,t∗)\hat{M} = F^{-1}_{j_t}(1 - \hat{q}^*_{j_t,t})

技术创新点

1. 近视后悔分解

将总后悔分解为: Regret(π)≤∑t=1TEctπ[Myopict(π,ctπ)]\text{Regret}(\pi) \leq \sum_{t=1}^T \mathbb{E}_{c^{\pi}_t}[\text{Myopic}_t(\pi, c^{\pi}_t)]

其中近视后悔定义为: Myopict(π,c)=Eπ,It[Vˉc(It)−Vˉc−at⋅xtπ(It+1)−rt⋅xtπ]\text{Myopic}_t(\pi, c) = \mathbb{E}_{\pi, I_t}[\bar{V}_c(I_t) - \bar{V}_{c - a_t \cdot x^{\pi}_t}(I_{t+1}) - r_t \cdot x^{\pi}_t]

2. Lipschitz连续性分析

证明了半流体问题最优解的Lipschitz性质(引理4): ∥q^∗−q~∗∥∞≤κ1⋅max⁡j∈[n]{∣dj/s−pj∣}\|\hat{q}^* - \tilde{q}^*\|_{\infty} \leq \kappa_1 \cdot \max_{j \in [n]} \{|d_j/s - p_j|\}

3. 边界吸引策略

当流体解接近边界时采用保守策略，避免可行性问题:

  • 接近1时总是接受
  • 接近0时总是拒绝
  • 中间区域使用阈值策略

实验设置

数值实验配置

  • 资源数: mm个资源
  • 客户类型: nn种类型
  • 容量设置: Ci=αi⋅TC_i = \alpha_i \cdot T
  • 奖励分布: 各类型在[lj,uj][l_j, u_j]上均匀分布
  • 比较算法:
    • 固定竞价策略(FBP)
    • 对偶更新策略
    • 算法2和算法3

评价指标

  • 期望总收益: 各策略收集的平均奖励
  • 相对性能: 与固定竞价策略的比值
  • 后悔增长率: 后悔随时间T的增长情况

实验结果

主要结果

理论结果

定理1: 算法2实现O(log⁡2T)O(\log^2 T)后悔: Regret(π)≤(2κ1+2α+4α∑j=1n1pj)log⁡2T+s0⋅rmax⁡\text{Regret}(\pi) \leq \left(2\kappa_1 + \frac{2}{\alpha} + \frac{4}{\alpha} \sum_{j=1}^n \frac{1}{p_j}\right) \log^2 T + s_0 \cdot r_{\max}

定理2: 在额外假设下，算法3实现O(log⁡T)O(\log T)后悔: Regret(π)≤C1⋅log⁡T+C2\text{Regret}(\pi) \leq C_1 \cdot \log T + C_2

数值实验结果

  1. 时间依赖性: 算法2和3在T增大时表现优于基准方法
  2. 资源数依赖性: 三种先进算法在不同资源数下表现相似
  3. 类型数依赖性: 当客户类型数增加时，算法2和3优于对偶更新策略

关键技术分析

对偶收敛界

在第二个结果中，证明了对偶变量的方差界: E[(at⊤μ~1−at⊤μ^1)2]≤8dˉ2α2β2(s−1)+19αˉdˉ2(s−1)+2s−1\mathbb{E}[(a^{\top}_t \tilde{\mu}_1 - a^{\top}_t \hat{\mu}_1)^2] \leq \frac{8\bar{d}^2}{\alpha^2\beta^2(s-1)} + \frac{1}{9\bar{\alpha}\bar{d}^2(s-1)} + \frac{2}{s-1}

相关工作

NRM文献发展

  1. O(T)O(\sqrt{T})后悔: Talluri和Van Ryzin (1998)的静态竞价策略
  2. O(1)O(1)后悔: Jasin和Kumar (2012)在非退化条件下的结果
  3. 无非退化: Bumpensanti和Wang (2020), Vera和Banerjee (2021)的离散情况

连续分布研究

  • 多秘书问题: Bray (2019)在单资源情况下的Θ(log⁡T)\Theta(\log T)结果
  • 非退化假设: Li和Ye (2021), Balseiro等(2021), Bray (2022)的工作

结论与讨论

主要结论

  1. 首次在连续奖励NRM中实现对数后悔而无需非退化假设
  2. 半流体松弛提供了新的分析框架
  3. 边界吸引策略有效处理了退化情况

局限性

  1. 密度下界: 仍需要密度函数远离0的假设
  2. 常数项: O(log⁡2T)O(\log^2 T)结果的常数项依赖于指数级的nn
  3. 二阶增长: 更好的O(log⁡T)O(\log T)结果需要额外的强凸性假设

未来方向

  1. 改进常数项的依赖关系
  2. 扩展到更一般的分布类
  3. 研究下界匹配性

深度评价

优点

  1. 理论突破: 解决了长期存在的退化问题
  2. 技术创新: 半流体松弛和边界吸引策略具有新颖性
  3. 实用价值: 方法适用于实际的连续定价场景
  4. 分析严谨: 数学证明详细完整

不足

  1. 假设限制: 仍需要有限类型和密度下界假设
  2. 常数项: 第一个结果的常数项较大
  3. 实验有限: 数值实验相对简单，缺乏真实数据验证

影响力

  1. 理论贡献: 为NRM理论提供了新的分析工具
  2. 方法论: 半流体松弛可能适用于其他在线优化问题
  3. 实践指导: 为实际收益管理系统提供了理论基础

适用场景

  • 航空收益管理中的座位分配
  • 酒店房间定价和分配
  • 在线广告竞价系统
  • 云资源动态定价

参考文献

主要相关工作包括：

  • Jasin和Kumar (2012): NRM中的重解启发式
  • Bumpensanti和Wang (2020): 无非退化假设的离散情况
  • Li和Ye (2021): 在线线性规划的对偶收敛
  • Bray (2022): 连续值多秘书问题

本文在网络收益管理理论中取得了重要突破，首次在连续分布设置下实现了对数级后悔而无需传统的非退化假设。技术创新包括半流体松弛、边界吸引策略和改进的对偶收敛分析，为该领域的理论发展做出了重要贡献。