Оптимизация бандитов

Томпсон предложил свой алгоритм ещё в 1933 году, но его оптимальность доказали только в 2012 году Chapelle и Li. 80 лет простой байесовский алгоритм ждал строгого анализа - и оказался оптимальным по Lai-Robbins.

• A/B тестирование: бандиты позволяют адаптивно распределять трафик к лучшей версии
• Клиническое испытание: бандитное распределение пациентов минимизирует вред
• Рекламные аукционы: LinUCB выбирает объявления с учётом контекста пользователя

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

• Предыдущий урок

UCB и Thompson Sampling

Lai и Robbins (1985) доказали нижнюю границу на сожаление многорукого бандита: R_T ≥ ∑_{i: μ_i<μ*} (μ*-μ_i)·log(T)/KL(μ_i, μ*). UCB1 (Auer 2002) достигает этой границы: выбирать руку i* = argmax μ̂_i + √(2 log t / n_i). Thompson Sampling (1933, переоткрыт Chapelle 2011) достигает того же сожаления байесовски.

Контекстные бандиты и LinUCB

LinUCB (Li et al. 2010): в каждом раунде наблюдается контекст x_t ∈ R^d, вознаграждение r_t = θ^T x_{t,a} + ε. Оценка θ через Ridge-регрессию, UCB = θ̂^T x + α√(x^T A^{-1} x). Сожаление O(d√T) вместо O(√(KT)). Основа рекомендательных систем Netflix, Yahoo! News.

Ключевые идеи

• UCB1: i* = argmax [μ̂_i + √(2 log t / n_i)], R_T = O(log T)
• Нижняя граница Lai-Robbins: R_T ≥ ∑ Δ_i log T / KL(μ_i, μ*)
• Thompson Sampling: θ_i ~ Beta(α_i, β_i), выбор argmax θ_i
• LinUCB: UCB = θ̂^T x + α√(x^T A^{-1} x), R_T = O(d√T)
• Контекстные бандиты: структура признаков заменяет перебор рук

Дальнейшие пути

Изученные концепции открывают следующие разделы.

• co-29-bayesian-opt — extends

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

• Приведите конкретный пример вычисления.
• Как изученные концепции связаны с другими разделами математики?