MDP — Марковский процесс принятия решений

Формальная рамка RL: состояния, действия, переходы, награды и коэффициент дисконтирования.

Ключевые тезисы

2 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.

Пять компонентов, задающих любую задачу RL.

M = ⟨ S, A, P (s^{'} ∣ s, a), R (s, a), γ ⟩

Обозначения

Марковское свойство: будущее зависит только от текущего состояния, а не от всей истории.
$\gamma \in [0,1)$ — коэффициент дисконтирования: насколько важна отложенная награда. При $γ = 0$ агент близорук, при $γ \to 1$ — планирует далеко.
POMDP — обобщение на случай, когда состояние наблюдается частично (почти все реальные задачи).

G_{t} = k = 0 \sum \infty γ^{k} r_{t + k + 1}

Обозначения

Возврат — то, что агент на самом деле максимизирует

Value iteration и policy iteration — с чего начинается RL.

V_{k + 1} (s) = a max s^{'} \sum P (s^{'} ∣ s, a) [R (s, a) + γ V_{k} (s^{'})]

Обозначения

Value iteration: повторяем до сходимости

Policy iteration чередует оценку политики и её улучшение; сходится за меньшее число итераций, но каждая дороже.
Оба метода требуют знания $P$ и $R$ — в реальных задачах их обычно нет, отсюда и появляется обучение с подкреплением.
Model-based RL сначала выучивает модель среды, затем планирует в ней — это резко экономит взаимодействия.

Основы обучения с подкреплением

Три базовых элемента задачи. Дизайн награды определяет поведение агента сильнее алгоритма.

V(s) оценивает ожидаемую отдачу из состояния, Q(s,a) — из пары состояние–действие.

Off-policy метод: агент учит оптимальную Q-функцию независимо от того, как исследует среду.

On-policy аналог Q-обучения: обновление идёт по реально выбранному следующему действию.

Прямая оптимизация параметров политики по градиенту ожидаемой награды.

Актор выбирает действия, критик оценивает их ценность — гибрид двух семейств методов.

Q-обучение с нейросетевой аппроксимацией: сеть предсказывает Q-значения по пикселям экрана.

Устойчивый policy-gradient метод с ограничением величины обновления политики.