Как стать автором
Обновить

Задача о многоруком бандите — сравниваем эпсилон-жадную стратегию и Томпсоновское сэмплирование

Время на прочтение 12 мин
Количество просмотров 19K
Всего голосов 13: ↑13 и ↓0 +13
Комментарии 5

Комментарии 5

А нажать кнопочку «Создать перевод» было трудно?

А то я уже думал, что автор публикации свое собственное исследование стратегий сэмплирования провел.

Но сама статья интересная. Жаль, что я Pyton не знаю от слова «совсем». Было бы полезнее не в кодах разбираться, а более подробное описание самих алгоритмов читать.

А вот вопрос: Здесь ищется оптимальная чистая стратегия. Т.е. единственная стратегия, дающая наилучший результат (при условии ее существования). А можно ли использовать данный подход для повышения эффективности поиска смешанных стратегий в условиях антагонистических игр?

P.S. А графики не увеличиваются по клику…
«А нажать кнопочку «Создать перевод» было трудно?»
Прошу прощения, не сразу заметил такую опцию. Буду знать.
" А можно ли использовать данный подход для повышения эффективности поиска смешанных стратегий в условиях антагонистических игр?"
Под антагонистической игрой, как я понял, в контексте данной задачи следует понимать adversarial bandits — это когда на каждом шаге не только игрок выбирает вариант, но и и игрок с другой стороны выбирает, какие будут вероятности вознаграждения ( чтобы минимизировать выигрыш соперника). Эпсилон-жадная стратегия и Томпсоновское сэмплирование, по крайней мере, в том виде, в котором они описаны в статье, для этой задачи, очевидно, не подойдут, т.к не учитывают изменение вероятностей вознаграждения — нужны более сложные методы.
«P.S. А графики не увеличиваются по клику…»
Спасибо за замечание, уже увеличиваются.
К сожалению. простого человеческого пояснения алгоритма сэмплирования Томпсона здесь не хватает.
Что такое бета-распределение — знаю.
Что такое байесовская вероятность — знаю.
Что бета-распределение связано с апостериорой байесовской вероятностью — слышал.
Но как именно эта связь применяется в этом алгоритме — не совсем ясно.

Интуитивно понятно следующее:

1. Случайное сэмплирование не накапливает опыт. Поэтому в ходе испытаний неоправданно много производится испытаний заведомо проигрышных вариантов.

2. Жадный алгоритм по итогам нескольких испытаний выбирает прима-кандидата на звание лучшей стратегии. Дальнейшие испытания — попытки уточнить выбор, но какие-то странные. Ведь раеально лучшая стратегия может быть отсеяна и затеряется в числе прочих, к которым во второй части жадного сэмплирования будет применяться все тот же алгоритм случайного сэмплирования.

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

Как-то так…
Хорошая статься. Но, мне кажется, нужно добавить в список определений терминов слово сэмплирование
Спасибо за замечание. Добавил.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Публикации

Истории