Задача Роббинса — нерешенная задача оптимальной остановки. На нашем канале мы разбирали несколько таких задач. Смысл их всех в том, что надо остановиться на одном из претендентов, зная их количество и не имея возможности вернуть того, кому отказали. А различаются задачи наличием информации и критерием оптимальности. Ведь можно знать численную оценку качества претендента, а можно только сравнивать их друг с другом. А еще можно гнаться за вероятностью взять самого лучшего, или за лучшим в среднем...
Задача Роббинса ставится так: есть n независимых претендентов, качество которых равномерно распределено на [0,1]. Изучив претендента, мы знаем оценку его качества. Можно взять претендента, тогда остальные потеряны; можно отказать, тогда он потерян. Мы стремимся минимизировать средний ранг принятого претендента.
Ранг — это номер в иерархии. Первый, самый лучший, имеет ранг 1. Второй имеет ранг 2. Все наглядно. Так вот, мы хотим ранг поменьше в среднем. Например "в среднем два" означает, что иногда мы берем второго, иногда первого, порой третьего, случается и больше... но на каждого третьего приходится первый, а на каждого четвертого два... Всё, конечно, на большом массиве попыток.
Почему эта задача сложнее, чем задача на максимизацию среднего качества? Потому что, получив претендента с качеством 0.99, мы понимаем: сильно лучше уже не будет, даже если впереди еще тысяча претендентов и вероятность найти лучше довольно велика. Нет смысла. А вот в задаче Роббинса смысл есть, так как если найдется кто-то лучше, ранг данного станет 2, а то и больше, и ведь еще важно, были ли такие классные раньше. Если кто-то с качеством 0.991 уже был, то 0.99 уже имеет ранг 2, а может еще увеличиться. Слишком уж много всего влияет на принятие решения.
Давайте рассмотрим, что известно об этой нерешенной задаче, опираясь на статью
F. Thomas Bruss What Is Known about Robbins' Problem? // Journal of Applied Probability, Vol. 42, No. 1 (Mar., 2005), pp. 108-120.
Обозначим оптимальный средний ранг выбранного претендента через V(n). Решить задачу — это найти V(n) и, главное, ту стратегию, которая позволит принимать решения: кого брать, а кого не брать. Решения пока нет, но кое-что мы про V(n) знаем.
Первый результат. Величина V(n) возрастает с ростом n.
В принципе, это почти очевидно. Чем больше претендентов, тем сложнее выбрать лучших. Но надо же строго доказать. Впрочем, в задаче на максимум качества как раз наоборот: чем больше претендентов, тем лучше результат, в среднем. Так что надо доказывать!
А доказательство очень изящное! Представим себе провидца, который обладает такой скромной суперспособностью: может один раз распознать самого плохого претендента. Понятно, что эта суперспособность ему не помешает, так что его результат P(n) будет не хуже нашего: P(n)<V(n). С другой стороны, его результат равен нашему при меньшем на единичку числе претендентов. Ведь он, откинув самого плохого, далее никаких преимуществ перед нами не имеет! Поэтому P(n)=V(n-1). Вот и получается возрастание.
Теперь встает вопрос: а ограничена ли эта величина, или с ростом n она будет расти до бесконечности? Во втором случае задача отчасти теряла бы интерес... Но нет, предел существует. Это
Второй результат. Задача, в которой мы знаем текущие ранги (то есть кто лучше кого, без абсолютных значений) и стремимся минимизировать ранг принятого претендента в среднем — решена. И в ней средний ранг имеет предел при растущем n и, следовательно ограничен. Но ведь ясно, что в задаче Роббинса, в которой информации больше (мы знаем не просто кто лучше кого, но и насколько) оптимальный ранг будет не хуже: мы же можем просто не использовать дополнительную информацию, и иметь тот же результат. Заодно мы имеем и грубую оценку асимптотического (при большом n) решения V: оно не больше, чем решение указанной задачи, а это W=3.8695.
Таким образом, решение у задачи есть. И это уже удивительно: из миллионов претендентов мы способны, потенциально, выбрать, в среднем, не хуже четвертого... Да, это в среднем, то есть иногда может оказаться и сотый... но тогда, для компенсации, довольно часто должен быть первый. А взять первого из миллиона, и делать это достаточно часто — кажется неправдоподобным. Но это так!
Третий результат. Между значениями качества и их рангами есть сильная корреляция. Это интуитивно ясно: если посередине, то примерно половина претендентов будет лучше, то есть и ранг будет посередине. Тогда можно попробовать использовать результат задачи на оптимизацию среднего качества претендента. Это срабатывает, подсказывая пороги "без памяти", то есть без использования качеств уже опрошенных претендентов. Пороги вида
где n — полное число претендентов, а k — номер шага, дают оценку 7/3~2.333. Неплохое улучшение о сравнению с 3.8695!
Порог того же вида с заменой двойки на число c и выбором этого c дает оценку чуть лучше: V<2.3318 при c=1.9469.
Выяснено, что решение в классе порогов без памяти равно 2.3267. Оценку можно получить на конкретных порогах.
Брюсс пишет, что верхнюю оценку лучше этой получить не удалось, разве что для маленьких n есть точное решение (для порогов без памяти!) V<2.32659.
В более новой работе (Meier M., Sogner L. A new Strategy for Robbins' Problem of Optimal Stopping // J. Applied Probability, 2017, 54, 331-336) получена оценка 2.32614. Видите, за какие "мелочи" идет борьба?
Оценка сверху показывает, что точно можно получить, то есть точное решение еще лучше. Теперь посмотрим оценки снизу: меньше чего точно получить нельзя. Очевидно, что меньше 1 быть не может, но это тривиально.
Четвертый результат. Оценка снизу не меньше, чем 1.4198. Ее легко получить таким образом. Будем считать результат иначе: если взяли лучшего, засчитываем ранг 1, а если нет, то 2. Ясно, что решение такой задачи лучше, у задачи Роббинса (в которой возможен ранг и три, и больше), то есть является оценкой снизу. А оно (решение) известно, ведь это задача о максимизации вероятности взять самого лучшего при полной информации, и она решена. Ее асимптотическое решение (вероятность p взять лучшего) равно 0.580164, что и дает оценку 1.4198=2-p.
Схему можно продолжать, отсекая ранги выше и чуть хитрее, хотя при этом экспоненциально растет объем вычислений и размер необходимой памяти. В статье приведены оценки вплоть до 1.908.
Пятый результат. Доказано, что порог для принятия решения "взять/отказать" на каждом шаге зависит от качества всех уже отвергнутых претендентов, и нельзя заменить эту историю какой-то статистикой (например, средним значением). Необходима вся информация о предыстории.
Это сильный результат, характеризующий задачу как очень сложную. Обычно в задачах, в которых много независимых одинаково распределенных величин, есть возможность агрегированного описания. Примером служит статистическая физика, или термодинамика, в которой не нужна полная информация о молекулах газа: достаточно средней энергии (температуры) и еще нескольких агрегатов. А здесь могут быть миллионы претендентов, и после миллиона уже опрошенных надо учитывать весь миллион значений, чтобы принять правильное решение.
Идея доказательства тоже основана на концепции провидца. Пусть у нас есть двое принимающих решение, Он и Она, причем Он никакими сверхспособностями не обладает, а Она кое-что может. А именно, на этапе k она волшебным образом узнает качества всех оставшихся претендентов, после того, как примет решение по текущему (правда, если она его примет, ей эта информация уже ни к чему).
Ясно, что Она покажет лучший результат в среднем, нежели Он. Оценка результата при остановке у них одинакова. А вот оценка результата при продолжении разная: Он будет решать задачу Роббинса для остатка очереди, а Она просто должна вычислить среднее по распределению лучшее значение из оставшихся. Она же точно узнает, кто это будет.
Она должна, таким образом, посчитать вероятность, что лучший из данного числа оставшихся будет лучше всех; вторым; третьим; и т.д., и посчитать средний ранг. Ей нужны все качества уже опрошенных, так как нужна вероятность попасть между первым и вторым, между вторым и третьим, и т.п.
Поскольку Он не может добиться лучшего результата, чем Она, то ее оптимальная остановка будет и его оптимальной остановкой. Но не наоборот: может быть, она решит продолжать, а он — нет.
Тут поможет такое рассуждение: вероятность добраться до предпоследнего шага ненулевая (это очевидно, но тоже доказывается, ибо всяко бывает!). А на предпоследнем шаге Он и Она в равных положениях! Он тоже обретает суперсилу)) на один шаг. А раз так, то Он должен использовать всю информацию, так же, как и Она. И, следовательно, Он должен ее запоминать.
Шестой результат. Доказано, что результат для порогов без памяти может быть улучшен для каждого n. Но вот можно ли сделать это асимптотически, при n→∞ — вроде как пока неясно. Не исключено, что асимптотическое решение W для порогов без памяти является асимптотическим решением V и задачи Роббинса.
Открытые вопросы. Конечно, главный вопрос — это решение задачи, то есть оптимальные пороги и средний ранг V(n) принимаемого претендента при полном числе n.
Неплохо было бы получить асимптотику, то есть оптимальный средний ранг V при большом числе претендентов (n→∞).
Неплохо было бы даже просто выяснить, V>2? И проверить неравенство V<W.
В 2016 году было получено точное решение для n=4...
Оглавление рубрики "Вероятность и теория игр"