Начало работы со стохастическими линейными бандитами
- Дифференциально приватные стохастические линейные бандиты: (почти) бесплатно(arXiv)
Автор: Усама А. Ханна, Антониус М. Гиргис, Кристина Фрагули, Сухас Диггави
Аннотация: В этой статье мы предлагаем дифференциально частные алгоритмы для задачи о стохастических линейных бандитах в центральной, локальной и перетасованной моделях. В центральной модели мы достигаем почти того же сожаления, что и оптимальные не приватные алгоритмы, а значит, приватность получаем бесплатно. В частности, мы получаем сожаление O~(T−−√+1ε), соответствующее известной нижней границе для частных линейных бандитов, в то время как лучший ранее известный алгоритм достигает O~(1εT−−√). В локальном случае мы получаем сожаление в размере O~(1εT−−√), которое соответствует нечастному сожалению для постоянного ε, но подвергается штрафу за сожаление, когда ε мало. В модели с перетасовкой мы также достигаем сожаления O~(T−−√+1ε) % для малых ε, как и в центральном случае, в то время как лучший ранее известный алгоритм страдает сожалением O~(1εT3/5). Наша численная оценка подтверждает наши теоретические результаты.
2. Совместные многоагентные стохастические линейные бандиты(arXiv)
Автор: Ахмадреза Морадипари, Мохаммад Гавамзаде, Махнуш Ализаде
Аннотация: мы изучаем совместную многоагентную стохастическую линейную бандитскую настройку, в которой N агентов, образующих сеть, взаимодействуют локально, чтобы свести к минимуму их общее сожаление. В этом сеттинге у каждого агента есть своя линейная бандитская задача (свой параметр вознаграждения), и цель состоит в том, чтобы выбрать наилучшее глобальное действие по сравнению с другими агентами. среднее значение их параметров вознаграждения. В каждом раунде каждый агент предлагает действие, и одно действие выбирается случайным образом и разыгрывается как сетевое действие. Все агенты наблюдают соответствующие вознаграждения за сыгранные действия и используют ускоренную процедуру консенсуса для вычисления оценки среднего вознаграждения, полученного всеми агентами. Мы предлагаем алгоритм распределенной верхней доверительной границы (UCB) и доказываем высокую вероятность его сожаления в T-раунде, в которое мы включаем линейный рост сожаления, связанный с каждым раундом связи. Наша граница сожаления имеет порядок O(TNlog(1/|λ2|)−−−−−−−−√⋅(logT)2), где λ2 — второе по величине (по модулю) собственное значение матрицы связи.
3. Бесплатное использование начальных подсказок в Stochastic Linear Bandits(arXiv)
Автор: Ашок Каткоски, Крис Данн, Абхиманью Дас, Цюи, Чжан
Аннотация: мы изучаем настройку оптимизации с бандитской обратной связью с дополнительными предварительными знаниями, предоставляемыми учащемуся в виде начальной подсказки оптимального действия. Мы представляем новый алгоритм для стохастических линейных бандитов, который использует эту подсказку, чтобы улучшить свое сожаление до O~(T−−√), когда подсказка является точной, сохраняя при этом минимаксно-оптимальное сожаление O~(dT−−√), независимое от качество подсказки. Кроме того, мы предлагаем границу Парето для жестких компромиссов между сожалением в лучшем и худшем случаях с соответствующими нижними границами. Возможно, это покажется удивительным, но наша работа показывает, что использование подсказки дает доказуемый выигрыш без ущерба для производительности в худшем случае, что означает, что наш алгоритм бесплатно адаптируется к качеству подсказки. Мы также обеспечиваем расширение нашего алгоритма на случай m начальных подсказок, показывая, что мы можем достичь O~(m2/3T−−√) сожалений.
