Понимание алгоритма верхней доверительной границы (UCB)

Введение

В сфере принятия решений и оптимизации крайне важно найти правильный баланс между разведкой и эксплуатацией. В ситуациях, когда мы сталкиваемся с неопределенной средой или ограниченными ресурсами, первостепенное значение приобретает осознанный выбор. Именно здесь алгоритм верхней доверительной границы (UCB) становится ценным инструментом. UCB — популярный метод, используемый в задачах о многоруких бандитах и ​​обучении с подкреплением. В этой статье мы углубимся в концепцию UCB, изучим ее работу и поймем ее значение для оптимизации процессов принятия решений.

Понимание проблем многорукого бандита

Прежде чем погрузиться в UCB, давайте сначала разберемся с концепцией проблем с многорукими бандитами. Представьте, что вы в казино столкнулись с несколькими игровыми автоматами (или «однорукими бандитами»). Каждая машина имеет неизвестное распределение выплат, и ваша цель — максимизировать общий выигрыш в серии испытаний. Задача состоит в том, чтобы сбалансировать ваше исследование различных машин для сбора информации об их выплатах и ​​использование вами машин, которые до сих пор показывали многообещающие результаты. Эта дилемма разведки и эксплуатации лежит в основе проблем многоруких бандитов.

Разведка против эксплуатации

В контексте проблем с многорукими бандитами под исследованием понимается опробование различных вариантов сбора информации об их наградах. Эксплуатация, с другой стороны, предполагает максимизацию вознаграждения, основанного на знаниях, полученных в результате исследования. Нахождение правильного баланса между этими двумя противоречащими друг другу целями необходимо для оптимизации процесса принятия решений.

Введение в алгоритм верхней доверительной границы (UCB)

Алгоритм UCB обеспечивает системный подход к решению задач о многоруких бандитах. Он достигает баланса между исследованием и эксплуатацией, назначая границы достоверности для каждой руки (например, игрового автомата) на основе наблюдаемых вознаграждений. Основная идея состоит в том, чтобы оценить верхнюю доверительную границу для каждой руки, которая представляет неопределенность в оценке ее истинного значения вознаграждения.

Алгоритм UCB работает в итерациях. В каждой итерации он выбирает руку с самой высокой верхней доверительной границей, которая соответствует самой высокой неопределенности или потенциалу для высоких вознаграждений. По мере продвижения алгоритма и сбора большего количества информации доверительные границы становятся уже, что приводит к более обоснованным решениям. Со временем UCB приближается к ветви с наивысшим ожидаемым вознаграждением, эффективно обеспечивая баланс между разведкой и эксплуатацией.

Математическая формулировка UCB

Давайте рассмотрим упрощенную версию алгоритма UCB, известную как UCB1. В этой формулировке выбор оружия основан на следующем уравнении:

UCB1 = среднее вознаграждение + срок исследования

Среднее вознаграждение представляет собой среднее наблюдаемое вознаграждение за конкретную руку, в то время как срок исследования количественно определяет уровень неопределенности, связанный с этой рукой. Период разведки обычно рассчитывается с использованием формулы доверительного интервала, такой как неравенство Хёффдинга или граница Чернова-Хёффдинга. Эти формулы учитывают количество раз, когда рука была сыграна, и общее количество итераций.

Пошаговый подход к алгоритму верхней доверительной границы (UCB):

Шаг 1. Инициализация

  • Начните с инициализации количества рук (или опций), доступных в вашей задаче.
  • Инициализируйте переменные и структуры данных, необходимые для отслеживания вознаграждений и игр для каждой руки.

Шаг 2. Этап исследования

  • Сыграйте каждую руку один раз, чтобы собрать исходные данные.
  • Обновите вознаграждение и количество игр для каждой руки на основе наблюдаемых результатов.

Шаг 3. Основной цикл

  • Введите цикл, который повторяется в течение предопределенного количества итераций или до тех пор, пока не будет выполнен критерий остановки.
  • Для каждой итерации:
  • Вычислите верхнюю доверительную границу (UCB) для каждой руки, используя формулу доверительного интервала.
  • Выберите руку с самым высоким значением UCB.
  • Сыграйте в выбранную руку и наблюдайте за наградой.
  • Обновите награду и количество игр для выбранной руки.
  • Обновите любую другую соответствующую статистику или переменные.

Шаг 4. Этап эксплуатации

  • После начальной фазы исследования перейдите к использованию руки с самой высокой ожидаемой наградой.
  • Продолжайте играть в руку с самой высокой предполагаемой наградой и обновляйте соответствующую статистику.

Шаг 5. Повторите шаги 3 и 4

  • Продолжайте повторять шаги 3 и 4, пока не будет достигнуто желаемое количество итераций или не будет удовлетворен критерий остановки.

Шаг 6. Окончательное решение

  • После завершения желаемого количества итераций примите окончательное решение на основе руки с самым высоким накопленным вознаграждением или руки, которая, скорее всего, будет иметь самое высокое ожидаемое вознаграждение.

Важно отметить, что существуют различные варианты алгоритма UCB, такие как UCB1, UCB2 и UCB-Tuned, каждый из которых имеет немного разные формулы и подходы для вычисления верхних доверительных границ. Конкретная используемая формула может зависеть от рассматриваемой проблемы и предположений о распределении вознаграждения.

Кроме того, выбор формулы доверительного интервала и параметры компромисса между разведкой и эксплуатацией могут повлиять на производительность алгоритма. Чтобы найти оптимальные настройки для вашей конкретной проблемы, могут потребоваться эксперименты и настройка.

Следуя этому пошаговому подходу, вы сможете внедрить алгоритм UCB, чтобы эффективно сбалансировать разведку и эксплуатацию, что позволит вам принимать обоснованные решения в условиях неопределенности.

Шаблон кода



Upper_Confidence_Bound.ipynb
Этот репозиторий Github представляет собой всеобъемлющий ресурс для ежедневного изучения основ машинного обучения. Он включает…github.com



Набор данных



Ads_CTR_Optimisation.csv
Этот репозиторий Github представляет собой исчерпывающий ресурс для ежедневного изучения основ машинного обучения. Он включает…github.com



Преимущества и области применения UCB

Алгоритм UCB предлагает несколько преимуществ и находит применение в различных областях:

  1. Простота. UCB — это простой алгоритм, который легко реализовать и понять, что делает его популярным среди многих исследователей и практиков.
  2. Компромисс между разведкой и добычей. UCB предлагает эффективный способ найти компромисс между разведкой и добычей, позволяя лицам, принимающим решения, делать оптимальный выбор и получать ценную информацию.
  3. Проблемы с бандитами:UCB широко используется для решения задач с многорукими бандитами, где он продемонстрировал превосходную эффективность в максимизации совокупных вознаграждений с течением времени.
  4. Интернет-реклама. UCB нашел применение в онлайн-рекламе, где он помогает выбирать наиболее перспективные варианты рекламы для показа пользователям на основе их предполагаемого рейтинга кликов.

Заключение

Алгоритм верхней доверительной границы (UCB) устанавливает баланс между разведкой и эксплуатацией, позволяя лицам, принимающим решения, делать осознанный выбор в условиях неопределенности и ограниченности ресурсов. Назначая границы достоверности для различных вариантов, UCB оптимизирует процессы принятия решений и максимизирует совокупное вознаграждение с течением времени. Его простота, универсальность и эффективность делают его ценным инструментом в различных областях, включая проблемы с многорукими бандитами и интернет-рекламу. Поскольку область принятия решений и оптимизации продолжает развиваться, UCB остается мощной техникой для решения компромиссов между разведкой и эксплуатацией.