Занятие 6
Лабораторная 6. Введение в обучение с подкреплением: MDP¶
0. Подготовка окружения¶
Убедимся, что нужные библиотеки установлены.
import numpy as np
import matplotlib.pyplot as plt
try:
import gymnasium as gym
except ImportError:
%pip install gymnasium
import gymnasium as gym
print('numpy:', np.__version__)
print('gymnasium:', gym.__version__)
1. Цикл «агент — среда»¶
В RL агент и среда обмениваются сообщениями: агент видит состояние $s$, выбирает действие $a$, а среда возвращает награду $r$ и следующее состояние $s'$. В библиотеке Gymnasium этот цикл уже реализован.
Шаг (step) — один такт взаимодействия: агент наблюдает состояние, выбирает действие, получает награду и новое состояние.
Эпизод (episode) — последовательность шагов от начального состояния до завершения. В CartPole эпизод заканчивается, когда шест падает (terminated) или достигнут лимит шагов (truncated).
Посмотрим на среду CartPole: тележка на рельсе, на ней шарнирно закреплён шест. Наблюдение — вектор из четырёх чисел:
- $x$ — положение тележки;
- $\dot{x}$ — скорость тележки;
- $\theta$ — угол шеста;
- $\dot{\theta}$ — угловая скорость шеста.
Действий два: $0$ — толкать влево, $1$ — толкать вправо. Награда $+1$ за каждый шаг, пока шест не упал.
env = gym.make('CartPole-v1', render_mode='rgb_array')
obs, info = env.reset(seed=42)
frame = env.render()
env.close()
plt.figure(figsize=(6, 4))
plt.imshow(frame)
plt.axis('off')
plt.title('CartPole')
plt.show()
Реализуем простейшую стратегию (политику): на каждом шаге будем выбирать случайное действие.
env = gym.make('CartPole-v1', render_mode='rgb_array')
obs, info = env.reset(seed=0)
from matplotlib import animation
frames = []
done = False
while not done:
action = env.action_space.sample() # случайное действие
obs, reward, terminated, truncated, info = env.step(action)
frames.append(env.render())
print(f'a={action}, r={reward}, obs={np.round(obs, 3)}')
done = terminated or truncated
env.close()
# Анимация эпизода
fig = plt.figure(figsize=(5, 3))
img = plt.imshow(frames[0])
plt.axis('off')
def animate(i):
img.set_data(frames[i])
return [img]
ani = animation.FuncAnimation(fig, animate, frames=len(frames), interval=80)
plt.show()
Задача 1 Напишите свою эвристическую политику для CartPole, которая балансирует шест лучше случайной.
Затем сравните награду (за эпизод) вашей политики и случайной.
# Ваш Код
2. Доход и дисконтирование¶
Доход (return) — это дисконтированная сумма будущих наград:
$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots$$Коэффициент $\gamma \in [0, 1]$ определяет, насколько агент ценит будущее. Реализуем подсчёт дохода двумя способами: «в лоб» и рекурсивно (справа налево).
rewards = [1.0, 1.0, 1.0, 1.0, 0.0]
def discounted_return_loop(rewards, gamma):
G = 0.0
for k, r in enumerate(rewards):
G += (gamma ** k) * r
return G
def discounted_return_recursive(rewards, gamma):
G = 0.0
for r in reversed(rewards):
G = r + gamma * G
return G
for gamma in [0.0, 0.5, 0.9, 1.0]:
a = discounted_return_loop(rewards, gamma)
b = discounted_return_recursive(rewards, gamma)
print(f'gamma={gamma}: loop={a:.4f}, recursive={b:.4f}')
Задача 2
- Чему равен доход при γ = 1, если наград бесконечно много и все они равны 1?
- Зачем вводят γ < 1, если горизонт эпизода конечен?
Ваш ответ:
3. MDP: полоска из трёх клеток¶
Среда: полоска клеток 0, 1, 2. В клетке 2 — цель (награда +1, эпизод завершается). В каждой клетке два действия: «вправо» и «стоять». Переходы детерминированы, γ = 0.9.
Посчитаем функции ценности V и Q для политики «всегда вправо» вручную, как на лекции.
gamma = 0.9
# Ценность терминальной клетки равна нулю
V = np.zeros(3)
V[2] = 0.0
V[1] = 1.0 + gamma * V[2] # из 1 вправо: награда +1 и терминал
V[0] = 0.0 + gamma * V[1] # из 0 вправо: награда 0, попадаем в 1
print('V =', V)
# Q(s, a) = r(s, a) + gamma * V(s')
def q_value(s, action):
if action == 'вправо':
r = 1.0 if s == 1 else 0.0
s_next = s + 1
else: # 'стоять'
r = 0.0
s_next = s
return r + gamma * V[s_next]
for s in [0, 1]:
qr = q_value(s, 'вправо')
qs = q_value(s, 'стоять')
print(f'Q({s}, вправо) = {qr:.3f}, Q({s}, стоять) = {qs:.3f}')
Жадная политика — это правило, по которому в каждом состоянии выбирается действие с наибольшей ценностью: $\pi_{\text{greedy}}(s) = \arg\max_a Q(s,a)$.
Посмотрим на значения $Q$, которые мы получили для политики «всегда вправо»:
- в клетке 0: для действия «вправо» $Q = 0{,}9$, для действия «стоять» $Q = 0{,}81$;
- в клетке 1: для действия «вправо» $Q = 1$, для действия «стоять» $Q = 0{,}9$.
В клетке 0 число $0{,}9$ больше, чем $0{,}81$, поэтому $\arg\max_a Q(0,a)$ выбирает действие «вправо». В клетке 1 число $1$ больше, чем $0{,}9$, поэтому $\arg\max_a Q(1,a)$ тоже выбирает «вправо».
Значит, жадная политика в обеих клетках говорит «вправо», то есть совпадает с исходной политикой «всегда вправо». Если попытаться улучшить её, заменив действия на более выгодные по $Q$, ничего не изменится — она уже выбирает самые ценные действия. В нашей среде это признак оптимальности: именно «вправо» ведёт к цели и приносит награду $+1$.
4. Выбор лучшей политики¶
Качество политики измеряем функционалом $$J(π) = V^π(0)$$ — ценностью стартовой клетки (эпизод всегда начинается в клетке 0).
Решим уравнение Беллмана для нескольких политик и сравним их.
gamma = 0.9
def evaluate_strip(p):
"""p[s] = вероятность действия 'вправо' в клетке s.
Решаем уравнение Беллмана в замкнутой форме."""
p0, p1 = p[0], p[1]
V1 = p1 * 1.0 / (1.0 - (1.0 - p1) * gamma)
V0 = p0 * gamma * V1 / (1.0 - (1.0 - p0) * gamma)
return np.array([V0, V1, 0.0])
policies = {
'pi1: всегда вправо': [1.0, 1.0],
'pi2: всегда стоять': [0.0, 0.0],
'pi3: вправо, потом стоять': [1.0, 0.0],
'pi4: стохастическая 0.8': [0.8, 0.8],
}
for name, p in policies.items():
V = evaluate_strip(p)
print(f'{name:28s} -> J(pi) = V(0) = {V[0]:.4f}')
5. Среда Taxi¶
На поле 5×5 такси должно подобрать пассажира на одном из четырёх пунктов (R, G, Y, B) и довезти его до пункта назначения.
- Состояний: 500 — это комбинации положения такси (25 клеток), местоположения пассажира (5 вариантов: R/G/Y/B или «уже в такси») и пункта назначения (4 варианта).
- Действий: 6 — 0 вниз, 1 вверх, 2 вправо, 3 влево, 4 подобрать, 5 высадить.
- Награда: −1 за каждый шаг, +20 за успешную доставку, −10 за неверные pickup/dropoff.
Каждое состояние можно расшифровать функцией decode: она возвращает (строка такси (положение в табличке), столбец такси (положение в табличке), местоположение пассажира, пункт назначения). Индексы пассажира и назначения: 0=R, 1=G, 2=Y, 3=B, а 4 у пассажира означает «уже в такси».
taxi = gym.make('Taxi-v4', render_mode='ansi')
obs, info = taxi.reset(seed=0)
print('Начальное состояние:', obs)
print('Расшифровка (строка, столбец, пассажир, назначение):', taxi.unwrapped.decode(obs))
print()
print(taxi.render())
taxi.close()
Текстовый вывод не слишком нагляден, поэтому нарисуем немного другой
taxi = gym.make('Taxi-v4', render_mode='rgb_array')
obs, info = taxi.reset(seed=0)
frame = taxi.render()
taxi.close()
plt.figure(figsize=(4, 4))
plt.imshow(frame)
plt.axis('off')
plt.title('Taxi')
plt.show()
Задача 3. Сделайте несколько шагов случайными действиями и понаблюдайте за наградой. Когда она становится −10, а когда +20? Подтвердите наблюдение, глядя на decode(obs).
taxi = gym.make('Taxi-v4', render_mode='ansi')
obs, info = taxi.reset(seed=1)
for _ in range(10):
action = taxi.action_space.sample()
obs, reward, terminated, truncated, info = taxi.step(action)
print(f'a={action}, r={reward}, obs={obs}, decode={taxi.unwrapped.decode(obs)}')
if terminated or truncated:
break
taxi.close()
Ваш ответ:
6. Модель среды: env.P¶
Taxi — среда с известной моделью: переходы и награды можно прочитать из env.P. Для пары (состояние, действие) там лежит список записей (вероятность, следующее_состояние, награда, завершённость эпизода).
В новых версиях Gymnasium среда обёрнута в TimeLimit, поэтому модель достаём через .unwrapped.
taxi = gym.make('Taxi-v4').unwrapped
nS = taxi.observation_space.n
nA = taxi.action_space.n
print('Состояний:', nS, ', действий:', nA)
s = 123 # произвольное состояние
print('Состояние', s, '=', taxi.decode(s))
print('Переходы по действиям:')
for a in range(nA):
print(f' действие {a}:', taxi.P[s][a])
Задача 4. Найдите состояние, в котором пассажир уже находится в такси, и посмотрите на его переходы. Почему при действии «высадить» эпизод может завершиться, а при «подобрать» — нет?
Ваш ответ:
7. Оценка политики (policy evaluation) — теория¶
Задача: дана политика $\pi$. Нужно найти её функцию ценности $V^\pi(s)$ — ожидаемый дисконтированный доход из каждого состояния при следовании $\pi$.
Уравнение Беллмана для ожидания — самосогласованное равенство, которому удовлетворяет $V^\pi$:
$$V^\pi(s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a) \left[ r + \gamma V^\pi(s') \right]$$Итеративный алгоритм. Задаём произвольное начальное приближение $V_0$ (обычно нули) и повторяем:
$$V_{k+1}(s) \leftarrow \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a) \left[ r + \gamma V_k(s') \right]$$Почему сходится. Оператор Беллмана — сжимающее отображение с коэффициентом $\gamma$: каждое применение умножает ошибку на $\gamma$. По теореме Банаха о неподвижной точке последовательность $V_k$ сходится к единственному решению $V^\pi$ независимо от начального приближения. Останавливаемся, когда максимальное изменение $\max_s |V_{k+1}(s) - V_k(s)|$ станет меньше $\theta$.
def policy_evaluation_taxi(env, policy, gamma=0.99, theta=1e-6):
nS = env.observation_space.n
nA = env.action_space.n
V = np.zeros(nS)
while True:
V_new = np.zeros(nS)
for s in range(nS):
val = 0.0
for a in range(nA):
q_sa = 0.0
for prob, s2, r, done in env.P[s][a]:
q_sa += prob * (r + (0.0 if done else gamma * V[s2]))
val += policy[s, a] * q_sa
V_new[s] = val
if np.max(np.abs(V_new - V)) < theta:
return V_new
V = V_new
taxi = gym.make('Taxi-v4').unwrapped
uniform = np.full((taxi.observation_space.n, taxi.action_space.n), 1.0 / taxi.action_space.n)
V_uniform = policy_evaluation_taxi(taxi, uniform)
print('Мин/макс V при случайной политике:', round(V_uniform.min(), 2), round(V_uniform.max(), 2))
print('V состояния 0:', round(V_uniform[0], 2))
Задача 5. Сравните значения $V$ для состояний, где пассажир ещё на пункте (ожидает такси), и для состояний, где он уже в такси. Где ценность выше и почему?
# Ваш Код
8. Value iteration — теория¶
Оптимальная ценность. $V^*(s) = \max_\pi V^\pi(s)$ — наилучший возможный доход из состояния $s$. Аналогично $Q^*(s,a)$ — наилучший доход, если сначала выполнить действие $a$, а дальше действовать оптимально.
Уравнение оптимальности Беллмана:
$$V^*(s) = \max_a \sum_{s',r} p(s',r|s,a) \left[ r + \gamma V^*(s') \right]$$Отличие от уравнения для $V^\pi$ — максимум вместо усреднения по политике.
Алгоритм value iteration.
$$V_{k+1}(s) \leftarrow \max_a \sum_{s',r} p(s',r|s,a) \left[ r + \gamma V_k(s') \right]$$После сходимости получаем $V^*$, а оптимальную политику строим жадно:
$$\pi^*(s) = \arg\max_a \sum_{s',r} p(s',r|s,a) \left[ r + \gamma V^*(s') \right] = \arg\max_a Q^*(s,a)$$Связь с policy iteration. Value iteration — это «усечённая» итерация политики: вместо полной оценки текущей политики до сходимости мы делаем один проход с максимумом. Оба метода находят $V^*$, но value iteration обычно требует меньше вычислений.
def value_iteration_taxi(env, gamma=0.99, theta=1e-6):
nS = env.observation_space.n
nA = env.action_space.n
V = np.zeros(nS)
while True:
V_new = np.zeros(nS)
for s in range(nS):
q = np.zeros(nA)
for a in range(nA):
for prob, s2, r, done in env.P[s][a]:
q[a] += prob * (r + (0.0 if done else gamma * V[s2]))
V_new[s] = np.max(q)
if np.max(np.abs(V_new - V)) < theta:
return V_new
V = V_new
taxi = gym.make('Taxi-v4').unwrapped
V_star = value_iteration_taxi(taxi)
print('V* состояния 0:', round(V_star[0], 2))
def greedy_policy_taxi(env, V, gamma=0.99):
nS = env.observation_space.n
nA = env.action_space.n
policy = np.zeros(nS, dtype=int)
for s in range(nS):
q = np.zeros(nA)
for a in range(nA):
for prob, s2, r, done in env.P[s][a]:
q[a] += prob * (r + (0.0 if done else gamma * V[s2]))
policy[s] = int(np.argmax(q))
return policy
policy = greedy_policy_taxi(taxi, V_star)
print('Политика построена: для каждого из 500 состояний выбрано действие.')
taxi = gym.make('Taxi-v4').unwrapped
actions_names = ['вниз', 'вверх', 'вправо', 'влево', 'подобрать', 'высадить']
for s in [0, 100, 200, 300, 400]:
print(s, taxi.decode(s), '->', actions_names[policy[s]])
Задача 6. Возьмите несколько состояний с разных этапов поездки (пассажир на пункте / пассажир в такси) и выведите выбранные политикой действия. Логичны ли они?
# Ваш Код
9. Проверка политики в среде — теория¶
Идея. До этого мы использовали модель env.P и считали ценности точно. Теперь проверим политику без модели: запустим её в среде и усредним фактически полученные награды.
Монте-Карло оценка $J(\pi)$. Запускаем политику $N$ эпизодов, в каждом получаем суммарную награду (доход) $G^{(i)}$, и усредняем:
$$\hat{J}(\pi) = \frac{1}{N} \sum_{i=1}^{N} G^{(i)}$$Это оценка ожидаемого дохода $J(\pi) = \mathbb{E}_\pi[G_0]$.
Зачем сравнивать со случайной политикой. Случайная политика — простой baseline: если наша политика не лучше случайной, значит, она ничему не научилась. Разница между средней наградой оптимальной и случайной политики показывает «выигрыш» от обучения.
Отличие от точного расчёта. Здесь есть шум выборки: при малом $N$ оценка колеблется. Поэтому берём много эпизодов, а для воспроизводимости фиксируем сиды (seed=ep).
def evaluate_policy(env, policy, n_episodes=100):
total = 0.0
for ep in range(n_episodes):
obs, info = env.reset(seed=ep)
done = False
while not done:
obs, reward, terminated, truncated, info = env.step(int(policy[obs]))
total += reward
done = terminated or truncated
return total / n_episodes
env = gym.make('Taxi-v4')
random_pol = np.random.randint(0, 6, size=env.observation_space.n)
print('Средняя награда случайной политики:', round(evaluate_policy(env, random_pol), 2))
print('Средняя награда оптимальной политики:', round(evaluate_policy(env, policy), 2))
env.close()
Задание 7. Визуализируйте один эпизод оптимальной политики (через render_mode='ansi' или функцию render_taxi): видно ли, как такси едет к пассажиру, подбирает и довозит его?
# Ваш Код