Бандиты и эксперты в метрических пространствах

В задаче многорукого бандита онлайн-алгоритм на последовательности испытаний выбирает стратегии из заданного множества, чтобы максимизировать суммарный выигрыш выбранных стратегий. Хотя эффективность бандитских алгоритмов при малом конечном множестве стратегий хорошо изучена, задачи многорукого бандита с большими множествами стратегий по-прежнему являются предметом активных исследований, чему способствуют практические приложения, такие как онлайн-аукционы и интернет-реклама. Цель таких исследований состоит в выявлении широких и естественных классов множеств стратегий и функций выигрыша, для которых возможно разработать эффективные решения. В данной работе мы рассматриваем общую постановку задачи многорукого бандита, в которой стратегии образуют метрическое пространство, а функция выигрыша удовлетворяет условию Липшица относительно метрики. Мы называем эту задачу липшицевой задачей многорукого бандита (Lipschitz MAB). Мы предлагаем решение задачи многорукого бандита в данной постановке. Для каждого метрического пространства мы определяем инвариант изометрии, задающий нижнюю границу эффективности липшицевых алгоритмов многорукого бандита для этого метрического пространства, и представляем алгоритм, эффективность которого может сколь угодно близко приближаться к этой границе. Кроме того, наш метод дает еще лучшие результаты для благоприятных функций выигрыша. Мы также рассматриваем версию задачи с полной обратной связью ("лучший эксперт"), в которой после каждого раунда раскрываются выигрыши всех рук.