Переосмотр социального благосостояния в многоруких бандитах: UCB — это (почти) всё, что вам нужно

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

• ID статьи: 2510.21312
• Название: Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need
• Авторы: Dhruv Sarkar (IIT Kharagpur), Nishant Pandey (IIT Kanpur), Sayak Ray Chowdhury (IIT Kanpur)
• Категория: cs.LG (Машинное обучение)
• Дата публикации: 24 октября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.21312
• Ссылка на код: https://github.com/NP-Hardest/UCBisAllYouNeed

Аннотация

В данной работе исследуется проблема справедливости в задаче многоруких бандитов (Multi-Armed Bandits, MAB). Традиционная метрика сожаления (regret), основанная на арифметическом среднем, не гарантирует справедливость между пользователями. Для решения этой проблемы в литературе введена метрика сожаления Нэша (Nash regret), основанная на геометрическом среднем. Однако существующие методы минимизации сожаления Нэша требуют специализированного проектирования алгоритмов и строгих предположений (таких как мультипликативные неравенства концентрации, ограниченные неотрицательные награды) и даже не применимы к гауссовым распределениям. В данной работе показано, что посредством адаптивной к данным начальной фазы равномерного исследования в сочетании со стандартным алгоритмом UCB можно достичь почти оптимального сожаления Нэша, опираясь только на аддитивное неравенство Хёффдинга, которое естественным образом распространяется на субгауссовы награды. Кроме того, авторы обобщают алгоритм на широкий класс мер справедливости — сожаление p-среднего, доказывая (почти) оптимальные границы сожаления для всех значений p без строгих предположений предыдущих работ.

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

Определение проблемы

1. Основная проблема: В задаче многоруких бандитов, как максимизировать кумулятивное вознаграждение, одновременно обеспечивая справедливость между временными шагами (соответствующими различным пользователям/пациентам)? Традиционное среднее сожаление (Average Regret) фокусируется только на общей полезности, что может привести к получению экстремально низких вознаграждений на некоторых временных шагах, что не обеспечивает справедливости.
2. Важность: В клинических испытаниях, распределении ресурсов и других приложениях каждый временной шаг соответствует отдельному индивиду (например, пациенту). Оптимизация только средней полезности может привести к несправедливому обращению с некоторыми индивидами, что неприемлемо с этической и социальной точек зрения.
3. Ограничения существующих методов:
   • Barman et al. (2023) предложили алгоритм Nash Confidence Bound (NCB), но он зависит от мультипликативных неравенств Хёффдинга/Чернова, требует ограниченных неотрицательных вознаграждений, не применим к гауссовым и другим общим распределениям, и неявно требует знания верхней границы μ*
   • Krishna et al. (2025) исследовали сожаление p-среднего, но требуют, чтобы ожидаемое вознаграждение каждого рычага было не менее Ω̃(√k/T^(1/4)), это предположение чрезвычайно строгое, исключает многие практические сценарии, и при некоторых значениях p граница сожаления субоптимальна
4. Исследовательская мотивация: Разработать универсальную схему, использующую классический алгоритм UCB для достижения целей справедливости, без необходимости в специально разработанных доверительных интервалах, применимую к общим субгауссовым распределениям, без нереалистичных предположений о неизвестных средних.

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

1. Схема редукции: Предложена схема редукции минимизации сожаления Нэша/p-среднего к кратковременному адаптивному к данным равномерному исследованию + стандартному алгоритму бандита (например, UCB), ключевое нововведение — адаптивное правило остановки
2. Проектирование алгоритма: Разработан алгоритм Welfarist-UCB с двухэтапной стратегией:
   • Этап I: Равномерное исследование до выполнения адаптивного условия завершения
   • Этап II: Исследование-использование с использованием стандартного индекса UCB
3. Теоретические гарантии:
   • Для сожаления Нэша (p=0): достигается граница Õ(σ√(k/T)) порядка-оптимальная, применима к σ-субгауссовым вознаграждениям
   • Для p∈0,1: достигается граница Õ(σ√(k/T)) порядка-оптимальная
   • Для p∈[-1,0): достигается граница Õ(k/√T), превосходит Õ(k^(3/4)T^(-1/4)) из Krishna et al.
   • Для p<-1: достигается граница Õ(|p|k^((|p|+1)/2)/√T), строго превосходит предыдущие работы в практически релевантном диапазоне T
4. Техническое нововведение: Использование аддитивного неравенства Хёффдинга вместо мультипликативного, избегает строгих ограничений на распределение вознаграждений и не требует верхней границы μ*
5. Экспериментальная проверка: Численное моделирование проверяет эффективность алгоритма при различных значениях p, демонстрирует принцип "отсутствия бесплатного обеда": более строгие требования справедливости приводят к более высокому сожалению

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

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

Входные данные:

• k рычагов, каждый рычаг i с распределением вознаграждения ρᵢ, являющимся σ-субгауссовым, с неизвестным средним μᵢ≥0
• Временной диапазон T
• Параметр справедливости p∈(-∞,1]

Выходные данные: Рычаг Iₜ, выбираемый на каждом раунде t∈T

Цель: Минимизировать сожаление p-среднего $R^p_T := \mu^* - \left(\frac{1}{T}\sum_{t=1}^T (\mathbb{E}[\mu_{I_t}])^p\right)^{1/p}$ где μ*=maxᵢμᵢ. В частности, p=0 соответствует сожалению Нэша (геометрическое среднее).

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

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

Стратегия исследования:

• Каждые k шагов составляют один блок
• В начале каждого блока равномерно случайно выбирается перестановка рычагов π∈Πₖ
• Рычаги последовательно вытягиваются в порядке π(1), π(2), ..., π(k)

Условие завершения: Этап I завершается, когда существует рычаг i, удовлетворяющий обоим условиям:

1. $\hat{\mu}_i > 2\sqrt{\frac{2\sigma^2\log T}{n_i}}$
2. $n_i > \frac{192p_a^2\sigma^2\log T}{(\hat{\mu}_i - 2\sqrt{\frac{2\sigma^2\log T}{n_i}})^2}$

где:

• nᵢ: количество раз, когда рычаг i был вытянут
• μ̂ᵢ: эмпирическое среднее наблюдаемых вознаграждений рычага i
• pₐ = 1 (если p≥-1), pₐ = p (если p<-1)

Ключевое свойство (Лемма 4.1): При высокой вероятности события E, продолжительность Этапа I τ удовлетворяет $32kS \leq \tau \leq 128kS$ где $S = \frac{4p_a^2\sigma^2\log T}{(\mu^*)^2}$

Это означает, что каждый рычаг вытягивается Θ(1/(μ*)²) раз, что является ключевым для последующего анализа.

Этап II: Исследование-использование UCB

Используется стандартный индекс UCB: $\text{UCB}_i = \hat{\mu}_i + 2\sqrt{\frac{2\sigma^2\log T}{n_i}}$

На каждом раунде выбирается рычаг с максимальным значением UCB.

Технические точки нововведения

1. Проектирование адаптивного к данным условия завершения

Нововведение: Знаменатель в условии завершения $(\hat{\mu}_i - 2\sqrt{\frac{2\sigma^2\log T}{n_i}})^2$ гарантирует, что Этап I завершается после Θ(1/(μ*)²) раундов, а не фиксированных Θ(√T) или Θ(1/μ*) раундов.

Обоснованность:

• Когда μ* велико, требуется меньше исследования для идентификации хорошего рычага
• Когда μ* мало, требуется больше исследования для различения рычагов
• Эта адаптивность гарантирует, что для любого вытянутого рычага i, $\xi_i := \frac{2\sqrt{2\sigma^2\log T}}{\mu^*\sqrt{n_i}} \leq 1/2$, что является ключевым для контроля сожаления Нэша

2. Использование аддитивного неравенства Хёффдинга

Сравнение с NCB:

• NCB: Обусловлено событием $\{\forall i, \mu_i \in [\hat{\mu}_i - 4\sqrt{\frac{\hat{\mu}_i\log T}{n_i}}, \hat{\mu}_i + 4\sqrt{\frac{\hat{\mu}_i\log T}{n_i}}]\}$, требует мультипликативное неравенство Хёффдинга
• Данная работа: Обусловлено событием $\{\forall i, \mu_i \in [\hat{\mu}_i - 2\sqrt{\frac{2\sigma^2\log T}{n_i}}, \hat{\mu}_i + 2\sqrt{\frac{2\sigma^2\log T}{n_i}}]\}$, требует только аддитивное неравенство Хёффдинга

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

• Аддитивная граница применима к любому субгауссовому распределению (включая гауссовы, ограниченные и т.д.)
• Не требует строго неотрицательных или ограниченных вознаграждений
• Не требует предварительного знания верхней границы μ*

3. Эквивалентность выборки перестановок (Лемма B.3)

Ключевое наблюдение: Стратегия выборки перестановок на Этапе I эквивалентна независимому равномерному выбору на каждом раунде в маргинальном распределении, т.е. PrIₜ=i=1/k, следовательно 𝔼μ_{Iₜ}≥μ*/k.

Техническое значение: Эта статическая связь (static coupling) упрощает анализ Этапа I, позволяя напрямую использовать свойства равномерной выборки.

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

Набор данных

Данная работа использует синтетические данные для численного моделирования:

1. Рычаги Бернулли: k=50 рычагов, средние значения равномерно случайно выбраны из 0.005, 1
2. Гауссовы рычаги: k=50 рычагов, средние значения равномерно случайно выбраны из 10, 1000, стандартное отклонение σ=20

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

• Сожаление Нэша (p=0): $\mu^* - (\prod_{t=1}^T \mathbb{E}[\mu_{I_t}])^{1/T}$
• Сожаление p-среднего: $\mu^* - (\frac{1}{T}\sum_{t=1}^T (\mathbb{E}[\mu_{I_t}])^p)^{1/p}$

𝔼μ_{Iₜ} оценивается средним вознаграждением из 50 запусков.

Сравниваемые методы

1. NCB (Barman et al., 2023): Использует индекс Nash Confidence Bound
2. Explore-then-UCB (Krishna et al., 2025): Использует UCB после фиксированной фазы исследования

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

• Временной диапазон T постепенно увеличивается от меньших к большим значениям
• Тестирование проводится для различных значений p (p=0.5, 0, -0.5, -1.5)
• Все эксперименты воспроизводимы с использованием предоставленного репозитория кода

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

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

1. Сожаление Нэша (p=0)

Вознаграждения Бернулли (рис. 1a):

• Сожаление Нэша Welfarist-UCB снижается значительно быстрее, чем NCB с увеличением T
• Подтверждает теоретическую скорость сходимости Õ(√(k/T))

Субгауссовы вознаграждения (рис. 1b):

• Welfarist-UCB эффективно минимизирует сожаление Нэша при гауссовом распределении
• NCB показывает худшую производительность в этой установке, подтверждает применимость метода к общим распределениям

2. Сожаление p-среднего в трёх интервалах

p=0.5 (0<p≤1) (рис. 1c):

• Welfarist-UCB превосходит Explore-then-UCB при всех значениях T
• Скорость снижения сожаления соответствует теоретическому предсказанию Õ(√(k/T))

p=-0.5 (-1<p<0) (рис. 1d):

• Welfarist-UCB значительно превосходит Explore-then-UCB
• Подтверждает, что граница Õ(k/√T) превосходит Õ(k^(3/4)T^(-1/4)) из Krishna et al.

p=-1.5 (p≤-1) (рис. 1e):

• Более строгие требования справедливости приводят к более высокому сожалению
• Welfarist-UCB по-прежнему превосходит методы-базовые линии

3. Абляционный эксперимент: влияние значения p (рис. 1f)

Ключевые находки:

• С уменьшением p (усиление требований справедливости) сожаление p-среднего постоянно растёт
• Подтверждает гипотезу "отсутствия бесплатного обеда": более строгая справедливость требует более высокого сожаления
• Когда p→-∞ (справедливость Роулса), граница сожаления становится пустой, указывая на недостижимость экстремальной справедливости в краткосрочном периоде

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

1. Практическая эффективность: Welfarist-UCB демонстрирует превосходную практическую производительность во всех протестированных сценариях
2. Робастность распределения: Алгоритм эффективен для различных распределений вознаграждений (Бернулли, гауссовы), подтверждает широкую применимость теории
3. Компромисс справедливость-полезность: Эксперименты ясно демонстрируют компромисс между параметром справедливости p и сожалением, предоставляя руководство для выбора подходящего p в практических приложениях
4. Скорость сходимости: При всех интервалах p скорость снижения сожаления Welfarist-UCB соответствует теоретическим предсказаниям и превосходит существующие методы

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

1. Справедливость в многоруких бандитах

Различные концепции справедливости:

• Справедливость рычагов (Joseph et al. 2016; Patil et al. 2021): Гарантирует справедливое обращение с различными рычагами
• Справедливость многоагентов (Hossain et al. 2021; Jones et al. 2023): Справедливое распределение вознаграждений между несколькими агентами на каждом вытягивании
• Фокус данной работы: Справедливость между временными шагами, каждый временной шаг соответствует отдельному индивиду

2. Сожаление Нэша

Barman et al. (2023):

• Впервые предложили концепцию сожаления Нэша
• Разработали алгоритм NCB, достигающий границы Õ(√(k/T))
• Ограничения: требует мультипликативные неравенства концентрации, ограничено ограниченными неотрицательными вознаграждениями

3. Благосостояние p-среднего

Теоретические основы (Moulin 2004):

• Функция p-среднего определяется пятью аксиомами: анонимность, масштабная инвариантность, непрерывность, монотонность, симметрия
• Удовлетворяет принципу передачи Пигу-Далтона (при p≤1)

Krishna et al. (2025):

• Исследуют общее сожаление p-среднего
• Используют Explore-then-UCB
• Ограничения: требуют μᵢ≥Ω̃(√k/T^(1/4)), граница сожаления субоптимальна в некоторых интервалах

4. Другие связанные направления

• Сожаление Нэша в линейных бандитах (Sawarni et al. 2024)
• Онлайн максимизация социального благосостояния Нэша (Zhang et al. 2024)
• Справедливость в многоагентном обучении с подкреплением (Mandal & Gan 2022)
• Пересечение приватности и справедливости (Sarkar et al. 2025): Фреймворк DP-NCB

Преимущества данной работы по сравнению с связанными работами

1. Более слабые предположения: Требует только μᵢ≥0 и субгауссовость, без нижней границы μᵢ или ограниченности вознаграждений
2. Более хорошие границы: При p∈[-1,0) достигает Õ(k/√T), превосходит предыдущие Õ(k^(3/4)T^(-1/4))
3. Единая схема: Один алгоритм обрабатывает все значения p, без необходимости разных стратегий для разных p
4. Техническая простота: Использует стандартный UCB и аддитивное неравенство Хёффдинга, избегает сложного специализированного проектирования

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

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

1. Теоретический вклад: Доказано, что классический алгоритм UCB в сочетании с адаптивным исследованием может достичь почти оптимальных гарантий справедливости без специализированного проектирования доверительных интервалов
2. Практическое значение: Делает последовательное принятие решений с учётом справедливости более практичным и широко применимым, особенно в сценариях, требующих обработки общих распределений (например, гауссовых)
3. Принцип "отсутствия бесплатного обеда": Более строгие требования справедливости по сути увеличивают сложность задачи обучения, требуя больше образцов для достижения низкого сожаления

Ограничения

1. Ограничения предположений:
   • По-прежнему требует предположение μᵢ≥0 (хотя стандартное, может быть ограничивающим в некоторых приложениях)
   • Предположение субгауссовости может не применяться к распределениям с тяжёлыми хвостами
2. Граница при p<-1:
   • Граница сожаления растёт экспоненциально с |p|, граница становится пустой при T≤p²k^|p|
   • Хотя превосходит предыдущие работы в практически релевантном диапазоне T, остаётся место для улучшения
3. Отсутствие нижних границ:
   • Отсутствуют доказательства нижних границ для интервала p<-1
   • Невозможно определить, являются ли текущие верхние границы плотными
4. Масштаб экспериментов:
   • Эксперименты в основном проводятся при среднем масштабе k=50
   • Производительность при большом масштабе (k≫50) недостаточно изучена

Будущие направления

1. Теоретическое совершенствование:
   • Доказать соответствующие нижние границы для p<-1, формализовать принцип "отсутствия бесплатного обеда"
   • Исследовать возможность дальнейшего улучшения верхних границ при p<-1
2. Ослабление предположений:
   • Исследовать обработку случаев, когда μᵢ может быть значительно отрицательным
   • Расширить на распределения с тяжёлыми хвостами или другие не-субгауссовы распределения
3. Расширение алгоритма:
   • Обобщить на контекстные бандиты или установки обучения с подкреплением
   • Объединить с другими концепциями справедливости (например, индивидуальная справедливость)
4. Практические приложения:
   • Проверить в реальных клинических испытаниях или сценариях распределения ресурсов
   • Разработать методы адаптивного выбора значения p
5. Вычислительная эффективность:
   • Проверка условия завершения на Этапе I может быть вычислительно интенсивной, исследовать более эффективные реализации

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

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

1. Сильная теоретическая новизна:
   • Проектирование адаптивного к данным условия завершения изящно, решает проблему отказа UCB в минимизации сожаления Нэша
   • Использование аддитивного неравенства Хёффдинга вместо мультипликативного — ключевой технический прорыв, значительно расширяет применимость
   • Единая схема для обработки всех значений p элегантна и мощна
2. Достаточность экспериментов:
   • Охватывает несколько интервалов p (p>0, p=0, -1<p<0, p<-1)
   • Сравнивает несколько методов-базовых линий (NCB, Explore-then-UCB)
   • Включает абляционные эксперименты для проверки гипотезы "отсутствия бесплатного обеда"
3. Убедительность результатов:
   • Теоретические границы в большинстве случаев порядка-оптимальны или близки к оптимальным
   • Экспериментальные результаты высоко согласуются с теоретическими предсказаниями
   • Строгие математические доказательства, технические леммы (такие как Лемма 4.1, 4.2) логически ясны
4. Ясность изложения:
   • Мотивация ясна, определение проблемы точно
   • Раздел о техниках доказательства (Раздел 4) предоставляет интуитивные объяснения
   • Сравнение с предыдущими работами детально и справедливо (Замечания 3.1, 3.2, 3.3)
5. Воспроизводимость:
   • Предоставлен полный репозиторий кода
   • Псевдокод алгоритма ясен (Алгоритм 1)
   • Экспериментальная установка описана подробно

Недостатки

1. Ограничения метода:
   • Предположение μᵢ≥0 в некоторых приложениях ограничивает (хотя Замечание 2.1 предоставляет разумное обоснование)
   • Условие завершения Этапа I включает член p², при больших |p| может привести к чрезмерно длительной фазе исследования
   • Граница при p<-1 не столь плотна, как в других интервалах
2. Недостатки экспериментальной установки:
   • Используются только синтетические данные, отсутствует проверка на реальных наборах данных
   • Масштаб k=50 относительно мал, производительность при большом масштабе (k=1000+) неизвестна
   • Не исследовано влияние изменения σ на производительность алгоритма
3. Недостаточность анализа:
   • Отсутствует статистика фактического времени завершения Этапа I (теоретическая граница 32kS до 128kS, как выглядит фактическое распределение?)
   • Не обсуждена вычислительная сложность алгоритма (особенно проверка условия завершения)
   • Анализ поведения алгоритма при различных значениях μ* недостаточно глубок
4. Теоретические пробелы:
   • При p<-1 отсутствуют нижние границы, невозможно судить о плотности верхних границ
   • Не исследовано, как выбрать σ² при неизвестном μ* (алгоритм требует σ² в качестве входа)
   • Необходимость множителя log k в границе сожаления Нэша недостаточно обсуждена

Влияние

1. Вклад в область:
   • Значительно продвигает теоретическое понимание алгоритмов бандитов с учётом справедливости
   • Доказывает применимость классических алгоритмов (UCB) к новым проблемам, поощряет переоценку простых методов
   • Предоставляет твёрдую теоретическую основу для применения благосостояния p-среднего в онлайн-обучении
2. Практическая ценность:
   • Алгоритм простой, легко реализуется и развёртывается
   • Применим к широкому спектру типов распределений, повышает потенциал практического применения
   • Предоставляет количественное описание компромисса справедливость-полезность, направляет выбор значения p на практике
3. Воспроизводимость:
   • Код открыт, описание алгоритма ясно
   • Теоретические доказательства полны, технические леммы могут служить справочником для последующих работ
   • Экспериментальная установка стандартизирована, легко воспроизводится и расширяется
4. Вдохновляющее значение:
   • Открытие принципа "отсутствия бесплатного обеда" имеет глубокое понимание
   • Идея адаптивного исследования может вдохновить исследования других вариантов бандитов
   • Обсуждение аддитивных vs мультипликативных неравенств концентрации имеет методологическое значение для проектирования алгоритмов

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

1. Клинические испытания: Требуют исследования эффективных методов лечения при одновременном справедливом обращении с каждым пациентом
2. Распределение ресурсов: Онлайн-распределение ограниченных ресурсов (например, вычислительные ресурсы, рекламные места) различным пользователям, требует баланса эффективности и справедливости
3. Системы рекомендаций: Рекомендация контента пользователям в разные временные периоды, требует избежать экстремально плохого опыта пользователей в некоторые периоды
4. A/B тестирование: При тестировании продукта требуется учитывать благосостояние участников, а не только средние показатели
5. Распределение образовательных ресурсов: Распределение образовательных ресурсов студентам, поступившим в разные периоды, требует справедливости между когортами

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

• Приложения, требующие экстремальной справедливости Роулса (p→-∞) в краткосрочном периоде (теоретическая граница становится пустой)
• Сценарии с распределениями вознаграждений с тяжёлыми хвостами или не-субгауссовы
• Приложения, где μᵢ может быть значительно отрицательным

Избранные ссылки

1. Barman et al. (2023): "Fairness and welfare quantification for regret in multi-armed bandits" — впервые предложили концепцию сожаления Нэша
2. Krishna et al. (2025): "p-mean regret for stochastic bandits" — исследуют общее сожаление p-среднего
3. Bubeck et al. (2012): "Regret analysis of stochastic and nonstochastic multi-armed bandit problems" — классический учебник по MAB
4. Moulin (2004): "Fair division and collective welfare" — аксиоматическая основа благосостояния p-среднего
5. Sawarni et al. (2024): "Nash regret guarantees for linear bandits" — сожаление Нэша в линейных бандитах

Общая оценка: Это высококачественная статья по теоретическому машинному обучению, вносящая значительный вклад в область алгоритмов бандитов с учётом справедливости. Посредством изящного проектирования алгоритма и строгого теоретического анализа доказано, что простые методы (UCB) эффективны для сложных целей (справедливость). Теоретические результаты мощны, экспериментальная проверка достаточна, область значительно продвинута. Основные недостатки — отсутствие проверки на реальных данных и некоторые теоретические пробелы (например, нижние границы при p<-1). Рекомендуется, чтобы последующие работы сосредоточились на проверке практического применения и теоретическом совершенствовании.