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

Чем эта задача отличается от предыдущих

Во всём курсе до сих пор были данные: пары «вход — правильный ответ» или просто выборка из распределения. Здесь их нет. Есть среда, которая отвечает на действия, и последствия, растянутые во времени.

Формально задача — это пятёрка $(S, A, P, R, \gamma)$: состояния, действия, вероятности перехода, награды и дисконт. Марковость означает, что $P$ зависит только от текущего состояния и действия, а не от истории.

$$\htmlData{k=ret}{G_t} = \sum_{k=0}^{\infty} \htmlData{k=gamma}{\gamma}^{k} r_{t+k+1}$$

Заметьте, что максимизируется возврат, а не награда на шаге. Отсюда все трудности: действие, дающее хорошую немедленную награду, может вести в плохое состояние, и наоборот.

Что делает дисконт

Дисконт обычно объясняют как «будущее менее важно», и это верно, но нечисло. Точное содержание — три вещи сразу.

Сходимость. При ограниченных наградах $|r| \le R$ ряд сходится и $|G| \le R/(1-\gamma)$. Без дисконта в бесконечной задаче сумма может расходиться, и «максимизировать» становится бессмысленно.

Горизонт. Величина $\frac{1}{1-\gamma}$ — характерное число шагов, которое «видит» агент:

$\gamma$	горизонт $\frac{1}{1-\gamma}$
$0.5$	$2$
$0.9$	$10$
$0.99$	$100$
$0.999$	$1000$

Сжатие. Это самое важное для следующих уроков: $\gamma < 1$ делает оператор Беллмана сжимающим, и отсюда существование и единственность решения (урок 030).

Стоит понимать, что дисконт — часть постановки задачи, а не гиперпараметр решателя. Меняя $\gamma$, вы меняете, какую задачу решаете; оптимальная политика при $\gamma = 0.5$ и при $\gamma = 0.99$ — разные политики, и обе правильные для своей задачи.

Потяните дисконт и посмотрите на стрелки в дальних от цели клетках.

цель стена

дисконт γ

0.9

проходов

2

цена шага

-0.04

горизонт 1/(1−γ)

10

значение старта

-0.076

изменение за проход

7.7e-1

проходов до сходимости

7

При $\gamma = 0.9$ и цене шага $-0.04$ значения сходятся к такой картине:

$0.621$	$0.734$	$0.860$	$1.000$
$0.519$	стена	$0.734$	$0.860$
$0.427$	$0.519$	$0.621$	$0.734$
$0.344$	стена	$0.519$	$0.621$

Проверьте одну клетку руками: значение соседа цели равно $-0.04 + 0.9\cdot 1 = 0.86$. Следующая за ней — $-0.04 + 0.9\cdot0.86 = 0.734$. Вся таблица получается этим правилом, и в этом весь урок 030.

Про скорость сходимости — поправка

Стандартное утверждение: ошибка убывает как $\gamma^k$. Проверим на этой сетке:

проход $k$	$\|V_k - V^*\|_\infty$	отношение
$1$	$0.774$	—
$2$	$0.697$	$0.90$
$3$	$0.627$	$0.90$
$10$	$0$	—

Первые проходы дают ровно $\gamma$, как и обещано. Но затем ошибка становится точным нулём, а не продолжает убывать геометрически. Причина в том, что среда детерминирована: как только до каждой клетки дошёл её оптимальный путь целиком, значение перестаёт меняться вовсе.

Отсюда вывод, полезный на практике: $\gamma^k$ — это верхняя граница для худшего случая. На детерминированных задачах с коротким диаметром сходимость наступает за число проходов порядка диаметра, независимо от $\gamma$. В этой сетке — за семь проходов и при $\gamma = 0.5$, и при $\gamma = 0.99$.

Что делает цену шага важной

Слагаемое $-0.04$ за каждый шаг выглядит технической деталью, но именно оно задаёт задачу. Уберите его — и агенту станет всё равно, сколько идти: любой путь к цели даст одно и то же значение при $\gamma = 1$ и почти одно и то же при $\gamma$ близком к единице. Сделайте его большим по модулю — и цель перестанет окупать дорогу.

Это первое проявление общей проблемы: награда задаёт задачу целиком, и ошибка в её формулировке не лечится ни алгоритмом, ни объёмом данных. Урок 130 покажет, во что это выливается, когда награду не пишут руками, а обучают.

Итог

• MDP — это $(S, A, P, R, \gamma)$; марковость означает, что история сжата в состояние.
• Максимизируется возврат, а не награда: последствия растянуты во времени.
• Дисконт делает три вещи сразу — обеспечивает сходимость, задаёт горизонт $\frac{1}{1-\gamma}$ и делает оператор Беллмана сжимающим.
• $\gamma$ — часть постановки, а не настройка решателя.
• Оценка $\gamma^k$ — верхняя граница; на детерминированных задачах сходимость бывает точной за число проходов порядка диаметра.