Введение в Q-Learning: учебник для начинающих

Обучение с подкреплением (RL) — это часть экосистемы машинного обучения, где агент обучается за счет взаимодействия со средой, чтобы выработать оптимальную стратегию для достижения целей. Оно существенно отличается от методов контролируемого обучения, где нам нужно загружать и обрабатывать данные. Обучение с подкреплением не требует предварительных данных. Вместо этого оно учится на основе среды и системы вознаграждений, чтобы принимать более удачные решения.

Например, в видеоигре про Марио, если персонаж выполнит случайное действие (например, двинется влево), в зависимости от этого действия он может получить вознаграждение. После действия агент (Марио) оказывается в новом состоянии, и процесс повторяется, пока персонаж не дойдет до конца уровня или не погибнет. 

Этот эпизод будет повторяться много раз, пока Марио не научится ориентироваться в среде, максимизируя вознаграждения. 

Изображение автора

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

1. Агент находится в нулевом состоянии в среде.
2. Он выполняет действие на основе определенной стратегии.
3. Он получает вознаграждение или наказание в зависимости от действия.
4. Обучается на прошлых ходах и оптимизирует стратегию. 
5. Процесс повторяется, пока не будет найдена оптимальная стратегия. 

Узнайте больше из нашего руководства Введение в обучение с подкреплением. Вы разберетесь, как работает RL, на примерах кода. 

В этом уроке мы познакомимся с Q-learning и поймем, зачем нужен Deep Q-learning. Кроме того, мы научимся создавать и обучать алгоритмы Q-learning с нуля с помощью Numpy и Gymnasium.

Примечание: Если вы новичок в машинном обучении, рекомендуем пройти карьерный трек Machine Learning Scientist with Python, чтобы лучше понять обучение с подкреплением и Q-Learning. 

Что такое Q-Learning?

Q-learning — это модель-независимый, ценностно-ориентированный, off-policy алгоритм, который находит лучшую последовательность действий, исходя из текущего состояния агента. «Q» означает quality — качество. Качество отражает, насколько полезно действие для максимизации будущих вознаграждений.  

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

Ценностные методы обучают функцию ценности, чтобы понять, какое состояние более выгодно, и исходя из этого действовать. С другой стороны, политические методы напрямую обучают политику, чтобы выбирать действие в заданном состоянии.

В off-policy алгоритм оценивает и обновляет политику, отличную от той, с которой выбираются действия. Напротив, on-policy алгоритм оценивает и улучшает ту же политику, по которой действует.  

Ключевые термины в Q-learning

Прежде чем разбираться, как работает Q-learning, нам нужно выучить несколько полезных терминов, чтобы понять его основы. 

• Состояния (s): текущее положение агента в среде. 
• Действие (a): шаг, который агент делает в определенном состоянии. 
• Вознаграждения: за каждое действие агент получает вознаграждение или штраф. 
• Эпизоды: конец этапа, когда агент больше не может действовать. Это происходит при достижении цели или провале. 
• Q(S_t+1, a): ожидаемое оптимальное Q-значение выполнения действия в данном состоянии. 
• Q(S_t, A_t): текущая оценка Q(S_t+1, a).
• Q-таблица: агент хранит Q-таблицу пар состояний и действий.
• Temporal Differences (TD): используется для оценки ожидаемого значения Q(S_t+1, a), используя текущее состояние и действие, а также предыдущее состояние и действие. 

Как работает Q-Learning?

Подробно разберем работу Q-learning на примере замерзшего озера. В этой среде агент должен перейти озеро от старта к цели, не провалившись в лунки. Лучшая стратегия — дойти до цели по кратчайшему пути. 

Gif автора

Q-таблица

Агент использует Q-таблицу, чтобы выбрать наилучшее действие по ожидаемому вознаграждению для каждого состояния в среде. Проще говоря, Q-таблица — это структура данных с наборами действий и состояний, а значения в таблице мы обновляем алгоритмом Q-learning. 

Q-функция

Q-функция использует уравнение Беллмана и принимает на вход состояние (s) и действие (a). Уравнение упрощает вычисление ценности состояния и ценности пара «состояние-действие». 

Изображение с сайта freecodecamp.org

Алгоритм Q-learning

Изображение автора

Инициализация Q-таблицы

Сначала инициализируем Q-таблицу. Построим таблицу с колонками по числу действий и строками по числу состояний.

В нашем примере персонаж может двигаться вверх, вниз, влево и вправо. У нас четыре возможных действия и четыре состояния (старт, ожидание, неверный путь и финиш). Неверный путь можно трактовать как падение в лунку. Инициализируем Q-таблицу нулями. 

Изображение автора

Выбор действия

Второй шаг прост. В начале агент выбирает случайное действие (вниз или вправо), а со второй попытки использует обновленную Q-таблицу для выбора действия. 

Выполнение действия

Выбор и выполнение действия повторяются много раз до остановки тренировочного цикла. Первое действие и состояние выбираются по Q-таблице. В нашем случае все значения Q-таблицы равны нулю. 

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

Изначально агент находится в режиме исследования и выбирает случайные действия, чтобы изучить среду. Стратегия Epsilon-Greedy — простой способ сбалансировать исследование и эксплуатацию. Эпсилон — это вероятность выбрать исследование; когда вероятность исследования мала, агент чаще эксплуатирует известное. 

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

Изображение автора

В примере с замерзшим озером агент не знает среду, поэтому вначале делает случайное действие (движется вниз). Как видно на изображении выше, Q-таблица обновляется по уравнению Беллмана.

Измерение вознаграждений

После действия мы оцениваем результат и вознаграждение. 

• Вознаграждение за достижение цели: +1
• Вознаграждение за неверный путь (падение в лунку): 0
• Вознаграждение за ожидание или движение по льду: 0. 

Обновление Q-таблицы

Мы обновим функцию Q(S_t, A_t) по уравнению. Она использует оцененные в прошлом эпизоде Q-значения, скорость обучения и ошибку временных разностей (TD). Ошибка TD вычисляется по немедленному вознаграждению, дисконтированному максимальному ожидаемому будущему вознаграждению и прежней оценке Q-значения. 

Процесс повторяется многократно, пока Q-таблица не будет обновлена и Q-функция не будет максимизирована. 

Изображение автора | Визуализация уравнения — Thomas Simonini

Сначала агент исследует среду, чтобы обновить Q-таблицу. А когда Q-таблица готова, агент начинает эксплуатировать и принимать более точные решения. 

Изображение автора

В случае замерзшего озера агент научится идти к цели кратчайшим путем и избегать лунок. 

Руководство по Q-Learning на Python 

В этом разделе мы построим модель Q-learning с нуля, используя среду Gymnasium, Pygame и Numpy. Учебник по Python — модифицированная версия ноутбука Thomas Simonini. Он включает инициализацию среды и Q-таблицы, определение жадной политики, настройку гиперпараметров, создание и запуск тренировочного цикла и оценки, а также визуализацию результатов.   

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

Подготовка

Настройка виртуального дисплея

Сначала установим все зависимости для генерации видео повтора (Gif). Нам понадобится виртуальный экран (pyvirtualdisplay), чтобы отрисовывать среду и записывать кадры. 

Примечание: с помощью %%capture мы подавляем вывод ячейки Jupyter. 

%%capture
!pip install pyglet==1.5.1
!apt install python-opengl
!apt install ffmpeg
!apt install xvfb
!pip3 install pyvirtualdisplay

# Virtual display
from pyvirtualdisplay import Display

virtual_display = Display(visible=0, size=(1400, 900))
virtual_display.start()

Установка зависимостей

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

• gymnasium: используется для инициализации среды FrozenLake-v1.
• pygame: используется для интерфейса FrozenLake-v1.
• numPy: используется для создания и работы с Q-таблицей.

%%capture
!pip install gymnasium
!pip install pygame
!pip install numpy

!pip install imageio imageio_ffmpeg

Импорт пакетов

Теперь импортируем необходимые библиотеки. 

• Imageio используется для создания анимации. 
• tqdm используется для индикаторов прогресса. 

import numpy as np
import gymnasium as gym
import random
import imageio
from tqdm.notebook import trange

Среда Gymnasium Frozen Lake 

Мы создадим нескользкую среду 4x4, используя библиотеку Gymnasium Frozen Lake. 

• Есть две версии сетки: «4x4» и «8x8».
• Если is_slippery=True, агент может сдвигаться не в выбранном направлении из‑за скользкой поверхности озера. 

После инициализации среды проведем ее анализ. 

env = gym.make("FrozenLake-v1",map_name="4x4",is_slippery=False)

print("Observation Space", env.observation_space)
print("Sample observation", env.observation_space.sample()) # display a random observation

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

Observation Space Discrete(16)
Sample observation 15

Давайте узнаем число действий и выведем случайное действие. 

Пространство действий:

• 0: движение влево
• 1: движение вниз
• 2: движение вправо
• 3: движение вверх

Функция вознаграждения:

• Достижение цели: +1
• Падение в лунку: 0
• Нахождение на льду: 0

print("Action Space Shape", env.action_space.n)
print("Action Space Sample", env.action_space.sample())

Action Space Shape 4
Action Space Sample 1

Создание и инициализация Q-таблицы

В Q-таблице столбцы соответствуют действиям, а строки — состояниям. Мы можем использовать Gymnasium, чтобы узнать пространство действий и состояний, а затем создать Q-таблицу. 

state_space = env.observation_space.n
print("There are ", state_space, " possible states")

action_space = env.action_space.n
print("There are ", action_space, " possible actions")

There are  16  possible states
There are  4  possible actions

Для инициализации Q-таблицы создадим массив Numpy размером state_space × action_space. Мы создадим массив 16 × 4. 

def initialize_q_table(state_space, action_space):
  Qtable = np.zeros((state_space, action_space))
  return Qtable

Qtable_frozenlake = initialize_q_table(state_space, action_space)

Политика epsilon-greedy

Ранее мы познакомились со стратегией epsilon-greedy, которая балансирует исследование и эксплуатацию. С вероятностью 1 − ɛ выполняется эксплуатация, а с вероятностью ɛ — исследование. 

В epsilon_greedy_policy мы будем:

1. Генерировать случайное число от 0 до 1.
2. Если случайное число больше эпсилон, выполняем эксплуатацию: агент выбирает действие с максимальным значением для данного состояния.
3. Иначе выполняем исследование (выбираем случайное действие). 

def epsilon_greedy_policy(Qtable, state, epsilon):
  random_int = random.uniform(0,1)
  if random_int > epsilon:
    action = np.argmax(Qtable[state])
  else:
    action = env.action_space.sample()
  return action

Определение жадной политики

Как мы знаем, Q-learning — это off-policy алгоритм, то есть политика выбора действия и политика обновления функции различаются. 

В этом примере действующая политика — Epsilon-Greedy, а политика обновления — Greedy. 

Жадная политика также будет финальной политикой после обучения агента. Она выбирает наибольшее значение состояния и действия из Q-таблицы.

def greedy_policy(Qtable, state):
  action = np.argmax(Qtable[state])
  return action

Гиперпараметры модели

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

Агенту нужно достаточно исследовать пространство состояний, чтобы выучить хорошую аппроксимацию ценности; поэтому необходим прогрессивный спад эпсилон. Если скорость спада слишком высока, агент может «застрять», не исследовав достаточно состояний.

• 10 000 тренировочных и 100 оценочных эпизодов.
• Скорость обучения — 0,7.
• Мы используем среду «FrozenLake-v1» с 99 максимальными шагами на эпизод.
• Gamma (дисконт-фактор) — 0,95.
• eval_seed: seed для среды при оценке.
• Вероятность исследования epsilon в начале — 1,0, минимальная — 0,05.
• Экспоненциальная скорость спада для epsilon — 0,0005.

# Training parameters
n_training_episodes = 10000
learning_rate = 0.7        

# Evaluation parameters
n_eval_episodes = 100      

# Environment parameters
env_id = "FrozenLake-v1"   
max_steps = 99             
gamma = 0.95               
eval_seed = []             

# Exploration parameters
max_epsilon = 1.0           
min_epsilon = 0.05           
decay_rate = 0.0005           

Обучение модели 

В тренировочном цикле мы будем:

1. Создавать цикл по тренировочным эпизодам.
2. Сначала уменьшать эпсилон, так как с каждым эпизодом нужно меньше исследования и больше эксплуатации. 
3. Сбрасывать среду.
4. Создавать вложенный цикл по максимальному числу шагов.
5. Выбирать действие по политике epsilon-greedy. 
6. Сделать действие (A_t) и наблюдать ожидаемое вознаграждение (R_t+1) и состояние (S_t+1).
7. Сделать действие (a) и наблюдать результирующее состояние (s') и вознаграждение (r).
8. Обновить Q-функцию по формуле. 
9. Если done= True, завершить эпизод и прервать цикл.
10. Наконец, заменить текущее состояние новым. 
11. После завершения всех тренировочных эпизодов функция вернет обновленную Q-таблицу. 

def train(n_training_episodes, min_epsilon, max_epsilon, decay_rate, env, max_steps, Qtable):
  for episode in trange(n_training_episodes):
 
    epsilon = min_epsilon + (max_epsilon - min_epsilon)*np.exp(-decay_rate*episode)
    # Reset the environment
    state = env.reset()
    step = 0
    done = False

    # repeat
    for step in range(max_steps):
   
      action = epsilon_greedy_policy(Qtable, state, epsilon)

   
      new_state, reward, done, info = env.step(action)

   
      Qtable[state][action] = Qtable[state][action] + learning_rate * (reward + gamma * np.max(Qtable[new_state]) - Qtable[state][action])

      # If done, finish the episode
      if done:
        break
     
      # Our state is the new state
      state = new_state
  return Qtable

На выполнение 10 000 тренировочных эпизодов у нас ушло 3 секунды. 

Qtable_frozenlake = train(n_training_episodes, min_epsilon, max_epsilon, decay_rate, env, max_steps, Qtable_frozenlake)

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

Qtable_frozenlake

array([[0.73509189, 0.77378094, 0.77378094, 0.73509189],
      [0.73509189, 0.        , 0.81450625, 0.77378094],
      [0.77378094, 0.857375  , 0.77378094, 0.81450625],
      [0.81450625, 0.        , 0.77378094, 0.77378094],
      [0.77378094, 0.81450625, 0.        , 0.73509189],
      [0.        , 0.        , 0.        , 0.        ],
      [0.        , 0.9025    , 0.        , 0.81450625],
      [0.        , 0.        , 0.        , 0.        ],
      [0.81450625, 0.        , 0.857375  , 0.77378094],
      [0.81450625, 0.9025    , 0.9025    , 0.        ],
      [0.857375  , 0.95      , 0.        , 0.857375  ],
      [0.        , 0.        , 0.        , 0.        ],
      [0.        , 0.        , 0.        , 0.        ],
      [0.        , 0.9025    , 0.95      , 0.857375  ],
      [0.9025    , 0.95      , 1.        , 0.9025    ],
      [0.        , 0.        , 0.        , 0.        ]])

Оценка

Функция evaluate_agent запускается на n_eval_episodes эпизодах и возвращает среднее значение и стандартное отклонение вознаграждения. 

1. В цикле сначала проверяем, задан ли seed для оценки. Если нет — сбрасываем среду без seed. 
2. Вложенный цикл выполняется до max_steps.
3. Агент выбирает действие с максимальным ожидаемым будущим вознаграждением в данном состоянии, используя Q-таблицу. 
4. Считаем вознаграждение.
5. Меняем состояние.
6. Если done (агент упал в лунку или достиг цели), прерываем цикл.
7. Добавляем результат.
8. В конце используем результаты для вычисления среднего и стандартного отклонения. 

def evaluate_agent(env, max_steps, n_eval_episodes, Q, seed):

  episode_rewards = []
  for episode in range(n_eval_episodes):
    if seed:
      state = env.reset(seed=seed[episode])
    else:
      state = env.reset()
    step = 0
    done = False
    total_rewards_ep = 0
   
    for step in range(max_steps):
      # Take the action (index) that have the maximum reward
      action = np.argmax(Q[state][:])
      new_state, reward, done, info = env.step(action)
      total_rewards_ep += reward
       
      if done:
        break
      state = new_state
    episode_rewards.append(total_rewards_ep)
  mean_reward = np.mean(episode_rewards)
  std_reward = np.std(episode_rewards)

  return mean_reward, std_reward

Как видите, мы получили идеальный счет с нулевым стандартным отклонением. Это означает, что наш агент достиг цели во всех 100 эпизодах. 

# Evaluate our Agent
mean_reward, std_reward = evaluate_agent(env, max_steps, n_eval_episodes, Qtable_frozenlake, eval_seed)
print(f"Mean_reward={mean_reward:.2f} +/- {std_reward:.2f}")

Mean_reward=1.00 +/- 0.00

Визуализация результата

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

1. Сначала создадим состояние, сбросив среду со случайным целым числом 0–500. 
2. Отрисуем среду с помощью rdb_array, чтобы получить массив изображения. 
3. Затем добавим img в массив images. 
4. В цикле будем делать шаги по Q-таблице и отрисовывать изображение на каждом шаге. 
5. В конце используем этот массив и imageio, чтобы создать Gif с частотой один кадр в секунду. 

def record_video(env, Qtable, out_directory, fps=1):
  images = [] 
  done = False
  state = env.reset(seed=random.randint(0,500))
  img = env.render(mode='rgb_array')
  images.append(img)
  while not done:
    # Take the action (index) that have the maximum expected future reward given that state
    action = np.argmax(Qtable[state][:])
    state, reward, done, info = env.step(action) # We directly put next_state = state for recording logic
    img = env.render(mode='rgb_array')
    images.append(img)
  imageio.mimsave(out_directory, [np.array(img) for i, img in enumerate(images)], fps=fps)

Если вы работаете в Jupyter Notebook, можно отобразить Gif с помощью функции Image из IPython.display. 

video_path="/content/replay.gif"
video_fps=1
record_video(env, Qtable_frozenlake, video_path, video_fps)

from IPython.display import Image
Image('./replay.gif')

Теперь вы можете поделиться этими результатами с коллегами и однокурсниками или опубликовать их в соцсетях.