Обучение с подкреплением, часть 4: Оптимальный поиск политик с помощью MDP

Обучение агента тому, как принимать решения, которые со временем увеличивают вознаграждение

С возвращением в мой блог об искусственном интеллекте! Мы уже многому научились, поэтому давайте подведем итоги того, что мы уже рассмотрели в моей серии статей по обучению с подкреплением:

Часть 1: Краткое введение в обучение с подкреплением (RL)

Часть 2: Знакомство с марковским процессом

Часть 3: Марковский процесс принятия решений (MDP)

Последний шаг в использовании MDP - это поиск оптимальной политики, о котором мы поговорим сегодня.

К концу этой статьи вы получите базовые знания о:

• Как оценить действие;
• Как реализовать поиск оптимальной политики.

Как вы помните из третьей части, мы описывали и оценивали состояния и действия молодого человека по имени Адам.

Теперь наш агент почти готов помочь ему принять последовательные решения, которые приведут к заработку максимально возможной суммы денег. Давай сделаем это!

Оптимальный поиск политики: как агенты выбирают лучший путь

Теперь, когда мы понимаем MDP, мы можем рассматривать его как среду, в которой работает агент. Чтобы со временем получить максимальное вознаграждение, этому агенту необходимо найти оптимальную политику. То есть он должен определять наилучшие действия, которые нужно предпринять в каждом состоянии.

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

Чтобы помочь нашему агенту сделать это, нам понадобятся две вещи:

1. Способ определения значения состояния в MDP.
2. Ориентировочная стоимость действия, предпринятого в определенном состоянии.

1. Уравнение оптимальности Беллмана.

Уравнение оптимальности Беллмана дает нам средства для оценки оптимального значения каждого состояния, отмеченного V * (s). Он оценивает ценность состояния, вычисляя ожидаемые вознаграждения, которые государство может генерировать.

Вот уравнение оптимальности Беллмана (функция состояния-значения):

В котором:

• P (s, a, s ’) - вероятность перехода из состояния s в состояние s’, когда агент выбирает действие a.
• R (s, a, s ’) - это немедленное вознаграждение от состояния s к состоянию s’, когда агент выбирает действие a.
• 𝛾 - ставка со скидкой. Вознаграждение со скидкой записывается рекурсивно.

Вы можете задаться вопросом, как перевести дисконтированное вознаграждение, которое мы представили в моем последнем посте, в рекурсивную нотацию. Возможно, описанный ниже процесс вычислений даст вам подсказку.

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

2. Алгоритм итераций Q-значений

Само по себе значение оптимального состояния не говорит агенту, какое действие следует предпринять в каждом состоянии. К счастью, вдохновленный вышеупомянутой концепцией оптимального значения состояния, Беллман предоставляет нам аналогичную формулу для оценки значений пар состояние-действие, названную Q-Value.

⏩ Q-Value: оценочное значение действия a, предпринятого в состоянии s; отмечен как Q * (s, a)

Q-Value явно сообщает агенту, какое действие следует выбрать в каждом состоянии в соответствии с оценкой Q-Value.

Вот как вычислить Q-Value:

В котором:

• P (s, a, s ’) - вероятность перехода из состояния s в состояние s’, когда агент выбирает действие a.
• R (s, a, s ’) - это немедленное вознаграждение от состояния s к состоянию s’, когда агент выбирает действие a.
• 𝛾 - ставка со скидкой. Вознаграждение со скидкой записывается рекурсивно.
• max a ’Qk (s’, a ’) - значение оптимального действия a’ в состоянии s ’

Примечание: эта функция предполагает, что агент действует оптимально после того, как выберет действие в текущем состоянии.

Как и в случае с уравнением оптимальности Беллмана, вы начнете с инициализации всех оценок Q-значения равными нулю. Затем вы обновляете их итеративно, используя результаты, вычисленные по этой формуле.

Реализация MDP поиска оптимальной политики

А теперь давайте применим полученные знания в действии! Мы будем использовать MDP нашего друга Адама на рисунке выше, чтобы выполнить поиск оптимальной политики.

Сначала мы вводим 5-кортеж (S, A, P, R, 𝛾) в нашу демонстрацию, чтобы создать среду MDP.

• Мы используем nan для представления состояний, в которые мы не можем попасть из предыдущего состояния.
• Вариант действия - A. Пространство действий с формой (s, a) представляет собой двумерный массив.
• P представляет вероятность перехода из состояния s в состояние s ’ при выборе действия a. Его форма должна быть (s, a, s ’), трехмерным массивом.
• R представляет собой немедленное вознаграждение, полученное после перехода из состояния s в s ’ в результате действия a. Его форма должна быть (s, a, s ’), трехмерным массивом.

import numpy as np
nan = np.nan
actions = [[0, 1, 2], [0, 2], [0]]
P = np.array([
[[1.0, 0.0, 0.0], [0.2, 0.8, 0.0], [0.5, 0.5, 0.0]],
[[0.8, 0.2, 0.0], [nan, nan, nan], [0.0, 0.0, 1.0]],
[[1.0, 0.0, 0.0], [nan, nan, nan], [nan, nan, nan]],
])
R = np.array([
[[20., 0.0, 0.0], [0.0, 0.0, 0.0], [-10., -10., 0.0]],
[[40., 30., 0.0], [nan, nan, nan], [0.0, 0.0, -10.]],
[[70., 0.0, 0.0], [nan, nan, nan], [nan, nan, nan]],
])

Теперь у нас есть среда MDP!

Давайте воспользуемся алгоритмом итераций Q-Value, чтобы получить Q * (s, a),, который содержит оценку действия a в состоянии s.

• Мы используем -inf для представления действий, которые мы не можем предпринять в состоянии s.
• Инициализируйте Q * (s, a) нулями.
• Для каждой итерации примените формулу Q-Value к каждому переходу из состояния s в состояние s ', выполнив действие a, и обновите Q * (s, a) с новым результатом.

Q = np.full((3, 3), -np.inf)
for s, a in enumerate(actions):
    Q[s, a] = 0.0
 
discount_factor = 0.99
iterations = 10
for i in range(iterations):
    Q_previous = Q.copy()
    for s in range(len(P)):
        for a in actions[s]:
            sum_v = 0
            for s_next in range(len(P)):
                sum_v += P[s, a, s_next] * (R[s, a, s_next] +
                          discount_factor * np.max(Q_previous[s_next]))
            Q[s, a] = sum_v
print(Q)

Вот Q, который мы получаем:

Эти строки представляют состояния, столбцы - действия, а числа - награды за действие a в состоянии s.

Долгожданные результаты Адама

Вот что нам говорит демонстрация: лучший способ действовать, когда Адам чувствует усталость, - это пойти немного поспать, затем пойти в тренажерный зал и потренироваться, чтобы стать здоровее, а затем пойти на работу. при максимальной эффективности.

Резюме

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

Понимание MDP - необходимый шаг в углублении ваших знаний о RL - и теперь вы на правильном пути! Вы должны знать, как:

• Смоделируйте марковский процесс принятия решений. Создайте среду и настройте способы вычисления вознаграждения на основе последовательных решений.
• Скидочные вознаграждения. Оцените действие в RL на основе ценности текущих и будущих вознаграждений.
• Реализуйте поиск оптимальной политики. Использование уравнения оптимальности Беллмана и итерационного алгоритма Q-Value.

В моем следующем посте мы углубимся в RL, исследуя Q-обучение. Следуйте за мной, чтобы не пропустить!