- Выбор модели в любое время в Linear Bandits (arXiv)
Автор: Парниан Кассраи, Альдо Паккиано, Николас Эмменеггер, Андреас Краузе.
Аннотация: Выбор модели в контексте бандитской оптимизации является сложной проблемой, поскольку требует баланса между разведкой и эксплуатацией не только для выбора действий, но и для выбора модели. Один из естественных подходов — полагаться на алгоритмы онлайн-обучения, которые рассматривают разные модели как экспертов. Существующие методы, однако, плохо масштабируются (полиМ) с количеством моделей М с точки зрения их сожаления. Наше ключевое понимание заключается в том, что для выбора модели в линейных бандитах мы можем эмулировать обратную связь с полной информацией для онлайн-учащегося с благоприятным компромиссом между смещением и дисперсией. Это позволяет нам разработать ALEXP, который имеет экспоненциально улучшенную (logM) зависимость от M для своего сожаления. ALEXP всегда дает гарантии на свое сожаление, не требует знания горизонта n и не полагается на начальный чисто исследовательский этап. В нашем подходе используется новый однородный по времени анализ Лассо, устанавливающий новую связь между онлайн-обучением и многомерной статистикой.
2. Подходы с учетом геометрии для балансировки производительности и теоретических гарантий в Linear Bandits (arXiv)
Автор: Ювэй Луо, Мохсен Баяти.
Аннотация: Эта статья мотивирована недавними разработками в литературе по линейным бандитам, которые выявили несоответствие между многообещающими эмпирическими характеристиками алгоритмов, таких как выборка Томпсона и Жадность, по сравнению с их пессимистическими теоретическими границами сожаления. Проблема возникает из-за того, что, хотя эти алгоритмы могут плохо работать в определенных случаях, в типичных случаях они превосходны. Чтобы решить эту проблему, мы предлагаем новый метод, основанный на данных, который отслеживает геометрию эллипсоида неопределенности, позволяя нам установить зависящее от экземпляра частотное сожаление, ограниченное для широкого класса алгоритмов, включая выборку Greedy, OFUL и Томпсона. Этот результат позволяет нам идентифицировать и «корректировать» случаи, когда базовые алгоритмы работают плохо. Алгоритмы коррекции курса обеспечивают минимаксное оптимальное сожаление порядка O~(dT−−√), сохраняя при этом большинство желательных свойств базовых алгоритмов. Мы представляем результаты моделирования, чтобы подтвердить наши выводы и сравнить производительность наших алгоритмов с базовыми показателями.
