Как стать автором
Поиск
Написать публикацию
Обновить

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

В реальной жизни наиболее «оптимальна» (не в математическом, а в общем смысле) стратегия №3. Первую треть отпуска можно и нужно ходить в разные столовые как минимум из любопытства и тяги к новому, выбирая из всех существующих те, которые кажутся наиболее интересными (не лучшими, а именно интересными для посещения и отличающимися от других). А потом, когда из них определена лучшая, а все остальные столовые не представляют интереса в силу однотипности с ранее посещёнными, можно ходить только в лучшую.
Всего голосов 4: ↑4 и ↓0+4
НЛО прилетело и опубликовало эту надпись здесь

Предположение о нормальности распределения качества столовых наиболее естественно. Распределение нормально в ситуациях, когда на величину влияют много независимых факторов.


Вас, вероятно, смущает среднее, равное нулю. Но ведь мы просто принимаем за ноль качество "на троечку" (и ничто не мешает смердящие столовые с бомжами исключить из рассмотрения вовсе).

Всего голосов 6: ↑6 и ↓0+6
НЛО прилетело и опубликовало эту надпись здесь

Скорее, не распределение перестаёт быть нормальным, а центрирующий параметр смещается (возможно, за пределы рассматриваемой области). В любом случае, важно распределение не столовых, в которые мы готовы пойти, а столовых, по которым мы считали квантили, нет?

Всего голосов 3: ↑3 и ↓0+3

Все рассмотренные стратегии детерминированные. Учитывая, что максимизируем мы матожидание, а также что в любой момент можем оценить квантиль текущего максимума, почему бы не рассмотреть такую стратегию: "каждый день с вероятностью, равной этому квантилю, выбираем exploit, а с оставшейся от единицы вероятностью – explore"?

Комментарий пока не оценивали0
Это противоречит принципу «сначала изучай»
Всего голосов 1: ↑1 и ↓0+1

Вот поэтому и интересно её рассмотреть. Принцип был выведен для детерминированных стратегий, интересно, как обстоит дело в случае вероятностных.

Комментарий пока не оценивали0

Можно было бы так — выбрать случайно сколько дней изучать, или с какой-то вероятностью каждый день переходить в состояние exploit, не возвращаясь больше к explore. Эта стратегия эквивалентна вашей, но не нарушает принципа оптимальности.

Всего голосов 1: ↑1 и ↓0+1
Над формализацией стоит подумать еще.
Комментарий пока не оценивали0
НЛО прилетело и опубликовало эту надпись здесь

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

Всего голосов 3: ↑3 и ↓0+3
Для случаев, когда распределение неизвестно, обычно применяются т.н. «непараметрические» методы, т.е. вместо абсолютных значений величины берётся их ранг в выборке. Так как распределение рангов известно — оно равномерное — то дальше можно применять теорию равномерного распределения.
Комментарий пока не оценивали0
Не всё так просто. В одной столовой может быть отличный суп, а в другой — борщ (по четвергам). То есть надо перепробовать ещё разные блюда, которые к тому же могут быть не каждый день.
Всего голосов 3: ↑3 и ↓0+3
Интересно… Я решаю подобные проблемы крайне просто — достаю монетку и подбрасываю. Орел — идем в проверенное, Решка — ищем новое. Но вот меня не хватит проверить математикой ожидаемый результат…
К слову хорошо работающая стратегия. Над нами с женой в магазинах постоянно ржут когда мы выбираем один из двух понравившихся товаров. Нервы она точно сохраняет. А это уже не самый плохой выигрыш.
Всего голосов 1: ↑1 и ↓0+1

Меня жена убивать готова за монетку при принятии решений, поэтому наловчился в кармане, например, незаметно покрутить и посмотреть.

Комментарий пока не оценивали0
НЛО прилетело и опубликовало эту надпись здесь
Есть теория что мы решения принимаем практически случайно, а после мозг придумывает объяснение, почему мы решили так. Исследования Роджера Сперри это частично доказывают. Нобелевская премия по медицине 81го года
Всего голосов 1: ↑1 и ↓0+1

попробуйте построить атомную станцию, процессор с миллиардами транзисторов или БАК подбрасывая монетку

Комментарий пока не оценивали0
Я что-то не понял, а разве это не известная проблема разборчивой невесты? Ею ещё Борис Березовский занимался до олигархического периода своей жизни.
Комментарий пока не оценивали0
теория момента остановки или марковский момент времени. Класические примеры — поиск места для парковки, поиск квартиры для аренды.
Комментарий пока не оценивали0
Задача о разборчивой невесте похожая, но другая. Отличия:
— К столовым можно возвращаться, а к женихам — нет
— В классической постановке задаче о невесте считается, что распределение качества женихов не известно, поэтому первое время нужно исследовать именно его, скипая женихов. В задаче о столовых игроку известно распределение
— В задаче о невесте цель найти лучшего жениха. В задаче про столовые цель максимизировать сумму качества посещенных столовых, что больше похоже на «как можно раньше найти более ли менее нормального (не лучшего) жениха»
В частности, это приводит к другой оптимальной стратегии
Всего голосов 2: ↑2 и ↓0+2

Когда сменил работу, с новыми коллегами обошли все ближайшие кафе на обед, которые находились в радиусе 10-15 минут пешком, а потом ходили в те, что понравились лучше, но не постоянно, чередуя разные варианты. Хотя этот вариант, конечно, не идеален, когда время ограничено.

Всего голосов 1: ↑1 и ↓0+1

Хорошо, когда идеальная столовая в одном здании с офисом

Комментарий пока не оценивали0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Показать лучшие за всё время

Истории

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr