- Одновременное изучение стохастических и состязательных бандитов с общей обратной связью по графику (arXiv)
Автор: Фанг Конг, Ичи Чжоу, Шуай Ли.
Аннотация: Проблема онлайн-обучения с графической обратной связью широко изучалась в литературе из-за ее общности и возможности моделирования различных учебных задач. Существующие работы в основном изучают состязательную и стохастическую обратную связь по отдельности. Если предварительные знания о механизме обратной связи недоступны или неверны, такие специально разработанные алгоритмы могут понести большие потери. Чтобы избежать этой проблемы, \citet{erez2021towards} попытайтесь оптимизировать для обеих сред. Однако они предполагают, что графы с обратной связью неориентированы, и каждая вершина имеет петлю, что ставит под угрозу универсальность структуры и может не удовлетворяться в приложениях. При использовании общего графика обратной связи наблюдение за рукой может быть недоступно, когда эта рука тянется, что делает исследование более дорогим, а алгоритмы более сложными для оптимальной работы в обеих средах. В этой работе мы преодолеваем эту трудность с помощью нового компромиссного механизма с тщательно разработанной пропорцией для разведки и эксплуатации. Мы доказываем, что предложенный алгоритм одновременно достигает полилогарифмического сожаления в стохастической обстановке и минимаксно-оптимального сожаления O~(T2/3) в состязательной обстановке, где T — это горизонт, а O~ скрывает параметры, не зависящие от T, а также логарифмические члены. Насколько нам известно, это первый лучший из двух миров результат для общих графиков обратной связи. △
2. Онлайн-метаобучение в Adversarial Multi-Armed Bandits (arXiv)
Автор : Илья Осадчий, Кфир Ю. Леви, Рон Меир
Аннотация: Мы изучаем метаобучение для враждебных многоруких бандитов. Мы рассматриваем установку «онлайн в онлайне», в которой игрок (учащийся) сталкивается с последовательностью эпизодов многорукого бандита. Производительность игрока измеряется как сожаление по отношению к лучшей руке в каждом эпизоде в соответствии с потерями, понесенными противником. Сложность задачи зависит от эмпирического распределения лучшей руки для каждого эпизода, выбранной противником. Мы представляем алгоритм, который может использовать неравномерность в этом эмпирическом распределении и получить границы сожаления в зависимости от проблемы. Это решение включает в себя внутренний обучаемый модуль, который воспроизводит каждый эпизод отдельно, и внешний обучаемый модуль, который обновляет гиперпараметры внутреннего алгоритма между эпизодами. В случае, когда наилучшее распределение рук далеко от равномерного, оно улучшает наилучшую оценку, которая может быть достигнута любым онлайн-алгоритмом, выполняемым для каждого эпизода отдельно без метаобучения.
