Комментарии 26
В реальной жизни наиболее «оптимальна» (не в математическом, а в общем смысле) стратегия №3. Первую треть отпуска можно и нужно ходить в разные столовые как минимум из любопытства и тяги к новому, выбирая из всех существующих те, которые кажутся наиболее интересными (не лучшими, а именно интересными для посещения и отличающимися от других). А потом, когда из них определена лучшая, а все остальные столовые не представляют интереса в силу однотипности с ранее посещёнными, можно ходить только в лучшую.

Статья на интересную тему, но как-то в ней всё ненадежно, по-дилетантски даже на взгляд дилетанта.


Будем считать, что качество столовой распределено нормально, со средним в нуле.

Почему? Вы пойдете в столовую, от которой на улице стоит смердящий запах? Или в соц. столовую с бомжами? Или в столовую с крайне негативными отзывами? А действительно ли столовые распределены по качеству нормально, или большая часть из них пытается экономить, смещая распределение ближе по качеству к плохим? Я ставлю под большое сомнение это предположение о нормальности распределения.


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

Было бы интересно его увидеть, и чтобы с формулами, с четкими выводами. А то вы и для своего численного решения особо ничего не показываете.


Численно проэкспериментируем с каждым вариантом много раз (пока не наберется статистическая значимость)

А где же расчет необходимого количества вычислений для стат. значимости? Где код вычислений? А сколько попыток можно сделать при поиске столовой? В моём районе, к примеру, 6 столовых, как-то учитывается максимальное количество столовых?


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

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


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

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


и ничто не мешает смердящие столовые с бомжами исключить из рассмотрения вовсе

Столовые с бомжами, столовые с плохими отзывами, удаленные столовые — так и получается, что распределение перестаёт быть нормальным.

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

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

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

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

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

Тогда тут больше подходит стратегия из этого видео:

То есть немного адаптировав под эту задачу (в задаче из видео нельзя возращаться назад) — первую треть ходить по новым столовым, а 2/3 по лучшей и первой трети.

П.с. понял, что у меня тут получаются математический пробел — в примере из видео таки есть шкала, ведь мы знаем что числа от 0 до гугла. Но стратегия судя по всему все равно лучше — она никак не привязана к размеру самого числа, привязана только к количеству «итераций».

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

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

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

Смотрите на секундную стрелку часов: меньше 30 — орёл, иначе — решка. На часы можно смотреть без палева по идее.

Есть теория что мы решения принимаем практически случайно, а после мозг придумывает объяснение, почему мы решили так. Исследования Роджера Сперри это частично доказывают. Нобелевская премия по медицине 81го года

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

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

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

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

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.