Принцип работы UCB: как найти золотую середину

Мы уже познакомились с Thompson Sampling, который выбирает "руку" вероятностным подходом. Теперь давайте разберем Upper Confidence Bound (UCB) — алгоритм, который действует детерминированно, но тоже ищет баланс между исследованием и эксплуатацией.

Как работает UCB: интуиция и формула

UCB не использует случайность. Он вычисляет для каждой "руки" индекс уверенности (confidence bound) и выбирает ту, у которой этот индекс максимален. Индекс состоит из двух частей:

1. Средняя награда (exploitation term): Текущая средняя награда от "руки". Чем она выше, тем привлекательнее "рука" для эксплуатации.
2. Доверительный интервал (exploration term): Компонент, который стимулирует исследование. Он увеличивается для "рук", которые выбирались реже или по которым мало данных.

Формула UCB для $i$-й "руки":

$$UCB_i = \bar{X}_i + \sqrt{\frac{2 \ln N}{n_i}}$$

Где:

• $UCB_i$ — индекс уверенности для $i$-й "руки".
• $\bar{X}_i$ — средняя награда от $i$-й "руки" (например, конверсия).
• $N$ — общее количество всех выборов в эксперименте.
• $n_i$ — количество раз, когда выбрана $i$-я "рука".

Важно: Логарифм $\ln N$ растет медленнее, чем $N$. Это значит, что компонент исследования постепенно уменьшается по мере накопления данных.

Разберем компоненты формулы

Посмотрим, как каждый компонент влияет на выбор "руки":

• $\bar{X}_i$ (Средняя награда): Это "эксплуатационная" часть. Чем выше средняя награда, тем чаще будет выбираться "рука", так как она уже показала хорошие результаты.
• $\sqrt{\frac{2 \ln N}{n_i}}$ (Компонент исследования): Это "исследовательская" часть.
  • $N$ (Общее количество попыток): С ростом общего числа попыток, этот компонент увеличивается. Это позволяет алгоритму продолжать исследовать, даже если разница в средних наградах становится небольшой.
  • $n_i$ (Количество выборов $i$-й "руки"): Если "рука" выбрана мало раз ($n_i$ мало), знаменатель будет маленьким, а весь компонент исследования — большим. Это дает "неисследованным" "рукам" высокий UCB-индекс, стимулируя их выбор. По мере того, как "рука" выбирается чаще, $n_i$ растет, и компонент исследования уменьшается, уступая место компоненту эксплуатации.

UCB постоянно балансирует: выбирает "руки", которые уже показали себя хорошо, и исследует те, о которых мало информации. Это позволяет ему эффективно находить оптимальный вариант, минимизируя потери.

Пример работы UCB на практике

Представьте, что вы тестируете три варианта заголовка для рекламного объявления: "Заголовок А", "Заголовок Б" и "Заголовок В".

1. Начало: Все заголовки имеют одинаковую среднюю награду (0), но $n_i$ для них очень малы. UCB будет выбирать их по очереди, чтобы собрать начальные данные.
2. Накопление данных: Допустим, "Заголовок А" показал высокую конверсию, "Заголовок Б" — среднюю, а "Заголовок В" — низкую.
3. Выбор UCB:
   • У "Заголовка А" будет высокая $\bar{X}_i$, и он будет часто выбираться.
   • У "Заголовка В" будет низкая $\bar{X}_i$, и его будут выбирать реже.
   • Но если "Заголовок Б" был выбран значительно реже, чем "Заголовок А", его компонент исследования может быть достаточно большим, чтобы UCB выбрал его, даже если его текущая средняя награда ниже, чем у "Заголовка А". Это позволяет UCB убедиться, что "Заголовок Б" действительно хуже, а не просто "не повезло" в первых попытках.

UCB — отличный выбор, когда вам нужен детерминированный алгоритм, который активно исследует, но при этом быстро переключается на лучшие варианты по мере накопления данных.

Теперь, когда вы понимаете принцип работы UCB, включая его формулу и логику баланса между исследованием и эксплуатацией, мы готовы сравнить его с Thompson Sampling, чтобы понять, какой алгоритм лучше подходит для ваших задач.