Теперь, когда мы узнали, что такое задача о «многоруком бандите» и как ее можно использовать в работе, попробуем ответить на вопрос: какие алгоритмы мы можем применить к проектам, требующим таких инструментов? Два наиболее распространенных метода, по крайней мере в мире бизнеса, – верхняя доверительная граница и выборка Томпсона. В обоих алгоритмах проводится последовательная проверка различных вариантов и ведется регистрация результатов в лог-файлы, содержащие лучшие и худшие распределения. В дальнейшем мы изучим нюансы каждого алгоритма, а также преимущества и недостатки их использования.
Верхняя доверительная граница
Предупреждаю: мы продолжим рассматривать пример игровых автоматов, но его следует воспринимать только как гипотетический. Проведение подобного эксперимента в Лас-Вегасе в лучшем случае сделает вас не слишком популярным, а в худшем – приведет в тюрьму. Применяя к нашей задаче алгоритм верхней доверительной границы (ВДГ), мы определим, у какой машины лучший ожидаемый выигрыш, – а это высветит ключевое различие между алгоритмами, рассмотренными в предыдущей главе, и теми, о которых говорится здесь. В наших предыдущих примерах мы, как правило, использовали массивы данных с собранными независимыми и зависимыми переменными. Однако в обучении с подкреплением все по-другому. Мы начинаем вообще не с данных. Мы должны экспериментировать, наблюдать и менять нашу стратегию на основе предыдущих действий.
Когда вы выигрываете, алгоритм верхней доверительной границы фиксирует в своем массиве данных получение вами выигрыша как 1. Потери будут записаны как 0. Для каждой игры ВДГ добавит результат в свой массив данных. Так алгоритм обучается с помощью исследования и одновременно разрабатывает стратегию, которая позволит избежать случайного выбора машин[55]. Ход выполнения алгоритма от одного автомата к другому будет зависеть от результатов каждого предыдущего раунда, а динамическая стратегия повышает точность при сборе дополнительной информации. Например, машина, выбранная алгоритмом в 281-м раунде нашего теста, будет выбрана на основе всех данных, собранных за предыдущие 280 раундов.
Построение алгоритма верхней доверительной границы
Прежде всего предварительно: мы начинаем с определенного количества «рук» – в нашем случае это соответствует пяти игровым автоматам в Вегасе. Выбор одного из пяти автоматов представляет собой «раунд», или «игру» (я буду использовать оба термина). Каждый раз, когда мы опускаем деньги в машину и тянем за рычаг, мы завершаем раунд. Как только раунд завершен, мы либо будем вознаграждены, либо потеряем свои деньги. Эта информация запишется алгоритмом верхней доверительной границы как 1 для выигрыша или 0 для потери. Как мы обсуждали, наша цель – найти машину с наивысшим ожидаемым выигрышем. Давайте покажем результаты, которые мы ищем, на диаграмме (рис. 7.3)