Статистическая теория обучения

Online Learning и Bandit Algorithms

Алгоритм UCB в Amazon A/B-тестировании на 200M пользователях даёт regret O(√(KT·log T)) против O(T) случайного выбора - это означает, что при T=200M тестов UCB теряет в √200M ≈ 14000 раз меньше, чем random. LinUCB в Yahoo! News увеличил CTR на 12.5%. Google Ads использует contextual bandits для real-time bidding на 5B+ аукционах в день. Это не академия - это несколько миллиардов долларов ежегодной выручки.

**Amazon Explore:** multi-armed bandits для A/B-тестирования UI изменений на 300M пользователей. Экономия: не нужно ждать стат. значимости, optimal allocation в realttime.
**Google Ads Smart Bidding:** contextual LinUCB (с нелинейными features через deep nets) для ставок в RTB аукционах. Обрабатывает 5M+ запросов/сек.
**Netflix thumbnails:** Thompson Sampling для выбора thumbnail'а - для каждого пользователя разный. 20%+ lift в click-through rate на browse.

Online Convex Optimization: regret bounds и Follow-the-Leader

**Алгоритм UCB в Amazon A/B-тестировании на 200M пользователях даёт regret O(√(KT·log T)) против O(T) случайного выбора.** Online Convex Optimization (OCO) - игра между алгоритмом и adversary: на каждом шаге t алгоритм выбирает w_t, получает функцию потерь f_t(w_t), goal - минимизировать cumulative regret. Это обобщает стохастический SGD на adversarial setting.

**Применения OCO:** AdaGrad, Adam, RMSProp - это FTRL с разными регуляризаторами. Online SVM, online logistic regression. Hedge (Multiplicative Weights) - optimal для expert problem. Все алгоритмы онлайн-рекламы (Google, Meta) - это OCO.

Какой regret достигает Online Gradient Descent для выпуклых потерь за T шагов?

OGD с lr = D/(G√T) достигает R_T ≤ DG√T. Это O(√T) - оптимальный minimax regret для online convex optimization с выпуклыми функциями потерь. Для strongly convex - можно O(log T).

Multi-Armed Bandits: UCB1 и теория сожаления

**Multi-Armed Bandit (MAB)** - задача последовательного принятия решений с частичной обратной связью: K рычагов, на каждом шаге выбрать один, получить стохастическую награду. Задача: баланс exploration и exploitation. UCB1 - theoretically optimal алгоритм с доказанным regret O(√(KT log T)).

**Variants:** Thompson Sampling (Bayesian UCB) - sample от posterior, O(√(KT log T)) regret, лучше на практике. EXP3 - adversarial bandits O(√(KT log K)). Gradient Bandits - REINFORCE в bandit setting.

Каков expected regret UCB1 за T шагов с K рычагами?

UCB1 имеет instance-dependent regret O(∑ log(T)/Δᵢ) и worst-case O(√(KT log T)). Нижняя граница Auer et al. - Ω(√(KT)), поэтому UCB1 оптимален с точностью до log T.

Contextual Bandits: LinUCB для рекомендаций

**Contextual bandits** - обобщение MAB: на каждом шаге наблюдается context x_t (features пользователя/запроса), алгоритм выбирает действие a_t, получает награду r_t. LinUCB (Li et al., 2010) предполагает линейную модель награды и строит confidence ellipsoid в feature space. Используется в Yahoo! News, Google Search, Netflix.

**Production deployment:** Yahoo! News (2010) использовал LinUCB для персонализации новостной ленты - CTR +12.5%. Google Ads - contextual bandits для ставок в реальном времени. Netflix - LinUCB для рекомендаций thumbnail'ов. Thompson Sampling (Bayesian LinUCB) обычно лучше на практике.

Чем contextual bandits отличается от обычного multi-armed bandit?

В contextual bandits на каждом шаге t наблюдается context x_t (например, user features), алгоритм выбирает действие a_t с учётом x_t, получает награду r_t. Это позволяет персонализировать: для разных users выбирать разные arms. В обычном MAB контекста нет.

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

**OCO regret:** R_T = cumulative loss - best fixed решение. OGD достигает O(√T) для выпуклых потерь - оптимально. FTRL с правильным регуляризатором => AdaGrad.
**UCB1:** выбирать arm с max(hat_mu + sqrt(2 ln t / N_k)). E[R_T] ≤ ∑ 8 ln(T)/Δᵢ + const. Worst-case O(√(KT log T)).
**Нижняя граница Lai-Robbins:** нельзя лучше Ω(∑ ln(T)/Δᵢ). UCB1 оптимален до константы.
**LinUCB:** модель награды r = θ_a^T x. UCB через confidence ellipsoid x^T A^{-1} x. Regret O(d√(T log³(KT))).
**Thompson Sampling:** Bayesian альтернатива UCB. Эмпирически лучше, теоретически те же bounds.

Связанные темы

Online learning и bandits - мост к reinforcement learning:

Online regret (урок 12) — Введение в online learning с Hedge и Weighted Majority
Reinforcement Learning — Bandits - RL без состояний и transitions

Связанные уроки

lt-12-online-regret — Урок 12 вводил online learning; здесь полные доказательства и bandits
lt-18-vc-sample-complexity — PAC bounds и regret bounds - два режима теории обобщения
ml-48-rl-intro — Bandits - простейший случай RL без состояний

Online Convex Optimization: regret bounds и Follow-the-Leader

Какой regret достигает Online Gradient Descent для выпуклых потерь за T шагов?

Multi-Armed Bandits: UCB1 и теория сожаления

Каков expected regret UCB1 за T шагов с K рычагами?

Contextual Bandits: LinUCB для рекомендаций

Чем contextual bandits отличается от обычного multi-armed bandit?

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

**OCO regret:** R_T = cumulative loss - best fixed решение. OGD достигает O(√T) для выпуклых потерь - оптимально. FTRL с правильным регуляризатором => AdaGrad.

**UCB1:** выбирать arm с max(hat_mu + sqrt(2 ln t / N_k)). E[R_T] ≤ ∑ 8 ln(T)/Δᵢ + const. Worst-case O(√(KT log T)).

**Нижняя граница Lai-Robbins:** нельзя лучше Ω(∑ ln(T)/Δᵢ). UCB1 оптимален до константы.

**LinUCB:** модель награды r = θ_a^T x. UCB через confidence ellipsoid x^T A^{-1} x. Regret O(d√(T log³(KT))).

**Thompson Sampling:** Bayesian альтернатива UCB. Эмпирически лучше, теоретически те же bounds.

Связанные уроки

lt-12-online-regret — Урок 12 вводил online learning; здесь полные доказательства и bandits

lt-18-vc-sample-complexity — PAC bounds и regret bounds - два режима теории обобщения

ml-48-rl-intro — Bandits - простейший случай RL без состояний