1-Конечные марковские процессы принятия решений
В этой статье мы рассмотрим принцип и свойства марковских процессов принятия решений в обучении с подкреплением.
Свойства цепи Маркова:
Цепь Маркова — это специальный стохастический процесс, целью которого является предсказание будущего состояния процесса на основе предыдущих состояний. Цепи Маркова можно различать по разным порядкам. Под порядком подразумевается, сколько предыдущих состояний было использовано для предсказания будущего состояния. В нашем случае мы ориентируемся на цепи Маркова первого порядка, что означает, что будущее напрямую связано с настоящим, а не с прошлыми состояниями (см. формулировку в уравнении ниже).
§ Пример:
Рассмотрим пример прогноза погоды с использованием цепей Маркова первого порядка, что означает, что необходимая и достаточная информация для предсказания завтрашних параметров погоды уже имеется в настоящем, а не в предыдущие дни.
Предыстория марковского процесса принятия решений:
Процесс принятия решений по Маркову (MDP) – это математическая основа для моделирования процесса принятия решений в среде с марковскими свойствами. : Цепи Маркова первого порядка при переходе между состояниями, исходы подчиняются статической вероятности перехода в каждом состоянии, а количество состояний находится под контролем, что означает, что оно не бесконечно велико.
Функция, которая характеризует этот MDP, – это динамическая функция eq. (3.2), позволяющее рассчитать вероятность определенных следующих состояний с определенным вознаграждением при условии текущего состояния и действия, которое будет выполнено в этом состоянии.
§ Пример:
В этом примере мы покажем, как можно получить разные награды за одинаковые условия начала и результата:
Мобильному роботу поручено собирать пустые банки из-под напитков в офисе. Для простоты предположим, что можно выделить только два уровня заряда (состояний), составляющих небольшой набор состояний S = {Высокий заряд, Низкий заряд}.
В каждом состоянии агент может решить, следует ли активно искать банку в течение определенного периода времени, оставаться на месте и ждать, пока кто-нибудь принесет ему банку, или вернуться на свою базу, чтобы перезарядить батарею.
Тогда наборы действий:
Теперь давайте рассмотрим случай, когда нас больше заботит то, чтобы робот обращал больше внимания на заряд батареи, чем на сбор пустых банок.
Из состояния «Низкий заряд» после выполнения соответствующих действий поиск или ожидание вознаграждение делится на два возможных результата с соответствующими вероятности.
Это моделирование вознаграждения сообщает роботу, что можно продолжать проверять наличие пустых банок; однако следует быть очень осторожным с уровнем заряда батареи.
Чтобы объяснить этот запрос с диаграммой выше:
Теперь мы рассматриваем моделирование вознаграждения, при котором основное внимание уделяется не уровню заряда батареи, а количеству собранных пустых банок с учетом уровня заряда батареи, когда робот находится в состоянии «Низкий заряд». (Здесь нет разделения вознаграждения после каждого действия)
Как вы заметили, мы уделили много внимания последнему уравнению динамическая функция. Причина в том, что это уравнение является фундаментальным и лежит в основе принципа MDP; понимание этого имеет решающее значение для следующих шагов. На основе динамической функции мы можем вывести ряд различных важных уравнений, которые позволяют нам делать множество оценок для различных ситуаций с различными вычислительными перспективами, например:
Вот сумма всех возможных распределений вероятностей вознаграждения, которые агент может получить, выполнив действие «а» в состоянии «s», а затем перейдя в следующее состояние. С помощью этой новой функции мы получаем распределение вероятности достижения следующего состояния путем выполнения действия «а» в состоянии «s», независимо от возможности получения вознаграждения.
Расчет функции ценности и функции ценности действия в MDP:
Выражение функции стоимости с помощью MDP:
Вывод функции ценности для случая MDP можно увидеть из следующих уравнений:
§ Пояснение:
Попробуем объяснить, как рассчитывается совокупное вознаграждение при переходе от определенного состояния к конечному, и какие факторы влияют на этот процесс:
Если мы определим вероятностную политику для агента, где его вероятностное решение в каждом состоянии показано на левом рисунке, и после выполнения «N» эпизодов, мы обнаружим, что вероятность пребывания агента в определенных состояниях не соответствует оптимальному прохождению политика (в синем пути).
Это предполагаемое перемещение или переход агента между состояниями среды зависит от его политической функции и динамической функции среды, которые мы уже видели в предыдущем разделе.
Этот правый рисунок отражает ожидаемое движение между состояниями для достижения конечного состояния, когда мы часто начинаем с начального состояния (выделено желтым цветом). С этой точки зрения перехода между состояниями рассчитывается предполагаемое кумулятивное вознаграждение.
§ Пояснение:
Чтобы дать представление о том, насколько интенсивны вычисления и какие комбинаторные возможности задействованы в вычислении функций ценности в определенных состояниях, далее будет рассмотрена процедура вычисления:
- В качестве начального состояния для расчета мы берем это состояние:
2. С помощью политики агента мы получаем все возможные действия, а также вероятность их выполнения в состоянии:
3. Теперь мы выбираем действие в качестве примера для дальнейшего расчета в состоянии:
4. С помощью функции policy мы получаем вероятность выполнения данного действия от агента в состоянии:
5. С точки зрения того, что агент находится в состоянии и действие, вероятно, будет выполнено, мы затем используем динамическую функцию для определения всех возможных следующих состояний и соответствующих им вознаграждений:
6. Если мы ограничимся следующим состоянием и его вознаграждением, то получим вероятность возникновения этого события из динамической функции, а такие элементы, как следующее вознаграждение и функция значения для следующего состояния, будут включены в дальнейший расчет:
Выражение функции ценности действия с помощью MDP:
По функции ценности действия мы уже выполнили действие в текущем состоянии и теперь хотим оценить совокупное вознаграждение за оставшиеся следующие состояния в этой марковской среде.
Ссылка:
- Обучение с подкреплением для киберфизических систем: с примерами кибербезопасности, Chong Li, Meikang Qiu
- Обучение с подкреплением: введение, Ричард С. Саттон и Эндрю Дж. Барто.
