Поиск
Удалить поисковый запрос
Закрыть поиск
Приложения Google
Главное меню

Обзор

Приложение (многорукий бандит)

Теоретические сведения и примеры вычислений

Название "многорукий бандит" подразумевает проблему, для которой предложено несколько готовых решений. Соответствующие подходы изложены в работе "Стимулируемое обучение" во вступительной главе, посвященной многоруким бандитам. Причина в том, что математика, стоящая за проблемой многорукого бандита, настолько сильна, что для ее решения требуется эвристическая аппроксимация. Связанные с ней трудности хорошо описывает цитата Питера Уиттла (Whittle, 1979):

[Проблема бандита] была сформулирована во время [Второй мировой] войны, и усилия по ее решению настолько подорвали силы и умы аналитиков союзников, что было предложено сбросить проблему на Германию в качестве идеального оружия для интеллектуального саботажа.

Мы используем эвристику, известную как отбор проб Томпсона, или рандомизированное соответствие вероятности, потому что оно сочетает в себе лучшие черты этих методов. Подробнее об этом инструментарии читайте здесь], а математические аспекты представлены в следующих статьях: 2], [3] и [4].

Вероятности оптимальной руки

Выборка Томпсона назначает сеансы рукам в соответствии с вероятностью того, что та или иная рука является оптимальной. Это байесовское вычисление. Пусть θ = (θ1, θ2,..., θk) обозначает вектор коэффициентов конверсии для рук 1, …, k. И допустим, что y обозначает данные, наблюдавшиеся до сих пор в эксперименте. Мы моделируем y как вектор независимых биномиальных результатов и считаем, что независимая постоянная имеет приоритет перед θ. Допустим, что Ia(θ) обозначает индикатор такого события, когда рука a является оптимальной. Тогда мы можем сформулировать следующее уравнение:

P(Ia) = ∫Ia(θ) p(θ|y) dθ

Этот интеграл может быть сделан в закрытой форме (хотя решение закрытой формы требует выполнения таких сложных специальных функций, как неполная бета-функция) или путем численного интегрирования. В любом случае вычисление быстро становится неустойчивым даже при относительно малых значениях y. Тем не менее, вероятности оптимальной руки можно стабильно вычислять методом моделирования. Каждый элемент θ является независимой от бета-распределения случайной величиной. Смоделируем большую матрицу, содержащую варианты θ из соответствующих бета-распределений, где строки матрицы представляют собой случайные варианты, а столбцы представляют руки k эксперимента. Оценка методом Монте-Карло вероятности того, что рука "a" оптимальна, является эмпирической долей строк, для которых у руки a было крупнейшее моделированное значение. Вероятность того, что та или иная рука победит оригинальную, можно вычислить аналогично.

Оставшаяся ценность

Моделирование, генерирующее вероятности оптимальной руки, может также генерировать распределение оставшейся ценности эксперимента. Оставшаяся ценность – это апостериорное распределение (θmax-θ*)/θ*, где θmax – наибольшее значение θ, а θ* – это значение θ для руки, которая, скорее всего, является оптимальной. Предположим, что есть три руки с 20, 30 и 40 сеансами, которые получили 12, 20 и 30 конверсий. Вероятности оптимальной руки составляют примерно 0,09, 0,20 и 0,71. Первые шесть вариантов моделирования θ методом Монте-Карло будут выглядеть так:

[,1] [,2] [,3]
[1,] 0,54 0,73 0,74
[2,] 0,55 0,66 0,73
[3,] 0,53 0,81 0,80
[4,] 0,57 0,50 0,65
[5,] 0,52 0,67 0,83
[6,] 0,65 0,84 0,63

Мы вычисляем значение построчно путем вычитания наибольшего элемента этой строки из элемента в столбце 3 (потому что рука 3 имеет наибольшие шансы стать оптимальной). В первых двух строках значение равно нулю, так как наибольший вариант обнаруживается в столбце 3. В третьей строке значение равно 0,01/0,80, потому что столбец 2 на 0,01 больше, чем столбец 3. Если мы будем продолжать спускаться построчно, мы получим распределение значений, из которых можно построить гистограмму, аналогичную изображенной в левой панели рисунка A1. Вероятность того, что рука 3 лучшая, составляет 71%, поэтому ценность переключения с руки 3 равна нулю в 71% случаев. 95-й процентиль распределения ценности является "потенциальной оставшейся ценностью" в эксперименте, который в данном случае составляет приблизительно 0,16. Это число можно интерпретировать следующим образом: "Мы все еще не уверены насчет коэффициента конверсии для руки 3, но каким бы он ни был, одна из других рук может победить ее на целых 16%".

Справа на рисунке A1 показано, что происходит с распределением оставшейся ценности при продолжении эксперимента. Предположим, что размер выборки для каждой руки увеличился в 5 раз (т. е. 100, 150 и 200 сеансов) с пятикратным увеличением количества конверсий (60, 100, 150). При больших размерах выборки существенно возрастает уверенность в коэффициентах конверсии рук. Теперь вероятность того, что рука 3 является оптимальной, составляет около 95%, поэтому 95-й процентиль распределения оставшейся ценности равен нулю.

Рисунок A1. Распределение ценности, оставшейся в эксперименте. Вертикальная линия в каждом случае является 95-м процентилем или потенциальной оставшейся ценностью.
Была ли эта статья полезна?
Как можно улучшить эту статью?