Введение в обучение с подкреплением 3 — динамическое программирование

Это первый день моего участия в августовском испытании обновлений, подробности о мероприятии:Испытание августовского обновления

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

Мы знаем оптимальную стратегию $\pi$ Соответствующее значение является функцией оптимального значения, и его решение делится на два метода: итерация стратегии и итерация значения. В этом разделе подробно описаны оба метода.

Все MDP, обсуждаемые в этом разделе, являются известными MDP. Известный означает, что известны динамические характеристики среды, т.е. $p(s',a | s,a)$ Эта функция плотности вероятности определяется.

итерация политики

Итерацию политики можно разделить на два этапа: оценка политики и улучшение политики. Оценка стратегии дает стратегию $\pi$ Решение функции значения состояния $v_{\pi}(s)$ , а улучшение стратегии заключается в поиске лучшей стратегии $\pi'$ , так что $v_{\pi'}(s)>v_{\pi}(s)$ .

Оценка политики

Получение аналитического решения

Оценка стратегии дает стратегию $\pi$ Решение уравнения Беллмана $v_{\pi}(s)$ . Мы знаем, что уравнение Беллмана имеет следующий вид:

v_{\pi}(s)=\sum_a \pi(a|s)\sum_{s',r}p(s',r|s,a)[r+\gamma v_{\pi}(s')]\;\;,\forall s\in S

мы кладем $v_{\pi}(s),v_{\pi'}(s)$ Видно как неизвестное, это можно увидеть $v_{\pi}(s),v_{\pi'}(s)$ Между ними существует линейная зависимость. из-за государства $s$ больше одного, поэтому $v_{\pi}(s)$ Можно записать в векторной форме:

v_{\pi}(s)= \begin{bmatrix} v_{\pi}(s_1)\\v_{\pi}(s_2)\\...\\v_{\pi}(s_S) \end{bmatrix}_{|S|\times1}

На самом деле задача состоит в том, чтобы решить $|S|$ Система линейных уравнений с неизвестными величинами. Мы используем матрицу для представления $v_{\pi}(s),v_{\pi'}(s)$ Связь между, очевидно, матрицей должна быть $S\times S$ размерный. Далее мы еще больше упростим систему уравнений, которую можно разбить на следующие две части:

v_{\pi}(s)=\sum_a \pi(a|s)\sum_{s',r}p(s',r|s,a)\cdot r+\sum_a \pi(a|s)\sum_{s',r}p(s',r|s,a)\cdot \gamma v_{\pi}(s')\;\;,\forall s\in S

Соблюдая левую часть выражения, на самом деле $s'$ можно интегрировать, становится $\sum_{r}p(r|s,a)r$ , которое находится в форме ожидания, которое определяется как функция вознаграждения $r(s,a)$ , представляющий данную политику $\pi$ вниз, статус $s$ действовать $a$ ожидаемое вознаграждение. Тогда левый элемент становится $\sum_a \pi(a|s)\cdot r(s,a)$ . мы знаем $\pi$ является распределением вероятностей относительно а, и интеграл от а может исключить а, и, наконец, левый член может быть записан как $r_{\pi}(s)$ . $r_{\pi}(s)$ Является $|S|\times 1$ матрица.

Затем обратите внимание на член в правой части формулы, $\gamma$ является константой, интегрируя r, становится $\gamma \sum_a \sum_{s'}\pi(a|s)p(s'|s,a)v_{\pi}(s')$ ,сделать $P_{\pi}(s,s')=\sum_a \sum_{s'}\pi(a|s)p(s'|s,a)$ , указывая на состояние $s,s'$ Матрица вероятности перехода между $|S|\times |S|$ . Тогда правый член окончательно может быть записан как $\gamma P_{\pi}(s,s')v_{\pi}(s')$ .

Наконец, формула упрощается до:

v_{\pi}(s)=r_{\pi}(s)+\gamma P_{\pi}(s,s')v_{\pi}(s') \\ v_{\pi}(s_i)=r_{\pi}(s_i)+\gamma \sum_{j=1}^{|S|} P_{\pi}(s_i,s_j)v_{\pi}(s_j)

Далее он сокращается как:

v_{\pi}=(I-\gamma P_{\pi})^{-1}r_{\pi}

Это аналитическое решение. очевидно $|S|\times 1$ размерная матрица. Из-за задействованных матричных операций временная сложность составляет $O(|S|^3)$ .

Вывод численного решения

Аналитические решения включают матричные операции и требуют большого объема вычислений Мы можем решить численно путем итерации. Мы строим массив $\{v_k(s)\},k\in[1,\infty]$ . в $v_k$ при включении $|S|$ Функциональный вектор функций значения состояния. $в_к, в_{к+1}$ Согласно уравнению Беллмана мы можем записать его итеративное соотношение:

\begin{aligned} v_{k+1}(s) =& E_{\pi}[R_{t+1}+\gamma G_{t+1}\;|\;S_t=s] \\ =&E_{\pi}[R_{t+1}+\gamma v_{k}(s')\;|\;S_t=s] \\ =&\sum_a \pi(a|s)\sum_{s',r}p(s',r|s,a)[r+\gamma v_{k}(s')] \\ \end{aligned}

фактически $v_1,v_2,...,v_{k}$ является приближенным решением функции цены, полученным путем итерации, и наша цель состоит в том, чтобы заставить его сходиться к $v_{\pi}$ . это $v_1$ Сначала он определяется случайными действиями, т. е. случайным начальным вектором функции.

数值解推导过程图解.jpg

Улучшение политики

когда мы сможем оценить $\pi'$ , мы хотим узнать разницу с текущей стратегией $\pi$ Что лучше, надо сравнивать $v_{\pi},v_{\pi'}$ . Это приводит к теореме об улучшении политики.

теорема об улучшении политики

【Определение】дано $\pi,\pi'$ , если для любого состояния s имеем $q_{\pi}(s,\pi'(s))\geq v_{\pi}(s)$ ,но $\forall s\in S,v_{\pi'}(s)\geq v_{\pi}(s)$ .

Эта теорема превращает первоначальную потребность в двух функциях значения состояния в только одну. $v_{\pi}(s)$ Просто хорошо.

Как это доказать?

Давайте сначала рассмотрим функцию «действие-ценность»:

q_{\pi}(s,a)=E[R_{t+1}+\gamma \cdot v_{\pi}(S_{t+1})\;|\;S_t=s,A_t=a] =\sum_{s',r}p(s',r|s,a)[r+\gamma v_{\pi}(s')]

В частности, $R_{t+1}$ и $\pi$ на самом деле не имеет значения, потому что в (s, a) среднее вознаграждение $R_{t+1}$ было получено, и $\pi$ Влияет на состояние следующего момента $s_{t+1}$ Для выбора действия, $R_{t+2}$ и $\pi$ только актуально.

мы кладем $\pi'(s)$ Замена действия $a$ ,Выражать $t$ Действие момента определяется $\pi'$ определено, действие в следующий момент все еще определяется $\pi$ Итак $R_{t+1}$ и $\pi'$ связанных, после вознаграждения и $\pi$ Процесс получения выглядит следующим образом:

\begin{aligned} v_{\pi}(s)\leq & q_{\pi}(s,\pi'(s)) \\ =& E[R_{t+1}+\gamma \cdot v_{\pi}(S_{t+1})\;|\;S_t=s,A_t=\pi'(s)] \\ =& E_{\pi'}[R_{t+1}+\gamma \cdot v_{\pi}(S_{t+1})\;|\;S_t=s] \\ \leq& E_{\pi'}[R_{t+1}+\gamma \cdot q_{\pi}(S_{t+1},\pi'(S_{t+1}))\;|\;S_t=s] \\ \leq& E_{\pi'}[R_{t+1}+\gamma R_{t+2} +\gamma^2\cdot q_{\pi}(S_{t+2},\pi'(S_{t+2}))\;|\;S_t=s] \\ \leq& E_{\pi'}[R_{t+1}+\gamma R_{t+2} +\gamma^2 R_{t+3}+...+...\;|\;S_{t+1}=s] \\ =& v_{\pi'}(s) \end{aligned}

Как с помощью этой теоремы найти оптимальную стратегию? Более интуитивный метод — жадный метод.

Для каждого состояния s выберите политику с наибольшей функцией значения действия. $\pi'$ ,Сейчас

\forall s\in S,\pi'(s)=\arg\max_a q_{\pi}(s,a)==\arg\max_a \sum_{s',r}p(s',r|s,a)[r+\gamma v_{\pi}(s')]

Согласно теореме об улучшении политики, если $q_{\pi}(s,\pi'(s))\geq v_{\pi}(s)$ , затем обновите политику. до определенного момента $v_{\pi'}(s)= v_{\pi}(s)$ При , алгоритм сошелся, и оптимальное уравнение Беллмана в этот момент выполняется, и стратегия в этот момент является нашей оптимальной стратегией.

Простая блок-схема выглядит следующим образом:

策略迭代流程图.jpg

итерация значения

В итерации политики наши шаги в каждой итерации: $\pi$ оценивать $v_{\pi}(s)$ , а затем используйте жадный метод для улучшения стратегии. Но при оценке политики, чтобы заставить функцию ценности сходиться к $v_{\pi}$ Нам нужно несколько раз выполнить итерацию для всех состояний, пока функция значения не сойдется, что вызывает итерацию матрешки в итерации, а расчет очень хлопотный.

Может ли это уменьшить количество итераций? Один из способов сделать это — выполнить только одну итерацию во время оценки, то есть просмотреть все состояния один раз, а затем внести улучшения в политику.

\begin{aligned} v_{k+1}(s) =& \max_a E_{\pi}[R_{t+1}+\gamma G_{t+1}\;|\;S_t=s] \\ =&\max_a E_{\pi}[R_{t+1}+\gamma v_{k}(s')\;|\;S_t=s] \\ =&\max_a \sum_a \pi(a|s)\sum_{s',r}p(s',r|s,a)[r+\gamma v_{k}(s')] \\ \end{aligned}

На самом деле это уравнение оптимальности Беллмана. Это устраняет необходимость повторных итераций для решения $v_{\pi}(s)$ .

Понять разницу между итерацией ценности и итерацией стратегии из процесса

Процесс итерации значения: $v_1\rightarrow v_2\rightarrow v_3\rightarrow ...\rightarrow v_*$
Процесс итерации политики: $\pi_1\rightarrow v_{\pi_1}\rightarrow\pi_2\rightarrow v_{\pi_2}\rightarrow \pi_3\rightarrow v_{\pi_3}\rightarrow ...\rightarrow \pi_*\rightarrow v_{*}$

Очевидно, что итерация политики должна сначала найти точную функцию значения состояния, а затем продолжать обновлять политику. Обновление — это обход всего пространства состояний. Итерация значения заключается в остановке оценки политики сразу после обхода, чтобы каждое состояние обновлялось только один раз и вычислялась функция приблизительного значения.

Хотя вычисление итерации значения упрощено, ему все же необходимо один раз пройти через пространство состояний.Этот метод также называетсяСинхронное динамическое программирование (Synchronous DP).

На самом деле существует более упрощенный подход, называемый итерацией политики на месте. принадлежатьАсинхронное динамическое программирование Асинхронный DPметод. То есть нам не нужно держать синхронизированными все обновления состояния.При определенном обновлении каждое состояние в наборе состояний S не обновляется, а только функция значения одного из состояний случайным образом выбирается для обновления, а остальные состояния остаются без изменений. . Таким образом, вычисление сокращается, и сходимость может быть достигнута быстрее.

резюме

В этом разделе описывается, как использовать динамическое программирование для решения оптимальных политик. Динамическое программирование является алгоритмом в модельном случае, поскольку мы предположили, что динамика среды известна. Динамическое программирование делится на итерацию стратегии и итерацию значения. Итерация политики делится на два этапа: один — оценка политики, а другой — улучшение политики. Оценка политики используется для расчета функции стоимости для данной политики и является точным расчетом. Улучшение политики использует теорему улучшения политики для сравнения функций ценности двух политик для обновления политики. Оценка стратегии требует итеративного расчета, а итерация стратегии сама по себе является итеративным процессом, включающим итерацию за итерацией, что делает расчет очень сложным, поэтому существует итерация значения. Видно, что итерация значения — это особая итерация стратегии, основная идея которой состоит в том, чтобы итерировать только один шаг при вычислении функции значения и аппроксимировать функцию значения. Итерация значения также известна как синхронное динамическое программирование. Несмотря на вычислительное упрощение, каждое состояние пространства состояний обновляется один раз в итерации значения, и пространство состояний все же необходимо пройти один раз. По этой причине некоторые люди предложили асинхронную итеративную итерацию стратегии «идея на месте». То есть нам не нужно поддерживать синхронизацию всех обновлений состояния.При определенном обновлении каждое состояние в наборе состояний S не обновляется, а только функция значения одного из состояний случайным образом выбирается для обновления, а остальные состояния остаются без изменений. .

Ссылаться на

[1] Саттон Барто «Обучение с подкреплением (второе издание)».

[2] Динамическое программирование — обучение с подкреплением, глава 4 — Zhihu (zhihu.com)

[2] [Машинное обучение] Серия выводов на доске (35) ~ Динамическое программирование обучения с подкреплением_bilibili