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

退化性は問題ない：離散的でない分布を伴うネットワーク収益管理のための対数的後悔

基本情報

論文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^2 T)$ 後悔を達成するオンラインアルゴリズムを開発し、唯一の(必要な)仮定は確率密度が0から遠く離れていることです。第二の結果として、二次増長の追加仮定の下で $O(\log T)$ 後悔を達成します。我々の知る限り、これらは連続値を持つNRMモデルで対数的後悔を達成する初めての結果であり、いかなる「非退化」仮定も必要としません。

研究背景と動機

問題定義

ネットワーク収益管理(NRM)は容量制御問題であり、長さTの有限時間範囲内で有限リソースを配分する必要があります。各時間ステップtで、クエリが到着し、リソースベクトル $\tilde{a}_t$ を必要とし、報酬 $\tilde{r}_t$ を提供します。意思決定者は、そのクエリにサービスを提供するかどうかについて、直ちに取り消し不可能な決定を下さなければなりません。

研究動機

実践的重要性: NRMは航空、ホテル等の業界で重要な応用価値を持つ
理論的課題: 既存文献は連続分布を扱う際に強い「非退化」仮定が必要
方法論的限界: 従来の方法は有限離散分布に限定するか、非退化条件を必要とする

既存方法の限界

小N仮定: 有限離散分布に限定され、連続報酬を処理できない
非退化仮定: 流体緩和の最適解が唯一であり、厳密な相補スラック条件を満たすことを要求
摂動方法: 従来のLP退化処理方法は $\Omega(\sqrt{T})$ 後悔をもたらす

核心的貢献

対数後悔の初実現: 連続分布NRMで非退化仮定なしに対数的後悔を初めて実現
新しい半流体緩和: オフライン最適と流体緩和の間の新しい緩和方法を提案
改善された近視的後悔界: 新しい近視的後悔分析技術を開発
二重結果:
- $O(\log^2 T)$ 後悔(密度下界のみ必要)
- $O(\log T)$ 後悔(追加の二次増長条件)

方法論の詳細

タスク定義

入力: T個の独立同分布クエリ、各クエリ $(r_t, a_t)$ は報酬とリソース需要を含む
制約: 初期容量 $C \in \mathbb{R}^m_{\geq 0}$ 、容量制約 $\sum_{t=1}^T a_{t,i} \cdot x_t \leq C_i$
目標: 収集された総報酬を最大化し、オフライン最適との後悔を最小化

モデルアーキテクチャ

分布仮定(仮定1)

各タイプ $j \in [n]$ について:

需要ベクトル $a_t$ は離散分布 $\{a_1, \ldots, a_n\}$ から抽出
条件付き報酬 $r_t$ は区間 $[l_j, u_j]$ 上で連続分布
密度関数は $f(r|a_j) \geq \alpha > 0$ を満たす

半流体緩和

与えられたタイプ計数 $d = (d_1, \ldots, d_n)$ に対して:

$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)]$

制約条件: $\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: $\hat{M}$ -推定器戦略

クエリ $(r_t, a_t)$ を観察
推定器 $\hat{M}_{c_t, a_t}$ を計算
$r_t \geq \hat{M}_{c_t, a_t}$ かつ $c_t \geq a_t$ の場合、受け入れ
それ以外の場合、拒否

アルゴリズム2: $O(\log^2 T)$ 後悔アルゴリズム

最適化問題(13)を解いて $\{\hat{q}^*_{j,t}\}$ を得る
$\hat{q}^*_{j_t,t}$ $\overset{q}{^}_{j_{t}, t}^{*}$ の値に基づいて境界吸引戦略を設定:
- $\hat{q}^*_{j_t,t} \geq 1 - 2\kappa_1 \sqrt{\frac{\log(T-t+1)}{T-t+1}}$ の場合、 $\hat{M} = l_{j_t}$ (常に受け入れ)を設定
- $\hat{q}^*_{j_t,t} \leq 2\kappa_1 \sqrt{\frac{\log(T-t+1)}{T-t+1}}$ の場合、 $\hat{M} = u_{j_t} + 1$ (常に拒否)を設定
- それ以外の場合、 $\hat{M} = F^{-1}_{j_t}(1 - \hat{q}^*_{j_t,t})$ を設定

技術的革新点

1. 近視的後悔分解

総後悔を以下のように分解: $\text{Regret}(\pi) \leq \sum_{t=1}^T \mathbb{E}_{c^{\pi}_t}[\text{Myopic}_t(\pi, c^{\pi}_t)]$

ここで近視的後悔は以下のように定義: $\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. リプシッツ連続性分析

半流体問題の最適解のリプシッツ性質を証明(補題4): $\|\hat{q}^* - \tilde{q}^*\|_{\infty} \leq \kappa_1 \cdot \max_{j \in [n]} \{|d_j/s - p_j|\}$

3. 境界吸引戦略

流体解が境界に近い場合に保守的な戦略を採用し、実行可能性の問題を回避:

1に近い場合は常に受け入れ
0に近い場合は常に拒否
中間領域では閾値戦略を使用

実験設定

数値実験構成

リソース数: $m$ 個のリソース
顧客タイプ: $n$ 種類
容量設定: $C_i = \alpha_i \cdot T$
報酬分布: 各タイプは $[l_j, u_j]$ 上で均一分布
比較アルゴリズム:
- 固定競価戦略(FBP)
- 双対更新戦略
- アルゴリズム2と3

評価指標

期待総収益: 各戦略が収集した平均報酬
相対性能: 固定競価戦略との比率
後悔増加率: 後悔の時間Tに対する増加挙動

実験結果

主要結果

理論的結果

定理1: アルゴリズム2は $O(\log^2 T)$ 後悔を達成: $\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)$ 後悔を達成: $\text{Regret}(\pi) \leq C_1 \cdot \log T + C_2$

数値実験結果

時間依存性: アルゴリズム2と3はTが増大するにつれてベースライン方法を上回る
リソース数依存性: 3つの先進アルゴリズムは異なるリソース数で同様の性能を示す
タイプ数依存性: 顧客タイプ数が増加するとき、アルゴリズム2と3は双対更新戦略を上回る

重要な技術分析

双対収束界

第二の結果において、双対変数の分散界を証明: $\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}$