Многорукие бандиты присутствуют во всех областях машинного обучения.
Недавно я запустил образовательный информационный бюллетень, посвященный ИИ, у которого уже более 150 000 подписчиков. TheSequence — это информационный бюллетень, ориентированный на машинное обучение, без BS (то есть без шумихи, без новостей и т. д.), чтение которого занимает 5 минут. Цель состоит в том, чтобы держать вас в курсе проектов машинного обучения, научных работ и концепций. Пожалуйста, попробуйте, подписавшись ниже:
В вычислительных приложениях часто возникает необходимость принимать решения в режиме реального времени для обслуживания входящих запросов с определенным уровнем неопределенности. Например, навигационное приложение должно реагировать на запросы водителя, определяя лучший маршрут. На удовлетворенность водителя влияют неизвестные факторы, такие как загруженность дорог и предпочтения водителя в отношении различных особенностей маршрута. Онлайн-машинное обучение имеет дело с такими настройками и предлагает различные методы принятия решений в условиях неопределенности. В недавней статье Google Research представлена новая техника, применимая к сценариям такого типа.
Хорошо известной проблемой в этой области является проблема многорукого бандита. Он включает в себя выбор из набора опций (рук) в каждом раунде, чтобы обеспечить наилучшее удовлетворение пользователя. Удовлетворение пользователя измеряется вознаграждением, которое зависит от различных неизвестных факторов. Производительность алгоритма за N раундов сравнивается с лучшим фиксированным действием задним числом с использованием сожаления, которое представляет собой разницу между вознаграждением за лучшую руку и вознаграждением, полученным алгоритмом за N раундов.
В своей статье Google показывает, как модель машинного обучения, которая дает слабую подсказку, может значительно улучшить производительность алгоритма в бандитских условиях. Модели с машинным обучением могут быть точно обучены с соответствующими прошлыми данными, такими как задержки на участках дороги, отзывы пользователей и т. д. Однако авторы добиваются надежных гарантий, даже когда обратная связь от модели представлена в виде слабой подсказки, например, вопроса. модель, предсказывающая, какой из двух вариантов лучше.
Многие методы, использованные в статье Google, хорошо зарекомендовали себя в течение многих лет. Например, алгоритм настройки бандитов использует хорошо известный алгоритм верхней доверительной границы (UCB). Алгоритм UCB отслеживает среднее вознаграждение, наблюдаемое в каждой руке, и добавил параметр оптимизма, который уменьшается с увеличением количества раз, когда рука была потянута, уравновешивая исследование и эксплуатацию. Авторы применяют баллы UCB к парам рук и группируют каждую пару как мета-руку, вознаграждение которой в каждом раунде равно максимальному вознаграждению между двумя руками. Алгоритм выбирает метаруку с наивысшим баллом и передает ее в качестве запроса вспомогательной модели парного прогнозирования ML, которая отвечает лучшим из двух ветвей.
Еще один важный аспект алгоритма для настройки экспертов заключается в том, что он использует подход «Следуй за регуляризованным лидером» (FtRL). Он использует регуляризованный алгоритм лидера для определения лучшего эксперта, добавляя термин исследования, который уравновешивает исследование и эксплуатацию. Алгоритм начинает с инициализации оценки каждого эксперта до 0. В каждом раунде алгоритм выбирает эксперта с наивысшей оценкой и обновляет оценку всех экспертов на основе наблюдаемых вознаграждений. Алгоритм завершается после T раундов, и окончательная оценка каждого эксперта сравнивается с лучшим экспертом в ретроспективе.
В начальном наборе тестов алгоритмы Google демонстрируют важные улучшения с точки зрения теоретических гарантий. При сравнении со стандартным базовым уровнем UCB мы видим, как алгоритм Google быстро определяет лучшую руку и продолжает играть, в то время как внешний алгоритм UCB продолжает накапливать сожаление.
Исследования Google по-прежнему в основном теоретические, но могут иметь серьезные последствия в таких условиях, как проблемы с экспертами и бандитами, которые вездесущи в сценариях ML в реальном мире.
