MDP: состояния, действия, переходы, награды

Урок вводит MDP — формальную рамку, в которой описывают любую задачу RL.

Марковский процесс принятия решений (MDP) — это пятёрка (S, A, P, R, gamma): множество состояний, множество действий, вероятности переходов, функция награды и коэффициент дисконтирования.

Пять компонентов MDP

Марковское свойство

Главная идея, давшая название модели: будущее зависит только от текущего состояния, а не от всей истории. Если состояние описано полно, агенту не нужно помнить, как он сюда попал. В шахматах текущая расстановка фигур полностью определяет дальнейшую игру — путь к ней неважен. Это и есть марковское свойство, и оно сильно упрощает математику.

Детерминированные и стохастические переходы

Переходы бывают предсказуемыми (нажал «вправо» — точно сдвинулся вправо) и случайными (нажал «вправо», но с вероятностью 0.1 поскользнулся и остался на месте). Функция P описывает оба случая. Покажем модель с «скользким полом».

import random
random.seed(0)

# Скользкая клетка: действие "вправо" срабатывает с вероятностью 0.8,
# иначе агент остаётся на месте. Это стохастический переход P(s'|s,a).
def step_right(s):
    if random.random() < 0.8:
        return s + 1      # успех
    return s              # поскользнулся

results = [step_right(0) for _ in range(1000)]
moved = results.count(1)
print("Сдвинулся вправо:", moved, "раз из 1000")
print("Остался на месте:", results.count(0), "раз")
print("Доля успехов:", moved / 1000)

Вывод:

Сдвинулся вправо: 810 раз из 1000
Остался на месте: 190 раз
Доля успехов: 0.81

Как работает под капотом

MDP — это контракт между задачей и алгоритмом. Любой RL-метод предполагает, что мир ведёт себя как MDP: есть конечное (или хотя бы описуемое) состояние, набор действий и стационарные правила переходов и наград. Когда мы пишем gridworld для Q-learning, мы фактически задаём MDP вручную: функция step — это и P, и R вместе. Алгоритм же не знает P и R заранее — он узнаёт их, пробуя действия.

Эпизодические и непрерывные задачи

Эпизодические задачи имеют конец (игра завершилась) — их удобно делить на эпизоды. Непрерывные длятся бесконечно (управление сервером) — для них особенно важно дисконтирование, иначе сумма наград расходится.

Частые ошибки

• Неполное состояние. Если в состоянии не хватает информации (например, скорости мяча — только позиции), марковское свойство нарушается и агент учится плохо.
• Путать P и R. P отвечает на вопрос «куда я попаду», R — «сколько за это дадут». Это разные функции.
• Считать переходы всегда детерминированными. Реальные среды часто стохастичны, и алгоритм должен это переживать.

Итоги

• MDP = (S, A, P, R, gamma) — универсальная рамка для RL-задач.
• Марковское свойство: будущее зависит только от текущего состояния.
• Переходы бывают детерминированными и стохастическими; функция P описывает оба случая.