Обновление до эпсилон-жадного алгоритма
В предыдущей статье я объяснил Эпсилон-Жадный Алгоритм и то, как он выигрывает от исследования разных бандитов достаточное количество раз, чтобы, наконец, определить оптимальный.
Однако вы, должно быть, заметили, что максимальное вознаграждение, которое модель (синяя линия) смогла получить, всегда немного меньше, чем оптимальное вознаграждение бандита (зеленая линия).
По иронии судьбы, это небольшое снижение общей ставки вознаграждения связано с фактором исследования, именно благодаря этому алгоритм работает так хорошо. Поскольку модель никогда не перестает исследовать в течение всего моделирования, всегда существует определенный шанс на каждой итерации, что модель пойдет на исследование, а не на эксплуатацию.
Хотя исследование может быть необходимо в начале моделирования, по мере сбора большего количества данных приоритет должен смещаться на использование собранных данных. Это один из способов сгладить небольшую разницу между общим коэффициентом выигрыша модели и наиболее оптимальным коэффициентом выигрыша бандита. Эта модификация называется Гниющий Эпсилон.
Вы можете обратиться к этой статье ниже для лучшего понимания, так как текущая статья основана на знаниях этой.
Итак, суть в том, что чрезмерная зависимость от фактора разведки (Эпсилон) увеличивает стоимость выбора неоптимальных бандитов несколько раз и, таким образом, дает несколько меньшие результаты, чем самый оптимальный бандит.
Итак, что, если мы можем исключить этот Эпсилон из уравнения, сохранив при этом возможность исследования в определенной степени?
Вот тут-то и появляются оптимистичные начальные ценности.
Оптимистичный подход к исходным значениям
Этот подход назван так потому, что, в отличие от Эпсилон-жадного алгоритма, мы начинаем с оптимизма в отношении винрейта бандитов и назначаем более высокий начальный винрейт. Иногда даже больше, чем реально возможно.
Что касается фактора исследования, вместо того, чтобы полагаться на Эпсилон, мы полагаемся на тот факт, что с каждой итерацией оптимистичные начальные винрейты будут продолжать падать до их фактических винрейтов. Основное внимание уделяется простому выбору бандита с самым высоким предполагаемым коэффициентом выигрыша во время этого процесса калибровки.
Это падение оценок винрейта достигнет точки, когда оценка винрейта всех субоптимальных бандитов упадет ниже оценки винрейта наиболее оптимального бандита.
Затем мы просто продолжаем выбирать этого оптимального бандита и максимизируем получаемые награды.
Демонстрация
Следующее поможет вам понять, почему это работает. У нас есть два игровых автомата (однорукие бандиты) Machine A и Machine B с фактическим коэффициентом выигрыша 25% и 75% соответственно. Помните, что, как и в случае с эпсилон-жадным алгоритмом, фактическая частота выигрышей неизвестна модели.
В соответствии с подходом оптимистичных начальных значений, скажем, мы назначаем начальный коэффициент выигрыша 200% для обеих машин. Обратите внимание, что максимально возможный винрейт равен 100%, а начальные значения винрейта, которые мы установили, никогда бы не были возможны.
Итерация 1
Поскольку оба игровых автомата имеют одинаковый процент выигрышей в начальном состоянии, мы выбираем один из них случайным образом.
Предположим, машина А была выбрана случайным образом, бандит дернул руку, но не получил сигнала вознаграждения.
Затем вычисляется оценка винрейта машины А, которая сохраняется в результатах.
Итерация 2
После итерации 1 машина Б имела более высокую оценку выигрыша, поэтому она была выбрана (жадный подход).
Бандиту выдернули руку и был получен сигнал о награде.
Оценка выигрыша машины B вычисляется и сохраняется в результатах.
Итерация 3
После итерации 2 у машины B была более высокая оценка выигрыша, поэтому она была выбрана.
Рука бандита была выдернута, и на этот раз сигнала о награде получено не было.
Оценка выигрыша машины B вычисляется и сохраняется в результатах.
Итерация 4
После итерации 3 обе машины имели одинаковые оценки винрейта, поэтому машина А была выбрана случайным образом.
Рука бандита была вытянута, а сигнала о награде получено не было.
Пересмотренная оценка винрейта машины А вычисляется и сохраняется в результатах.
Итерация 5
После итерации 4 у машины B была более высокая оценка выигрыша, поэтому она была выбрана.
Рука бандита была вытянута, а сигнала о награде получено не было.
Оценка выигрыша машины B вычисляется и сохраняется в результатах.
Обратите внимание, что на этой итерации были выполнены два особых условия:
- Оценка винрейта машины B почти достигла фактического винрейта.
- Оценка винрейта машины А упала ниже фактического винрейта машины Б.
Значение этих условий заключается в том, что цель исследования состоит в том, чтобы подвергнуть модель воздействию всех бандитов, чтобы определить оптимального бандита с самым высоким коэффициентом выигрыша, что и было достигнуто в этой итерации.
Поскольку модель следовала жадному подходу и всегда выбирала игровой автомат с наивысшей оценкой выигрыша, она будет продолжать делать это даже в следующих итерациях и выберет автомат B.
Поскольку оценка винрейта машины B уже приблизилась к ее фактической оценке винрейта, поэтому будет очень меньше отклонений от текущего состояния оценок винрейта.
Этот повторный выбор машины B в конечном итоге приведет к максимизации вознаграждения в долгосрочной перспективе.
Некоторые ключевые выводы:
- В подходе с оптимистичными начальными значениями высокие начальные значения отвечают за исследование модели.
- Чем выше начальное значение, тем больше объем исследования. Это связано с тем, что чем выше вы устанавливаете начальные значения, тем больше итераций потребуется модели, чтобы приблизиться к ее фактическим значениям винрейта, и, следовательно, будет больше исследований.
Возможно, вы зададитесь вопросом, как найти наилучшее начальное значение для моделирования? Ну, в той или иной степени требуется некоторое количество проб и ошибок. Тем не менее, это помогает, если у вас есть некоторые знания предметной области проблемы.
Например, задача многорукого бандита находит широкое применение в маркетинге, основанном на онлайн-рекламе. Цель состоит в том, чтобы выбрать рекламные объявления с самым высоким рейтингом кликов (количество кликов / количество показов), чтобы максимизировать доход.
Кто-то, кто имеет опыт работы в этой области, должен знать, что рейтинг кликов 2–4% — это обычно наблюдаемый показатель для разных форматов объявлений.
Предположим, симуляция предназначена для проверки винрейта (в данном случае рейтинга кликов) двух разных объявлений и выбора оптимального. Тогда хорошей базой для оптимистичного начального значения может быть, скажем, 10%.
Суть в том, что некоторое раскрытие домена может привести к хорошо обоснованному предположению.
Код реализации и результаты
Код имитирует сценарий с тремя игровыми автоматами с фактическим коэффициентом выигрыша 25%, 50% и 75%. Начальные значения равны 1 (оценка 100% количества побед).
Результаты моделирования
Следующие результаты были получены с использованием кода, предоставленного с этой статьей. Начальная оценка винрейта установлена на значение 100%.
Обратите внимание, что:
- Оценки винрейта неоптимальных бандитов никогда не сходятся к их фактическим значениям, потому что, как только их оценка винрейта падает ниже оценки оптимального бандита, они больше никогда не выбираются.
- В отличие от Эпсилон-жадного алгоритма, существует незначительная разница между общим коэффициентом выигрыша модели (синяя линия) и оптимальным коэффициентом выигрыша бандита (красная линия).
Для Результаты моделирования — 1 times_selected показывает, что:
- Бандит №1 был выбран 20 раз [фактический процент побед: 25%]
- Бандит #2 был выбран 6 раз [фактический процент побед: 50%]
- Бандит №3 был выбран 9974 раза [фактический процент побед: 75%] (оптимальный бандит)
Кроме того, вы можете попробовать более высокие начальные значения, чтобы заставить модель исследовать больше. На следующем изображении показан результат модели с начальной оценкой процента побед, установленной на 200% вместо 100%, использовавшейся ранее.
Обратите внимание, как эта модель выбрала неоптимальных бандитов больше по сравнению с предыдущей конфигурацией.
Спасибо за прочтение!
Это меня очень вдохновляет! 😃Если этот пост показался вам интересным и вы хотите больше, рассмотрите возможность подписаться на меня🥁. Я публикую еженедельные сообщения на темы, связанные с машинным обучением, статистикой и анализом данных. Мне нравится учиться с помощью визуализаций, поэтому мои сообщения содержат большое количество диаграмм, симуляций и примеров кода.
Небольшое примечание: я стараюсь свести ошибки к минимуму, но они являются частью нашего обучения, поэтому указывайте, если что-то заметите. Наконец, не стесняйтесь предлагать темы, на которые вы хотели бы, чтобы я написал.
