Марковские процессы принятия решений (MDP): Фундамент обучения с подкреплением

MDP — это строгий математический каркас для моделирования последовательного принятия решений в условиях неопределенности. Процесс описывается кортежем из пяти элементов (S, A, P, R, γ):

• S (States): множество всех возможных состояний среды (все клетки лабиринта).
• A (Actions): множество всех действий, доступных агенту (вверх, вниз, влево, вправо).
• P (Transition Probability): функция вероятности перехода. В реальном мире действия не всегда идеальны. Выбрав команду "вперед", робот из-за проскальзывания колес может сместиться вбок. P(s' | s, a) — это вероятность попасть в состояние s', если в состоянии s было выбрано действие a.
• R (Reward): функция вознаграждения. Агент получает баллы (или штрафы) за каждый переход. Именно эта функция задает цель (например, +100 за выход, -1 за каждый шаг).
• γ (Gamma, Discount factor): фактор дисконтирования. Это коэффициент от 0 до 1, определяющий, насколько сиюминутная награда ценнее отложенной. Он не дает математическому ожиданию бесконечных маршрутов уйти в бесконечность.

Решить MDP — значит найти Оптимальную политику (Policy, π). Политика — это универсальная математическая функция, которая для абсолютно каждого состояния графа говорит агенту, какое действие ему следует выбрать прямо сейчас, чтобы максимизировать суммарную ожидаемую награду в долгосрочной перспективе.

Для нахождения этой политики Ричард Беллман вывел знаменитое Уравнение Беллмана — рекурсивную формулу, связывающую ценность текущего состояния с ценностью его соседей. Решение этого уравнения осуществляется классическими алгоритмами динамического программирования: итерацией по ценности (Value Iteration) или итерацией по политике (Policy Iteration).

Сегодня аппарат MDP является абсолютным фундаментом для Обучения с подкреплением (Reinforcement Learning). Программы, которые обыграли чемпионов мира в Го (AlphaGo), агенты, проходящие сложные видеоигры (StarCraft II), и алгоритмы автопилотов в беспилотных автомобилях — все они опираются на модификации Марковских процессов принятия решений, дополненные глубокими нейронными сетями.