Вырождение допустимо: логарифмический регрет для управления доходом сети с недискретными распределениями

Основная информация

• 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
• Дата публикации: 2 января 2025 г. (arXiv v5)
• Ссылка на статью: https://arxiv.org/abs/2210.07996

Аннотация

В данной работе исследуется классическая задача управления доходом сети (NRM), включающая решения о принятии/отклонении и T независимых одинаково распределённых поступлений. Рассматривается форма распределения, в которой каждое поступление должно принадлежать конечному числу возможных категорий с детерминированными векторами потребления ресурсов, но стоимость непрерывно распределена на интервале. Разработан онлайн-алгоритм, достигающий регрета $O(\log^2 T)$ в данной модели при единственном (необходимом) предположении, что плотность вероятности отделена от нуля. Получен второй результат, достигающий регрета $O(\log T)$ при дополнительном предположении о росте второго порядка. Насколько нам известно, это первые результаты, достигающие логарифмического регрета в модели NRM с непрерывными стоимостями без каких-либо предположений о «невырождении».

Исследовательский контекст и мотивация

Определение задачи

Управление доходом сети (NRM) — это задача контроля пропускной способности, требующая распределения ограниченных ресурсов в течение конечного временного горизонта длины T. На каждом временном шаге t поступает запрос, требующий вектор ресурсов $\tilde{a}_t$ и предлагающий вознаграждение $\tilde{r}_t$. Лицо, принимающее решение, должно немедленно принять необратимое решение о том, обслуживать ли данный запрос.

Исследовательская мотивация

1. Практическая значимость: NRM имеет важные приложения в авиационной, гостиничной и других отраслях
2. Теоретические вызовы: Существующая литература требует сильных предположений о «невырождении» при работе с непрерывными распределениями
3. Ограничения методов: Традиционные подходы либо ограничиваются конечными дискретными распределениями (предположение малого N), либо требуют условий невырождения

Ограничения существующих методов

• Предположение малого N: Ограничивается конечными дискретными распределениями, не может обрабатывать непрерывные вознаграждения
• Предположение о невырождении: Требует уникальности оптимального решения релаксации жидкости и выполнения условий строгой дополняющей нежёсткости
• Методы возмущения: Традиционные методы обработки вырождения в линейном программировании приводят к регрету $\Omega(\sqrt{T})$

Основные вклады

1. Первое достижение логарифмического регрета: Впервые достигнут логарифмический регрет в NRM с непрерывными распределениями без предположения о невырождении
2. Новая полужидкостная релаксация: Предложен новый метод релаксации, находящийся между офлайн-оптимумом и релаксацией жидкости
3. Улучшенный анализ близорукого регрета: Разработана новая техника анализа близорукого регрета
4. Двойной результат:
   • Регрет $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$
• Цель: Максимизировать общее собранное вознаграждение, минимизировать регрет относительно офлайн-оптимума

Архитектура модели

Предположение о распределении (Assumption 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}$

1. Наблюдать запрос $(r_t, a_t)$
2. Вычислить оценитель $\hat{M}_{c_t, a_t}$
3. Если $r_t \geq \hat{M}_{c_t, a_t}$ и $c_t \geq a_t$, принять
4. В противном случае отклонить

Алгоритм 2: Алгоритм с регретом $O(\log^2 T)$

• Решить задачу оптимизации (13) для получения $\{\hat{q}^*_{j,t}\}$
• Установить граничную привлекающую стратегию на основе значения $\hat{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$

Результаты численных экспериментов

1. Зависимость от времени: Алгоритмы 2 и 3 превосходят базовые методы при увеличении T
2. Зависимость от количества ресурсов: Три продвинутых алгоритма показывают сходную производительность при различном количестве ресурсов
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}$

Связанные работы

Развитие литературы по NRM

1. Регрет $O(\sqrt{T})$: Статическая стратегия цены Talluri и Van Ryzin (1998)
2. Регрет $O(1)$: Результаты Jasin и Kumar (2012) при условиях невырождения
3. Без невырождения: Работы Bumpensanti и Wang (2020), Vera и Banerjee (2021) для дискретного случая

Исследования непрерывных распределений

• Задача множественного секретаря: Результат $\Theta(\log T)$ Bray (2019) для одноресурсного случая
• Предположение о невырождении: Работы Li и Ye (2021), Balseiro и др. (2021), Bray (2022)

Заключение и обсуждение

Основные выводы

1. Впервые достигнут логарифмический регрет в NRM с непрерывными вознаграждениями без предположения о невырождении
2. Полужидкостная релаксация предоставляет новую аналитическую базу
3. Стратегия граничного притяжения эффективно обрабатывает вырожденные случаи

Ограничения

1. Нижняя граница плотности: По-прежнему требуется предположение, что функция плотности отделена от нуля
2. Константные члены: Константные члены в результате $O(\log^2 T)$ зависят экспоненциально от $n$
3. Рост второго порядка: Лучший результат $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): Задача множественного секретаря с непрерывными значениями

Данная работа достигает важного прорыва в теории управления доходом сети, впервые достигая логарифмического регрета в условиях непрерывного распределения без традиционного предположения о невырождении. Технические инновации включают полужидкостную релаксацию, стратегию граничного притяжения и улучшенный анализ двойственной сходимости, что представляет значительный вклад в теоретическое развитие данной области.