UCB

Материал из MachineLearning.

(Различия между версиями)

Версия 20:45, 17 июля 2026

Содержание

1 UCB

UCB

UCB (англ. Upper Confidence Bound, «верхняя доверительная граница») — семейство алгоритмов для решения задачи многорукого бандита, основанное на принципе оптимизма в условиях неопределённости. На каждом шаге алгоритм выбирает действие с учётом одновременно накопленной оценки ожидаемого вознаграждения и меры неопределённости этой оценки.

В типичном алгоритме UCB каждому действию сопоставляется индекс, состоящий из двух частей:

оценки среднего вознаграждения, полученного при предыдущих выборах действия;
исследовательской добавки, отражающей неопределённость этой оценки.

Алгоритм выбирает действие с максимальным индексом. Благодаря этому действия, ранее приносившие высокое вознаграждение, выбираются для использования накопленных знаний, а недостаточно исследованные действия получают дополнительное преимущество за счёт высокой неопределённости.

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

Задача многорукого бандита

В классической задаче многорукого бандита агенту доступно $K$ действий:

$\mathcal{A} = {1,2,\ldots,K}.$

Действия также называют ручками, руками или рычагами бандита. Каждому действию $i$ соответствует неизвестное распределение вознаграждений с математическим ожиданием

$\mu_i = \mathbb{E}[X_i].$

На шаге $t$ агент выбирает действие $A_t$ и наблюдает случайное вознаграждение $X_t$ . Вознаграждения остальных действий на этом шаге обычно остаются неизвестными.

Такая обратная связь называется частичной: агент наблюдает результат только выбранного действия и не знает, какой результат дали бы остальные варианты.

Оптимальным называется действие

$i^* \in \arg\max_{1 \leq i \leq K} \mu_i.$

Максимальное ожидаемое вознаграждение обозначается через

$\mu^* = \max_i \mu_i.$

Разрыв между оптимальным действием и действием $i$ определяется как

$\Delta_i = \mu^* - \mu_i.$

Для оптимального действия $\Delta_i = 0$ , а для неоптимального действия $\Delta_i > 0$ .

Основная трудность заключается в том, что значения $\mu_i$ заранее неизвестны. Агент должен одновременно:

исследовать разные действия, чтобы уточнять оценки их вознаграждений;
использовать наиболее перспективные действия, чтобы получать высокий результат.

Это противоречие называется балансом между исследованием и использованием.

Псевдосожаление

Качество алгоритма многорукого бандита обычно оценивается с помощью псевдосожаления за горизонт $T$ :

$R_T = T\mu^* - \mathbb{E}\left[\sum_{t=1}^{T}\mu_{A_t}\right].$

Эту величину можно представить в виде

$R_T = \sum_{i=1}^{K}\Delta_i,\mathbb{E}[N_i(T)],$

где $N_i(T)$ — число выборов действия $i$ за первые $T$ шагов.

Псевдосожаление показывает, насколько меньше ожидаемого вознаграждения получил алгоритм по сравнению со стратегией, которая заранее знает оптимальное действие.

Если сожаление растёт линейно,

$R_T = O(T),$

то алгоритм продолжает терять постоянную долю потенциального вознаграждения.

Если же

$R_T = o(T),$

то среднее сожаление на один шаг стремится к нулю:

$\frac{R_T}{T} \to 0.$

Для классических алгоритмов UCB при стандартных предположениях характерен логарифмический порядок сожаления:

$R_T = O(\ln T).$

Это означает, что число неоптимальных решений продолжает расти, но значительно медленнее общего числа шагов.

Принцип оптимизма в условиях неопределённости

Основная идея UCB состоит в том, чтобы при недостатке информации временно предполагать благоприятный вариант.

Для каждого действия строится верхняя оценка его неизвестного среднего вознаграждения:

$U_i(t) = \widehat{\mu}_i(t) + B_i(t),$

где:

$\widehat{\mu}_i(t)$ — эмпирическая оценка среднего вознаграждения;
$B_i(t)$ — исследовательская добавка, отражающая неопределённость;
$U_i(t)$ — оптимистическая оценка качества действия.

На шаге $t$ выбирается действие

$A_t \in \arg\max_i U_i(t).$

Если действие использовалось много раз, его среднее вознаграждение оценено сравнительно точно, поэтому исследовательская добавка становится небольшой. Если действие выбиралось редко, неопределённость остаётся высокой и его индекс увеличивается.

Такой механизм автоматически организует исследование. Отдельная фаза случайного выбора обычно не требуется: недостаточно исследованные действия становятся привлекательными благодаря широкой доверительной границе.

Термин «оптимизм» не означает, что алгоритм считает каждое действие хорошим. Он означает, что при принятии решения используется благоприятная оценка, остающаяся согласованной с имеющимися наблюдениями и уровнем статистической неопределённости.

Алгоритм UCB1

Одним из наиболее известных представителей семейства является алгоритм UCB1, предложенный Питером Ауэром, Николо Чезой-Бьянки и Полом Фишером.^[1]

Пусть к началу шага $t$ действие $i$ было выбрано $N_i(t-1)$ раз. Его эмпирическое среднее определяется как

$\widehat{\mu}*i(t-1) = \frac{1}{N_i(t-1)} \sum*{\substack{s<t \ A_s=i}} X_s.$

Индекс UCB1 имеет вид

$U_i(t) = \widehat{\mu}_i(t-1) + \sqrt{\frac{2\ln t}{N_i(t-1)}}.$

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

$A_t \in \arg\max_{1 \leq i \leq K} \left[\widehat{\mu}_i(t-1) + \sqrt{\frac{2\ln t}{N_i(t-1)}}\right].$

Первое слагаемое отвечает преимущественно за использование накопленных знаний, а второе — за исследование.

Высокое значение $\widehat{\mu}_i$ означает, что действие ранее приносило высокое вознаграждение. Большое значение исследовательской добавки означает, что действие было проверено недостаточное число раз.

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

Формула UCB1 содержит деление на $N_i(t-1)$ , поэтому индекс не определён для действия, которое ещё ни разу не выбиралось.

Стандартная инициализация состоит в том, чтобы в течение первых $K$ шагов выбрать каждое действие по одному разу. После этого для всех действий существуют начальные оценки среднего вознаграждения.

Другой способ состоит в присвоении неисследованным действиям бесконечного индекса:

$U_i(t) = +\infty, \qquad N_i(t-1)=0.$

В результате каждое действие также будет исследовано хотя бы один раз.

Начальная инициализация особенно важна, если первые наблюдения обладают высокой дисперсией. Одно случайно большое или маленькое вознаграждение может заметно повлиять на первые решения алгоритма.

Исследовательская добавка

В алгоритме UCB1 исследовательская добавка равна

$B_i(t) = \sqrt{\frac{2\ln t}{N_i(t-1)}}.$

Она зависит от общего времени $t$ и числа выборов конкретного действия $N_i(t-1)$ .

При увеличении $N_i(t-1)$ добавка уменьшается. Чем больше наблюдений получено для действия, тем точнее оценивается его среднее вознаграждение.

При увеличении общего времени $t$ добавка медленно возрастает за счёт множителя $\ln t$ . Благодаря этому действие, которое долго не выбиралось, со временем может снова стать привлекательным.

Этот механизм позволяет алгоритму периодически проверять, не было ли перспективное действие ошибочно исключено из-за случайно неудачных ранних наблюдений.

Чтобы исследовательская добавка для неоптимального действия оставалась небольшой на поздних этапах, число его выборов должно постепенно увеличиваться. Для классического UCB1 оно растёт примерно логарифмически по времени.

Примечательной особенностью UCB1 является то, что после инициализации его выбор может быть детерминированным относительно накопленной истории, если правило разрешения равных индексов также детерминировано. В отличие от ε-жадной стратегии, UCB не обязан явно выбирать случайное действие на каждом шаге.

Связь с доверительными границами

Исследовательская добавка UCB1 связана с концентрационными неравенствами для эмпирического среднего.

Для независимых ограниченных случайных величин вероятность значительного отклонения эмпирического среднего от истинного среднего уменьшается экспоненциально с числом наблюдений.

В упрощённом виде верхнюю границу для неизвестного среднего можно представить как

$\mu_i \lesssim \widehat{\mu}_i + \sqrt{\frac{c\ln t}{N_i}},$

где $c$ — константа, зависящая от выбранного концентрационного неравенства и требуемого уровня уверенности.

UCB выбирает действие, которое всё ещё могло бы оказаться оптимальным с учётом статистической неопределённости.

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

При этом индекс UCB не всегда следует интерпретировать как обычный доверительный интервал в классическом статистическом смысле. Его форма подбирается прежде всего так, чтобы обеспечить концентрацию вероятности и получить границу сожаления.

Теоретические гарантии UCB1

Для классического алгоритма UCB1 обычно предполагается, что:

число действий конечно;
распределение вознаграждений каждого действия не меняется во времени;
наблюдения для одного действия независимы и одинаково распределены;
вознаграждения ограничены, например принадлежат интервалу $[0,1]$ .

При этих предположениях ожидаемое число выборов неоптимального действия $i$ ограничивается величиной порядка

$\mathbb{E}[N_i(T)] = O\left(\frac{\ln T}{\Delta_i^2}\right).$

Следовательно, вклад этого действия в сожаление имеет порядок

$\Delta_i\mathbb{E}[N_i(T)] = O\left(\frac{\ln T}{\Delta_i}\right).$

Суммарное ожидаемое сожаление UCB1 имеет вид

$R_T = O\left(\sum_{i:\Delta_i>0}\frac{\ln T}{\Delta_i}\right).$

Логарифмический порядок согласуется с фундаментальными нижними границами для достаточно широкого класса стационарных задач многорукого бандита.^[1]

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

Почему неоптимальные действия продолжают исследоваться

После нескольких неудачных наблюдений алгоритм может определить, что некоторое действие, вероятно, хуже текущего лидера. Тем не менее исследовательская добавка этого действия не исчезает навсегда.

Если действие долго не выбирается, значение $N_i(t)$ остаётся постоянным, тогда как $\ln t$ продолжает расти. В некоторый момент индекс действия может снова стать достаточно большим для повторной проверки.

Поэтому классический UCB не прекращает исследование неоптимальных действий окончательно. При неограниченном горизонте они могут выбираться бесконечно много раз, но частота таких выборов уменьшается.

Для неоптимального действия обычно выполняется

$\frac{N_i(T)}{T} \to 0.$

Это означает, что доля неоптимальных выборов стремится к нулю, хотя абсолютное число таких выборов продолжает увеличиваться.

Подобное поведение защищает алгоритм от окончательного отказа от хорошего действия из-за случайно низкого начального результата.

Сравнение с задачей многорукого бандита

Задача многорукого бандита — это математическая модель последовательного принятия решений, а UCB — семейство алгоритмов для решения этой задачи.

Задача многорукого бандита определяет:

множество доступных действий;
неизвестные распределения вознаграждений;
способ получения обратной связи;
критерий качества, например суммарное вознаграждение или сожаление.

UCB задаёт конкретное правило выбора действий. Алгоритм оценивает среднее вознаграждение каждого действия, добавляет меру неопределённости и выбирает действие с максимальной оптимистической оценкой.

Таким образом, задача многорукого бандита является постановкой задачи, а UCB — одним из методов её решения.

Классическая постановка многорукого бандита не содержит состояния среды и переходов между состояниями. Выбранное действие влияет на получаемое вознаграждение и объём доступной информации, но обычно не изменяет структуру будущей среды.

Сравнение с обучением с подкреплением

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

Общая задача обучения с подкреплением часто описывается марковским процессом принятия решений. На шаге $t$ агент наблюдает состояние $S_t$ , выбирает действие $A_t$ , получает вознаграждение $R_{t+1}$ и переходит в состояние $S_{t+1}$ .

Выбранное действие может влиять не только на немедленное вознаграждение, но и на будущие состояния среды. Поэтому агенту необходимо учитывать долгосрочную сумму вознаграждений:

$G_t = \sum_{k=0}^{\infty}\gamma^k R_{t+k+1},$

где $\gamma$ — коэффициент дисконтирования.

В классической задаче многорукого бандита состояния и переходы отсутствуют. Каждое решение влияет прежде всего на немедленное вознаграждение и на информацию, доступную для будущих решений.

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

Различается и используемая информация. Стандартный UCB хранит число выборов и статистику вознаграждений каждого действия. Алгоритмы обучения с подкреплением могут учитывать:

состояние среды;
динамику переходов;
отложенные последствия действий;
структуру траекторий;
долгосрочное накопленное вознаграждение.

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

Несмотря на эти различия, принцип оптимизма применяется и в общем обучении с подкреплением. Некоторые алгоритмы строят оптимистические оценки функций ценности или неизвестной модели среды. В этом смысле UCB является частным и наглядным примером более общего способа исследования.

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

Промежуточное положение между классическим многоруким бандитом и полной задачей обучения с подкреплением занимает контекстный бандит.

На каждом шаге агент наблюдает контекст $\mathbf{x}_t$ , описывающий текущую ситуацию, после чего выбирает действие. Ожидаемое вознаграждение зависит от контекста:

$\mathbb{E}[X_t \mid \mathbf{x}_t, A_t=i].$

Контекст может описывать пользователя, рекламное объявление, документ, медицинского пациента или состояние технической системы.

В отличие от общего обучения с подкреплением, действие в контекстном бандите обычно не влияет на будущий контекст. Агент оптимизирует непосредственное вознаграждение, а не долгосрочную траекторию состояний.

Для контекстных задач существуют обобщения UCB. Например, алгоритм LinUCB предполагает линейную зависимость ожидаемого вознаграждения от признаков контекста.

Сравнение с ε-жадной стратегией

ε-жадная стратегия — простой способ балансировать исследование и использование.

С вероятностью $1-\varepsilon$ выбирается действие с наибольшей текущей оценкой среднего вознаграждения:

$A_t \in \arg\max_i \widehat{\mu}_i(t).$

С вероятностью $\varepsilon$ выбирается случайное действие, часто равномерно среди всех доступных вариантов.

UCB и ε-жадная стратегия решают сходную задачу, но организуют исследование по-разному.

В ε-жадной стратегии исследование обычно не зависит от того, насколько хорошо изучено конкретное действие. Уже тщательно проверенное и явно невыгодное действие может выбираться с той же исследовательской вероятностью, что и малоизученное действие.

UCB направляет исследование к действиям, для которых неопределённость наиболее высока. Действие получает большую исследовательскую добавку, если оно выбиралось редко. Поэтому исследование является не равномерным, а статистически ориентированным.

ε-жадная стратегия явно разделяет два режима:

использование с вероятностью $1-\varepsilon$ ;
случайное исследование с вероятностью $\varepsilon$ .

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

Различается и учёт неопределённости. ε-жадная стратегия использует точечные оценки среднего, но обычно не принимает во внимание число наблюдений при выборе исследуемого действия. UCB явно включает меру неопределённости, убывающую по мере накопления данных.

Если $\varepsilon$ постоянно и положительно, ε-жадная стратегия продолжает выбирать случайные действия с постоянной частотой. В результате неоптимальные действия могут составлять постоянную долю всех решений, что приводит к линейному сожалению:

$R_T = O(T).$

Для получения сублинейного сожаления параметр $\varepsilon_t$ можно уменьшать со временем. Например, при подходящем расписании убывания возможно получить логарифмический порядок сожаления. Однако расписание необходимо выбирать отдельно, а его эффективная форма может зависеть от характеристик задачи.

UCB автоматически уменьшает частоту выбора явно неоптимальных действий по мере накопления информации. При стандартных предположениях UCB1 имеет доказанную логарифмическую границу сожаления без явного задания убывающей вероятности случайного исследования.

При этом ε-жадная стратегия проще в реализации и в некоторых практических задачах может показывать конкурентоспособный результат. Теоретическое преимущество UCB не гарантирует его превосходства на любом конечном горизонте.

Различия по балансу исследования и использования

В UCB исследование и использование объединены в одном индексе:

$\widehat{\mu}_i + B_i.$

Действие может быть выбрано по двум причинам:

его оценка среднего вознаграждения высока;
его оценка остаётся недостаточно точной.

В ε-жадной стратегии причина выбора задаётся случайным переключением между использованием и исследованием. Случайное исследование не обязательно направлено на действие с наибольшей неопределённостью.

В полном обучении с подкреплением баланс исследования и использования сложнее, поскольку действие может открывать новые состояния, изменять будущую информацию и влиять на долгосрочное вознаграждение.

Различия по использованию информации о состоянии

Стандартный UCB не использует информацию о состоянии среды. Для каждого действия хранится одна общая оценка ожидаемого вознаграждения.

В контекстном бандите решение может зависеть от текущего контекста, но обычно не учитываются переходы между состояниями.

В обучении с подкреплением состояние среды является центральной частью задачи. Одно и то же действие может иметь различную ценность в разных состояниях. Кроме того, действие влияет на состояние, которое агент увидит в будущем.

Следовательно, обычный UCB подходит для задач без долгосрочной динамики состояний. Если действие изменяет будущую среду, стандартная бандитная постановка может быть недостаточной.

Различия по теоретическим гарантиям

Для UCB1 существуют конечновременные верхние границы сожаления при стационарных ограниченных вознаграждениях. Они показывают, что ожидаемое число выборов каждого неоптимального действия растёт логарифмически.

Для ε-жадной стратегии гарантии зависят от расписания $\varepsilon_t$ . При постоянном $\varepsilon$ сожаление в общем случае линейно. При правильно убывающем $\varepsilon_t$ могут быть получены более сильные результаты.

Для общей задачи обучения с подкреплением гарантии зависят от модели среды и конкретного алгоритма. Границы UCB1 нельзя непосредственно переносить на задачи с состояниями и переходами.

Наличие теоретической гарантии также не означает, что алгоритм будет лучшим на коротком горизонте. Асимптотический порядок не полностью описывает константы, вычислительные затраты и поведение при нарушении предположений.

Пример работы UCB1

Рассмотрим три действия. После нескольких шагов получены оценки:

$\widehat{\mu}_1 = 0{,}60, \qquad N_1 = 100,$

$\widehat{\mu}_2 = 0{,}55, \qquad N_2 = 10,$

$\widehat{\mu}_3 = 0{,}40, \qquad N_3 = 2.$

Пусть текущий шаг равен $t=112$ . Индексы UCB1 будут равны

$U_1 = 0{,}60 + \sqrt{\frac{2\ln 112}{100}},$

$U_2 = 0{,}55 + \sqrt{\frac{2\ln 112}{10}},$

$U_3 = 0{,}40 + \sqrt{\frac{2\ln 112}{2}}.$

Первое действие имеет наибольшее эмпирическое среднее, но исследовано значительно лучше остальных, поэтому его исследовательская добавка мала.

Третье действие имеет низкое наблюдаемое среднее, но было выбрано только два раза. Из-за этого оно получает большую исследовательскую добавку.

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

После дополнительных выборов неопределённость уменьшится. Если среднее вознаграждение останется низким, индекс снизится и действие будет выбираться реже.

Практическая реализация

Для каждого действия обычно хранятся:

число выборов $N_i$ ;
сумма полученных вознаграждений $S_i$ ;
эмпирическое среднее $\widehat{\mu}_i$ .

Среднее вычисляется как

$\widehat{\mu}_i = \frac{S_i}{N_i}.$

После выбора действия $i$ и получения вознаграждения $x_t$ статистики обновляются:

$N_i \leftarrow N_i + 1,$

$S_i \leftarrow S_i + x_t.$

Среднее можно обновлять без хранения всей истории наблюдений:

$\widehat{\mu}_i \leftarrow \widehat{\mu}_i + \frac{x_t-\widehat{\mu}_i}{N_i}.$

Такое обновление требует постоянного объёма памяти для каждого действия.

Вычислительная сложность прямого вычисления всех индексов составляет $O(K)$ на один шаг.

Для очень большого числа действий могут потребоваться приближённый поиск максимального индекса, дополнительные структуры данных или модели, использующие общие признаки действий.

Масштаб вознаграждений

Классическая гарантия UCB1 обычно формулируется для вознаграждений из интервала $[0,1]$ .

Если вознаграждения принадлежат известному интервалу $[a,b]$ , их можно нормировать:

$X'_t = \frac{X_t-a}{b-a}.$

Если использовать стандартную формулу UCB1 без учёта масштаба вознаграждений, баланс между эмпирическим средним и исследовательской добавкой может нарушиться.

Например, при вознаграждениях порядка тысяч исследовательская добавка порядка единицы окажется слишком слабой. При вознаграждениях порядка $10^{-3}$ та же добавка может полностью доминировать над различиями между средними.

Поэтому практическая реализация должна учитывать диапазон, дисперсию и форму распределения вознаграждений.

Коэффициент исследования

На практике часто используется параметризованная формула

$U_i(t) = \widehat{\mu}_i(t-1) + c\sqrt{\frac{\ln t}{N_i(t-1)}},$

где $c>0$ регулирует интенсивность исследования.

При большом $c$ алгоритм чаще выбирает малоизученные действия. Это может быть полезно при длинном горизонте, но увеличивает краткосрочные потери.

При малом $c$ алгоритм быстрее концентрируется на текущем лидере, но возрастает риск преждевременно выбрать действие, получившее случайно высокие начальные вознаграждения.

Классический коэффициент UCB1 вытекает из конкретного теоретического анализа. Изменение коэффициента может улучшить практические результаты, но исходная теоретическая граница не обязательно сохраняется без дополнительного доказательства.

Варианты UCB

UCB-V

Алгоритм UCB1 использует исследовательскую добавку, зависящую главным образом от числа наблюдений. Однако два действия с одинаковым числом выборов могут иметь различную дисперсию вознаграждений.

Алгоритмы семейства UCB-V дополнительно учитывают эмпирическую дисперсию.^[1]

Действия со стабильными вознаграждениями могут получать более узкие доверительные границы, а действия с высокой вариативностью — более широкие.

KL-UCB

В алгоритме KL-UCB верхняя граница строится с использованием дивергенции Кульбака — Лейблера.^[1]

Для бернуллиевских вознаграждений индекс определяется как наибольшее значение $q$ , удовлетворяющее условию

$N_i(t),d\left(\widehat{\mu}_i(t),q\right) \leq \ln t + c\ln\ln t,$

где $d$ — дивергенция между распределениями Бернулли.

KL-UCB учитывает форму распределения точнее, чем квадратичная граница UCB1, и может обеспечивать лучшие теоретические константы.

LinUCB

LinUCB применяется в контекстных бандитах. Предполагается, что ожидаемое вознаграждение линейно зависит от вектора признаков:

$\mathbb{E}[X_t \mid \mathbf{x}*{t,i}] = \mathbf{x}*{t,i}^{\mathsf T}{\theta}.$

Индекс объединяет линейное предсказание и неопределённость параметров:

$U_{t,i} = \mathbf{x}*{t,i}^{\mathsf T}\widehat{{\theta}} + \alpha\sqrt{\mathbf{x}*{t,i}^{\mathsf T}A^{-1}\mathbf{x}_{t,i}}.$

Такой подход позволяет переносить информацию между действиями с похожими признаками.

LinUCB применялся, в частности, в исследованиях рекомендательных систем и персонализации новостного контента.^[1]

Sliding-Window UCB

В нестационарной среде старые наблюдения могут перестать соответствовать текущим распределениям.

Sliding-Window UCB использует только наблюдения из последнего временного окна. Это позволяет быстрее реагировать на изменения, но уменьшает эффективный объём данных.

Discounted UCB

В Discounted UCB старые наблюдения получают экспоненциально убывающие веса. Недавние вознаграждения влияют на оценку сильнее, чем давние.

Коэффициент забывания определяет компромисс между устойчивостью оценки и скоростью адаптации к изменениям среды.

Нестационарные среды

Стандартный UCB предполагает, что среднее вознаграждение каждого действия постоянно:

$\mu_i(t) = \mu_i.$

Во многих практических задачах это предположение нарушается. Предпочтения пользователей, спрос, эффективность рекламы и состояние оборудования могут изменяться.

Обычный UCB накапливает всю историю наблюдений, поэтому старые данные продолжают влиять на оценки. Если оптимальное действие изменилось, алгоритм может адаптироваться медленно.

Для нестационарных задач применяются:

скользящие временные окна;
дисконтирование старых наблюдений;
детекторы изменений;
периодические перезапуски;
динамические модели параметров;
алгоритмы для состязательных бандитов.

Выбор метода зависит от предполагаемой частоты и характера изменений.

Состязательные бандиты

В стохастическом многоруком бандите вознаграждения генерируются из фиксированных распределений.

В состязательной постановке последовательность вознаграждений может формироваться произвольным или адаптивным образом.

Классический UCB1 не предназначен для такой среды, поскольку его анализ использует предположение о стационарных средних и концентрации независимых наблюдений.

Для состязательных бандитов применяются другие алгоритмы, например Exp3, основанные на экспоненциальном взвешивании и явной рандомизации.

Само наличие нескольких действий и частичной обратной связи ещё не означает, что применение UCB теоретически обосновано.

Задержанные вознаграждения

В некоторых системах результат действия становится известен не сразу. Например, пользователь может совершить покупку через несколько дней после показа рекомендации.

Если задержки не учитывать, недавно выбранные действия будут выглядеть недостаточно исследованными, поскольку соответствующие вознаграждения ещё не получены. Это может привести к их чрезмерно частому выбору.

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

Пакетный выбор действий

Иногда несколько действий необходимо выбрать одновременно до получения обратной связи.

Например, система может одновременно назначить варианты нескольким пользователям. Обычный последовательный UCB после каждого действия обновляет статистику, но в пакетной постановке результаты внутри пакета неизвестны.

Из-за этого алгоритм может многократно выбрать одно и то же действие на основании устаревшей оценки неопределённости.

Для пакетных задач применяются виртуальные обновления, штрафы за ожидающие наблюдения и специальные пакетные варианты UCB.

Большое число действий

Если число действий велико, начальный выбор каждого действия может быть слишком дорогим.

При миллионах товаров, документов или рекламных объявлений стандартный UCB с отдельной независимой оценкой каждого действия не использует сходство между объектами.

Контекстные и линейные варианты представляют действия через признаки. Наблюдение для одного действия обновляет общую модель и может уменьшать неопределённость для других похожих действий.

При динамически изменяющемся наборе действий использование признаков особенно важно, поскольку новые действия не имеют собственной истории наблюдений.

Практические области применения

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

К таким задачам относятся:

выбор рекламного объявления;
рекомендательные системы;
адаптивное тестирование интерфейсов;
распределение вычислительных ресурсов;
маршрутизация запросов;
выбор параметров алгоритма;
клинические и адаптивные эксперименты;
байесовская оптимизация;
автоматическая настройка гиперпараметров;
выбор стратегий управления.

Применимость UCB зависит не только от возможности измерить вознаграждение, но и от допустимости исследовательских действий.

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

Практические преимущества

К преимуществам UCB относятся:

явный учёт статистической неопределённости;
автоматическое уменьшение частоты исследования;
отсутствие необходимости задавать постоянную вероятность случайного действия;
простая реализация UCB1;
небольшие требования к памяти;
доказанные границы сожаления при стандартных предположениях;
возможность расширения на контекстные и структурированные задачи.

Особенно полезен UCB в задачах с достаточно длинным горизонтом, где исследовательские потери могут окупиться за счёт более точных решений в будущем.

Ограничения

К ограничениям UCB относятся:

зависимость от предположения о стационарности;
чувствительность к масштабу вознаграждений;
необходимость начального исследования всех действий;
возможная избыточная осторожность на коротком горизонте;
слабое использование структуры при независимом моделировании действий;
ограниченная применимость при тяжёлых хвостах распределения;
отсутствие непосредственного учёта состояний и переходов;
необходимость модификаций при задержанной или пакетной обратной связи;
отсутствие автоматических гарантий безопасности исследовательских действий.

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

Типичные ошибки применения

Одной из распространённых ошибок является применение стандартной формулы UCB1 без нормирования вознаграждений. Исследовательская добавка при этом может иметь несопоставимый масштаб с эмпирическим средним.

Другой ошибкой является использование UCB в нестационарной среде без механизма забывания. Алгоритм будет усреднять наблюдения из старого и нового режимов.

Также неправильно считать индекс UCB точной вероятностной гарантией независимо от распределения данных. Доверительная добавка выводится при определённых предположениях, которые необходимо учитывать.

При офлайн-оценке нельзя непосредственно узнать результат действия, которое историческая система не выбрала. Для корректного сравнения бандитных алгоритмов применяются специальные методы, например обратное взвешивание по вероятности выбора, случайно собранные данные или симуляторы среды.

Наконец, UCB оптимизирует заданное числовое вознаграждение, но не определяет, насколько выбранная метрика соответствует реальным интересам пользователя или системы.

UCB и краткосрочная эффективность

Логарифмическая граница сожаления является асимптотическим результатом.

На небольшом числе шагов исследовательская добавка может быть слишком сильной, особенно при большом числе действий.

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

С другой стороны, слишком жадная стратегия может дать высокий краткосрочный результат только при удачных начальных наблюдениях. При неудачной инициализации она способна надолго закрепиться на неоптимальном действии.

Поэтому выбор алгоритма должен учитывать:

длину горизонта;
число действий;
разрывы между средними вознаграждениями;
дисперсию наград;
стоимость ошибочного решения;
допустимый уровень исследования.

Интересные свойства

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

Другой важный факт заключается в логарифмической частоте исследования неоптимальных действий. UCB не прекращает проверять их полностью, но делает это всё реже.

Такая стратегия одновременно защищает от ошибочных ранних выводов и обеспечивает стремление доли неоптимальных решений к нулю.

Принцип UCB применяется далеко за пределами простой задачи многорукого бандита. Верхние доверительные оценки используются в контекстных рекомендациях, байесовской оптимизации, планировании и некоторых алгоритмах обучения с подкреплением.

Алгоритм Monte Carlo Tree Search использует близкое правило UCT — Upper Confidence bounds applied to Trees. Оно применяет идею UCB для выбора ветвей дерева, сочетая среднее качество найденных продолжений и неопределённость, вызванную малым числом посещений.

Заключение

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

В UCB исследование направляется к действиям, оценки которых остаются неопределёнными. Это отличает метод от ε-жадной стратегии, где исследовательское действие обычно выбирается случайно без точного учёта степени изученности каждого варианта.

Задача многорукого бандита является математической постановкой, тогда как UCB представляет конкретное семейство способов её решения.

По сравнению с общим обучением с подкреплением классический UCB не использует состояния, переходы и долгосрочные последствия действий.

При стационарных ограниченных вознаграждениях UCB1 обладает логарифмической верхней границей сожаления. Однако эти гарантии зависят от предположений модели.

Нестационарность, задержки, тяжёлые хвосты, большое число действий и наличие состояния требуют специальных модификаций.

Практическая ценность UCB заключается в сочетании простой реализации, явного учёта неопределённости и строгого теоретического анализа. Вместе с тем конкретный вариант алгоритма следует выбирать с учётом статистических свойств вознаграждений, структуры среды и стоимости исследовательских действий.

См. также

Литература

Lattimore T., Szepesvári C. Bandit Algorithms. Cambridge: Cambridge University Press, 2020.
Sutton R. S., Barto A. G. Reinforcement Learning: An Introduction. 2nd ed. Cambridge, Massachusetts: MIT Press, 2018.
Bubeck S., Cesa-Bianchi N. Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems // Foundations and Trends in Machine Learning. 2012. Vol. 5, No. 1. P. 1–122.
Slivkins A. Introduction to Multi-Armed Bandits // Foundations and Trends in Machine Learning. 2019. Vol. 12, No. 1–2. P. 1–286.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=UCB»

@@ Строка 453: / Строка 453: @@
 '''LinUCB''' применяется в контекстных бандитах. Предполагается, что ожидаемое вознаграждение линейно зависит от вектора признаков:
-: <tex>\mathbb{E}[X_t \mid \mathbf{x}*{t,i}] = \mathbf{x}*{t,i}^{\mathsf T}\boldsymbol{\theta}.</tex>
+: <tex>\mathbb{E}[X_t \mid \mathbf{x}*{t,i}] = \mathbf{x}*{t,i}^{\mathsf T}{\theta}.</tex>
 Индекс объединяет линейное предсказание и неопределённость параметров:
-: <tex>U_{t,i} = \mathbf{x}*{t,i}^{\mathsf T}\widehat{\boldsymbol{\theta}} + \alpha\sqrt{\mathbf{x}*{t,i}^{\mathsf T}A^{-1}\mathbf{x}_{t,i}}.</tex>
+: <tex>U_{t,i} = \mathbf{x}*{t,i}^{\mathsf T}\widehat{{\theta}} + \alpha\sqrt{\mathbf{x}*{t,i}^{\mathsf T}A^{-1}\mathbf{x}_{t,i}}.</tex>
 Такой подход позволяет переносить информацию между действиями с похожими признаками.

UCB