Linear Upper Confidence Bound (LinUCB)

LinUCB — это один из самых популярных алгоритмов контекстных многоруких бандитов (Contextual Bandits), который идеально подходит для персонализированных рекомендаций, где важно учитывать контекст пользователя и баланс между исследованием и эксплуатацией.

LinUCB особенно полезен в сценариях с ограниченными данными.

Основные бласти применения

Рекомендательные системы (Выбор рекламного баннера или товара для пользователя на основе его демографии и истории просмотров)
Торговля ( Подбор оптимальной цены для товара в реальном времени)
Биотехнологии и медицина (Подбор персонализированного лечения на основе симптомов пациента)
Социальные сети (Выбор поста или уведомления, который максимизирует вовлечённость)

1. Основная идея LinUCB

LinUCB сочетает:

Линейную регрессию для предсказания награды (например, кликабельности) на основе контекста.
Принцип UCB (Upper Confidence Bound) для исследования новых действий.

Формула выбора действия

Для каждого действия $ a $ (например, товара) вычисляется оценка + доверительный интервал:

\[ \text{score}(a) = \theta_a^T x + \alpha \sqrt{x^T A_a^{-1} x} \]

где:

$ x $ — контекст пользователя (например, возраст, история просмотров),
$ \theta_a $ — веса для действия $ a $,
$ A_a $ — матрица ковариации для действия $ a $,
$ \alpha $ — параметр исследования (чем выше, тем больше exploration).

Алгоритм выбирает действие с максимальным score.

2. Где применяется LinUCB?

Персонализированные рекомендации (новости, товары, музыка).
A/B-тестирование с динамическим выбором лучшего варианта.
Медицинские назначения (подбор лечения на основе симптомов).

3. Пример на Python

import numpy as np

class LinUCB:
    def __init__(self, n_actions, context_dim, alpha=1.0):
        self.n_actions = n_actions
        self.context_dim = context_dim
        self.alpha = alpha

        # Инициализация для каждого действия:
        # A_a = I_d (матрица ковариации)
        # b_a = нулевой вектор
        self.A = [np.identity(context_dim) for _ in range(n_actions)]
        self.b = [np.zeros(context_dim) for _ in range(n_actions)]
        self.theta = [np.zeros(context_dim) for _ in range(n_actions)]

    def act(self, context):
        scores = []

        for a in range(self.n_actions):
            # Оценка theta_a: A_a^{-1} * b_a
            self.theta[a] = np.linalg.inv(self.A[a]) @ self.b[a]

            # Расчет UCB-оценки
            score = self.theta[a].T @ context + \
                    self.alpha * np.sqrt(context.T @ np.linalg.inv(self.A[a]) @ context)
            scores.append(score)

        return np.argmax(scores)  # Выбор действия с максимальным UCB

    def update(self, action, context, reward):
        # Обновляем A_a и b_a для выбранного действия
        self.A[action] += np.outer(context, context)
        self.b[action] += reward * context

# Пример использования
n_actions = 3  # 3 статьи для рекомендации
context_dim = 2  # Контекст: [возраст, время дня]
linucb = LinUCB(n_actions, context_dim, alpha=1.0)

# Симуляция данных
users_contexts = [
    np.array([25, 0.8]),  # Молодой пользователь, утро
    np.array([40, 0.3]),  # Взрослый пользователь, вечер
]
rewards = [1, 0]  # Клик (1) или нет (0)

# Обучение и рекомендации
for _ in range(100):  # 100 итераций обучения
    for user_ctx, true_reward in zip(users_contexts, rewards):
        action = linucb.act(user_ctx)
        linucb.update(action, user_ctx, true_reward)

# Тестирование
new_user_ctx = np.array([30, 0.5])  # Новый пользователь
best_action = linucb.act(new_user_ctx)
print(f"Рекомендуемая статья: {best_action}")

4. Разбор ключевых компонентов

a) Инициализация

Для каждого действия $ a $ (статьи) храним:

$ A_a = I_d $ (начальная матрица ковариации),
$ b_a = \vec{0} $ (вектор для обновления весов).

b) Выбор действия (act)

Для каждого действия вычисляем:
Оценку $ \theta_a = A_a^{-1} b_a $.
UCB-оценку = линейный прогноз + доверительный интервал.
Выбираем действие с максимумом UCB.

c) Обновление модели (update)

После получения награды (например, клика) обновляем:

$ A_a \leftarrow A_a + x x^T $,
$ b_a \leftarrow b_a + r x $.

5. Параметр `alpha` и его роль

alpha = 0: Только эксплуатация (exploitation), нет исследования.
alpha > 0: Баланс между исследованием и эксплуатацией.
Как выбирать alpha:
Обычно $ \alpha \in [0.5, 2] $.
Можно подбирать на A/B-тестах.

6. Плюсы и минусы LinUCB

Преимущества

Учитывает контекст пользователя.
Гарантированно находит оптимальное действие со временем.
Прост в реализации.

Недостатки

Требует обращения матриц ($ A_a^{-1} $), что дорого при большом количестве действий.
Не учитывает нелинейные зависимости (решение: KernelUCB или нейросетевые подходы).

7. Оптимизации и расширения

a) Линейная алгебра

Используйте Cholesky decomposition для эффективного обращения матриц:
```
L = np.linalg.cholesky(A_a)
inv_A = np.linalg.inv(L.T) @ np.linalg.inv(L)
```

b) Гибридные подходы

LinUCB + DQN: Для комбинации контекстуального bandit и долгосрочного RL.

c) Динамический `alpha`

Адаптируйте alpha на основе дисперсии оценок:
```
alpha = 1.0 / np.sqrt(1 + t)  # t — номер итерации
```

8. Готовые библиотеки

Vowpal Wabbit (vw): Реализует LinUCB и другие bandit-алгоритмы.
Scikit-learn: Можно адаптировать LinearRegression для UCB.