Итерация по стратегиям (Policy Iteration) в марковских процессах принятия решений

Математическая философия алгоритма Итерации по стратегиям строится на жестком разделении процесса оптимизации на два чередующихся этапа: Оценку стратегии (Policy Evaluation) и Улучшение стратегии (Policy Improvement). Алгоритм стартует с абсолютно любой, даже совершенно нелепой, случайной стратегии (например, робот всегда выбирает движение вперед, независимо от препятствий). Стратегия жестко фиксирует, какое действие агент предпримет в каждом состоянии. Из-за этой фиксации возможность выбора пропадает, и сложный Марковский процесс принятия решений алгебраически схлопывается в обычную марковскую цепь с вознаграждениями (Markov Reward Process, MRP).

На первом этапе (Оценка стратегии) алгоритм должен точно вычислить, насколько хороша эта текущая случайная стратегия. Для этого используется уравнение Беллмана, которое превращается в систему линейных алгебраических уравнений. Ценность каждого состояния V(s) равна математическому ожиданию немедленной награды плюс дисконтированная ценность состояния, в которое система перейдет на следующем шаге при следовании текущей стратегии. Поскольку стратегия фиксирована, матрица переходных вероятностей известна и константна. Аналитик (или компьютер) решает эту гигантскую систему линейных уравнений (через обращение матриц или итерационные численные методы Гаусса-Зейделя) и получает точный вектор ценностей для всех возможных состояний системы.

После того как каждое состояние получило точную оценку своей перспективности, наступает второй этап (Улучшение стратегии). Алгоритм применяет жадный поиск (Greedy Approach). Для каждого состояния агент перебирает абсолютно все доступные действия (даже те, которые не входили в текущую стратегию) и смотрит: а что, если в этом конкретном состоянии сделать одно отклонение от плана (выбрать другое действие), а затем продолжить следовать старой стратегии? Агент использует уже вычисленные ценности соседних состояний, чтобы найти действие, которое максимизирует сумму немедленной награды и ожидаемой ценности перехода. Найденное жадное действие записывается в новую, обновленную стратегию.

Теорема об улучшении стратегии (Policy Improvement Theorem) Ховарда является одной из самых красивых теорем в исследовании операций. Она строго доказывает, что если новая (жадная) стратегия отличается от старой, то она гарантированно является строго лучше старой (или как минимум не хуже) по показателю ожидаемого вознаграждения. Алгоритм зацикливается: новая стратегия снова подвергается оценке, решается новая система уравнений, и стратегия снова улучшается. Как только на этапе улучшения ни одно состояние не изменит своего действия (стратегия стабилизировалась), математика дает железную гарантию: найденная стратегия является абсолютно оптимальной политикой Беллмана. Несмотря на необходимость решения системы линейных уравнений на каждом шаге, алгоритм Policy Iteration феноменально эффективен и сходится на порядок быстрее (по количеству итераций), чем конкурирующий алгоритм Value Iteration, являясь эталоном для проектирования систем автономной навигации и управления портфелями ценных бумаг.