Многорукие бандиты: особенности использования алгоритмов ранжирования

[rjhdby]

> однако обновить параметры в алгоритме бандита можно было только раз в 30 минут.

А с чем связано такое странное ограничение, если не секрет?

[newrlan]

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

[rjhdby]

Я не очень понял, как это бьётся с утверждением

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

Если у вас значения конкретных счётчиков приходят раз в пол часа, то каким образом вы определяете, сколько показов было? Или идея в том, что после получения свежей статистики Томпсон работает на статичных данных и вытягивает только за счёт рандома по бэта-распределению?

[newrlan]

Ага, именно так.

[uchitel]

Задача о многоруких бандитах — это задача поиска руки с наибольшим мат ожиданием награды (!) при условии, что распределение награды неизвестно. Вы начали решать свою задачу, как типичный «частотник». Представьте, что вместо видеороликов вы имеете дело с продажей дорогих авто. Будете ли вы использовать алгоритм Томпсона для определения лучшей цены? Нет, вы мигом переобуетесь из «частотника» в «байесовиста» :) Сначала вы поймете, что вполне приемлемый доверительный интервал для матожидания награды в большинстве случаев может быть построен всего с 8-й попытки. А возможно ли построить доверительный интервал всего после одной попытки? Если нет, то тогда чем занимается алгоритм Томпсона? А если вам известно хотя бы название распределения, нужно ли вам использовать алгоритм Томпсона?

[rjhdby]

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

[newrlan]

Бета распределение для дорогих авто не подойдёт. Я не понимаю в чем ваше утверждение или вопрос :) В семплировании Томпсона мы предполагаем, что распределение биноминомиальное (сопряжённым к которому является бета-распределение). Вы это имели ввиду? Семплирование по Томпсону и есть байесовский метод, один из самых простых и понятных.

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

[uchitel]

Я просто клоню к тому, что задача о многоруких бандитах это просто способ теоретически показать, что есть способы создавать агентов, которые могут самостоятельно исследовать среду, находить источник лучшей выгоды, а потом останавливаться на этом найденном источнике. На практике, часто можно встретить всевозможные апгрейды этих агентов, причем иногда эти апгрейды настолько сильные, что волей-неволей начинаешь задумываться над тем, что может вообще не стоит пытаться решать задачу «традиционным» способом, а придумать что-то свое. Или вообще переформулировать задачу как-нибудь по другому. Например, иногда все руки в совокупности представляют собой единое распределение, тогда вообще не имеет смысла дергать за все руки. В других случаях, совокупность всех рук может быть разбита на подмножества (категории) внутри которых так же существует единое распределение и внутри этих подгрупп так же не имеет смысла дергать за все руки.

Задача о многоруких бандитах подчеркивает, что изначально агенту вообще ничего неизвестно об окружающей среде. Но на практике это не так. Как правило всегда имеется какая-то информация, которая позволяет ускорить этап исследования среды. Большинство апгрейдов как раз направлены на то что бы использовать эту информацию, или подстроиться под какие-то особенности среды. И безусловно, очень круто что вы смогли модифицировать алгоритм под свои нужды. Наверняка вы проводили не один эксперимент и построили не один график. Просто мне кажется что в статье как раз и не хватает этих экспериментов и графиков.

Когда-то я потратил кучу времени, безуспешно пытаясь модифицировать алгоритм Томпсона под заданные требования. Смотрел другие статьи, в которых все получалось и шикарно работало. Потом, спустя довольно долгое время, до меня дошло, что среда в которой должен работать агент на самом деле является пространством гипотез, что иногда это пространство может быть уменьшено, а иногда все гипотезы могут быть объединены в одну «большую» гипотезу.