Disclaimer

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

Обложка книги "Bandit Algorithms for Website Optimization"

Представьте себе, что вы находитесь перед несколькими игральными автоматами и хотите сыграть в них. У каждого из них есть одна ручка, за которую можно дернуть и с какой-то вероятностью получить выигрыш. Вероятность выигрыша на конкретном автомате вы не знаете. Если вы рациональный игрок, то хотите найти автомат, который даст вам максимальный выигрыш. Главная проблема – это то, что вы не знаете какой именно автомат даст вам такой выигрыш, а единственный доступный способ оценить вероятность выигрыша на автомате – это сыграть на нём.

Вы можете играть на одном, получать какой-то выигрыш (это будет эксплуатацией лучшего известного варианта, exploitation), но рядом может стоять другой автомат, потенциальный выигрыш на котором будет больше. Если же вы начнёте искать автомат лучше (это будет исследованием других вариантов, exploration), то вы можете потерять часть выигрыша в случае, если ваш текущий автомат действительно окажется самым лучшим.

Проблема выбора в такой ситуации называется компромисов между исследованием и эксплуатацией (exploration-exploitation trade-off). Группа итерационных алгоритмов, описанных в этой книге, нужна для максимизации возможного выигрыша в такой ситуации.

По названию книги можно догадаться, что игральные автоматы (англ. bandits) – это всего лишь модель (multi-armed bandit problem или N-armed bandit problem), которую можно использовать не только в казино, но и для других целей. Автор предлагает её как альтернативу традиционным A/B-тестам, в которых каждый из вариантов выбирается с заданной заранее фиксированной вероятностью. Например, вы можете сделать несколько вариантов одного и того же баннера и сравнить их. В этом случае выигрышем может считаться клик по такому баннеру после после его показа (1), а проигрышем – отсутствие клика (0).

Чтобы не придумывать свои названия для терминов и не создавать тем самым путаницу, в тексте я буду использовать терминологию игральных автоматов. В ней «рука» означает один из доступных вариантов, а «выигрыш» – результат, который вы получаете после использования выбранной руки.

Всего в книге описываются три алгоритма:

  • Эпсилон жадный (epsilon greedy)
  • Алгоритм мягкого максимума (softmax)
  • Алгоритм верхнего доверительного интервала (upper confidence bound, UCB)

В этом обзоре я постараюсь кратко объяснить общую идею каждого алгоритма (без погружения в детали), а также его плюсы и минусы. Я не буду приводить примеры кода для алгоритмов, т.к. в противном случае обзор будет очень большим. Если вам всё-таки нужны примеры, то автор книги разместил их в репозитории на Github.

У всех этих алгоритмов общая последовательность шагов на каждой итерации:

Шаг №1 (выбор руки): алгоритм выбирает руку на основе уже имеющихся у него данных. Поначалу данных мало иили совсем нет и выбор неточен, но постепенно данные накапливаются за счёт обучения и выбор становится более обоснованным;

Шаг №2 (использование руки): Мы получаем какой-то выигрыш (он может быть нулевым). Если мы не можем оценить выигрыш от использования руки, то данные алгоритмы неприменимы (т.к. невозможно итерационное обучение алгоритма);

Шаг №3 (обучение): мы отдаём алгоритму данные для обучения - пару (номер руки, выигрыш), которые повлияют на последующие выборы рук. Обучение всех алгоритмов проходит одинаково - мы должны знать количество использований и вредний выигрыш для каждой из имеющихся рук.

Эпсилон жадный алгоритм

Эпсилон жадный алгоритм (epsilon greedy) – самый простой для понимания и реализации алгоритм из описанных в книге. Его суть заключается в фиксированной вероятности проведения исследования вариантов. Эта вероятность обозначается epsilon и именно она дала название алгоритму.

При выборе руки генерируется случайное число и интервале от 0 до 1. Если это число меньше epsilon, то мы запускаем режим исследования и выбираем случайную руку, в противном случае выбираем руку с максимальным средним выигрышем.

Изменением значения epsilon можно влиять на поведение этого алгоритма. Чем больше его значение, тем быстрее будет найдена рука с максимальным выигрышем, но и больше потери при выборе невыгодных рук в режиме исследования. Большие потери при исследовании являются главным недостатоком этого алгоритма.

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

Алгоритм мягкого максимума

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

arm_weight = math.exp(average_arm_reward / temperature)

average_arm_reward - это среднее значение выигрыша руки на момент выбора. Оно позволяет придать больший вес выгодным рукам.

temperature - это параметр, с помощью которого можно настраивать поведение алгоритма (он называется температура). Он может принимать значения от нуля до бесконечности. Если он близок к бесконечности, то softmax будет меньше зависеть от значения выигрыша и выбирать руки более равномерно (т.е. перейдёт в режим исследования). Если он близок к нулю, то алгоритм будет больше ориентироваться на известный средний выигрыш рук (т.е. перейдёт в режим эксплуатации).

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

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

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

Алгоритм верхнего доверительного интервала

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

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

Как и в softmax в UCB1 при выборе рук используется весовой коэффициент, который представляет собой верхнюю границу доверительного интервала (upper confidence bound, что и дало название алгоритму) значения выигрыша:

arm_weight = average_arm_reward + arm_bonus

average_arm_reward - это среднее значение выигрыша руки на момент выбора. Он ничем не отличается от того, что используется в других алгоритмах.

arm_bonus - это бонусное значение, которые показывает, насколько недоисследована эта рука по сравнению с остальными. Он вычисляется следующим образом:

arm_bonus = math.sqrt(2 * math.log(total_count) / arm_count)

total_count - это суммарное количество использований всех рук, а arm_count - это количество использований данной руки.

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

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

Заключение

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

См. также: