Случайный, Эпсилон-жадный, бандит UCB
Многорукий бандит — это задача выбора между альтернативными вариантами с неизвестными наградами, попытка максимизировать ожидаемую награду и одновременно изучить ее. вики-статья.
Весь блокнот доступен здесь
Мы создадим простую среду для моделирования таких проблем и попробуем несколько стратегий для их решения.
База
- Настроить библиотеку
- Реализуйте класс для генерации вознаграждений за каждое действие, предпринятое решателем.
- Реализуйте базовый класс для различных средств решения проблем
- Напишите функцию, которая помещает наш решатель в среду
Случайный
Давайте попробуем простой решатель, который просто выбирает действие случайным образом.
Для случайного бандита средняя награда как функция времени — это просто случайное блуждание: он вообще не использует предыдущий опыт.
Эпсилон-жадный
Вместо чистой случайности мы можем запрограммировать так называемый epsilon-greedy
решатель: с вероятностью 𝜀 он исследует (выполняет случайное однородное действие) и с вероятностью 1−𝜀 использует: выбирает действие с наилучшей средней наградой в соответствии с его историей .
Теперь мы можем посмотреть, как работают различные значения ε.
Вы можете видеть, что, когда ε слишком велико, среднее вознаграждение сходится к меньшему значению, потому что доля случайных действий высока.
А если ε слишком мало, решатель слишком рано придерживается неоптимального действия и улучшается очень медленно.
УКБ бандит
Мы можем еще больше улучшить наш решатель, заставив его выбирать на каждом шаге действие с максимально возможной верхней доверительной границей среднего вознаграждения.
Один из простых способов аппроксимировать верхнюю доверительную границу для среднего — добавить несколько стандартных отклонений выборочного среднего к выборочному среднему — как в нормальном распределении (к которому рано или поздно сходится распределение выборочного среднего):
Здесь 𝑚 — это просто некоторый множитель, отражающий степень исследования, которое мы собираемся провести. Чем выше этот множитель, тем больше будет склонность пробовать действия с маленьким 𝑛 и высоким 𝜎̂. То есть самые неопределенные действия.
Теперь мы можем попробовать, как работает наша стратегия с разными мультипликаторами.
Кажется, что очень маленького множителя уже достаточно, чтобы достаточно хорошо изучить все варианты и быстро сойтись к лучшему.
В блокноте есть бонусная часть
Следующий шаг: присоединяйтесь к Kaggle