MDP дает математическую формулировку задачи обучения с подкреплением
Марковский процесс принятия решений (MDP) - это среда с марковскими состояниями; Марковские состояния удовлетворяют марковскому свойству: состояние содержит всю необходимую информацию из прошлого для предсказания будущего. Математически,
Итак, если я говорю, что состояние S ‹t› является марковским, это означает, что оно имеет все важные представления окружающей среды из предыдущих состояний (что означает, что вы можете отбросить все предыдущие состояния). Подумайте об этом так: когда у вас есть посадочный талон, вам больше не нужен билет, чтобы сесть в самолет; ваш посадочный талон уже содержит всю необходимую информацию о посадке.
MDP формально определяется как:
Давайте рассмотрим пример, чтобы развить интуицию в отношении MDP.
Предположим, вы студент, и на рисунке выше изображен один из ваших школьных дней. Круги и квадрат представляют состояния, в которых вы можете находиться, а слова красного цвета - действия, которые вы можете предпринять в зависимости от того, в каком состоянии вы находитесь; например, в состоянии Class 1 вы можете выбрать, хотите ли вы изучать или проверять свой Facebook, и в зависимости от того, какие действия вы предпринимаете, дается числовое вознаграждение. Также есть узел действия (задняя точка на рисунке), откуда вы можете попасть в разные состояния в зависимости от вероятности перехода; например, после того, как вы решите перейти в Pub из класса 3, у вас есть 0,2 вероятности попасть в класс 1. Этот узел показывает случайность среды, которую вы не можете контролировать. Во всех остальных случаях вероятность перехода равна 1, и если коэффициент дисконтирования равен 1, то MDP можно определить как:
Теперь, когда у нас есть MDP, нам нужно решить его, чтобы найти лучший путь, который максимизирует сумму вознаграждений, что является целью решения задач обучения с подкреплением. Формально нам нужно найти оптимальную политику, которая максимизирует общее вознаграждение, которое может получить агент.
Чтобы решить MDP, мы сначала должны узнать о функции политики и ценности.
Проще говоря, политика говорит вам, какие действия следует предпринять. Это определяется как:
Для MDP политика зависит только от текущего состояния.
Функцию значения можно определить двумя способами: функцию значения состояния и функцию значения действия. Функция значения состояния сообщает вам, «насколько хорошо» ваше состояние, а функция значения действия сообщает вам, «насколько хорошо» выполнять определенное действие в конкретном состоянии. «Насколько хорошо» состояние (или пара состояние-действие) определяется с точки зрения ожидаемых будущих вознаграждений.
Функция состояния-значения определяется как:
Точно так же функция ценности действия определяется как:
Если мы возьмем максимум функции ценности по всем политикам, мы получим функцию оптимального значения. Как только мы узнаем функцию оптимальной стоимости, мы сможем решить MDP, чтобы найти лучшую политику.
Функции цены, которые мы определили выше, удовлетворяют уравнению Беллмана; в нем говорится: «значение начального состояния должно равняться (дисконтированному) значению ожидаемого следующего состояния плюс вознаграждение, ожидаемое по пути».
Например, если мы выберем путь от класса 1 к классу 2, то мы можем записать уравнение Беллмана следующим образом:
Уравнение оптимальности Беллмана можно записать аналогичным образом:
Эти концепции можно легко распространить на несколько путей с разными действиями в разных состояниях. В этом случае уравнение оптимальности Беллмана имеет вид:
Используя приведенное выше уравнение, мы можем найти функцию оптимального значения для каждого состояния в нашем примере MDP для учащихся.
Оптимальная ценность действия может быть выражена аналогичным образом как:
Это уравнение дает следующий результат в нашем примере MDP для студентов.
Когда у нас есть функция «действие-значение», мы можем найти оптимальную политику, взяв их максимум. Формально это было бы:
Оптимальная политика, которая максимизирует вознаграждение для нашего ученика, показана красными дугами на рисунке ниже.
Резюме:
MDP математически представляет проблему обучения с подкреплением, и цель решения MDP - найти оптимальную политику, которая максимизирует сумму ожидаемого вознаграждения. Поиск оптимальной политики становится проще, когда у нас есть функция ценности действия. Интуиция, лежащая в основе уравнения Беллмана, упрощает процесс нахождения функции ценность-действие.
Использованная литература:
PS: Я написал этот пост, основываясь на моем понимании обучения с подкреплением. Мы будем благодарны за любые предложения / улучшения в отношении содержания и / или стиля письма.
