Занятие 6

Лабораторная 6. Введение в обучение с подкреплением: MDP

0. Подготовка окружения

Убедимся, что нужные библиотеки установлены.

In [ ]:
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__)
numpy: 2.4.6
gymnasium: 1.4.0

1. Цикл «агент — среда»

В RL агент и среда обмениваются сообщениями: агент видит состояние $s$, выбирает действие $a$, а среда возвращает награду $r$ и следующее состояние $s'$. В библиотеке Gymnasium этот цикл уже реализован.

Шаг (step) — один такт взаимодействия: агент наблюдает состояние, выбирает действие, получает награду и новое состояние.

Эпизод (episode) — последовательность шагов от начального состояния до завершения. В CartPole эпизод заканчивается, когда шест падает (terminated) или достигнут лимит шагов (truncated).

Посмотрим на среду CartPole: тележка на рельсе, на ней шарнирно закреплён шест. Наблюдение — вектор из четырёх чисел:

  • $x$ — положение тележки;
  • $\dot{x}$ — скорость тележки;
  • $\theta$ — угол шеста;
  • $\dot{\theta}$ — угловая скорость шеста.

Действий два: $0$ — толкать влево, $1$ — толкать вправо. Награда $+1$ за каждый шаг, пока шест не упал.

In [ ]:
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()

Реализуем простейшую стратегию (политику): на каждом шаге будем выбирать случайное действие.

In [ ]:
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()
a=0, r=1.0, obs=[ 0.013 -0.217 -0.047  0.23 ]
a=0, r=1.0, obs=[ 0.009 -0.412 -0.042  0.507]
a=1, r=1.0, obs=[ 0.001 -0.216 -0.032  0.201]
a=0, r=1.0, obs=[-0.004 -0.411 -0.028  0.484]
a=1, r=1.0, obs=[-0.012 -0.215 -0.018  0.182]
a=0, r=1.0, obs=[-0.016 -0.41  -0.015  0.469]
a=0, r=1.0, obs=[-0.024 -0.605 -0.005  0.757]
a=1, r=1.0, obs=[-0.037 -0.41   0.01   0.463]
a=1, r=1.0, obs=[-0.045 -0.215  0.019  0.173]
a=1, r=1.0, obs=[-0.049 -0.02   0.022 -0.114]
a=1, r=1.0, obs=[-0.049  0.175  0.02  -0.399]
a=0, r=1.0, obs=[-0.046 -0.021  0.012 -0.1  ]
a=1, r=1.0, obs=[-0.046  0.174  0.01  -0.389]
a=1, r=1.0, obs=[-0.043  0.369  0.002 -0.678]
a=1, r=1.0, obs=[-0.035  0.564 -0.011 -0.97 ]
a=1, r=1.0, obs=[-0.024  0.76  -0.031 -1.266]
a=0, r=1.0, obs=[-0.009  0.565 -0.056 -0.983]
a=1, r=1.0, obs=[ 0.002  0.761 -0.076 -1.293]
a=1, r=1.0, obs=[ 0.018  0.957 -0.101 -1.608]
a=1, r=1.0, obs=[ 0.037  1.153 -0.134 -1.931]
a=0, r=1.0, obs=[ 0.06   0.959 -0.172 -1.683]
a=1, r=1.0, obs=[ 0.079  1.156 -0.206 -2.023]
a=1, r=1.0, obs=[ 0.102  1.353 -0.246 -2.372]
/usr/local/lib/python3.13/dist-packages/matplotlib/animation.py:908: UserWarning: Animation was deleted without rendering anything. This is most likely not intended. To prevent deletion, assign the Animation to a variable, e.g. `anim`, that exists until you output the Animation using `plt.show()` or `anim.save()`.
  warnings.warn(

Задача 1 Напишите свою эвристическую политику для CartPole, которая балансирует шест лучше случайной.

Затем сравните награду (за эпизод) вашей политики и случайной.

In [ ]:
# Ваш Код

2. Доход и дисконтирование

Доход (return) — это дисконтированная сумма будущих наград:

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots$$

Коэффициент $\gamma \in [0, 1]$ определяет, насколько агент ценит будущее. Реализуем подсчёт дохода двумя способами: «в лоб» и рекурсивно (справа налево).

In [ ]:
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}')
gamma=0.0: loop=1.0000, recursive=1.0000
gamma=0.5: loop=1.8750, recursive=1.8750
gamma=0.9: loop=3.4390, recursive=3.4390
gamma=1.0: loop=4.0000, recursive=4.0000

Задача 2

  • Чему равен доход при γ = 1, если наград бесконечно много и все они равны 1?
  • Зачем вводят γ < 1, если горизонт эпизода конечен?

Ваш ответ:

3. MDP: полоска из трёх клеток

Среда: полоска клеток 0, 1, 2. В клетке 2 — цель (награда +1, эпизод завершается). В каждой клетке два действия: «вправо» и «стоять». Переходы детерминированы, γ = 0.9.

Посчитаем функции ценности V и Q для политики «всегда вправо» вручную, как на лекции.

In [ ]:
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}')
V = [0.9 1.  0. ]
Q(0, вправо) = 0.900,  Q(0, стоять) = 0.810
Q(1, вправо) = 1.000,  Q(1, стоять) = 0.900

Жадная политика — это правило, по которому в каждом состоянии выбирается действие с наибольшей ценностью: $\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).

Решим уравнение Беллмана для нескольких политик и сравним их.

In [ ]:
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}')
pi1: всегда вправо           -> J(pi) = V(0) = 0.9000
pi2: всегда стоять           -> J(pi) = V(0) = 0.0000
pi3: вправо, потом стоять    -> J(pi) = V(0) = 0.0000
pi4: стохастическая 0.8      -> J(pi) = V(0) = 0.8566

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 у пассажира означает «уже в такси».

In [ ]:
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()
Начальное состояние: 314
Расшифровка (строка, столбец, пассажир, назначение): (3, 0, 3, 2)

+---------+
|R: | : :G|
| : | : : |
| : : : : |
| | : | : |
|Y| : |B: |
+---------+


Текстовый вывод не слишком нагляден, поэтому нарисуем немного другой

In [ ]:
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).

In [ ]:
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()
a=5, r=-10, obs=252, decode=(2, 2, 3, 0)
a=0, r=-1, obs=352, decode=(3, 2, 3, 0)
a=3, r=-1, obs=332, decode=(3, 1, 3, 0)
a=1, r=-1, obs=232, decode=(2, 1, 3, 0)
a=5, r=-10, obs=232, decode=(2, 1, 3, 0)
a=1, r=-1, obs=132, decode=(1, 1, 3, 0)
a=3, r=-1, obs=112, decode=(1, 0, 3, 0)
a=4, r=-10, obs=112, decode=(1, 0, 3, 0)
a=2, r=-1, obs=132, decode=(1, 1, 3, 0)
a=5, r=-10, obs=132, decode=(1, 1, 3, 0)

Ваш ответ:

6. Модель среды: env.P

Taxi — среда с известной моделью: переходы и награды можно прочитать из env.P. Для пары (состояние, действие) там лежит список записей (вероятность, следующее_состояние, награда, завершённость эпизода).

В новых версиях Gymnasium среда обёрнута в TimeLimit, поэтому модель достаём через .unwrapped.

In [ ]:
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])
Состояний: 500 , действий: 6
Состояние 123 = (1, 1, 0, 3)
Переходы по действиям:
  действие 0: [(1.0, 223, -1, False)]
  действие 1: [(1.0, 23, -1, False)]
  действие 2: [(1.0, 123, -1, False)]
  действие 3: [(1.0, 103, -1, False)]
  действие 4: [(1.0, 123, -10, False)]
  действие 5: [(1.0, 123, -10, False)]

Задача 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$.

In [ ]:
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))
Мин/макс V при случайной политике: -395.5 -88.06
V состояния 0: -217.88

Задача 5. Сравните значения $V$ для состояний, где пассажир ещё на пункте (ожидает такси), и для состояний, где он уже в такси. Где ценность выше и почему?

In [ ]:
# Ваш Код

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 обычно требует меньше вычислений.

In [ ]:
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))
V* состояния 0: 18.8
In [ ]:
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 состояний выбрано действие.')
Политика построена: для каждого из 500 состояний выбрано действие.
In [ ]:
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]])
0 (0, 0, 0, 0) -> подобрать
100 (1, 0, 0, 0) -> вверх
200 (2, 0, 0, 0) -> вверх
300 (3, 0, 0, 0) -> вверх
400 (4, 0, 0, 0) -> вверх

Задача 6. Возьмите несколько состояний с разных этапов поездки (пассажир на пункте / пассажир в такси) и выведите выбранные политикой действия. Логичны ли они?

In [ ]:
# Ваш Код

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).

In [ ]:
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()
Средняя награда случайной политики: -1348.85
Средняя награда оптимальной политики: 7.69

Задание 7. Визуализируйте один эпизод оптимальной политики (через render_mode='ansi' или функцию render_taxi): видно ли, как такси едет к пассажиру, подбирает и довозит его?

In [ ]:
# Ваш Код