- Ближайший сосед с Bandit Feedback (arXiv)
Автор: Стивен Пастерис, Крис Хикс, Василиос Маврудис.
Аннотация: В этой статье мы адаптируем правило ближайшего соседа к контекстуальной проблеме бандита. Наш алгоритм обрабатывает полностью состязательную среду, в которой вообще не делается никаких предположений о процессе генерации данных. В сочетании с достаточно быстрой структурой данных для (возможно, приблизительного) адаптивного поиска ближайшего соседа, например, с навигационной сетью, наш алгоритм чрезвычайно эффективен — время выполнения за попытку полилогарифмическое как по количеству попыток, так и по количеству действий, и он принимает только квазилинейное пространство.
2. Логарифмическое сожаление для матричных игр против противника с шумной бандитской обратной связью (arXiv)
Автор: Арнаб Маити, Кевин Джеймисон, Лилиан Дж. Рэтлифф.
Аннотация: В этой статье рассматривается вариант матричных игр с нулевой суммой, где на каждом временном шаге игрок в строке выбирает строку i, игрок в столбце выбирает столбец j, а игрок в строке получает зашумленное вознаграждение со средним значением Ai,j. Цель рядового игрока состоит в том, чтобы накопить как можно больше наград, даже против враждебного игрока из столбца. Если игрок в ряд использует стратегию EXP3, алгоритм, известный для получения сожаления T−−√ против произвольной последовательности вознаграждений, игрок в ряду сразу же достигает сожаления T−−√ по отношению к равновесию Нэша в этой игровой настройке. Однако отчасти из-за того, что стратегия EXP3 близорука по отношению к структуре игры, О'Донохью и др. (2021) предложил алгоритм в стиле UCB, который использует структуру игры, и продемонстрировал, что этот алгоритм значительно превосходит EXP3 эмпирически. Хотя они показали, что этот алгоритм в стиле UCB достигает T−−√ сожаления, в этой статье мы спрашиваем, существует ли алгоритм, который доказуемо достигает полилогарифмического (T) сожаления против любого противника, аналогично результатам стохастических бандитов. Мы предлагаем новый алгоритм, который дает положительный ответ на этот вопрос для простой настройки 2×2, предоставляя гарантии, зависящие от первого экземпляра, для игр в настройке сожаления. Наш алгоритм преодолевает два основных препятствия: 1) получение логарифмического сожаления, несмотря на то, что равновесие Нэша оценивается только с точностью 1/T−−√, и 2) разработка стратегий игроков в ряд, которые гарантируют, что любой из противников предоставит информацию о равновесии Нэша. , или игрок-рядник получает негативное сожаление. Кроме того, в случае полной информации мы обращаемся к общему случаю n×m, где первое препятствие все еще актуально. Наконец, мы показываем, что EXP3 и алгоритм на основе UCB обязательно не могут работать лучше, чем T−−√
