Информация

Дата основания
Местоположение
Россия
Сайт
team.mail.ru
Численность
5 001–10 000 человек
Дата регистрации

Блог на Хабре

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

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

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


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

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

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

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

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


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

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

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

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