Привет, Хабр!
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 вы сможете освоить практические инструменты работы с данными и не только. Также в календаре мероприятий вы можете зарегистрироваться на любой понравившийся бесплатный вебинар.