В лекции стэнфордского курса CS221 по искусственному интеллекту подробно разбираются марковские процессы принятия решений (MDP), которые расширяют классические задачи поиска в условиях неопределенности. В отличие от детерминированных графов, реальный мир полон случайных исходов, где одно и то же действие может привести к совершенно разным результатам. На практических примерах «ненадежного трамвая» и игры в кости наглядно демонстрируется, как строгий математический аппарат и алгоритмы динамического программирования позволяют вычислять точную ценность стратегий и находить оптимальное поведение агентов.
🎲 От детерминированного поиска к марковским процессам 0:07
На предыдущих занятиях студенты рассматривали классические задачи поиска, ключевой особенностью которых была абсолютная детерминированность действий. Находясь в определенном состоянии графа и совершая выбранное действие, агент гарантированно переходил в одно-единственное, заранее известное следующее состояние. В качестве примера приводилась задача о трамвайных путях, где из начальной точки необходимо добраться до локации 10. Каждое действие имело фиксированную стоимость, а маршрут можно было просчитать до самого конца еще на старте.
Однако в реальном мире детерминизм практически не встречается, поскольку среда всегда наполнена неопределенностью. Когда человек бросает кубик в игре или решает, как добраться до продуктового магазина — пешком, на велосипеде или на машине, — ему приходится закладывать в модель стохастические факторы: плотность трафика на дорогах, вероятность задержек транспорта и время на поиск свободной парковки. Для моделирования систем с элементами случайности применяются марковские процессы принятия решений (Markov Decision Processes, MDP), концепция которых восходит к исследованиям операций, проводившимся еще в 1950-х годах,.
Сам термин раскрывает глубинную суть этой методологии:
- Марковский (Markov): Название отсылает к теории марковских цепей в теории вероятностей и статистике, где будущее не зависит от прошлого, если известно настоящее состояние. Текущее состояние полностью инкапсулирует в себе всю необходимую предысторию.
- Решение (Decision): В отличие от простого пассивного моделирования случайных процессов, в MDP присутствует активный агент, который принимает последовательные решения и стремится найти наилучшую стратегию поведения.
- Процесс (Process): Термин указывает на то, что события развиваются строго последовательно во времени.
🚋 Математика случайности: задача о «ненадежном трамвае» 3:34
Чтобы наглядно показать отличия новой модели от обычного поиска, лектор модифицирует классическую задачу о перемещении между локациями от 1 до $n$. Переход пешком из точки $i$ в точку $i+1$ по-прежнему занимает ровно 1 минуту. Поездка на трамвае позволяет мгновенно переместиться из точки $i$ в точку $2i$ и занимает 2 минуты. Однако теперь вводится реалистичное условие — трамвай является ненадежным и ломается с фиксированной вероятностью 0,4. Если происходит поломка, пассажир теряет 2 минуты, но при этом остается в исходной локации $i$.
Цель агента формулируется как необходимость добраться из начальной точки в конечную за минимальное ожидаемое время (in expectation). В детерминированном поиске достаточно найти путь с минимальной фиксированной стоимостью, но в стохастической среде из-за поломок приходится оперировать средними значениями по всем возможным исходам. Вместо «стоимости» (cost) в MDP по конвенции используется понятие «награды» (reward), которая является отрицательной стоимостью: шаг пешком дает награду -1, а попытка поехать на трамвае — -2.
Формально математический аппарат MDP описывается следующими компонентами:
- Множество состояний $s$ и доступных из них действий $A(s)$.
- Функция переходов $T(s, a, s')$, определяющая вероятность оказаться в состоянии $s'$ после совершения действия $a$ в состоянии $s$.
- Функция наград $R(s, a, s')$, возвращающая выигрыш за конкретный совершенный шаг.
При этом решение о выборе действия принимает сам агент, а вот за то, какой именно исход реализуется (сломается трамвай или доедет), отвечает природа. Для любого фиксированного сочетания состояния и действия сумма вероятностей перехода во все возможные последующие состояния обязательно должна быть равна 1. В примере с первой локацией при выборе трамвая вероятность успеха составляет 0,6 (переход в точку 2), а вероятность неудачи — 0,4 (остаемся в точке 1), что в сумме дает строго 1,0 и служит базовой проверкой корректности модели.
🎲 Стратегия азарта: игра в кости 13:10
Для закрепления понимания стохастических процессов лектор предлагает аудитории разобрать математическую модель простой азартной игры, проходящей по раундам. В начале каждого раунда перед игроком стоит выбор из двух действий: выйти из игры (quit) или продолжить играть (stay). Если игрок решает завершить сессию, он гарантированно забирает \$10, и игра на этом прекращается. Если же он решает остаться, то гарантированно получает промежуточную выплату в размере \$4, но после этого ведущий бросает стандартный шестигранный кубик.
Если на кубике выпадают грани 1 или 2 (вероятность составляет 1/3), игра принудительно завершается, и игрок уходит с накопленными за этот раунд деньгами. Если же выпадают числа 3, 4, 5 или 6 (вероятность равна 2/3), игрок успешно переходит в следующий раунд, где снова встает перед точно таким же выбором.
Лектор проводит интерактивный опрос среди студентов, чтобы узнать, какую стратегию они предпочли бы на практике. Аудитория разделяется: часть студентов выбирает сиюминутную синицу в руках в виде гарантированных \$10, в то время как другие готовы рискнуть ради потенциально долгой серии выигрышей по \$4,. Как показывает строгий математический анализ, в данной задаче нет никакого смысла придумывать гибридные стратегии вроде «подождать три раунда, а затем выйти». Оптимальный выбор здесь строго бинарен — нужно либо сразу забирать деньги, либо играть бесконечно, поскольку условия каждого раунда абсолютно идентичны.
📈 Что такое политика и как её оценить через симуляции 17:39
В детерминированных задачах решением является жесткая последовательность действий. В MDP из-за случайности исходов такой подход неприменим: агент может застрять на месте из-за поломки или улететь далеко вперед. Поэтому решением марковского процесса является так называемая «политика» ($\pi$) — функция, которая принимает на вход любое текущее состояние среды и возвращает действие, которое необходимо предпринять. Политика становится для агента путеводной звездой в любой непредвиденной ситуации.
Для оценки качества конкретной политики применяется симуляция, называемая «роллаутом» (rollout). Мы запускаем агента в среду и заставляем его выполнять команды согласно оцениваемой стратегии до тех пор, пока он не упрется в терминальное состояние. Сумма всех собранных наград на этом пути формирует полезность (utility) данного прогона.
Важнейшим элементом расчетов выступает фактор дисконтирования ($\gamma$), принимающий значения от 0 до 1. Он математически определяет, насколько сильно нас заботит далекое будущее по сравнению с текущим моментом:
- При $\gamma = 1$ (отсутствие дисконтирования): Награды в будущем имеют точно такую же ценность, как и награды прямо сейчас.
- При $\gamma = 0$ (полное дисконтирование): Будущее вообще не имеет значения. Агент становится экстремально близоруким, учитывая исключительно мгновенный выигрыш на текущем шаге.
- При промежуточных значениях (например, $\gamma = 0,5$): Ценность награды на каждом последующем шаге $i$ искусственно уменьшается путем умножения на $\gamma^i$. Действует экономический принцип: один доллар сегодня стоит дороже, чем один доллар завтра.
В реальных задачах ИИ коэффициент дисконтирования обычно выбирают очень близким к единице (например, 0,99). Это заставляет алгоритм думать на долгосрочную перспективу, но одновременно накладывает мягкий «штраф за длину» траектории, побуждая ИИ достигать цели быстрее.
Самый очевидный метод оценки политики — метод Монте-Карло. Мы запускаем множество независимых случайных роллаутов и просто усредняем полученную полезность. Полученное среднее число называется «значением политики» ($V^\pi(s)$),. Лектор демонстрирует это на коде: для стратегии «всегда выходить» в игре в кости достаточно одного роллаута, так как она детерминирована, и её ценность равна 10. Для стратегии «всегда оставаться» после 20 случайных прогонов средняя полезность колеблется в районе 12,8. Метод Монте-Карло гарантированно сходится к истинному математическому ожиданию, но его погрешность убывает довольно медленно — пропорционально $1/\sqrt{N}$, где $N$ — число симуляций,.
🧮 Точный расчет: уравнения Беллмана и бутстрэппинг 42:24
Вместо проведения миллионов случайных симуляций, ценность политики можно рассчитать абсолютно точно с помощью рекуррентных соотношений динамического программирования. Ключевым понятием здесь становится Q-ценность ($Q(s, a)$) — ожидаемая полезность выполнения действия $a$ в состоянии $s$ с последующим следованием базовой функции ценности $V$,.
Математически это выражается через взвешенную по вероятностям сумму по всем возможным следующим состояниям $s'$:
$$Q(s, a) = \sum_{s'} T(s, a, s') [R(s, a, s') + \gamma V(s')]$$
Алгоритм оценки политики (Policy Evaluation) использует фундаментальную идею бутстрэппинга (bootstrapping) — последовательного обновления текущих значений на основе их собственных предыдущих оценок. Процесс устроен следующим образом:
- Инициализируем ценности всех состояний базовыми значениями (например, 0 для терминальных состояний и -100 для всех остальных как признак того, что путь оттуда еще не найден).
- На каждой итерации $t$ обновляем ценность состояния $s$, приравнивая её к Q-ценности для действия, предписанного нашей политикой $\pi(s)$: $V_t(s) = Q(s, \pi(s), V_{t-1})$.
- Повторяем этот шаг для всех состояний системы до тех пор, пока значения не перестанут значимо меняться.
Для фиксации момента сходимости используется расстояние $L_\infty$ (L-infinity distance) — максимальное абсолютное изменение ценности среди всего массива состояний между двумя последовательными шагами алгоритма. Когда эта дистанция падает ниже заданного порога толерантности (например, $10^{-5}$), вычисления прекращаются. В случае с задачей о трамвае точная оценка политики «ехать на трамвае при первой возможности» успешно сходится за 27 итераций и выдает точный результат -12,. Это означает, что в среднем такая стратегия будет стоить агенту 12 минут времени.
🏆 Поиск идеала: алгоритм итерации ценности 1:09:08
Конечная цель работы с MDP — найти не просто оценку случайной и не всегда удачной стратегии, а вычеслить оптимальную политику ($\pi^*$), обеспечивающую максимально возможную награду в долгосрочной перспективе. Классический метод решения этой задачи, разработанный Ричардом Беллманом, получил название «итерация ценности» (Value Iteration).
Преподаватель обращает внимание на удивительный математический факт: в оптимизации поиск экстремума функции часто бывает несоизмеримо сложнее её простого вычисления, однако в контексте MDP переход от оценки конкретной политики к поиску глобального оптимума требует изменения всего одной строки кода. Вместо жесткого следования действию, которое диктует фиксированная политика, алгоритм Value Iteration на каждом шаге итеративно перебирает абсолютно все доступные действия и выбирает то из них, которое максимизирует Q-ценность:
$$V^t(s) = \max{a \in A(s)} \sum_{s'} T(s, a, s') [R(s, a, s') + \gamma V^_{t-1}(s')]$$
После достижения сходимости по критерию $L_\infty$ оптимальное действие для каждого конкретного состояния извлекается через оператор $\text{argmax}$. Запуск этого алгоритма для задачи о трамвае дает точную ценность оптимальной стратегии, равную -7,3. Это существенно эффективнее, чем слепая езда на трамвае (-12) или постоянная ходьба пешком, которая обошлась бы в -9.
Сама вычисленная оптимальная стратегия выглядит весьма любопытно:
- Находясь в локациях с 1 по 4, агенту следует целенаправленно идти пешком.
- Начиная строго с локации 5, необходимо пытаться састь на трамвай.
Интуитивно это объясняется тем, что на ранних этапах риск поломки трамвая (вероятность 0,4) обходится слишком дорого — агент тратит 2 минуты и топчется на месте в самом начале длинного пути. Однако на середине маршрута (начиная с точки 5) потенциальный прыжок трамвая сразу в точку 10 с вероятностью 0,6 полностью окупает любые возможные неудачи, поскольку у агента остается достаточно «попыток», чтобы компенсировать простой.
В завершение лекции преподаватель отмечает, что для марковских процессов принятия решений оптимальная политика всегда является строго детерминированной, в то время как в теории игр случайный выбор действий (смешанные стратегии) часто дает математическое преимущество,. На следующем занятии начнется разбор обучения с подкреплением (Reinforcement Learning), где агенту придется искать эти оптимумы в условиях, когда функции переходов и наград изначально ему полностью неизвестны.
