UCB-тип алгоритма для обучения экспертов с ограничением бюджета

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

• ID статьи: 2510.22654
• Название: UCB-type Algorithm for Budget-Constrained Expert Learning
• Авторы: Ilgam Latypov, Alexandra Suvorikova, Alexey Kroshnin, Alexander Gasnikov, Yuriy Dorn
• Классификация: cs.LG (Машинное обучение), cs.MA (Многоагентные системы)
• Дата публикации: 28 октября 2025 г. (Препринт)
• Ссылка на статью: https://arxiv.org/abs/2510.22654

Аннотация

Во многих современных приложениях системы должны динамически выбирать между несколькими адаптивными алгоритмами обучения, работающими в режиме онлайн. Примеры включают выбор модели в потоковых средах, переключение торговых стратегий в финансах и координацию нескольких контекстных многоруких бандитов или агентов обучения с подкреплением. На каждом раунде обучающийся должен выбрать предсказатель из K адаптивных экспертов для прогнозирования, при этом имея возможность обновить не более M≤K экспертов в рамках фиксированного бюджета обучения.

В данной работе решается эта проблема в стохастической постановке путём предложения алгоритма M-LCB — вычислительно эффективного метаалгоритма типа UCB с гарантиями сожаления в любой момент времени. Доверительные интервалы строятся непосредственно из реализованных потерь без дополнительной оптимизации и естественным образом отражают свойства сходимости базовых экспертов. Если каждый эксперт достигает внутреннего сожаления Õ(T^α), то M-LCB гарантирует общую границу сожаления Õ(√(KT/M) + (K/M)^(1-α)T^α).

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

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

Многие приложения в реальном мире требуют динамического выбора между несколькими самообучающимися экспертами:

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

Основные вызовы

Ограничения традиционных подходов:

• Классические многорукие бандиты (MAB): предполагают статическое или противоборствующее распределение вознаграждений, не учитывая способность рук к обучению
• Алгоритмы экспертов: обычно требуют полной обратной связи, не учитывая скорость обучения экспертов
• Существующие методы: не решают адекватно задачу управления несколькими одновременно обучающимися экспертами при ограничениях бюджета обучения на каждом раунде

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

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

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

1. Новый метаалгоритм типа UCB (M-LCB): предложен новый алгоритм для управления пулом K самообучающихся экспертов с учётом ограниченного бюджета обучения M на каждом раунде (M≤K)
2. Вычислительная эффективность: предоставлен метод построения доверительных границ непосредственно из реализованных потерь, вычислительно эффективный и избегающий дорогостоящей вспомогательной оптимизации
3. Теоретический анализ: производительность метаалгоритма оценивается на основе индивидуальных скоростей сходимости экспертов; при сожалении эксперта Õ(n^α) общее сожаление составляет Õ(√(KT/M) + (K/M)^(1-α)T^α)
4. Расширение на многоигровые бандиты: доказано, что M-LCB расширяется на постановку многоигровых бандитов

Детальное описание метода

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

• Пространство решений U: пространство рекомендаций экспертов
• Пространство окружения E: пространство стохастических исходов
• Функция потерь: ℓ : U×E → R₊
• Спецификация эксперта: каждый эксперт k задаётся кортежем (Wₖ,Hₖ,Aₖ,gₖ,υₖ)
  • Wₖ: пространство состояний/параметров
  • Hₖ: пространство истории
  • Aₖ: алгоритм онлайн-обучения
  • gₖ: отображение состояния в рекомендацию
  • υₖ: генератор безопасной рекомендации

Протокол выполнения

Выполнение на раунде t:

1. Метапрограмма выбирает советника iₜ∈K и подмножество обучения Sₜ⊆K, удовлетворяющие |Sₜ|≤M и iₜ∈Sₜ
2. Эксперт iₜ предоставляет безопасную рекомендацию uₜ = υᵢₜ(Hᵢₜᵗ)∈U
3. Окружение выбирает ξᵗ～D, программа несёт потери ℓ(uₜ,ξᵗ)
4. Эксперты k∈Sₜ обновляют историю и внутреннее состояние

Ядро алгоритма M-LCB

Определение доверительных границ

Для эксперта k определяются:

• Нормализованные накопленные потери: LAₖ(t) = (1/nₖᵗ)∑_{τ∈Iₖ(t)} ℓₖᵗ(wₖᵗ)
• Нижняя доверительная граница: LCBₖ(t,δ) = LAₖ(t) - Uₖ(nₖᵗ,δₐᵣₘ)/nₖᵗ - G(nₖᵗ,δₙᵗ)
• Верхняя доверительная граница: UCBₖ(t,δ) = LAₖ(t) + H(nₖᵗ,δₙᵗ)

Где:

• δₐᵣₘ = δ/(2K), δₙ = δ/(7Kn²)
• G(n,δ) = √(2log(1/δ)/n) + 2log(1/δ)/(3n)
• H(n,δ) = √(2log(1/δ)/n)

Стратегия выбора

• Выбор набора обучения: Sₜ := argmin_{S⊆K,|S|≤M} ∑_{k∈S} LCBₖ(t,δ)
• Выбор советника: iₜ := argmin_{k∈Sₜ} UCBₖ(t,δ)

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

1. Прямое построение доверительных границ: построение непосредственно из реализованных потерь без дополнительной оптимизации
2. Адаптивное управление экспертами: одновременный учёт выбора экспертов и распределения бюджета обучения
3. Гарантии в любой момент времени: обеспечение границ сожаления для всех временных шагов T
4. Гибкая структура: поддержка различных типов алгоритмов обучения в качестве экспертов

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

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

Статья в основном проводит синтетические эксперименты:

Выбор обобщённых линейных моделей

• Количество экспертов: K=10 обобщённых линейных моделей
• Размерность признаков: векторы признаков равномерно выбираются из единичной сферы Sᵈ⁻¹
• Сложная постановка: функции f₇,f₈,f₉ высоко похожи в областях с высокой плотностью данных, увеличивая сложность исследования

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

1. Накопленные потери: ∑ᵗ₌₁ᵀ ℓ(uᵗ,ξᵗ)
2. Распределение выбора рук: окончательная частота выбора каждого эксперта
3. Распределение вычислительного бюджета: распределение количества обновлений, полученных каждым экспертом

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

1. ED2RB: алгоритм с гарантиями обучаемых рук
2. LimitedAdvice: алгоритм экспертов, способный обрабатывать обновления нескольких рук на раунде

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

• Ограничения обновления: M∈{1,2,3}
• Количество повторений: 30 независимых запусков для усреднения
• Доверительные интервалы: показаны ±0.5 стандартного отклонения
• Настройка гиперпараметров: параметр исследования ED2RB c=0.1, масштабирование члена концентрации M-FLCB 0.3

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

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

1. Производительность сходимости: M-LCB достигает сублинейного сожаления, конкурентоспособного с базовыми методами
2. Идентификация экспертов: успешная идентификация оптимального эксперта (k=9)
3. Эффективность бюджета: основное распределение обновлений среди высокопроизводительных экспертов, в то время как LimitedAdvice распределяет более равномерно

Теоретические результаты

Теорема верхней границы

Теорема 2: Пусть α,δ∈(0,1), предположим, что каждый эксперт k удовлетворяет Uₖ(t,δ)=O(t^α c(δ)), тогда с вероятностью не менее 1-δ сожаление алгоритма 1 ограничено для всех T≥1:

Reg(T) = O(√(KT/M)log(KT/δ) + (K/M)^(1-α)T^α c(δ))

Теорема нижней границы

Теорема 1: Существуют константы c₁,c₂>0 такие, что для любого алгоритма обучения и метапрограммы:

sup EReg(T) ≥ c₁√(KT/M) + c₂T^α(K/M)^(1-α)

Это показывает, что M-LCB оптимален с точностью до логарифмических множителей.

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

Самообучающиеся эксперты (руки)

• 6: введение самообучающихся рук в постановке MAB, где каждая рука является параметризованной функцией, параметры которой обновляются при выборе

Метауровневый выбор модели

• CORRAL8: управление пулом алгоритмов бандитов через зеркальный спуск с логарифмическим барьером с обратной связью по важности
• Динамическая балансировка9: метаалгоритм на основе известных выражений скорости сожаления, обновляющий только одного обучающегося на раунде
• 10: онлайн-оценка коэффициентов для каждого обучающегося, получение высокой вероятности зависимых от данных гарантий для стохастических бандитов

MAB с обновлениями нескольких рук

• LimitedAdvice12: запрос не более M рук, получение границы сожаления Õ(√(KT logK/M))
• 13: минимаксное оптимальное сожаление Õ(max{√(KT/M), √(T logK)})

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

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

1. Впервые установлены гарантии сожаления для одновременного обучения нескольких адаптивных экспертов при ограничениях бюджета на каждом раунде
2. Алгоритм M-LCB достигает минимаксной оптимальности с точностью до логарифмических множителей
3. Структура объединяет онлайн-оптимизацию и постановку стохастических бандитов

Ограничения

1. Известное масштабирование доверия: анализ предполагает, что функция масштабирования доверия c(δ) известна
2. Предположение об ограниченных потерях: основное внимание уделяется случаю ограниченных потерь
3. Стохастическая постановка: анализ в основном проводится в стохастической среде; противоборствующая постановка требует дальнейшего исследования

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

1. Случай неизвестного c(δ): как в работе Pacchiano и др.11
2. Расширение дополнительными наблюдениями: расширение на ограниченные советы и многоигровые бандиты
3. Контекстный режим: расширение на случаи, когда эксперты специализируются на основе наблюдаемых признаков

Углубленная оценка

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

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

Недостатки

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

Влияние

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

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

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

Библиография

Статья ссылается на важные работы в областях многоруких бандитов, онлайн-обучения, алгоритмов экспертов, в частности:

• Классический алгоритм UCB Ауэра и др.1
• Теория алгоритмов экспертов Чеза-Бьянки и Лугози4
• Онлайн-выпуклая оптимизация Хазана5
• Современные метаалгоритмы обучения, такие как CORRAL8

Общая оценка: Это высококачественная теоретическая работа, вносящая значительный вклад в важную, но ранее недостаточно изученную проблему обучения экспертов при ограничениях бюджета. Дизайн алгоритма остроумен, теоретический анализ строг, что создаёт прочную основу для дальнейшего развития в этой области.