Привет, Хабр!
Q-learning — это алгоритм обучения с подкреплением, который позволяет агенту оптимизировать свою стратегию действий в динамичной среде, стремясь максимизировать сумму будущих наград. Агент исследует среду, принимая решения, основанные на предыдущем опыте, а не на предварительной модели мира.
В этой статье мы и рассмотрим этот алгоритм.
Принцип работы
Агент выбирает действия на основе данных из Q-таблицы, в которой изначально все значения равны нулю и таким образом на каждом шаге....Стоп..что за Q-таблица?
Q-таблица представляет собой матрицу, где строки обозначают возможные состояния среды, а столбцы — возможные действия агента в этих состояниях. Значения в Q-таблице отражают ожидаемую суммарную награду за выполнение действия в данном состоянии и следование оптимальной политике впоследствии.
В начале обучения Q-таблица инициализируется нулями или случайными значениями. Это представляет начальное предположение о том, насколько хороши различные действия в различных состояниях.
После каждого шага агента Q-значения в таблице обновляются с использованием уравнения Беллмана (о нем чуть позже).
Агент выбирает действия, основываясь на значениях из Q-таблицы, часто с использованием ε-жадной стратегии, которая балансирует между исследованием новых действий и эксплуатацией уже известных действий с максимальным Q-значением.
Допустим, есть простая среда с четырьмя возможными состояниями S1, S2, S3, S4 и двумя возможными действиями A1, A2 в каждом состоянии. Q-таблица для этой среды выглядела бы примерно так:
Состояние/действие | A1 | A2 |
|---|---|---|
S1 | 0.5 | 0.2 |
S2 | 0.1 | -0.4 |
S3 | -0.2 | 0.0 |
S4 | 0.6 | 0.3 |
Значения в таблице указывают на ожидаемую суммарную награду за выбор действия A1 или A2 в соответствующем состоянии. Например, значение 0.5 в ячейке S1, A1 означает, что ожидаемая суммарная награда за выбор действия A1 в состоянии S1 составляет 0.5. С течением времени, по мере обучения агента, эти значения будут обновляться, отражая полученный опыт и уточняя оценки ожидаемых наград.
Так вот...
На каждом шаге агент обновляет Q-таблицу, используя уравнение Беллмана, учитывая полученные награды.
Уравнение Беллмана используется для расчета Q-значений, которые представляют собой оценки качества или полезности выполнения определенного действия из конкретного состояния. Эти Q-значения затем используются для определения оптимальной стратегии агента, направленной на максимизацию общей ожидаемой награды.
Уравнение Беллмана для Q-значений может быть выражено как:
Где:
Q(s, a) — ожидаемое Q-значение состояния и действия,
r — немедленная награда, полученная после выполнения действия a из состояния s,
γ — коэффициент дисконтирования, который представляет собой важность будущих наград (обычно значение между 0 и 1),
А max и все то, что после него — максимальное Q-значение для всех возможных действий a' из следующего состояния s'.
Уравнение Беллмана по сути позволяет агенту учиться оценивать долгосрочные последствия своих действий, принимая во внимание текущую награду и ожидаемые будущие награды.
Таким образом можно рекурсивно раскрывать связь между Q-значениями текущих и будущих состояний.
Реализация алгоритма в Python
Первый пример с чистым нампаем, для задачи сетки 3x3:
import numpy as np # инициализация Q-таблицы Q = np.zeros([3, 3]) # параметры алгоритма alpha = 0.1 # коэф. обучения gamma = 0.9 # коэф. дисконтирования epsilon = 0.1 # параметр исследования vs. эксплуатации # основной цикл for episode in range(1000): # колво эпизодов обучения state = np.random.randint(0, 3) # стартовое состояние while state != 2: # пока не достигнута цель # выбор действия if np.random.rand() < epsilon: action = np.random.randint(0, 3) # случайное действие else: action = np.argmax(Q[state]) # переход в новое состояние и получение награды new_state = action reward = -1 if new_state != 2 else 0 # награда -1 за каждый шаг, 0 за достижение цели # обновление Q-значения Q[state, action] = (1 - alpha) * Q[state, action] + alpha * (reward + gamma * np.max(Q[new_state])) state = new_state print("Q-таблица:") print(Q)
Q-таблица: [[-0.6861894 -0.71757046 0. ] [-0.74581342 -0.81469798 0. ] [ 0. 0. 0. ]]
Q-learning для простой среды Gridworld:
import numpy as np # Определение среды (Gridworld) class Gridworld: def __init__(self): self.grid_size = (4, 4) self.num_actions = 4 self.goal_state = (3, 3) def reset(self): self.agent_pos = (0, 0) return self.agent_pos def step(self, action): if action == 0: # Вверх self.agent_pos = (max(0, self.agent_pos[0] - 1), self.agent_pos[1]) elif action == 1: # Вниз self.agent_pos = (min(self.grid_size[0] - 1, self.agent_pos[0] + 1), self.agent_pos[1]) elif action == 2: # Влево self.agent_pos = (self.agent_pos[0], max(0, self.agent_pos[1] - 1)) elif action == 3: # Вправо self.agent_pos = (self.agent_pos[0], min(self.grid_size[1] - 1, self.agent_pos[1] + 1)) reward = -1 if self.agent_pos != self.goal_state else 0 done = self.agent_pos == self.goal_state return self.agent_pos, reward, done # Инициализация Q-таблицы Q = np.zeros((4, 4, 4)) # Параметры обучения alpha = 0.1 gamma = 0.99 epsilon = 0.1 num_episodes = 1000 # Обучение env = Gridworld() for i in range(num_episodes): state = env.reset() done = False while not done: if np.random.rand() < epsilon: action = np.random.randint(0, env.num_actions) # Случайное действие else: action = np.argmax(Q[state[0], state[1], :]) # Действие с максимальным Q-значением next_state, reward, done = env.step(action) Q[state[0], state[1], action] = (1 - alpha) * Q[state[0], state[1], action] + alpha * (reward + gamma * np.max(Q[next_state[0], next_state[1], :])) state = next_state print("Q-таблица:") print(Q)
Q-таблица: [[[-5.63733656 -4.90099172 -5.78723972 -4.90099167] [-4.53658863 -3.9403968 -5.34673741 -3.94039681] [-3.58282726 -2.97009883 -3.97937951 -2.97009888] [-2.37438071 -1.98999995 -2.93539914 -2.21899042]] [[-5.27339855 -3.9403967 -4.51348278 -3.94039674] [-3.86562705 -2.97009964 -4.10058156 -2.97009964] [-2.75481593 -1.98999997 -2.33378391 -1.98999997] [-2.12960968 -1. -2.06496437 -1.56168583]] [[-4.18589727 -2.97009877 -3.28672302 -2.97009878] [-3.13003944 -1.98999995 -3.10226658 -1.98999994] [-2.51335353 -1. -2.29706595 -1. ] [-1.5997738 0. -1.40803817 -0.81469798]] [[-2.87489189 -2.15624595 -2.15161794 -1.98999995] [-1.23354402 -1.45941412 -2.08135222 -1. ] [-1.25371027 -0.77123208 -1.45474141 0. ] [ 0. 0. 0. 0. ]]]
Также часто реализуют через либу gym от OpenAI. Например с окружением taxi:
import gym import numpy as np env = gym.make('Taxi-v3') alpha = 0.1 gamma = 0.99 epsilon = 0.1 # Q-таблица num_states = env.observation_space.n num_actions = env.action_space.n Q = np.zeros((num_states, num_actions)) # обучение агента num_episodes = 1000 for episode in range(num_episodes): state = env.reset() done = False while not done: # выбор действия if np.random.rand() < epsilon: action = env.action_space.sample() # случайное действие для исследования else: action = np.argmax(Q[state]) # действие с наивысшим Q-значением # выполнение действия и получение награды next_state, reward, done, _ = env.step(action) # обновление Q-значения по уравнению Беллмана Q[state, action] = (1 - alpha) * Q[state, action] + alpha * (reward + gamma * np.max(Q[next_state])) # переход к следующему состоянию state = next_state print("Q-таблица:") print(Q)
Q-таблица: [[ 0. 0. 0. 0. 0. 0. ] [-4.37743896 -4.30379883 -4.52970509 -4.37685397 1.29064633 -7.46319523] [-1.66879694 -0.44507461 -2.07826517 -1.23688895 13.8078767 -2.43668637] ... [-1.07785638 -0.74885187 -0.99551198 -0.99053731 -1. -1. ] [-2.74269569 -2.73474617 -2.73781084 -2.76714114 -3.95870558 -4.68360176] [-0.1999 -0.19 -0.1 6.47055995 -1.9 -1. ]]
На этом все. Напомню, что в рамках онлайн-курсов от экспертов OTUS вы сможете освоить практические инструменты работы с данными и не только. Также в календаре мероприятий вы можете зарегистрироваться на любой понравившийся бесплатный вебинар.
