Справедливые алгоритмы с зондированием для многоагентных многорукавых бандитов

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

• ID статьи: 2506.14988
• Название: Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits
• Авторы: Tianyi Xu, Jiaxin Liu, Nicholas Mattei, Zizhan Zheng
• Учреждения: Tulane University, University of Illinois Urbana-Champaign
• Классификация: cs.LG, cs.AI
• Дата публикации: препринт arXiv, версия от 26 ноября 2025 года
• Ссылка на статью: https://arxiv.org/abs/2506.14988v4

Аннотация

В данной работе предложена структура многоагентного многорукавого бандита (MA-MAB), направленная на обеспечение справедливости между агентами при одновременной максимизации общей производительности системы. Для решения проблемы принятия решений при ограниченной информации о вознаграждениях рукавов введен новый механизм зондирования, который стратегически собирает информацию о выбранных рукавах перед распределением. В автономной постановке (при известном распределении вознаграждений) разработан жадный алгоритм зондирования с гарантиями приближения с постоянным множителем, основанный на свойствах субмодулярности. В онлайн-постановке разработан алгоритм, достигающий сублинейного сожаления при сохранении справедливости. Обширные эксперименты на синтетических и реальных наборах данных демонстрируют превосходство предложенного метода над базовыми методами как в справедливости, так и в эффективности.

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

Основная проблема

Традиционные задачи многорукавого бандита обычно оптимизируют утилитарное благосостояние (utilitarian welfare, то есть сумму общих вознаграждений), что приводит к серьезным проблемам справедливости. Например, в сценариях с сервисами совместного использования автомобилей центральная система диспетчеризации при распределении водителей по различным географическим регионам может привести к ситуации, когда некоторые водители вообще не получают заказы, что вызывает явление "голодания" (starvation).

Важность проблемы

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

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

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

1. Отсутствие справедливости: существующие методы MA-MAB в основном сосредоточены на максимизации общего вознаграждения, игнорируя справедливость отдельных агентов
2. Зависимость от информации: полагаются на немедленную обратную связь для обновления оценок, плохо работают при неполной информации или в шумной среде
3. Недостаточное исследование: отсутствует механизм активного сбора информации, что приводит к распространению ошибок оценки на неопределенные рукава в решениях распределения

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

В данной работе путем введения механизма зондирования и целевой функции социального благосостояния Нэша (Nash Social Welfare, NSW) преодолевается разрыв между справедливыми многоагентными методами и стратегиями активного исследования, позволяя информации, полученной через активное исследование, непосредственно преобразоваться в справедливые результаты для всех агентов.

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

1. Новая структура: расширение структуры MA-MAB с введением механизма зондирования для тестирования выбранных рукавов перед распределением, обеспечение справедливости через оптимизацию NSW
2. Автономный алгоритм: разработка простого и эффективного жадного алгоритма зондирования с доказуемыми гарантиями производительности для известных моделей вознаграждений
3. Онлайн-алгоритм: предложение алгоритма, балансирующего исследование и справедливость, с доказательством того, что зондирование и справедливое распределение не ухудшают асимптотическую производительность (сублинейное сожаление)
4. Экспериментальная проверка: демонстрация превосходства метода над базовыми методами в справедливости и эффективности на синтетических и реальных данных

Подробное описание методов

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

Основная постановка:

• Агенты: M агентов, обозначаемые j ∈ M
• Рукава: A рукавов, обозначаемые a ∈ A
• Распределения вознаграждений: каждая пара агент-рукав (j,a) имеет неизвестное распределение D_{j,a} со средним μ_{j,a} ∈ 0,1

Процесс принятия решений (каждый раунд t):

1. Фаза зондирования: выбор набора зондирования S_t ⊆ A, получение свежих образцов вознаграждения R_{j,a,t} для каждого a ∈ S_t
2. Фаза распределения: на основе наблюдаемых вознаграждений и текущих оценок распределение рукавов агентам через политику π_t

Целевая функция справедливости: максимизация социального благосостояния Нэша (NSW) $\text{NSW}(S_t, R_t, \mu, \pi_t) = \prod_{j \in [M]} \left( \sum_{a \in S_t} \pi_{j,a,t} R_{j,a,t} + \sum_{a \notin S_t} \pi_{j,a,t} \mu_{j,a} \right)$

Стоимость зондирования: эффективное вознаграждение определяется как $R^{\text{total}}_t = (1 - \alpha(|S_t|)) \mathbb{E}_{R_t}[\text{NSW}(S_t, R_t, \mu, \pi_t)]$ где α(·) — неубывающая функция стоимости, α(0)=0, α(I)=1

Определение сожаления: $R_{\text{regret}}(T) = \sum_{t=1}^T \left[ (1-\alpha(|S^*_t|)) \mathbb{E}[\text{NSW}(S^*_t, R_t, \mu, \pi^*_t)] - R^{\text{total}}_t \right]$

Автономная постановка: алгоритм жадного зондирования

Разложение целевой функции оптимизации

Определены две функции полезности:

1. Полезность зондирования g(S): ожидаемое NSW, использующее только зондируемые рукава $g(S) = \max_{\pi \in \Delta^A_S} \mathbb{E}\left[ \prod_{j \in [M]} \left( \sum_{a \in S} \pi_{j,a} R_{j,a} \right) \right]$
2. Полезность без зондирования h(S): NSW, использующее только незондируемые рукава $h(S) = \max_{\pi \in \Delta^A_{[A]\backslash S}} \prod_{j \in [M]} \left( \sum_{a \notin S} \pi_{j,a} \mu_{j,a} \right)$

Построение кусочно-линейной верхней границы

Поскольку log(g(S)) не является субмодулярной, прямая оптимизация затруднена. Применяется приближение кусочно-линейной оболочки:

• Интервал 0, x_max разбивается на мелкие сегменты с точками разрыва τ_0, τ_1, ..., τ_L
• В каждой точке разрыва строится касательная T_{τ_i}(z) = log(τ_i) + (z - τ_i)/τ_i
• Определяется φ(z) = max_{0≤i<L} T_{τ_i}(z), удовлетворяющая φ(z) ≥ log(z)
• Устанавливается f_upper(S) = φ(g(S))

Свойство субмодулярности

Леммы 1-5 устанавливают ключевые свойства:

• Лемма 1: g(S) монотонно возрастает
• Лемма 2: f_upper(S) монотонно возрастает
• Лемма 3: f_upper(S) субмодулярна (ключевое свойство)
• Лемма 4: h(S) монотонно убывает
• Лемма 5: R(S) ≤ (1-α(|S|))(g(S) + h(S))

Алгоритм 1: Автономное жадное зондирование

Вход: распределения {F_{m,a}}, функция стоимости α(·), бюджет I, параметр ζ≥1
Выход: набор зондирования S_pr

1. Инициализация S_0 = ∅
2. Для i = 1 до I:
   - Выбрать рукав с максимальным маржинальным приростом:
     a = argmax_{a∉S_{i-1}} [f_upper(S_{i-1}∪{a}) - f_upper(S_{i-1})]
   - S_i = S_{i-1} ∪ {a}
3. Отсортировать кандидатов по убыванию (1-α(|S_j|))f_upper(S_j)
4. Пройти по отсортированному набору:
   - Если (1-α(|S_j|))f_upper(S_j) < h(∅), вернуть ∅
   - Если (1-α(|S_j|))f_upper(S_j) > ζR(S_j), продолжить
   - Иначе вернуть S_j

Теорема 1 (гарантия приближения): для любого ζ≥1 алгоритм возвращает S_pr, удовлетворяющий $R(S_{pr}) \geq \frac{e-1}{2e-1} \cdot \frac{1}{\zeta} \cdot R(S^*)$ это выводится на основе приближающего множителя (1-1/e) для субмодулярной максимизации.

Онлайн-постановка: алгоритм OFMUP

Алгоритм 2: Online Fair Multi-Agent UCB with Probing (OFMUP)

Фаза инициализации (t = 1 до MA):

• Каждая пара агент-рукав исследуется по крайней мере один раз
• Построение эмпирической функции распределения F̂_{j,a,t} и оценки среднего μ̂_{j,a,t}

Основной цикл (t > MA):

1. Выбор набора зондирования: вызов Алгоритма 1 на основе текущих оценок F̂_{j,a,t} для выбора S_t
2. Обновление зондирования: выборка из рукавов в S_t, обновление статистики и верхних доверительных границ $U_{j,a,t} = \min(\hat{\mu}_{j,a,t} + w_{j,a,t}, 1)$ где w_{j,a,t} — ширина доверительного интервала, основанная на неравенстве Фридмана
3. Оптимизация политики: $\pi_t = \arg\max_{\pi_t \in \Delta^A} (1-\alpha(|S_t|)) \mathbb{E}_{R_t}[\text{NSW}(S_t, R_t, U_t, \pi_t)]$
4. Выбор рукава: каждый агент j выбирает рукав согласно π_t, наблюдает вознаграждение и обновляет

Построение доверительных границ

Лемма 7 (граница концентрации): с вероятностью по крайней мере 1-δ/2 для всех t>A, a∈A, j∈M: $|\mu_{j,a} - \hat{\mu}_{j,a,t}| \leq \sqrt{\frac{2(\hat{\mu}_{j,a,t} - \hat{\mu}^2_{j,a,t}) \ln(\frac{2MAT}{\delta})}{N_{j,a,t}}} + \frac{\ln(\frac{2MAT}{\delta})}{3N_{j,a,t}} = w_{j,a,t}$

Технические инновации

1. Объединение зондирования и справедливости: первое объединение механизма активного зондирования с целевой функцией NSW справедливости, отличающееся от предыдущих работ, оптимизирующих только общее вознаграждение
2. Техника субмодулярного приближения: преобразование нежелательной субмодулярной задачи в субмодулярную оптимизацию через кусочно-линейную верхнюю границу, сохраняя вычислительную эффективность
3. Слияние UCB и NSW: онлайн-алгоритм искусно объединяет доверительные границы UCB с оптимизацией NSW, балансируя исследование-использование и справедливость
4. Многоуровневый анализ сожаления: разделение раундов на "большие γ" и "малые γ" категории, отдельная обработка высокой и низкой неопределенности

Экспериментальная установка

Наборы данных

Синтетические данные:

• Малый масштаб: M=12 агентов, A=8 рукавов
• Средний масштаб: M=20 агентов, A=10 рукавов
• Распределения вознаграждений:
  • Распределение Бернулли (вознаграждение 0 или 1, среднее в 0.3, 0.8)
  • Дискретное распределение (вознаграждение из {0.3, 0.4, 0.5, 0.6, 0.7, 0.8})

Реальные данные: набор данных NYYellowTaxi 2016

• Агенты: транспортные средства (случайно предварительно выбранные позиции)
• Рукава: дискретизированные позиции подачи заказов (сетка 0.01°×0.01°)
• Вознаграждение: основано на нормализованном расстоянии Манхэттена от транспортного средства до позиции подачи заказа (чем ближе, тем выше вознаграждение)

Метрики оценки

• Накопленное сожаление: рассчитывается по формуле (1), оптимальное вознаграждение определяется исчерпывающим поиском
• Численная стабильность: использование геометрического среднего для агрегирования накопленного NSW каждого агента
• Проверка приближения: проверка того, что разница между f_upper(S) и log(g(S)) ≤0.03

Методы сравнения

1. Non-Probing: алгоритм справедливого MAB Jones и др. (2023), без возможности зондирования, оптимизация распределения только на основе текущей информации
2. Random P+A: случайный выбор фиксированного количества рукавов для зондирования, затем случайное распределение
3. Greedy P+A: использование того же алгоритма жадного зондирования, но случайное распределение после зондирования

Детали реализации

• Бюджет зондирования: установлен в соответствии с размером задачи
• Функция стоимости: α(|S|) — возрастающая функция, α(0)=0, α(I)=1
• Параметр доверия: δ установлен для обеспечения высокой вероятности гарантий
• Открытый исходный код: https://github.com/jiaxin26/Fair-MA-MAB-with-Probing

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

Основные результаты

Основные выводы, представленные на Рисунке 1:

1. Малый масштаб (M=12, A=8, Бернулли):
   • OFMUP при T=3000 имеет сожаление на 85% ниже, чем Random P+A
   • На 60% ниже, чем Greedy P+A
   • Значительно превосходит Non-Probing
2. Средний масштаб (M=20, A=10, Бернулли):
   • Преимущество OFMUP еще более выраженно
   • При T=3000 сожаление на 88% ниже, чем Random P+A
   • На 80% ниже, чем Greedy P+A
   • Демонстрирует лучшую масштабируемость
3. Сценарий дискретного распределения:
   • OFMUP постоянно превосходит базовые методы
   • Разрыв с другими методами увеличивается по мере обучения моделям вознаграждений
   • При T=3000 на 85% ниже, чем Random P+A, на 65% ниже, чем Non-Probing
4. Аномалия Random P+A:
   • При малом масштабе сожаление немного выше ожидаемого
   • Причина: при расчете справедливости через геометрическое среднее малые выборки увеличивают вариативность

Анализ масштабируемости

Масштабируемость, представленная на Рисунке 2:

1. Фиксированное количество рукавов (A=8), переменное количество агентов:
   • OFMUP показывает хорошую производительность при всех количествах агентов
   • Относительное преимущество растет с увеличением сложности задачи
2. Фиксированное количество агентов (M=20), переменное количество рукавов:
   • Преимущество OFMUP становится более выраженным с увеличением количества рукавов
   • Доказывает ценность механизма зондирования в высокомерных пространствах

Экспериментальные выводы

1. Ключевая роль зондирования: зондирование играет решающую роль в сборе информации и руководстве распределением
2. Важность справедливого распределения: Greedy P+A показывает результаты намного хуже, чем OFMUP, что подчеркивает критическую важность справедливого распределения после зондирования
3. Теоретическая проверка: экспериментальные результаты подтверждают теоретический анализ — OFMUP эффективно балансирует исследование-использование и справедливость
4. Применимость к реальным данным: успех на данных NYYellowTaxi доказывает потенциал практического применения

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

Основы многорукавого бандита

• Одноагентный MAB: Lai & Robbins (1985), Garivier & Cappé (2011)
• Многоагентный MAB: Martínez-Rubio и др. (2019), Hossain и др. (2021)
• Исследования справедливости: Joseph и др. (2016, 2018), Patil и др. (2021)

Социальное благосостояние Нэша

• Теоретические основы: Kaneko & Nakamura (1979)
• Методы вычисления: Cole & Gkatzelis (2015)
• Применение в MA-MAB: Jones, Nguyen & Nguyen (2023) — работа, непосредственно расширяемая в данной статье

Механизмы зондирования

• Экономическое происхождение: Weitzman (1979)
• Одноагентный бандит с зондированием:
  • Aaron D. Tucker и др. (2023): дорогостоящие наблюдения вознаграждений, граница Θ(c^{1/3}T^{2/3})
  • Elumar и др. (2024): зондирование одного рукава за раунд, сожаление Õ(√KT)
  • Zuo и др. (2020): структура Observe-Before-Play
• Субмодулярное зондирование: Bhaskara и др. (2020) для задач маршрутизации
• Вклад данной работы: первое объединение зондирования с многоагентной справедливостью

Исследовательский пробел

Существующие работы либо сосредоточены на справедливом MAB, но полагаются на пассивную обратную связь, либо исследуют зондирование, но игнорируют справедливость. Данная работа заполняет этот пробел.

Теоретический анализ

Гарантия приближения в автономной постановке (Теорема 1)

Результат: R(S_pr) ≥ (e-1)/(2e-1) · 1/ζ · R(S*)

Ключевые этапы доказательства:

1. Использование Леммы 5: R(S) ≤ (1-α(|S|))(g(S) + h(S))
2. Применение приближающего множителя (1-1/e) для субмодулярной максимизации
3. Связь f_upper с R через условия отбора алгоритма
4. Получение гарантии приближения с постоянным множителем

Граница сожаления в онлайн-постановке (Теорема 2)

Результат: с вероятностью по крайней мере 1-δ, $R_{\text{regret}}(T) = O\left(\zeta(\sqrt{MAT} + MA) \ln^c\left(\frac{MAT}{\delta}\right)\right)$

Структура доказательства:

1. Гладкость NSW (Лемма 6): свойство Липшица NSW относительно матрицы вознаграждений
2. Граница концентрации (Лемма 7): доверительные границы, основанные на неравенстве Фридмана
3. Многоуровневое разделение раундов (Лемма 8):
   • Определение γ_{j,t} = Σ_a π_{j,a,t}(1-U_{j,a,t})
   • Раунды с большим γ: |Q(t,p)| ≥ 2^p·3lnT, вклад ≤1/T²
   • Раунды с малым γ: применение границ концентрации, разложение на корневой и линейный члены
4. Граница корневого члена: обработка через неравенство Юнга и Лемму 8
5. Граница линейного члена: использование Леммы 4.4 из Jones и др. (2023)
6. Финальное объединение: получение главного члена O(√MAT) плюс члены низшего порядка

Ключевые техники:

• Преобразование сожаления от (S*,π*) к (S_t,π_t), использование множителя из Теоремы 1
• Оптимизм UCB: U_{j,a,t}≥μ_{j,a} обеспечивает исследование
• Многоуровневый анализ избегает прямой обработки сложной зависимости всех раундов

Выводы и обсуждение

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

1. Теоретические вклады:
   • Автономная постановка: вычислимый алгоритм с гарантией приближения с постоянным множителем
   • Онлайн-постановка: сублинейное сожаление O(√MAT), сравнимое с алгоритмами справедливого MAB без зондирования, но с лучшей практической производительностью
2. Практическая ценность:
   • Механизм зондирования значительно улучшает оценку вознаграждений
   • Балансирует исследование-использование и справедливость
   • Проверена эффективность на реальных данных сервисов совместного использования автомобилей
3. Методологические инновации:
   • Первое объединение активного зондирования с многоагентной справедливостью
   • Техника субмодулярного приближения для обработки невыпуклой оптимизации
   • Структура онлайн-обучения, объединяющая UCB и NSW

Ограничения

1. Вычислительная сложность:
   • Автономный алгоритм требует итеративного решения оптимизации NSW (NP-сложная)
   • Каждый раунд онлайна требует вычисления оптимальной политики π_t
   • Возможные вычислительные узкие места в крупномасштабных сценариях (M,A>100)
2. Теоретические предположения:
   • Кусочно-линейное приближение требует достаточно мелкого разбиения (предположение d/d'≥τ_i/τ_j)
   • Бюджет зондирования I требует предварительной установки
   • Форма функции стоимости α(·) должна быть известна
3. Диапазон экспериментов:
   • Относительно ограниченный масштаб экспериментов (максимум M=20, A=10)
   • Реальные данные протестированы только на сценарии сервиса совместного использования автомобилей
   • Отсутствует сравнение с большим количеством новейших методов справедливого MAB
4. Мера справедливости:
   • Рассматривается только NSW, не исследуются другие концепции справедливости (такие как max-min, envy-freeness)
   • NSW чувствительна к нулевым вознаграждениям (требует положительного вознаграждения для всех агентов)

Направления будущих исследований

Хотя статья не предлагает явно, можно предположить следующие направления:

1. Расширение на другие меры справедливости: исследование объединения механизмов зондирования с другими концепциями справедливости
2. Адаптивный бюджет зондирования: динамическая корректировка количества зондирований вместо фиксированного I
3. Распределенная реализация: децентрализованные решения по зондированию и распределению
4. Нестационарная среда: сценарии, где распределения вознаграждений изменяются со временем
5. Ограничения: включение бюджетных, задержечных и других практических ограничений

Глубокая оценка

Преимущества

1. Теоретическая строгость:
   • Строгие теоретические гарантии как для автономной, так и для онлайн-постановок
   • Полные и детальные доказательства (приложение превышает 20 страниц)
   • Построение свойств субмодулярности является искусным и критическим
2. Важность проблемы:
   • Решает реальные проблемы в практических приложениях (справедливость и неопределенность)
   • Пример с сервисом совместного использования автомобилей имеет прямую прикладную ценность
   • Заполняет исследовательский пробел между справедливым MAB и активным исследованием
3. Инновационность метода:
   • Объединение механизма зондирования и NSW является новым
   • Техника кусочно-линейной верхней границы является искусной
   • Слияние UCB и оптимизации NSW нетривиально
4. Достаточность экспериментов:
   • Охватывает синтетические и реальные данные
   • Множество распределений и размеров задач
   • Полный анализ масштабируемости
   • Четкие абляционные исследования (сравнение с Greedy P+A)
   • Наглядные и эффективные графики
5. Ясность изложения:
   • Четкое объяснение мотивации
   • Полное описание технических деталей
   • Наглядные таблицы и графики

Недостатки

1. Недостаточное обсуждение вычислительной эффективности:
   • Не сообщается время выполнения алгоритма
   • Отсутствует анализ вычислительной сложности оптимизации NSW
   • Сомнения в практической осуществимости для крупномасштабных сценариев
2. Упрощенное моделирование стоимости зондирования:
   • Функция α(|S|) слишком абстрактна
   • Недостаточно подробно объясняется установка α в практических приложениях
   • Не исследуются различия в характеристиках стоимости для разных приложений
3. Ограниченные методы сравнения:
   • Основное сравнение с методом Jones и др. (2023)
   • Отсутствует сравнение с большим количеством новейших методов справедливого MAB
   • Нет сравнения с неправедными, но эффективными алгоритмами зондирования
4. Ограниченный масштаб экспериментов:
   • Максимум M=20, A=10 относительно мал
   • Реальные данные протестированы только на одном наборе данных
   • Не тестировались экстремально несбалансированные сценарии (M>>A или A>>M)
5. Разрыв между теорией и практикой:
   • Гарантия приближения в Теореме 1 включает параметр ζ, но не объясняется, как выбрать ζ на практике
   • Константа c в Теореме 2 не уточняется
   • Не анализируется, как фактическая ошибка кусочно-линейного приближения (0.03) влияет на производительность
6. Недостаточное обсуждение справедливости:
   • Ограничения NSW (чувствительность к нулевым вознаграждениям) недостаточно обсуждены
   • Отсутствует сравнение с другими мерами справедливости
   • Не рассматривается индивидуальная рациональность (individual rationality)

Влияние

Академическое влияние:

• Высокое: заполняет важный исследовательский пробел, ожидается высокий уровень цитирования
• Предоставляет новую исследовательскую парадигму для области справедливого MAB
• Объединение механизмов зондирования и справедливости может вдохновить последующие работы

Практическая ценность:

• Средняя-высокая:
  • Прямой потенциал применения на платформах совместного использования автомобилей
  • Вычислительная сложность может ограничить крупномасштабное развертывание
  • Требуется дальнейшая инженерная оптимизация

Воспроизводимость:

• Высокая: исходный код открыт, описание алгоритма детально
• Теоретические доказательства полные и легко проверяемые
• Экспериментальная установка четко описана

Применимые сценарии

Сильно применимые сценарии:

1. Диспетчеризация сервисов совместного использования автомобилей: среднемасштабные города (10-20 регионов, 10-50 автомобилей)
2. Системы рекомендации контента: платформы, требующие балансировки воздействия создателей
3. Планирование беспроводных сетей: сценарии WLAN 60 ГГц (упомянуто в статье)
4. Распределение ресурсов: любые сценарии, требующие справедливости и имеющие неопределенность

Слабо применимые сценарии:

1. Крупномасштабные системы: M,A>100 могут быть вычислительно неосуществимы
2. Системы реального времени: вычислительная задержка оптимизации NSW может быть чрезмерной
3. Динамические среды: сценарии с быстро изменяющимися распределениями вознаграждений
4. Нулевая сумма конкуренции: ситуации с прямой конкуренцией между агентами

Неприменимые сценарии:

1. Одноагентные задачи: метод чрезмерно сложен
2. Известные вознаграждения: механизм зондирования не требуется
3. Экстремальные требования справедливости: NSW может быть недостаточно "справедливой" (рассмотрение max-min)

Ключевые ссылки

1. Jones, Nguyen & Nguyen (2023): "An efficient algorithm for fair multi-agent multi-armed bandit with low regret" — базовая работа, непосредственно расширяемая в данной статье
2. Cole & Gkatzelis (2015): "Approximating the Nash social welfare with indivisible items" — теоретические основы оптимизации NSW
3. Zuo, Zhang & Joe-Wong (2020): "Observe Before Play: Multi-Armed Bandit with Pre-Observations" — пионерская работа по механизмам зондирования
4. Bhaskara et al. (2020): "Adaptive probing policies for shortest path routing" — применение субмодулярного зондирования
5. Caragiannis et al. (2019): "The unreasonable fairness of maximum Nash welfare" — теория справедливости NSW

Резюме

Данная работа вносит значительный вклад в область многоагентных многорукавых бандитов, впервые систематически объединяя механизм активного зондирования с целевой функцией справедливости. Теоретически строга (гарантия приближения с постоянным множителем и сублинейное сожаление), экспериментально полна (синтетические и реальные данные), методологически инновативна (субмодулярное приближение + слияние UCB-NSW). Основные ограничения связаны с вычислительной сложностью и масштабом экспериментов, но это не умаляет академическую ценность и практический потенциал. Данная работа открывает новые направления исследований в области справедливого машинного обучения и онлайн-принятия решений, заслуживая дальнейшего изучения и применения.