Дорога к обучению с подкреплением
В первой части я обсудил некоторые основные концепции для создания основы для обучения с подкреплением (RL), такие как состояния Маркова, цепь Маркова и процесс принятия решений Маркова (MDP). Задачи обучения с подкреплением строятся поверх MDP.
MDP — это четырехкортежная модель (𝓢, 𝓐, 𝓟, 𝓡), где s ∈ 𝓢 — состояние, a ∈ 𝓐 — действие, совершаемое, когда агент состояние s, 𝓟(s' | s, a) — матрица вероятности перехода в состояние s' из s под действием действия a (или какой-либо другой функции плотности вероятности некоторого условия), а r(s, a) ∈ 𝓡 — функция вознаграждения.
Функция политики: функция политики, обычно обозначаемая π в литературе по RL, определяет отображение из пространства состояний 𝓢 в пространство действий 𝓐.
Цель MDP — найти оптимальную политику, максимизирующую долгосрочное вознаграждение.
Фактор скидки
MDP требует понятия дискретного времени t, поэтому MDP определяется как процесс стохастического управления с дискретным временем. В контексте RL каждый MDP параметризуется коэффициентом дисконтирования γ (гамма), который определяет важность будущих вознаграждений по сравнению с текущими вознаграждениями. Другими словами, это мера того, насколько ценны будущие вознаграждения для агента по сравнению с вознаграждениями, которые он получает в настоящем. Коэффициент дисконтирования — это значение от 0 до 1, где значение 0 означает, что агент заботится только о немедленных вознаграждениях и полностью игнорирует любые будущие вознаграждения, а значение 1 означает, что агент будет рассматривать будущие вознаграждения с такой же важностью, как и те, которые он получает в настоящем.
Например, в ситуации, когда агент выбирает между двумя действиями, А и В, которые приведут к различным последовательностям будущих вознаграждений, можно использовать коэффициент дисконтирования для определения относительной ценности этих различных последовательностей вознаграждений. Если коэффициент дисконтирования низкий, то агент с большей вероятностью выберет действие, которое приведет к немедленному вознаграждению, а если коэффициент дисконтирования высокий, агент с большей вероятностью выберет действие, которое приведет к большей сумме вознаграждения в будущем. награды.
В целом фактор дисконтирования является важным фактором в MDP, поскольку он позволяет агенту обменивать краткосрочные вознаграждения на долгосрочные вознаграждения и уравновешивать потребность в немедленном вознаграждении с потенциальными преимуществами отсроченного вознаграждения.
Таким образом, MDP в контексте RL — это (𝓢, 𝓐, 𝓟, 𝓡, γ).
Формулировка вознаграждения
С учетом коэффициента дисконтирования γ награда в момент времени t может быть записана как
а общая награда, т. е. совокупная награда за все время, равна
Политика π, которая максимизирует совокупное вознаграждение, является решением нашей проблемы MDP.
Давайте посмотрим на пример (агент автономного вождения):
В контексте автономного вождения марковский процесс принятия решений можно использовать для моделирования процесса принятия решений транспортным средством, чтобы минимизировать расход топлива в долгосрочной перспективе. В этом сценарии состояние системы может быть представлено текущей скоростью и ускорением транспортного средства, а цель состоит в том, чтобы найти оптимальную последовательность действий, которая минимизирует расход топлива.
Мгновенный расход топлива автомобиля можно смоделировать как функцию g(v, a), где v — текущая скорость, а a — текущее ускорение. Эту функцию можно использовать для оценки стоимости каждого возможного действия в заданном состоянии, а марковский процесс принятия решений можно использовать для нахождения оптимальной последовательности действий, которая сведет к минимуму потребление топлива транспортным средством в долгосрочной перспективе.
Например, в заданном состоянии, когда текущая скорость равна v, а текущее ускорение равно a, MDP может рассмотреть ряд возможных действий, таких как ускорение, замедление или поддержание текущей скорости. Стоимость каждого из этих действий можно оценить с помощью функции g(v, a), и можно выбрать оптимальное действие, исходя из того, какое действие приведет к наименьшему расходу топлива в долгосрочной перспективе. Затем этот процесс можно повторить в каждом последующем состоянии, чтобы найти оптимальную последовательность действий, минимизирующую расход топлива.
Важным моментом, на который стоит обратить внимание, является то, что я не рассматриваю вероятность перехода 𝓟 в приведенном выше примере, чтобы сделать наш пример более удобоваримым, но в то же время несколько реалистичным.
Немного кода на питоне:
Рассмотрим MDP, где состояниями являются скорость, а ускорение со скоростью имеет минимальное значение 0 м/с, максимальное значение 50 м/с, ускорение имеет минимальное значение -4,5 м/с², максимальное значение 3,0 м/с², каждое из которых квантовано. на 0,1. Мы можем рассмотреть класс MDP в следующем конструкторе:
def __init__(self, velocity_min, velocity_max, acceleration_min, acceleration_max, velocity_step, acceleration_step, acceleration_min_accelerate, acceleration_max_accelerate):
# Define minimum and maximum values for velocity and acceleration
self.VELOCITY_MIN = velocity_min
self.VELOCITY_MAX = velocity_max
self.ACCELERATION_MIN = acceleration_min
self.ACCELERATION_MAX = acceleration_max
# Define quantization step for velocity and acceleration
self.VELOCITY_STEP = velocity_step
self.ACCELERATION_STEP = acceleration_step
# Define minimum and maximum values for acceleration when accelerating or decelerating
self.ACCELERATION_MIN_ACCELERATE = acceleration_min_accelerate
self.ACCELERATION_MAX_ACCELERATE = acceleration_max_accelerate
# Calculate number of possible values for velocity and acceleration
self.num_velocity_values = int((self.VELOCITY_MAX - self.VELOCITY_MIN) / self.VELOCITY_STEP) + 1
self.num_acceleration_values = int((self.ACCELERATION_MAX - self.ACCELERATION_MIN) / self.ACCELERATION_STEP) + 1
# Create list of possible values for velocity and acceleration
self.velocity_values = [self.VELOCITY_MIN + i * self.VELOCITY_STEP for i in range(self.num_velocity_values)]
self.acceleration_values = [self.ACCELERATION_MIN + i * self.ACCELERATION_STEP for i in range(self.num_acceleration_values)]
Желаемые действия могут быть «Ускорение», «Замедление» или «Поддержание постоянной скорости транспортного средства».
# Function to calculate available actions in a given state
def calculate_actions(self, v, a):
# Initialize list of available actions
actions = []
# If current velocity is less than maximum, add option to accelerate
if v < self.VELOCITY_MAX:
for a_new in self.acceleration_values:
if self.ACCELERATION_MIN_ACCELERATE <= a_new <= self.ACCELERATION_MAX_ACCELERATE:
actions.append((v, a_new))
# If current velocity is greater than minimum, add option to decelerate
if v > self.VELOCITY_MIN:
for a_new in self.acceleration_values:
if -self.ACCELERATION_MAX_ACCELERATE <= a_new <= -self.ACCELERATION_MIN_ACCELERATE:
actions.append((v, a_new))
# Add option to maintain current velocity and acceleration
actions.append((v, a))
return actions
Далее мы можем определить функцию для расчета ожидаемого расхода топлива:
# Function to evaluate the expected fuel consumption for a given state and action
def evaluate_fuel_consumption(self, v, a, v_new, a_new):
# Calculate expected fuel consumption for current state and action
fuel_current = self.fuel_consumption(v, a)
fuel_new = self.fuel_consumption(v_new, a_new)
return fuel_current + fuel_new
Наивный способ расчета оптимальной политики может охватывать все пространство состояний:
# Function to find the optimal action in a given state, based on minimizing expected fuel consumption
def find_optimal_action(self, v, a):
# Calculate available actions in current state
actions = self.calculate_actions(v, a)
# Initialize minimum expected fuel consumption
min_fuel = float("inf")
# Initialize optimal action
optimal_action = None
# Iterate over available actions and find action with minimum expected fuel consumption
for v_new, a_new in actions:
fuel = self.evaluate_fuel_consumption(v, a, v_new, a_new)
if fuel < min_fuel:
min_fuel = fuel
optimal_action = (v_new, a_new)
return optimal_action
# Function to calculate the optimal policy for the MDP
def calculate_optimal_policy(self):
# Initialize dictionary to store optimal policy
optimal_policy = {}
# Iterate over all possible states and calculate optimal action for each state
for v in self.velocity_values:
for a in self.acceleration_values:
optimal_policy[(v, a)] = self.find_optimal_action(v, a)
return optimal_policy
Тестовая реализация приведенных выше фрагментов кода, взятых вместе, выглядит следующим образом:
# Create MDP instance
mdp = MDP(VELOCITY_MIN, VELOCITY_MAX, ACCELERATION_MIN, ACCELERATION_MAX, VELOCITY_STEP, ACCELERATION_STEP, ACCELERATION_MIN_ACCELERATE, ACCELERATION_MAX_ACCELERATE)
# Calculate optimal policy for the MDP
optimal_policy = mdp.calculate_optimal_policy()
# Print optimal policy for the first few states
for i in range(10):
for j in range(10):
print(optimal_policy[(mdp.velocity_values[i], mdp.acceleration_values[j])])
Полный код приведенного выше примера можно загрузить с https://gist.github.com/rahulbhadani/92d3be52529a64372c796ca5e7cb3770.
Теперь мы можем задать вопрос: эффективна ли приведенная выше реализация?
Мы ясно видим, что приведенная выше реализация просматривает все пространство состояний и не очень эффективна. Чтобы повысить эффективность этой реализации, мы можем использовать динамическое программирование для сохранения оптимального действия для каждого состояния, а затем использовать сохраненные значения для расчета оптимальной политики для всего MDP без необходимости повторения всех возможных состояний. Это позволило бы более эффективно рассчитывать оптимальную политику, используя тот факт, что оптимальная политика для любого данного состояния зависит только от оптимальных политик для состояний, которые могут быть достигнуты из текущего состояния.
Другим вариантом может быть использование аппроксимации функций для аппроксимации оптимальной политики, что может быть более эффективным, чем явное вычисление оптимальной политики для всех возможных состояний. Это можно сделать, обучив такую модель, как нейронная сеть (глубокое RL), на репрезентативной выборке пространства состояний, а затем используя обученную модель для прогнозирования оптимального действия для любого заданного состояния.
На этом этапе нам должно быть удобно обсуждать уравнение Беллмана, динамическое программирование и Q-функцию.
Уравнение Беллмана также называют уравнением Гамильтона-Якоби в теории управления или технике управления.
Уравнение Беллмана: функция ценности и Q-функция
В контексте MDP, определенного выше, где целью является минимизация потребления топлива в долгосрочной перспективе, уравнение Беллмана играет важную роль в определении оптимальной политики. Уравнение Беллмана обеспечивает рекурсивную связь между значением состояния и значениями состояний, которые могут быть достигнуты из текущего состояния, которые можно использовать для определения оптимальной политики путем нахождения действия, которое приводит к состоянию с наивысшим значением.
Эта рекурсия решается с использованием итеративных алгоритмов информатики, таких как динамическое программирование и линейное программирование. Их вариации привели ко многим видам алгоритмов обучения RL.
Уравнения Беллмана для значений состояния и значений состояния-действия называются функциями ценности и Q-функциями соответственно.
Значение Функция
В MDP значение состояния определяется как ожидаемый расход топлива в долгосрочной перспективе, начиная с текущего состояния. Мы называем эту функцию ценности.
Математически функция ценности может быть записана как
где P( s(t) , a(t) ) вероятность перехода из состояния s(t) в s(t +1 ) под влиянием действия a(t). Определение уравнения 3 представляет собой модифицированную форму функции стоимости, полученной из [1].
Функцию значения можно использовать для расчета значения состояния путем суммирования ожидаемого расхода топлива в текущем состоянии с ожидаемым расходом топлива в следующем состоянии, где ожидаемый расход топлива в следующем состоянии рассчитывается путем взятия максимума по всем возможные действия, которые можно предпринять в текущем состоянии. Этот процесс можно повторять рекурсивно, чтобы вычислить значение каждого состояния, начиная с начального состояния и работая в обратном направлении до конечного состояния.
После того, как значения всех состояний были рассчитаны с использованием уравнения Беллмана, оптимальную политику можно определить, найдя действие, которое приводит к состоянию с наивысшим значением для каждого состояния. Затем эту оптимальную политику можно использовать для определения оптимальных действий в каждом состоянии, чтобы минимизировать потребление топлива в долгосрочной перспективе.
Q-функция
В контексте MDP, определенного выше, где целью является минимизация потребления топлива в долгосрочной перспективе, Q-функция представляет собой функцию, которая отображает каждую пару состояний и действий в действительное число, представляющее ожидаемый расход топлива в долгосрочной перспективе. начиная с этого состояния и предпринимая это действие.
Математически Q-функцию можно записать как
которая является модифицированной формой Q-функции, используемой в [1].
Q-функцию можно вычислить с помощью уравнения Беллмана, которое обеспечивает рекурсивную связь между значением состояния и значениями состояний, которые могут быть достигнуты из текущего состояния. Q-функция может быть рассчитана путем суммирования ожидаемого расхода топлива в текущем состоянии с ожидаемым расходом топлива в следующем состоянии, где ожидаемый расход топлива в следующем состоянии рассчитывается путем принятия максимально возможных общих возможных действий, которые могут быть предприняты в текущее состояние.
После того, как значения всех пар состояние-действие были рассчитаны с использованием уравнения Беллмана, оптимальная политика может быть определена путем нахождения действия, которое максимизирует функцию Q для каждого состояния. Затем эту оптимальную политику можно использовать для определения оптимальных действий в каждом состоянии, чтобы минимизировать потребление топлива в долгосрочной перспективе.
Давайте посмотрим, как они выглядят на примере, представленном в этой статье.
class MDP:
# ...
# Function to calculate the value function for the MDP
def calculate_value_function(self):
# Initialize dictionary to store values of each state
values = {}
# Iterate over all possible states and calculate value of each state
for v in self.velocity_values:
for a in self.acceleration_values:
values[(v, a)] = self.evaluate_value(v, a, values)
return values
# Function to evaluate the value of a state using the Bellman equation
def evaluate_value(self, v, a, values):
# Check if value of current state has already been calculated
if (v, a) in values:
return values[(v, a)]
# Calculate available actions in current state
actions = self.calculate_actions(v, a)
# Initialize maximum expected fuel consumption
max_fuel = float("-inf")
# Iterate over available actions and find action with maximum expected fuel consumption
for v_new, a_new in actions:
fuel = self.evaluate_fuel_consumption(v, a, v_new, a_new)
if fuel > max_fuel:
max_fuel = fuel
# Return maximum expected fuel consumption
return max_fuel
class MDP:
# ...
# Function to calculate the Q-function for the MDP
def calculate_q_function(self):
# Initialize dictionary to store values of each state-action pair
q_values = {}
# Iterate over all possible states and actions
for v in self.velocity_values:
for a in self.acceleration_values:
for v_new, a_new in self.calculate_actions(v, a):
q_values[((v, a), (v_new, a_new))] = self.evaluate_q_value(v, a, v_new, a_new, q_values)
return q_values
# Function to evaluate the Q-value of a state-action pair using the Bellman equation
def evaluate_q_value(self, v, a, v_new, a_new, q_values):
# Check if Q-value of current state-action pair has already been calculated
if ((v, a), (v_new, a_new)) in q_values:
return q_values[((v, a), (v_new, a_new))]
# Calculate expected fuel consumption in current state
fuel = self.evaluate_fuel_consumption(v, a, v_new, a_new)
# Calculate expected fuel consumption in next state by taking maximum over all possible actions
max_fuel = float("-inf")
for v_next, a_next in self.calculate_actions(v_new, a_new):
fuel_next = self.evaluate_q_value(v_new, a_new, v_next, a_next, q_values)
if fuel_next > max_fuel:
max_fuel = fuel_next
# Return expected fuel consumption in current state plus expected fuel consumption in next state
return fuel + max_fuel
Конечно, в примере отсутствует понятие вероятности перехода, и, следовательно, функция ценности и Q-функция, используемые для примера оптимизации расхода топлива, намного проще, чем для некоторых реальных практических задач.
В этой статье я обсудил решение MDP для получения оптимальной политики, связанной функции ценности и Q-функции, которые можно использовать для оптимального решения MDP.
В следующей статье я расскажу о динамическом программировании в контексте задач обучения с подкреплением. В будущих статьях я буду обсуждать глубокие концепции RL и внедрение нейронных сетей в такие сценарии с некоторыми примерами моделирования. Присоединяйтесь к моему списку адресов электронной почты, чтобы получать мои будущие статьи прямо на ваш почтовый ящик.
Если вы еще не ознакомились с первой статьей серии Foundation RL, обязательно ознакомьтесь с ней: https://towardsdatascience.com/foundational-rl-markov-states-markov-chain-and-markov-decision- процесс-be8ccc341005.
Понравилась ли вам эта статья? Купи мне кофе.
Нравится, что я пишу? Присоединяйтесь к моему списку рассылки.
Хотите узнать больше о темах, связанных с STEM? Присоединяйтесь к Меду
Рекомендации
- Глубокое обучение с подкреплением, Aske Plaat, https://doi.org/10.1007/978-981-19-0638-1, Springer Singapore
- Обучение с подкреплением и стохастическая оптимизация: унифицированная структура для последовательных решений Уоррена Б. Пауэлла (ред.), Wiley (2022). Твердый переплет. ISBN 9781119815051.
- Ховард, Рональд А. (1960). Динамическое программирование и марковские процессы (PDF). Массачусетский технологический институт Нажимать.
