Модуль 3. Бандиты, исследование и одношаговые решения

Для каждого случая выберите наиболее точную модель: обычный бандит, контекстный бандит или марковский процесс принятия решений (Markov decision process, MDP).

1. Сервис на каждом независимом запросе выбирает одну из трёх моделей; известны признаки запроса, после ответа приходит скалярная оценка, а выбор не влияет на будущие запросы.

2. Агент открывает страницы сайта, извлекает сведения и решает, какую ссылку открыть дальше.

3. Для одинаковой аудитории поочерёдно показываются два неизменных баннера; регистрируется только клик по показанному баннеру.

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

Для каждого ответа укажите одно предположение, нарушение которого изменило бы выбранную модель.

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

1. Псевдорегрет конкретной траектории можно вычислить без знания истинных средних наград.

2. Разложение $R_T=\sum_a\Delta_a\mathbb{E}[N_a(T)]$ показывает, что неоптимальное действие с малым разрывом может выбираться чаще без большой мгновенной цены.

3. Сублинейный регрет означает $R_T/T\to0$.

4. Логарифмический регрет гарантирует, что алгоритм превосходит все другие алгоритмы на каждом конечном горизонте.

5. Реализованная накопленная награда случайна даже при фиксированной последовательности действий, если награды шумные.

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

1. При постоянном $\varepsilon>0$ ε-жадная стратегия продолжает с положительной частотой выбирать неоптимальные действия.

2. Оптимистичная инициализация гарантирует логарифмический регрет в любой нестационарной среде.

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

4. Чистая жадность всегда имеет линейный регрет на каждом запуске.

5. Убывающее $\varepsilon_t$ автоматически даёт оптимальный регрет независимо от скорости убывания.

Метод верхней доверительной границы (upper confidence bound, UCB) применяется к стационарному бандиту; UCB1 — его классический вариант.

Выберите три условия или оговорки, необходимые для корректного чтения гарантии UCB1.

1. Награды ограничены, в стандартной теореме — интервалом $[0,1]$.

2. Средние наград не меняются со временем.

3. Логарифмическая оценка не зависит от разрывов $\Delta_a$.

4. Конечный регрет может быть заметным, если два действия почти одинаковы.

5. Любой численный показатель неопределённости нейросети является доверительной границей UCB.

6. Множество действий может произвольно меняться по ходу обучения, а классическое доказательство UCB1 остаётся без изменений.

Для бернуллиевского действия задано априорное распределение $\operatorname{Beta}(1,1)$. После 8 успехов и 2 неудач выберите три корректных утверждения.

1. Апостериорное распределение равно $\operatorname{Beta}(9,3)$.

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

3. На каждом раунде сэмплируется одно правдоподобное среднее для каждого действия.

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

5. Дата публикации идеи в 1933 году сама доказывает современную логарифмическую гарантию.

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

1. Если запрос считается контекстом, полный ответ — одним действием, а после скалярной награды эпизод заканчивается, внешняя постановка является контекстным бандитом.

2. Из одношаговой абстракции с наградой за полный ответ следует, что токены перестают быть последовательными действиями.

3. Для многоходового агента с инструментами обычно нужно состояние, содержащее последствия предыдущих действий.

4. Выбор между несколькими моделями для независимых запросов может быть контекстным бандитом.

5. Любая процедура Best-of-N автоматически является многоруким бандитом.

Оценивание с обратной вероятностью выбора (inverse propensity scoring, IPS) используется для новой политики $\pi$ по журналу поведенческой политики $\mu$. Его самонормированная версия — self-normalized inverse propensity scoring (SNIPS), а оцениватель, объединяющий модель награды и веса вероятностей, — оценивателем с двойной устойчивостью (doubly robust estimator, DR).

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

1. Для всех пар $(x,a)$ с $\pi(a\mid x)>0$ требуется $\mu(a\mid x)>0$.

2. Малые вероятности поведения могут создавать большие веса и высокую дисперсию.

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

4. SNIPS-оценка в общем случае имеет смещение.

5. DR создаёт наблюдаемую награду для действия, которое никогда не выбиралось и не моделировалось.

В пункте 6 используется групповая относительная оптимизация политики (group relative policy optimization, GRPO). Выберите четыре корректных утверждения.

1. Повышение температуры чистого softmax при фиксированных логитах делает распределение более плоским.

2. Температурная генерация фиксированной LLM сама по себе обновляет политику по награде.

3. Для независимых кандидатов с одной вероятностью успеха $p$ формула $1-(1-p)^N$ задаёт вероятность наличия хотя бы одного успеха в пуле.

4. Комбинаторный оцениватель pass@$k$ по $n$ кандидатам и $c$ успехам равен $1-\binom{n-c}{k}/\binom{n}{k}$.

5. Снижение энтропии всегда означает ухудшение политики.

6. Если все награды в группе GRPO одинаковы, после вычитания группового среднего относительный сигнал равен нулю.

Действие выбиралось 4 раза. Его текущая оценка равна $Q_4=0.35$. Пятая награда равна $1$.

1. Вычислите $Q_5$ инкрементально.

2. Найдите сумму первых четырёх наград, совместимую с $Q_4$.

3. Проверьте результат прямым средним по пяти наблюдениям.

Средние трёх действий равны

За $T=100$ раундов ожидаемые числа выборов равны

1. Найдите $\mu^*$ и разрывы $\Delta_a$.

2. Вычислите ожидаемый регрет.

3. Как изменится регрет, если 10 выборов второго действия заменить 10 выборами третьего?

На раунде $t=101$ два действия имеют оценки и числа выборов:

Для индекса

вычислите $I_1$ и $I_2$ с точностью до $0.001$ и укажите выбранное действие. Объясните, почему действие с меньшим средним может победить.

Для двух бернуллиевских действий используется априорное распределение $\operatorname{Beta}(1,1)$.

• действие 1: 12 успехов и 8 неудач;
• действие 2: 3 успеха и 1 неудача.

1. Запишите оба апостериорных распределения.

2. Вычислите их средние.

3. Какое действие имеет большее апостериорное среднее?

4. Почему сэмплирование Томпсона всё же может выбрать другое действие?

Журнал содержит:

1. Вычислите веса $w_i=\pi/\mu$.

2. Вычислите $\widehat V_{\mathrm{IPS}}=n^{-1}\sum_iw_ir_i$.

3. Вычислите $\widehat V_{\mathrm{SNIPS}}=\sum_iw_ir_i/\sum_iw_i$.

4. Вычислите DR-оценку.

5. Укажите, какая строка сильнее всего влияет на дисперсию IPS и почему.

Оценки двух действий равны $q=(0,1)$, температура $\tau=0.5$.

1. Вычислите оптимальную энтропийно-регуляризованную политику $\pi^*(a)\propto\exp(q(a)/\tau)$.

2. Если вероятность успеха одного независимого кандидата $p=0.2$, найдите вероятность хотя бы одного успеха при $N=5$.

3. Найдите минимальное $N$, обеспечивающее вероятность не менее $0.9$.

4. Для $n=10$, $c=2$, $k=3$ вычислите оцениватель pass@$k$ по конечной выборке.

5. Объясните, почему ответы из пунктов 2 и 4 описывают разные статистические объекты.

Реализуйте функцию:

import numpy as np

def pseudo_regret_curve(means: np.ndarray, actions: np.ndarray) -> np.ndarray:
    """Вернуть накопленный псевдорегрет после каждого действия."""
    ...

Требования:

• means — одномерный массив средних;
• actions — одномерный массив целых индексов;
• неверный индекс вызывает ValueError;
• результат имеет тип float и ту же длину, что actions.

Проверка:

means = np.array([0.2, 0.5, 0.7])
actions = np.array([0, 2, 1])
# ожидается [0.5, 0.5, 0.7]

Открытые проверки:

np.testing.assert_allclose(
    pseudo_regret_curve([0.2, 0.5, 0.7], [0, 2, 1]),
    [0.5, 0.5, 0.7],
)

Реализуйте:

import numpy as np

def run_epsilon_greedy(
    probabilities: np.ndarray,
    horizon: int,
    epsilon: float,
    seed: int,
) -> tuple[np.ndarray, np.ndarray]:
    """Вернуть массивы действий и наград."""
    ...

Правила:

• награда выбранного действия — rng.random() < probabilities[action];
• при жадной ничьей выбирайте случайно среди максимумов;
• оценка обновляется выборочным средним;
• используйте np.random.default_rng(seed);
• на каждом раунде сначала решается вопрос исследования, затем генерируется награда.

Сравните $\varepsilon=0$, $0.05$ и $0.2$ на одном наборе вероятностей минимум по 100 независимым запускам. Постройте таблицу среднего псевдорегрета: вывод по одному начальному значению генератора случайных чисел недостаточен.

Открытые проверки:

actions, rewards = run_epsilon_greedy([0.1, 0.4, 0.6], 40, 0.1, 17)
assert actions.shape == (40,)
assert rewards.shape == (40,)
assert np.all((rewards == 0.0) | (rewards == 1.0))

Реализуйте UCB1 для наград в $[0,1]$:

import numpy as np

def run_ucb1(
    probabilities: np.ndarray,
    horizon: int,
    seed: int,
) -> tuple[np.ndarray, np.ndarray]:
    ...

Условия:

1. первые $K$ раундов выберите действия 0, 1, ..., K-1;

2. затем используйте $\widehat\mu_a+\sqrt{2\log t/N_a}$;

3. обновляйте среднее инкрементально;

4. верните действия и награды.

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

Открытые проверки:

actions, rewards = run_ucb1([0.1, 0.4, 0.6], 3, 5)
assert np.array_equal(actions, [0, 1, 2])
assert rewards.shape == (3,)

Реализуйте сэмплирование Томпсона с бета-бернуллиевской моделью награды:

import numpy as np

def run_thompson(
    probabilities: np.ndarray,
    horizon: int,
    seed: int,
    prior_alpha: float = 1.0,
    prior_beta: float = 1.0,
) -> tuple[np.ndarray, np.ndarray, np.ndarray, np.ndarray]:
    """Вернуть действия, награды и итоговые alpha/beta."""
    ...

После каждого успеха увеличивайте alpha[action], после неудачи — beta[action]. Сравните с UCB1 на нескольких экземплярах, включая случай с близкими средними. В отчёте отделите наблюдение вашего эксперимента от общей гарантии.

Открытые проверки:

actions, rewards, alpha, beta = run_thompson(
    [0.1, 0.4, 0.6], 10, 23
)
assert actions.shape == rewards.shape == (10,)
assert alpha.shape == beta.shape == (3,)
assert np.isclose((alpha + beta).sum(), 16.0)

Реализуйте три функции:

def ips_value(rewards, behavior_probs, target_probs) -> float:
    ...

def snips_value(rewards, behavior_probs, target_probs) -> float:
    ...

def doubly_robust_value(
    rewards,
    behavior_probs,
    target_probs,
    predictions_logged,
    predictions_target,
) -> float:
    ...

predictions_target[i] уже содержит $\sum_a\pi(a\mid x_i)\widehat r(x_i,a)$. Выдавайте ValueError, если вероятность поведения неположительна. Добавьте эксперимент, где одна вероятность уменьшается от $0.5$ до $0.01$, и покажите, как меняется IPS-вес.

Открытые проверки:

actual = ips_value(
    [1.0, 0.0, 1.0],
    [0.5, 0.25, 0.5],
    [1.0, 0.0, 0.5],
)
assert np.isclose(actual, 1.0)

Реализуйте:

import numpy as np

def stable_softmax(logits, temperature=1.0) -> np.ndarray:
    ...

def categorical_entropy(probabilities) -> float:
    ...

def best_of_n_success(p: float, n: int) -> float:
    ...

def pass_at_k(n: int, c: int, k: int) -> float:
    ...

Требования:

• softmax устойчив к большим логитам;
• энтропия измеряется в натах и использует соглашение $0\log0=0$;
• Best-of-N использует устойчивые log1p/expm1 для малых $p$ и больших $N$;
• pass@$k$ реализуется как $1-\binom{n-c}{k}/\binom{n}{k}$ либо эквивалентное устойчивое произведение;
• недопустимые $n,c,k,p$ вызывают ValueError.

Проверьте, что для фиксированных логитов энтропия возрастает при температурах $0.5$, $1$ и $2$, но не делайте из этого вывода о качестве или истинности ответа.

Открытые проверки:

p = stable_softmax([1000.0, 1001.0])
assert np.isclose(p.sum(), 1.0)
assert np.all(p > 0.0)