В рамках осеннего курса «AA228 Decision Making Under Uncertainty» в Стэнфордском университете прошла лекция, посвященная приближенным методам планирования в автономном режиме (offline) для частично наблюдаемых марковских процессов принятия решений (POMDP). Приглашенный лектор Сидни, постдок исследовательской лаборатории профессора Майкла Кочендорфера, подробно разобрала, почему точные решения POMDP оказываются практически невычислимыми для реальных задач, и представила ключевые алгоритмы аппроксимации, позволяющие находить эффективные стратегии управления в условиях неопределенности. В центре внимания оказались методы QMDP, Fast Informed Bound (FIB) и интерполяция на основе опорных точек (PBVI), которые находят свое практическое применение в таких критически важных индустриальных системах, как авиационная защита от столкновений ACAS X.
🧩 Проблема размерности и крах точных методов 2:43
Точные методы решения частично наблюдаемых марковских процессов принятия решений (POMDP) сталкиваются с фундаментальным препятствием — так называемым проклятием размерности. На прошлой лекции рассматривались два классических подхода к точному решению: сведение задачи к процессу принятия решений на основе непрерывного пространства убеждений (Belief State MDP) и точная итерация ценности (Exact Value Iteration). Однако оба этих пути ведут к вычислительному тупику даже при умеренных масштабах системы.
Основная сложность Belief State MDP заключается в том, что пространство убеждений (распределений вероятностей над состояниями) является непрерывным. Из-за этого точный расчет функции ценности для каждой точки становится невозможным. С другой стороны, классическая итерация ценности оперирует так называемыми условными планами и связанными с ними альфа-векторами. Проблема в том, что количество необходимых альфа-векторов растет экспоненциально по мере увеличения горизонта планирования $T$.
Сидни приводит наглядную иллюстрацию из учебника — простейшую задачу POMDP (аналогичную классической задаче о плачущем младенце, Crying Baby Problem), где доступны всего два возможных действия и два варианта наблюдений. Даже для скромного горизонта планирования всего в 10 шагов потенциальное количество условных планов (и соответствующих им альфа-векторов), которые алгоритму пришлось бы отслеживать, составляет безумные $10^{338}$.
«Очевидно, что у нас нет абсолютно никаких шансов справиться с таким объемом вычислений, — констатирует лектор. — Иногда в мелких задачах помогает процедура отсечения (pruning) избыточных векторов, но в общем случае точное решение POMDP не масштабируется».
Именно поэтому современная инженерия полагается на приближенные (аппроксимационные) методы. На текущем занятии фокус сделан на автономных (offline) алгоритмах: все тяжелые вычисления производятся заранее, до развертывания системы, а агент получает готовую стратегию (policy) для мгновенного исполнения в реальном времени.
✈️ Алгоритм QMDP: аппроксимация через призму MDP 5:02
Если временно отбросить сложные математические конструкции точных решений и попытаться найти максимально интуитивный подход к POMDP, логично использовать уже накопленные знания о полностью наблюдаемых марковских процессах (MDP). Сидни предлагает разобрать эту логику на классическом для курса примере — системе предотвращения столкновений воздушных судов.
Представьте синий самолет, оснащенный автоматической системой безопасности, которая должна выбирать действия (например, набрать высоту — climb, снизиться — descend или лететь горизонтально — stay level), чтобы избежать опасного сближения с нарушителем — красным самолетом. В реальности параметров геометрии может быть бесконечно много, но для простоты модель сокращена до пяти дискретных геометрических состояний ($S_1, \dots, S_5$).
Если бы эта задача решалась в рамках обычного MDP (где состояние среды известно абсолютно точно), алгоритм рассчитывал бы функцию ценности состояние-действие — так называемую $Q$-функцию ($Q$-function). Для каждой пары «состояние — действие» вычисляется значение $Q(s, a)$, отражающее ожидаемую полезность (utility) при условии, что мы совершаем действие $a$ из состояния $s$ и далее следуем оптимальной стратегии. Онлайн-исполнение такой стратегии элементарно: мы смотрим, в каком состоянии находимся (например, $S_2$), берем вектор значений для доступных действий и выбираем то, у которого $Q$-значение максимально (для маневра уклонения это, скорее всего, будет наводящий подъем с наивысшей полезностью).
Однако в условиях POMDP точное текущее состояние агенту неизвестно. Всё, чем располагает система — это история прошлых наблюдений и совершенных действий. Эта история упаковывается в состояние убеждения (belief state) — распределение вероятностей по всем возможным состояниям. Например, система может с вероятностью 0.6 предполагать, что находится в состоянии $S_2$, но сохранять вероятность 0.2 для $S_1$ и $S_3$.
Идея алгоритма QMDP до гениального проста: почему бы не взять уже рассчитанные для идеального MDP-мира $Q$-значения и не усреднить их, взвесив по текущим вероятностям состояний из нашего убеждения? Математически выбор действия сводится к формуле:
$$\underset{a}{\operatorname{max}} \sum_{s} b(s) Q(s, a)$$
Мы просто интерполируем идеальные значения полезности на основе текущего распределения вероятностей. По словам Сидни, несмотря на свою простоту, метод QMDP работает на удивление хорошо во множестве практических сценариев. Более того, именно эта логика легла в основу реальной международной системы безопасности полетов ACAS X, о которой часто упоминает профессор Кочендорфер.
📐 Альфа-векторы и геометрия пространства убеждений 11:38
Чтобы бесшовно связать QMDP с последующими, более сложными алгоритмами приближенного планирования, лектор переводит описание метода на язык альфа-векторов ($\alpha$-vectors). По сути, это лишь смена математической нотации, но она критически важна для понимания геометрии POMDP.
Вместо записи $Q(s, a)$ вводится понятие альфа-векторов $\alpha_a$, где для каждого конкретного действия $a$ существует свой вектор, длина которого равна количеству состояний в системе. Если в задаче 50 состояний и 4 действия, у нас будет 4 альфа-вектора, каждый из которых содержит 50 числовых элементов. Сидни разряжает атмосферу шуткой, призывая студентов «не путать альфа-вектор с миллениальским вектором».
Каждый элемент альфа-вектора $\alpha_a(s)$ представляет собой ожидаемую будущую полезность выполнения действия $a$ в предположении, что реальным состоянием среды является именно $s$, а дальнейшее управление будет осуществляться по заданной POMDP-стратегии. Оценка функции ценности для текущего убеждения $b$ превращается в скалярное произведение вектора убеждения на альфа-вектор:
$$V(b) = \underset{\alpha \in \Gamma}{\operatorname{max}} \sum_{s} b(s) \alpha(s)$$
В контексте QMDP мы имеем ровно по одному альфа-вектору на каждое доступное действие агента.
На примере упрощенной задачи о плачущем младенце (где есть всего два состояния: «сыт» и «голоден», два действия: «кормить» и «игнорировать», и наблюдения: «плачет» или «тихо») геометрию альфа-векторов можно наглядно отобразить на графике. Поскольку состояний всего два, ось абсцисс можно представить в виде одномерного отрезка от 0 до 1, отражающего вероятность $b(s_2)$ того, что ребенок голоден. Автоматически вероятность состояния «сыт» равна $1 - b(s_2)$, то есть одна координата полностью описывает все пространство убеждений.
Если мы абсолютно уверены, что ребенок сыт ($b(s_2) = 0$), то ожидаемая полезность действия «кормить» составляет -4, а действия «игнорировать» (оптимального в данном случае) равна -1. Если же мы точно знаем, что он голоден ($b(s_2) = 1$), полезность кормления равна -10, а игнорирования — -15. Альфа-вектор для каждого действия графически представляет собой прямую линию, соединяющую эти крайние точки, поскольку операция скалярного произведения линейно интерполирует значения полезности на всем промежутке. Итоговая функция ценности всей стратегии является верхней огибающей (maximum) этих линий. Если наше убеждение в том, что ребенок голоден, составляет, например, 0.1, доминирует вектор действия «игнорировать», а если уверенность достигает 0.9 — доминирует вектор «кормить».
🛑 Ограничения QMDP и верхние границы ценности 18:59
При всей своей элегантности и вычислительной эффективности, метод QMDP таит в себе фундаментальный изъян, на который обращает внимание Сидни. Классический расчет $Q$-значений через уравнение Белльмана для базового MDP учитывает лишь немедленное вознаграждение и ожидаемую полезность следующего шага, исходя из предположения, что в следующий момент времени истинное состояние среды станет полностью известным. В уравнениях QMDP полностью отсутствует математическое описание структуры будущих наблюдений или динамики изменения убеждений.
Лектор приводит шуточную, но доходчивую аналогию:
«Представьте, что в следующий четверг я предложу вам выбрать вариант А или вариант Б. За правильный выбор вы получите $1000, за неверный — ничего. У вас есть возможность потратить силы и время, поехать в Сан-Хосе, где вам точно раскроют правильный ответ. Но одновременно с этим вам обещают, что завтра утром этот ответ и так волшебным образом материализуется у вас в голове. Поедете ли вы в Сан-Хосе? Конечно, нет, в этом нет смысла. Зачем тратить ресурсы на сбор информации, если завтра вы и так все узнаете?»
Именно так «мыслит» алгоритм QMDP. Поскольку он математически закладывает стопроцентную наблюдаемость на следующем шаге, стратегия QMDP фундаментально не способна выбирать действия, направленные на сбор информации (information gathering actions), если они сопряжены с какими-либо издержками. В задачах навигации или игры в прятки, где агенту жизненно необходимо совершать поисковые действия для уточнения координат, QMDP полностью провалится. В системе ACAS X это ограничение некритично, так как радары и датчики непрерывно поставляют информацию извне независимо от маневров самолета, но для других робототехнических систем это может стать фатальным фактором.
Поскольку QMDP исходит из избыточно оптимистичного предположения о полной наблюдаемости среды в будущем, рассчитанная им функция ценности гарантированно формирует верхнюю границу (upper bound) для истинной, оптимальной функции ценности POMDP. Мы физически не способны показать результаты лучше, чем в условиях идеальной осведомленности о состоянии среды.
Для инициализации подобных итерационных алгоритмов, если мы хотим сохранить свойство верхней границы на каждом шаге вычислений, часто применяется концепция «лучшее действие — лучшее состояние» (best-action best-state upper bound). Мы аналитически рассчитываем гипотетический сценарий, в котором агент мог бы бесконечно находиться в самом выгодном состоянии и получать максимальное вознаграждение, что с учетом коэффициента дисконтирования $\gamma$ дает простую формулу бесконечной геометрической прогрессии:
$$\frac{\max_{s,a} R(s,a)}{1-\gamma}$$
Стартуя с этой заведомо завышенной планки, алгоритм в ходе итераций постепенно опускается вниз, сходясь к максимально строгой и точной верхней границе.
🔍 Метод Fast Informed Bound (FIB) 33:54
Существует ли способ получить более точную и поджатую верхнюю границу функции ценности, не скатываясь в экспоненциальный кошмар точных вычислений? Да, и этот метод называется Fast Informed Bound (FIB).
Идея FIB заключается в том, чтобы частично интегрировать модель наблюдений POMDP прямо в итерационный процесс уравнения Белльмана. В отличие от QMDP, который полностью игнорирует вероятности получения тех или иных сигналов от среды на следующем шаге, FIB честно вводит операцию суммирования по всему множеству возможных наблюдений $O$.
Математическая структура FIB сохраняет архитектуру QMDP в том смысле, что алгоритм по-прежнему поддерживает строго по одному альфа-вектору на каждое действие агента. Однако из-за необходимости на каждой итерации перебирать все доступные наблюдения, вычислительная сложность одного шага аппроксимации возрастает пропорционально размеру множества наблюдений $|O|$.
Это классический инженерный компромисс (trade-off): мы платим дополнительным временем процессора на этапе автономных расчетов, но взамен получаем значительно более плотную и реалистичную верхнюю границу функции ценности. На графиках для задачи с младенцем отчетливо видно, насколько кривая FIB лежит ближе к истинному оптимальному решению, нежели избыточно оптимистичная кривая QMDP.
📉 Point-Based Value Iteration (PBVI): движение снизу вверх 37:10
Все рассмотренные выше методы оперировали жестким допущением: количество альфа-векторов жестко ограничено числом доступных действий. Однако оптимальная POMDP-стратегия может иметь сложную структуру, требующую множества векторов под разные зоны пространства убеждений. Прорывным решением в этом направлении стал алгоритм итерации ценности на основе опорных точек (Point-Based Value Iteration, или PBVI). Лектор шутит: «Emphasis on the bass. It's based».
Вместо привязки к действиям, PBVI формирует и поддерживает специальный пул (bag) альфа-векторов, обозначаемый большой греческой буквой $\Gamma$ (гамма), причем каждый вектор в этом пуле жестко ассоциирован с конкретной репрезентативной точкой в пространстве убеждений, взятой из заранее сформированного множества $B$.
В отличие от QMDP/FIB, PBVI строит аппроксимацию функции ценности «снизу вверх», формируя строгую нижнюю границу (lower bound). Для инициализации процесса используется стратегия «лучшее действие в худшем состоянии» (best-action worst-state lower bound), где предполагается, что агент зажат в самом неблагоприятном состоянии среды, но пытается извлечь из него максимум. Как отмечает Сидни, для полноты картины в учебнике описана и альтернативная, более строгая нижняя граница: расчет полезности сценария, при котором агент выбирает одно и то же фиксированное действие навсегда, без оглядки на меняющиеся убеждения. Такая оценка рассчитывается по базовому транзитивному уравнению среды и дает более качественный старт для алгоритма.
Ядром PBVI является операция резервного обновления, известная как backup. Сидни признается, что когда она впервые столкнулась с этим понятием, ей было трудно уложить его в голове, поэтому она предлагает визуализировать процесс без перегрузки формулами:
- У нас есть текущий набор альфа-векторов, фактически задающий некоторую промежуточную стратегию.
- Алгоритм последовательно берет конкретную точку убеждения (например, $b_1$) из набора $B$.
- Для этой точки вычисляется абсолютно новый, улучшенный альфа-вектор, который точнее аппроксимирует ожидаемую полезность, основываясь на данных о том, какие векторы из пула $\Gamma$ захватят доминирование на следующем шаге после выполнения действий и получения гипотетических наблюдений.
- Старый вектор, привязанный к точке $b_1$, безжалостно замещается свежесгенерированным вектором.
Повторяя операцию backup циклически для всего массива опорных точек $B$, мы заставляем ломаную линию функции ценности постепенно выгибаться вверх от стартовой нижней границы, приближаясь к идеальной функции ценности. На тестовой задаче плачущего младенца PBVI, оперируя всего двумя опорными точками убеждений, за несколько итераций сошелся к практически неотличимой от оригинала нижней границе ценности.
🎲 Рандомизированный PBVI и экономия вычислений 57:28
Главный недостаток стандартного PBVI — его вычислительная прожорливость при росте базы опорных точек $B$. Проводить тяжелую операцию backup абсолютно для каждой точки на каждой итерации становится накладно. Для обхода этого узкого места был разработан рандомизированный вариант алгоритма (Randomized PBVI).
Логика рандомизации опирается на красивое геометрическое свойство альфа-векторов. Вместо тотального обновления, алгоритм помещает все точки убеждений в список кандидатов и случайным образом выбирает оттуда одну точку (допустим, $b_2$). Для нее рассчитывается честный backup, генерирующий новый, более приподнятый альфа-вектор.
Когда этот вектор добавляется в общую геометрию функции ценности, он, будучи непрерывной линией, чисто математически может приподнять значения ценности не только в целевой точке $b_2$, но и автоматически улучшить показатели в соседних точках — $b_1$, $b_3$, $b_4$, о существовании которых алгоритм на данном шаге даже не задумывался.
Рандомизированный PBVI проверяет список кандидатов: если за счет нового вектора функция ценности в каких-то точках уже выросла по сравнению с предыдущей итерацией, эти точки объявляются «достаточно хорошими» и досрочно удаляются из списка кандидатов текущего цикла без проведения для них индивидуальных аппроксимаций. Алгоритм берет следующую случайную точку из оставшихся (например, $b_6$), делает backup для нее, закрывает потребности точки $b_5$, и завершает итерацию с колоссальной экономией процессорного времени.
🗺️ Стратегии выбора точек убеждений (Belief Expansion) 1:04:25
Финальный вопрос, который оставался неотвеченным: откуда изначально берутся те самые репрезентативные точки убеждений $B$, на которых строятся алгоритмы PBVI?
Сидни формулирует ключевой постулат: инженеру нет никакого дела до точности функции ценности в тех зонах пространства убеждений, которые агент никогда физически не сможет достичь в процессе функционирования. Она приводит яркий бытовой пример:
«Когда мы играем в баскетбол один на один с моим мужем, а его рост составляет 5 футов 10 дюймов, у меня никогда в жизни не возникнет убеждения (belief), что он способен совершить слэм-данк — забить мяч сверху. Соответственно, мне абсолютно незачем тратить вычислительные ресурсы и закладывать в свою стратегию ходы на случай его данка. Мы должны планировать только для достижимых убеждений».
Самый простой инструмент отбора таких точек — случайное расширение убеждений (Random Belief Expansion). Мы берем стартовое убеждение $b_0$ (с которого гарантированно начинается эксплуатация системы), выбираем случайное действие, моделируем случайное наблюдение через симулятор среды, вычисляем по формулам аппроксимации следующее убеждение и сохраняем его в пул достижимых точек. На следующем шаге процесс повторяется уже для всех накопленных точек. По такой схеме массив точек удваивается с каждой итерацией, очерчивая контуры реальной траектории агента. На этой идее, но со значительно более умным симулятором оптимальных траекторий, построен знаменитый в области POMDP алгоритм SERSOP.
Чуть более продвинутый и геометрически выверенный подход — исследовательское расширение убеждений (Exploratory Belief Expansion). Помимо критерия достижимости, нам критически важно, чтобы опорные точки были максимально равномерно распределены (spread out) по пространству, а не сбивались в кучу в одном узком углу.
Для этого алгоритм из текущей точки симулирует последствия всех возможных действий агента одновременно. Из получившегося веера потенциальных новых точек убеждения выбирается строго та, которая находится на максимальном математическом расстоянии (максимальное удаление по метрике) от абсолютно всех уже имеющихся в пуле $B$ опорных точек. Это гарантирует быструю и эффективную экспансию алгоритма во все уголки достижимого пространства убеждений.
Отвечая на вопросы студентов в конце лекции, Сидни подчеркнула, что описанные методы расширения — это прежде всего эвристика. Ничто не мешает инженеру вручную внедрить в пул $B$ экспертные знания (expert domain knowledge). Если вы заранее знаете, что какое-то редкое состояние критически опасно с точки зрения безопасности (как в авиации), вы можете принудительно добавить соответствующую точку убеждения в алгоритм, чтобы PBVI гарантированно просчитал для нее надежную нижнюю границу ценности.
