Causal Calculus

Причинное обучение с подкреплением

Стандартный бандит не может отличить 'реклама работает' от 'богатые пользователи видят рекламу и покупают'. Причинный бандит использует do-исчисление: он оценивает $Q^*(a) = E[R|\mathrm{do}(A=a)]$, а не $E[R|A=a]$. Это позволяет избежать конфаундинга и снизить сожаление с $O(\sqrt{|\mathcal{A}|T})$ до $O(\sqrt{dT\log T})$.

Персонализация рекламы: причинный эффект показа объявления, а не корреляция с кликом
Клинические испытания адаптивного дизайна: выбор следующего лечения на основе do-оценки
Рекомендательные системы: деконфаундирование популярности от персонального предпочтения
Автономные агенты: планирование с учётом причинной структуры окружения
A/B тестирование при интерференции: сетевые эффекты нарушают SUTVA

Цели урока

Формализовать каузальный Q-функционал через do-оператор и отличать от стандартного Q-обучения
Понимать поправку на важность выборки (IS) для офлайн-оценки политик
Сравнивать сожаление $O(\sqrt{dT\log T})$ причинного бандита с $O(\sqrt{|\mathcal{A}|T})$ стандартного UCB

Предварительные знания

Do-исчисление и критерий бэкдора
Многорукий бандит: UCB, Thompson Sampling, сожаление
Q-обучение и уравнение Беллмана

Каузальный Q-функционал

Стандартное Q-обучение оценивает $Q(s,a) = E[R|S=s, A=a]$ - наблюдательную корреляцию. При наличии конфаундеров (ненаблюдаемые переменные, влияющие как на политику, так и на награду) это смещено. Каузальный Q: $Q^*(s,a) = E[R|S=s, \mathrm{do}(A=a)]$ - истинный эффект вмешательства. При отсутствии конфаундинга они совпадают.

Поправка на важность выборки (IS)

Офлайн-оценка политики $\pi$ по данным от поведенческой политики $\mu$: $V^\pi = E_{\mu}\left[\frac{\pi(A|S)}{\mu(A|S)} R\right]$. IS-веса $w = \pi/\mu$ корректируют распределение. При больших отклонениях $\pi$ от $\mu$ дисперсия растёт; doubly-robust оценщик снижает её через аддитивную коррекцию модели исхода.

Сожаление причинного бандита

Стандартный UCB-бандит с $|\mathcal{A}|$ действиями: сожаление $O(\sqrt{|\mathcal{A}|T\log T})$. Если известна причинная структура (DAG) с $d$ родительскими переменными действия, причинный UCB достигает $O(\sqrt{dT\log T})$. Когда $d \ll |\mathcal{A}|$, выигрыш огромен: структура среды уменьшает пространство поиска.

Причинная Q-функция и do-calculus в MDP

Lu et al. (2021) показали: если среда описывается SCM, причинная Q-функция Q^causal(s,a) = E[sum γ^t R_t | do(A=a), S=s] устраняет смещение обычного Q(s,a) = E[R|S=s, A=a], возникающее из-за конфаундеров, влияющих на выбор действий. Разница критична при off-policy обучении: biased reward → suboptimal policy.

Чем причинная Q-функция отличается от стандартной Q(s,a)?

Сожаление причинного агента и SCM среды

Lattimore et al. (2016) показали: агент с известной причинной структурой среды достигает сожаления O(sqrt(dT log T)), где d - размерность DAG, против O(sqrt(|A|T)) для наивного бандита. При |A| = 100 и d = 5 это сокращение в sqrt(20) ≈ 4.5 раз. Задача: агент строит SCM среды, выбирает вмешательство в родителей целевой переменной, а не прямо в неё.

Какое сожаление достигает агент, знающий причинную структуру среды с DAG размерностью d?

Причинный бандит: две руки с конфаундером

Конфаундер $Z$ влияет на выбор $A$ (реклама показывается богатым) и на $R$ (богатые покупают чаще). Наблюдательная оценка $E[R|A=1] > E[R|A=0]$ даже если реклама не работает. Критерий бэкдора: $E[R|\mathrm{do}(A=a)] = \sum_z E[R|A=a, Z=z]P(Z=z)$ - усреднение по $Z$ устраняет смещение.

Итоги

Каузальный Q $= E[R|\mathrm{do}(A=a)]$ отличается от наблюдательного $E[R|A=a]$ при конфаундинге политики
IS-поправка $w = \pi/\mu$ обеспечивает несмещённую офлайн-оценку; DR-оценщик снижает дисперсию
Причинный UCB с DAG-структурой: сожаление $O(\sqrt{dT})$ vs $O(\sqrt{|\mathcal{A}|T})$ при $d \ll |\mathcal{A}|$

Связь с другими темами

Причинное RL объединяет структурные причинные модели и теорию обучения с подкреплением. Смежные направления: офлайн RL с деконфаундированием, мировые модели на основе SCM для планирования, причинная инференция в рекомендательных системах для устранения смещения популярности.

Связанные темы — развивает

Вопросы для размышления

Когда причинный Q совпадает со стандартным Q? Какое структурное условие это гарантирует?
IS-веса могут быть очень большими при сильном отклонении политик. Как clipping весов влияет на смещение и дисперсию?
Если DAG неизвестен, можно ли одновременно открывать структуру и минимизировать сожаление? Какой компромисс возникает?