- PVSM.RU - https://www.pvsm.ru -
Представим ситуацию: приехали в новый город на неделю-другую, и нужно понять, как выбирать места для обедов. Риски понятны: если постоянно ходить в несколько уже знакомых столовых, то можно упустить совсем хорошую; но и идти в непонятно какую новую столовую вместо хорошей проверенной тоже не хочется. Каждый охотник желает знать, где баланс эксплорейшена-эксплотейшена. Под катом разберемся как нужно действовать.
Сформулируем задачу так:
Цель: максимизировать суммарное качество посещенных столовых за все дни пребывания.
Понятно, что суммарное качество зависит от того, какие столовые попались, поэтому максимизируем его матожидание.
Будем считать, что качество столовой распределено нормально, со средним в нуле. То есть, если качество столовой около нуля — она средненькая; если сильно отрицательное — значит, не очень; если сильно положительное — хороша. В задаче считаем, что мы уже видели много столовых в других городах и представляем распределение качества столовых.
При выборе новой столовой для нас все непосещенные столовые одинаковы, поэтому мы из них не выбираем, просто берем следующую из какого-то списка.
Есть похожие задачи, но они существенно отличаются. В отличие от задачи о разборчивой невесте [1], к столовым можно возвращаться, а к женихам — нет.
От задачи о многоруком бандите [2] наша отличается тем, что после посещения столовой мы точно знаем ее качество.
Во-первых, понятно, что если мы возвращаемся в одну из посещенных столовых, то нет смысла выбирать не лучшую из них.
Есть еще одно соображение: сначала должна быть фаза исследования столовых, и строго после нее — фаза посещения лучшей. Рассмотрим стратегию, при которой это не так или не всегда так. Тогда на каком-то этапе возникает ситуация, когда мы сначала выбираем лучшую столовую, а потом идем исследовать новую. Но если мы поступим наоборот — сначала посетим новую столовую, а потом пойдем в лучшую, — то наш выигрыш точно не уменьшится, а может даже увеличится, если при проверке новой столовой её качество окажется выше, чем у текущей лучшей.
Соответственно, каждый день нам нужно принимать решение:
Из этого становится понятно, что оптимальная стратегия зависит только от уровня лучшей найденной столовой и оставшегося количества дней.
Ясно, что чем качественнее найденная лучшая столовая, тем меньше смысла искать еще более хорошую. Это значит, что для фиксированного оставшегося количества () дней есть порог качественности : если текущий максимум больше, чем , то есть найденная столовая достаточно клевая, мы начинаем ходить только в нее, а если меньше — испытываем судьбу в новой столовой. Получается, что стратегия — это правильный набор чисел .
Первый ход, разумеется, всегда «пойти в новую столовую», потому что вариантов-то и нет.
Эта задача имеет аналитическое решение, но оно довольно громоздкое и нетривиальное, поэтому мы обойдемся меньшей кровью и вычислим эти коэффициенты численно.
Если мы знаем оптимальную стратегию для случая, когда осталось дней, то есть знаем коэффициенты , тогда искать стратегию на дней существенно проще, потому что нужно оптимизировать только одно число.
Зафиксируем текущий максимум и рассмотрим две ситуации:
Численно проэкспериментируем с каждым вариантом много раз (пока не наберется статистическая значимость) и посмотрим, какой из них дает больший выигрыш. Если первый: значит, оптимальная стратегия для этого m — эксплуатировать максимум, то есть .
Иными словами, для любого m мы можем понять, больше или меньше он, чем . Это позволяет сделать бинарный поиск по — сойдется он к .
А , потому что, когда остался последний день, мы просто выбираем то, что больше: наш текущий максимум или ожидание качества новой столовой, равное нулю.
Таким образом мы можем последовательно вычислить любое . Правда, с уменьшающейся точностью, но для нас это не критично.
Коэффициенты оптимальной стратегии получаются такие: 0, 0,27, 0,43, 0,55, 0,63, 0,71, 0,75, 0,82 и т.д.
Это, конечно, отлично, но давайте разберемся, как их интерпретировать. Чтобы эти коэффициенты получили понятный физический смысл, их нужно перевести в квантили распределения качества столовых, то есть в квантили нормального распределения. Тогда получится: 0,5, 0,61, 0,67, 0,71, 0,74, 0,76, 0,77, 0,79.
Это значит:
Выглядит сложновато для практического применения. Сравним с более простыми в использовании стратегиями.
Прогоним 10 000 экспериментов и посмотрим распределение выигрыша для каждой из стратегий. Будем смотреть на периоде в 7 дней и на 30 дней. На графиках по горизонтальной оси — значение выигрыша, по вертикальной — плотность вероятности получить такой выигрыш. В легенде и на вертикальной линии — средний выигрыш стратегии.
Что тут у нас:
Автор: Георгий Борисенко
Источник [4]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/matematika/358828
Ссылки в тексте:
[1] задачи о разборчивой невесте: https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D0%B1%D0%BE%D1%80%D1%87%D0%B8%D0%B2%D0%BE%D0%B9_%D0%BD%D0%B5%D0%B2%D0%B5%D1%81%D1%82%D0%B5
[2] о многоруком бандите: https://en.wikipedia.org/wiki/Multi-armed_bandit
[3] на канал: https://vk.cc/aCgIZS
[4] Источник: https://habr.com/ru/post/527994/?utm_source=habrahabr&utm_medium=rss&utm_campaign=527994
Нажмите здесь для печати.