- О дифференциально частных федеративных линейных контекстных бандитах (arXiv)
Автор: Синью Чжоу, Саяк Рэй Чоудхури.
Аннотация: Мы рассматриваем проблему межсистемного федеративного линейного контекстуального бандита (LCB) в условиях дифференциальной конфиденциальности. В этом случае несколько разрозненных хранилищ или агентов взаимодействуют с локальными пользователями и обмениваются данными через центральный сервер, чтобы реализовать совместную работу, не жертвуя при этом конфиденциальностью каждого пользователя. Мы выявили две проблемы в современном алгоритме \cite{dubey2020 Differentially}: (i) отказ от заявленной защиты конфиденциальности и (ii) просчет шума в связи с сожалением. Для решения этих проблем мы используем двухэтапный принципиальный подход. Во-первых, мы разрабатываем алгоритмическую структуру, состоящую из общего федеративного алгоритма LCB и гибких протоколов конфиденциальности. Затем, используя предложенную структуру, мы изучаем федеративные LCB при двух разных ограничениях конфиденциальности. Сначала мы устанавливаем гарантии конфиденциальности и сожаления в рамках локальной дифференциальной конфиденциальности на изолированном уровне, которые устраняют проблемы, присутствующие в современном алгоритме. Чтобы еще больше улучшить производительность сожаления, мы затем рассмотрим модель дифференциальной конфиденциальности в случайном порядке, в рамках которой мы покажем, что наш алгоритм может достичь почти «оптимального» сожаления без доверенного сервера. Мы достигаем этого с помощью двух разных схем: одна опирается на новый результат усиления конфиденциальности за счет перетасовки для механизмов DP, а другая использует интеграцию протокола перетасовки для векторной суммы в древовидный механизм, обе из которых могут представлять независимый интерес. . Наконец, мы подкрепляем наши теоретические результаты числовыми оценками контекстуальных случаев бандитов, полученных как из синтетических, так и из реальных данных.
2. Оценка оптимальной ценности политики в общих линейных контекстных бандитах (arXiv)
Автор: Джонатан Н. Ли, Вейхао Конг, Альдо Паккиано, Видья Мутукумар, Эмма Бранскилл.
Аннотация: Во многих бандитских задачах максимальное вознаграждение, достижимое политикой, часто заранее неизвестно. Мы рассматриваем проблему оценки оптимального значения политики в сублинейном режиме данных еще до того, как оптимальную политику можно будет изучить. Мы называем это оценкой V∗. Недавно было показано, что быстрая оценка V∗ возможна, но только в непересекающихся линейных бандитах с гауссовскими ковариатами. Возможно ли это для более реалистичного распределения контекста, остается открытым и важным вопросом для таких задач, как выбор модели. В этой статье мы сначала даем нижние оценки, показывающие сложность этой общей проблемы. Однако при более сильных предположениях мы приводим алгоритм и анализ, доказывающие, что сублинейная оценка O˜(d−−√) V∗ действительно возможна с теоретической точки зрения, где d — размерность. Затем мы представляем более практичный и эффективный в вычислительном отношении алгоритм, который оценивает зависящую от задачи верхнюю границу V∗, которая выполняется для общих распределений и является точной, когда распределение контекста является гауссовым. Мы доказываем, что наш алгоритм требует только O˜(d−−√) отсчетов для оценки верхней границы. Мы используем эту верхнюю границу и оценщик, чтобы получить новые и улучшенные гарантии для нескольких приложений при выборе бандитской модели и тестировании эффектов лечения.
