Случайный, Эпсилон-жадный, бандит UCB

Многорукий бандит — это задача выбора между альтернативными вариантами с неизвестными наградами, попытка максимизировать ожидаемую награду и одновременно изучить ее. вики-статья.

Весь блокнот доступен здесь

Мы создадим простую среду для моделирования таких проблем и попробуем несколько стратегий для их решения.

База

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

Случайный

Давайте попробуем простой решатель, который просто выбирает действие случайным образом.

Для случайного бандита средняя награда как функция времени — это просто случайное блуждание: он вообще не использует предыдущий опыт.

Эпсилон-жадный

Вместо чистой случайности мы можем запрограммировать так называемый epsilon-greedy решатель: с вероятностью 𝜀 он исследует (выполняет случайное однородное действие) и с вероятностью 1−𝜀 использует: выбирает действие с наилучшей средней наградой в соответствии с его историей .

Теперь мы можем посмотреть, как работают различные значения ε.
Вы можете видеть, что, когда ε слишком велико, среднее вознаграждение сходится к меньшему значению, потому что доля случайных действий высока.
А если ε слишком мало, решатель слишком рано придерживается неоптимального действия и улучшается очень медленно.

УКБ бандит

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

Один из простых способов аппроксимировать верхнюю доверительную границу для среднего — добавить несколько стандартных отклонений выборочного среднего к выборочному среднему — как в нормальном распределении (к которому рано или поздно сходится распределение выборочного среднего):

Здесь 𝑚 — это просто некоторый множитель, отражающий степень исследования, которое мы собираемся провести. Чем выше этот множитель, тем больше будет склонность пробовать действия с маленьким 𝑛 и высоким 𝜎̂. То есть самые неопределенные действия.

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

В блокноте есть бонусная часть

Следующий шаг: присоединяйтесь к Kaggle