Привет, Хабр!

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) = r + \gamma \max_{a'}Q(s', a')$

Где:

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

Кратко про алгоритм обучения Q-learning и как он реализуется в Python для новичков