Модуль 2. Состояние, ценность и уравнения Беллмана

Рассмотрите четыре ситуации. Для каждой выберите наиболее точный вариант:

• A. наблюдение уже является достаточным марковским состоянием;
• B. наблюдение неполно, и естественна постановка с частичной наблюдаемостью.

1. Видна только координата мяча, но не его скорость; динамика инерционная.

2. Задана полная шахматная позиция, очередь хода, права рокировки и возможность взятия на проходе.

3. В чистой авторегрессионной генерации известны запрос и весь префикс; переход состоит только в добавлении выбранного токена.

4. Агент видит только последние два сообщения. Ранее инструмент сообщил, какой файл открыт, но это сообщение удалено из контекста; следующий ответ зависит от выбранного файла.

Запишите ответ как 1-?, 2-?, 3-?, 4-?. Затем одним предложением объясните, почему фраза «состояние — это сжатая история» полезна, но не является универсальным определением состояния среды.

Выберите три корректных утверждения о конечном марковском процессе принятия решений (Markov decision process, MDP).

1. Политика $\pi(a\mid s)$ является частью динамики $P(s'\mid s,a)$ и не может меняться без изменения MDP.

2. Среднее $\bar r(s,a)$ получается усреднением $\bar r(s,a,s')$ по следующим состояниям с вероятностями $P(s'\mid s,a)$; условная независимость не требуется.

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

4. Любая текстовая история взаимодействия с инструментом автоматически является полным состоянием.

5. Один и тот же MDP можно сочетать с несколькими политиками.

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

Для каждого перехода выберите корректную одношаговую TD-цель. Пусть $r=1$, $\gamma=0.9$, $V(s')=4$.

1. Агент достиг терминальной цели задачи.

2. Эпизод остановлен внешним лимитом сбора данных, но процесс мог бы продолжиться.

3. Задача определена как «завершить не более чем за 100 шагов»; оставшийся бюджет входил в состояние, и лимит исчерпан.

Варианты:

• A. $y=r=1$;
• B. $y=r+\gamma V(s')=4.6$.

Запишите ответ как 1-?, 2-?, 3-?. Одним предложением объясните, почему одного старого признака done недостаточно.

Выберите три корректных утверждения.

1. $V^\pi(s)$ всегда равна $\max_aQ^\pi(s,a)$.

2. $V^\pi(s)=\sum_a\pi(a\mid s)Q^\pi(s,a)$.

3. $A^\pi(s,a)>0$ означает, что действие лучше среднего действия текущей политики в этом состоянии.

4. Если произвольно изменить награды MDP, $A^\pi$ обязательно останется неизменным.

5. Для любого состояния $\sum_a A^\pi(s,a)=0$ независимо от политики.

6. Если ко всем $Q(s,a)$ одного состояния прибавить одну константу $c(s)$ и затем пересчитать $V$, преимущества в этом состоянии не изменятся.

Выберите все утверждения, которые следуют из определений без изменения MDP.

Выберите пять корректных утверждений.

1. Для фиксированной политики уравнение ожидания Беллмана линейно по $V^\pi$.

2. Оператор оптимальности заменяет усреднение по действиям политики максимумом по действиям.

3. Уравнение Беллмана само по себе является конкретным алгоритмом обучения нейросети.

4. При $0\le\gamma<1$ операторы $T_\pi$ и $T_*$ являются $\gamma$-сжатиями в норме максимума.

5. При $\gamma=1$ отдельные корректные эпизодические задачи могут решаться, но обычное доказательство через строгое сжатие уже не применимо.

6. Малый остаток Беллмана всегда означает такую же по величине ошибку ценности независимо от $\gamma$.

7. Неподвижная точка $T_\pi$ соответствует ценности фиксированной политики.

Сопоставьте метод и целевое значение.

Запишите A-?, B-?, C-?.

Затем выберите наиболее точное утверждение:

1. MC всегда имеет меньшую дисперсию, чем TD.

2. TD всегда точнее MC при любом бюджете данных.

3. Компромисс зависит от среды, горизонта, представления, размера шага и бюджета; универсального рейтинга нет.

4. Бутстрэппинг в TD означает повторную выборку эпизодов с возвращением.

Действия собирает $\varepsilon$-жадная политика. Выберите одно наиболее точное утверждение.

1. SARSA и Q-learning оба off-policy, потому что используют случайные действия.

2. SARSA использует фактически выбранное $A_{t+1}$, а Q-learning — $\max_{a'}Q(S_{t+1},a')$; поэтому Q-learning оценивает жадную целевую политику по данным $\varepsilon$-жадного поведения.

3. Q-learning становится off-policy только после добавления буфера повторного использования опыта.

4. SARSA не может использовать $\varepsilon$-жадное исследование.

Выберите четыре корректных утверждения.

1. Средняя награда группы ответов в канонической GRPO является точным токеновым $V^\pi(s_t)$ для каждого префикса.

2. Групповая нормировка даёт относительный сигнал без отдельного обучаемого критика, но остаётся выборочной статистикой группы полных ответов.

3. Максимум по шумным несмещённым оценкам может иметь положительное смещение отбора.

4. Double Q-learning разделяет выбор действия и его оценивание между двумя оценивателями.

5. Double Q-learning гарантирует абсолютно несмещённую оценку при любой зависимости ошибок.

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

В состоянии $s$ два действия:

Вычислите $V^\pi(s)$, $A^\pi(s,a_1)$ и $A^\pi(s,a_2)$. Затем проверьте нулевое среднее преимущества по политике.

В состоянии $s$ доступны два действия.

• $a_1$ детерминированно ведёт в $s_1$ с наградой $1$, $V(s_1)=3$;
• $a_2$ с вероятностью $0.5$ ведёт в $s_2$ с наградой $0$, $V(s_2)=6$, и с вероятностью $0.5$ — в $s_3$ с наградой $2$, $V(s_3)=1$.

Пусть $\gamma=0.9$. Вычислите одношаговые $Q(s,a_1)$ и $Q(s,a_2)$, затем $(T_*V)(s)$ и жадное действие.

Есть одно нетерминальное состояние $s$ и терминал. Из $s$ фиксированная политика:

• с вероятностью $0.5$ переходит в терминал с наградой $0$;
• с вероятностью $0.5$ возвращается в $s$ с наградой $1$.

При $\gamma=0.9$ запишите уравнение Беллмана для $V^\pi(s)$ и решите его точно.

Дано

Вычислите новое $V(s)$ в трёх случаях:

1. обычный нетерминальный переход;

2. настоящий терминальный переход;

3. техническое усечение, после которого процесс мог бы продолжиться.

Наблюдены награды $[1,2,3]$, $\gamma=0.5$, а $V(S_{t+3})=4$. Вычислите

Как изменится ответ, если третий переход завершил задачу терминально?

Пусть в следующем состоянии

$r=0.5$, $\gamma=0.9$.

1. Вычислите обычную Q-learning цель, используя $Q^A$ и максимум той же таблицы.

2. Вычислите Double Q-цель, если действие выбирается по $Q^A$, а оценивается по $Q^B$.

3. Объясните, почему числа заметно различаются.

Реализуйте две небольшие функции. Обе получают массивы формы (n_states, n_actions).

import numpy as np


def v_from_q(q_values: np.ndarray, policy: np.ndarray) -> np.ndarray:
    """V(s) = sum_a policy[s,a] * q_values[s,a]."""
    raise NotImplementedError


def advantage(q_values: np.ndarray, policy: np.ndarray) -> np.ndarray:
    """A(s,a) = Q(s,a) - V(s)."""
    raise NotImplementedError

Минимальная проверка:

Q = np.array([[1., 3.], [0., 2.]])
pi = np.array([[0.5, 0.5], [0.2, 0.8]])
np.testing.assert_allclose(v_from_q(Q, pi), [2.0, 1.6])
np.testing.assert_allclose(advantage(Q, pi), [[-1.0, 1.0], [-1.6, 0.4]])
np.testing.assert_allclose((pi * advantage(Q, pi)).sum(axis=1), 0.0, atol=1e-12)

Реализуйте решение линейной системы по нетерминальным состояниям:

def exact_policy_value(
    transitions: np.ndarray,  # (nS, nA, nS)
    rewards: np.ndarray,      # E[R | s,a,s'], та же форма
    policy: np.ndarray,       # (nS, nA)
    gamma: float,
    terminals: np.ndarray,    # bool, (nS,)
) -> np.ndarray:
    """Терминальные значения остаются нулевыми."""
    raise NotImplementedError

Используйте

Функция должна вернуть нули для терминалов и решить $(I-\gamma P_{NN})V_N=r_N$ для множества нетерминальных состояний $N$.

Минимальная проверка:

P = np.zeros((2, 1, 2))
R = np.zeros_like(P)
P[0, 0] = [0.5, 0.5]
R[0, 0] = [1.0, 0.0]
P[1, 0, 1] = 1.0
pi = np.ones((2, 1))
terminal = np.array([False, True])
np.testing.assert_allclose(
    exact_policy_value(P, R, pi, 0.9, terminal),
    [10.0 / 11.0, 0.0],
)

Реализуйте локальную механику итерации ценности: сначала вычислите значения всех действий из старого вектора $V$, затем максимум по действиям.

def bellman_optimality_sweep(
    transitions: np.ndarray,
    rewards: np.ndarray,
    values: np.ndarray,
    gamma: float,
    terminals: np.ndarray,
) -> np.ndarray:
    """Верните T_* V; терминальные компоненты равны нулю."""
    raise NotImplementedError

Важно: функция выполняет один синхронный проход, а не обновляет состояния последовательно на месте.

Минимальная проверка одного синхронного прохода:

P = np.zeros((3, 2, 3))
R = np.zeros_like(P)
P[0, 0, 1] = 1.0
P[0, 1, 2] = 1.0
R[0, 0, 1] = 1.0
R[0, 1, 2] = 2.0
P[1, :, 1] = 1.0
P[2, :, 2] = 1.0
V = np.array([0.0, 3.0, 1.0])
out = bellman_optimality_sweep(P, R, V, 0.9, np.zeros(3, dtype=bool))
assert abs(out[0] - 3.7) < 1e-12

Реализуйте одношаговую и $n$-шаговую цели. Внешнее truncated=True само по себе не должно обнулять продолжение.

def td_target(
    reward: float,
    next_value: float,
    gamma: float,
    *,
    terminated: bool,
    truncated: bool = False,
) -> float:
    raise NotImplementedError


def n_step_target(
    rewards: list[float],
    bootstrap_value: float,
    gamma: float,
    *,
    terminated_at_end: bool,
) -> float:
    raise NotImplementedError

Проверки:

assert td_target(1, 2, 0.9, terminated=False) == 2.8
assert td_target(1, 2, 0.9, terminated=True) == 1.0
assert td_target(1, 2, 0.9, terminated=False, truncated=True) == 2.8
assert abs(n_step_target([1, 2, 3], 4, 0.5, terminated_at_end=False) - 3.25) < 1e-12
assert abs(n_step_target([1, 2, 3], 4, 0.5, terminated_at_end=True) - 2.75) < 1e-12

Реализуйте две функции для уже известного вектора $Q(s',\cdot)$.

def q_learning_target(
    reward: float,
    next_q_values: np.ndarray,
    gamma: float,
    *,
    terminated: bool,
) -> float:
    raise NotImplementedError


def sarsa_target(
    reward: float,
    next_q_values: np.ndarray,
    next_action: int,
    gamma: float,
    *,
    terminated: bool,
) -> float:
    raise NotImplementedError

Терминальный переход не должен обращаться к продолжению. Для нетерминального перехода Q-learning использует максимум, а SARSA — значение фактически выбранного next_action.

Минимальная проверка:

q_next = np.array([1.0, 4.0, 3.0])
assert q_learning_target(0.5, q_next, 0.9, terminated=False) == 4.1
assert sarsa_target(0.5, q_next, 2, 0.9, terminated=False) == 3.2
assert q_learning_target(1.0, np.array([]), 0.9, terminated=True) == 1.0
assert sarsa_target(1.0, np.array([]), 99, 0.9, terminated=True) == 1.0

Реализуйте Double Q-цель: одна таблица выбирает индекс действия, другая оценивает выбранный индекс.

def double_q_target(
    reward: float,
    selector_q: np.ndarray,
    evaluator_q: np.ndarray,
    gamma: float,
    *,
    terminated: bool,
) -> float:
    raise NotImplementedError

Проверка:

qa = np.array([1., 4., 3.])
qb = np.array([10., 2., 8.])
assert double_q_target(0.5, qa, qb, 0.9, terminated=False) == 2.3
assert double_q_target(0.5, qa, qb, 0.9, terminated=True) == 0.5