Переоценка известного уравнения Беллмана в формулировках обучения с подкреплением и MDP.
В академических кругах часто принято совмещать алгоритм обучения с подкреплением (RL) с формулировкой марковского процесса принятия решений (MDP) и знаменитым уравнением Беллмана. На первый взгляд, это имеет смысл, так как мы часто стремимся найти примерно оптимальные политики для MDP. Однако во многих отношениях RL настолько далеко ушел от истоков динамического программирования, что можно задаться вопросом, действительно ли нам нужны уравнения Беллмана в наших определениях задач.
Эта статья не предназначена для критики самого уравнения Беллмана. Как мы вскоре увидим, это очень элегантная формулировка, которая сводит даже самые запутанные проблемы в одну строку математики. Это настоящий подвиг, учитывая, что многие комбинаторные задачи реального мира имеют больше проблемных состояний, чем атомов во Вселенной.
Когда вы поймете всю сложность и масштаб проблем последовательного принятия решений, вы, вероятно, оцените вклад Беллмана так же, как и я. Однако это не означает, что мы должны использовать их в RL.
Что такое динамическое программирование?
Динамическое программирование берет свое начало в 1950-х годах. В то время Ричард Беллман работал в корпорации RAND в Санта-Монике. И там, сидя под пальмой — или мне так кажется — Ричард Беллман изобрел свое знаменитое уравнение.
Хотя я не буду здесь слишком подробно объяснять динамическое программирование, ключевое понятие состоит в том, что большие проблемы, охватывающие временной горизонт, могут быть разложены на вложенную последовательность более мелких проблем. Эти небольшие проблемы можно решать рекурсивно, получая оптимальную политику принятия решений, обеспечивающую наилучшее действие для каждого состояния проблемы.
Чтобы развернуть динамическое программирование, мы должны иметь возможность определить задачу как MDP, включая формализации (i) пространства состояний, (ii) пространства действий, (iii) функции перехода и (iv) функции вознаграждения (и, возможно, (v) скидки. ставка). Крайне важно, чтобы решения зависели только от текущего состояния — так называемого марковского (или безпамятного) свойства. Если условия соблюдены, мы можем (теоретически) решить задачу с помощью динамического программирования.
Беллман понял, что для каждого состояния может быть определена функция стоимости, отражающая как прямое вознаграждение/стоимость действия, так и (дисконтированную) последующую ценность. Например, мы можем решить, сколько продуктов запасать каждый день, предвидя вероятностные сценарии продаж.
Рассмотрим задачу с тремя состояниями. В каждом состоянии мы можем выполнить действие a∈A. Затем с вероятностью p_s,s’,a мы переходим в другое состояние с ассоциированной функцией значения V(s’). Мы можем определить функции ценности для каждого состояния в виде системы уравнений:
Максимизация каждой функции ценности оптимизирует политику. Короче говоря, если мы знаем функции оптимальной ценности, мы всегда можем выбрать действие, которое максимизирует ожидаемое совокупное вознаграждение. Это решение Беллмана в двух словах.
Прелесть подхода, основанного на функции ценности, заключается в том, что нам не нужно ничего знать о фактической структуре проблемы или правилах принятия решений. Знание функций оптимального значения эквивалентно знанию оптимальной политики.
Классическими методами решения динамического программирования для поиска оптимальных функций значений являются итерация значения и итерация политики. Подробно о них можно прочитать в следующих статьях:
Уравнение Беллмана и проклятия размерности
Только что обсуждавшаяся проблема с тремя состояниями вполне разрешима, но с миллионом состояний система уравнений будет беспорядочной. К счастью, нам не нужно выписывать все уравнения вручную. На самом деле всю систему можно свести к одной строке высочайшего математического изящества:
Это ослепительно, если подумать. Состояние s может быть массивным вектором с элементами, потенциально даже включающими стохастические знания. Действие a может иметь множество ограничений и может быть определено только путем решения сложной математической программы. Обманчиво простая функция вероятности P может скрывать гротескную стохастическую систему, приводящую к множеству возможных исходных состояний s’, все из которых требуют явного вычисления. Последовательная оптимизация в стохастической среде часто бывает очень, очень грязной. И все же Беллману удалось уловить всю эту динамику в одной понятной линии. Это настоящее произведение искусства.
К сожалению, способность смоделировать проблему не означает, что мы действительно можем ее решить. Помните ту систему уравнений с тремя состояниями? На самом деле задача будет содержать не три состояния, а гораздо больше. Предположим, у нас есть миллион состояний с миллионом возможных действий в каждом и миллион состояний (результатов), которых мы можем достичь впоследствии. Это 10¹⁸ возможных вариантов, примерно столько же песчинок на Земле. Те, кто знаком с комбинаторной оптимизацией, знают, как легко решать задачи такого масштаба и далеко за его пределами.
Сам Ричард Беллман прекрасно осознавал вычислительные ограничения своего метода решения и придумал термин «проклятие размерности», чтобы подчеркнуть отсутствие масштабируемости своего подхода. Фактически, это могут быть три проклятия: пространство состояния, пространство действия и пространство результата.
Для многих задач мы просто не можем оптимизировать MDP, независимо от того, сколько вычислительной мощности у нас есть. Вот здесь и приходит на помощь обучение с подкреплением.
Приближение функции значения
Если мы хотим решить уравнение Беллмана, мы должны найти функцию ценности для каждого состояния s∈S. Для каждой отдельной функции ценности мы должны оценить функцию ценности, связанную с каждым потенциальным результатом s’∈S’ (пространство результатов S’ вполне может равняться полному пространству состояний S). Для больших пространств состояний это просто не работает.
Типичный подход к обучению с подкреплением заключается в (i) повторной выборке случайных переходов состояний (вместо исчерпывающей оценки каждого возможного результата) и (ii) замене полного описания состояния набором признаков (избегая необходимости определять функции ценности для каждого отдельного состояние). Таким образом, мы стремимся найти политику, которая, как мы надеемся, близка к оптимальной. Однако есть различные способы добиться этого.
Оставаясь близким подходу динамического программирования, мы могли бы прибегнуть к аппроксимации функции ценности. При таком подходе мы явно пытаемся смоделировать V(s) с помощью аппроксимативной функции. Примерами являются Q-таблицы (SARSA, Q-learning), аппроксимации линейных функций на основе признаков или критические сети. Обратите внимание, что уравнение Беллмана — конечно, в приблизительной форме — используется для выражения политики принятия решений:
Можно сказать, что мы аппроксимируем уравнения Беллмана, и эта аналогия не слишком надуманная.
Тем не менее, эта аналогия не применима ни ко всей области обучения с подкреплением, ни к процессу принятия решений человеком в целом. Если вы приближаетесь к перекрестку, вы, скорее всего, думаете в терминах «налево», «направо», «прямо», а не размышляете о значениях ниже по течению для пути дальше. Многие менеджеры прекрасно способны ежедневно принимать последовательные решения, даже не слышав об уравнениях Беллмана. Бесчисленные алгоритмы RL не пытаются явно моделировать функции значений.
Короче говоря, функции ценности не являются необходимостью для формулирования политики принятия решений.
Целевые функции
Мы медленно подходим к сути этой истории (да, наконец). Если существует так много решений, не требующих определения функций ценности, почему мы продолжаем включать их в наши формулировки задач?
Похоже, что в основе этого соглашения лежит распространенное заблуждение. Короче говоря, уравнение Беллмана нецелевая функция. Это условие оптимальности. Если мы найдем функции оптимального значения, мы найдем оптимальную политику. Однако определение MDP никоим образом не требует функций значений.
Источники путаницы легко увидеть: функция максимизации, намекающая на цель, основы динамического программирования, гарантия оптимальной политики для функций оптимального значения. Однако повторяю: уравнение Беллмана — это просто условие оптимальности. Ее можно решить с помощью динамического программирования, чтобы найти оптимальную политику для MDP. Не больше, не меньше.
Итак, если целью является не уравнение Беллмана, тогда что же это?
Ответ заключается в функции вознаграждения (которая является обязательным компонентом любого MDP). В то время как функции стоимости — несколько абстрактное и искусственное понятие, функции вознаграждения определяют очень ощутимое вознаграждение (или цену) за каждое наше действие. Поскольку мы оптимизируем в течение (потенциально бесконечного) временного горизонта, имеет смысл основывать нашу цель на кумулятивных вознаграждениях.
Для конечных горизонтов принятия решений мы можем просто взять сумму вознаграждений в качестве нашей целевой функции (например, максимизировать продажи на следующей неделе). Для задач с бесконечным горизонтом мы можем взять последовательность вознаграждения со скидкой или просто среднее вознаграждение (Ричард Саттон предлагает последнее). Обратите внимание, что это очень естественные цели, соответствующие тому, как люди обычно принимают решения.
Другие занятия по обучению с подкреплением
Без уравнения Беллмана обычные методы RL, такие как алгоритмы градиента политики, приобретают больше смысла. Фактически, из четырех классов политики, определенных Уорреном Пауэллом, только один (приближение функции ценности) тесно связан с уравнением Беллмана. В альтернативных классах политик, таких как описанные ниже, мы не видим следов динамического программирования:
Вы видите, что обучение с подкреплением определенно не влечет за собой решения уравнения Беллмана, даже приблизительного.
Заключительные слова
Время завершить круг. Обучение с подкреплением — это основа для решения вычислительно сложных последовательных задач принятия решений. Поскольку они могут стать довольно сложными, нам нужны точные и недвусмысленные определения проблем, чтобы общаться с заинтересованными сторонами и находить решения. Для этой цели использование условных обозначений MDP имеет смысл.
Хотя значительная часть алгоритмов RL пытается аппроксимировать функции значений, как это постулируется в уравнении Беллмана, многие решения вообще не следуют парадигме динамического программирования. Поскольку уравнение Беллмана — это условие оптимальности, а не целевая функция, включение его в лучшем случае избыточно, а в худшем — вводит в заблуждение. Во всяком случае, политика принятия решений может быть аппроксимацией уравнения Беллмана, если предположить, что мы придерживаемся ценностно-ориентированного подхода.
Для MDP нужны всего четыре компонента: (i) пространство состояний, (ii) пространство действий, (iii) функция перехода и (iv) функция вознаграждения. Уравнение Беллмана или функции ценности нигде не найдены. Для работы RL нужна целевая функция, но это просто суммированная или усредненная последовательность вознаграждений. Если мы не аппроксимируем функции ценности, уравнение Беллмана просто не играет никакой роли.
Динамическое программирование и соответствующая система рекурсивных функций значений — это образец математического великолепия. Работа Беллмана стала прорывом в последовательном принятии решений, который сохраняет большое теоретическое и практическое значение даже сегодня.
Как и везде, есть только время и место для его использования.
Выводы
- Уравнение Беллмана — это условие оптимальности для решения MDP, а не целевая функция. Основное понятие состоит в том, что наличие функций оптимальной стоимости означает наличие оптимальной политики. Система функций ценности может быть решена с помощью динамического программирования.
- Типичные целевые функции просто максимизируют кумулятивное вознаграждение, например, беря дисконтированный поток вознаграждения или среднее значение с течением времени. Для этого требуются только функции вознаграждения, а не функции ценности .
- Многие решения для обучения с подкреплением не имеют прямого отношения к динамическому программированию. Уравнение Беллмана явно используется только для одного из четырех классов политик, а именно для приближения функции ценности.
- Функции ценности, предложенные Беллманом, не обязательно отражают то, как люди принимают решения. Максимальное (дисконтированное) совокупное или среднее вознаграждение — более естественный способ сообщить о решениях.
дальнейшее чтение
Беллман, Р. (1961). Адаптивные процессы управления: обзор. Издательство Принстонского университета.
Пауэлл, У.Б. (2019). Единая структура стохастической оптимизации. Европейский журнал операционных исследований 275.3 (2019): 795–821.
Саттон, Р.С. и Барто, А.Г. (2018). Обучение с подкреплением: введение. Массачусетский технологический институт Пресс.
Пауэлл, У.Б. и Майзель, С. (2015). Учебное пособие по стохастической оптимизации в энергетике — Часть II: Иллюстрация накопления энергии. IEEE Transactions on Power Systems 31.2 (2015): 1468–1475.
Наик А., Шариф Р., Ясуи Н., Яо Х. и Саттон Р. (2019). Обучение с подкреплением со скидкой — это не проблема оптимизации. https://arxiv.org/pdf/1910.02140.pdf
Википедия (2022). Уравнение Беллмана. https://en.wikipedia.org/wiki/Bellman_equation
Википедия (2022). Динамическое программирование. https://en.wikipedia.org/wiki/Динамическое_программирование
Википедия (2022). Марковский процесс принятия решений. https://en.wikipedia.org/wiki/Markov_decision_process
Википедия (2022). Ричард Беллман. https://en.wikipedia.org/wiki/Richard_E._Bellman
