UCB

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

Версия от 20:31, 17 июля 2026; Alfit Gaifullin (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 UCB

UCB

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

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

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

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

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

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

В классической задаче многорукого бандита агенту доступно <math>K</math> действий, называемых также ручками, рычагами или руками:

<math> \mathcal{A}=\{1,2,\ldots,K\}. </math>

Каждому действию <math>i</math> соответствует неизвестное распределение вознаграждений с математическим ожиданием

<math> \mu_i=\mathbb{E}[X_i]. </math>

На шаге <math>t</math> агент выбирает действие <math>A_t</math> и наблюдает случайное вознаграждение

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

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

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

то разрыв между оптимальным действием и действием <math>i</math> равен

<math> \Delta_i=\mu^*-\mu_i. </math>

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

Основная трудность состоит в том, что значения <math>\mu_i</math> заранее неизвестны. Агент должен одновременно:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<math> U_i(t) = \widehat{\mu}_i(t) + B_i(t), </math>

где

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

На шаге <math>t</math> выбирается действие

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

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

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

Алгоритм UCB1

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

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

<math> \widehat{\mu}_i(t-1) = \frac{1}{N_i(t-1)} \sum_{\substack{s<t\\A_s=i}}X_s. </math>

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

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

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

<math> 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]. </math>

Первое слагаемое отвечает за использование, а второе — за исследование.

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

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

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

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

<math> U_i(t)=+\infty, \qquad N_i(t-1)=0. </math>

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

Интерпретация исследовательской добавки

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

Она зависит от двух величин.

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

При увеличении общего времени <math>t</math> добавка медленно возрастает за счёт <math>\ln t</math>. Благодаря этому действие, которое долго не выбиралось, со временем снова может стать привлекательным. Алгоритм периодически проверяет, не было ли перспективное действие исключено из рассмотрения из-за случайно неудачных ранних наблюдений.

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

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

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

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

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

<math> \mu_i \lesssim \widehat{\mu}_i + \sqrt{ \frac{c\ln t}{N_i} }, </math>

где <math>c</math> — константа, зависящая от выбранного неравенства и уровня уверенности.

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

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

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

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

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

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

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

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

<math> \Delta_i\mathbb{E}[N_i(T)] = O \left( \frac{\ln T}{\Delta_i} \right). </math>

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

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

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

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

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

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

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

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

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

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

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

Задача задаёт:

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

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

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

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

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

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

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

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

<math> G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}, </math>

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

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

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

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

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

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

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

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

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

<math> \mathbb{E}[X_t\mid\mathbf{x}_t,A_t=i]. </math>

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

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

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

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

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

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

<math> A_t \in \arg\max_i\widehat{\mu}_i(t). </math>

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

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

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

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

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

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

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

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

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

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

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

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

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

В UCB исследование и использование не рассматриваются как полностью отдельные действия. Индекс

<math> \widehat{\mu}_i+B_i </math>

объединяет накопленное вознаграждение и неопределённость.

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

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

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

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

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

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

Для ε-жадной стратегии гарантии зависят от расписания <math>\varepsilon_t</math>. При постоянном <math>\varepsilon</math> сожаление в общем случае линейно. При правильно убывающем <math>\varepsilon_t</math> могут быть получены более сильные результаты, но стратегия может требовать знания или оценки характеристик задачи.

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

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

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

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

<math> \widehat{\mu}_1=0{,}60, \qquad N_1=100, </math>

<math> \widehat{\mu}_2=0{,}55, \qquad N_2=10, </math>

<math> \widehat{\mu}_3=0{,}40, \qquad N_3=2. </math>

Пусть текущий шаг равен <math>t=112</math>. Индексы UCB1 имеют вид

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

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

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

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

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

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

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

<math> N_i\leftarrow N_i+1, </math>

<math> S_i\leftarrow S_i+x_t, </math>

<math> \widehat{\mu}_i\leftarrow\frac{S_i}{N_i}. </math>

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

<math> \widehat{\mu}_i \leftarrow \widehat{\mu}_i + \frac{x_t-\widehat{\mu}_i}{N_i}. </math>

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

Вычислительная сложность прямого выбора максимального индекса составляет <math>O(K)</math> на один шаг. Для очень большого числа действий могут потребоваться дополнительные структуры данных, приближённый поиск или модели, использующие общие признаки действий.

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

Классическая гарантия UCB1 обычно формулируется для вознаграждений из интервала <math>[0,1]</math>. Если значения принадлежат известному интервалу <math>[a,b]</math>, их можно нормировать:

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

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

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

Выбор коэффициента исследования

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

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

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

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

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

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

Варианты UCB

UCB-V

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

Алгоритмы типа UCB-V дополнительно используют эмпирическую дисперсию. Действия со стабильными вознаграждениями могут получать более узкие границы, а действия с высокой вариативностью — более широкие.^[1]

Это позволяет эффективнее распределять исследование, если дисперсии действий существенно различаются.

KL-UCB

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

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

<math> N_i(t)\, d \left( \widehat{\mu}_i(t),q \right) \leq \ln t+c\ln\ln t, </math>

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

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

LinUCB

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

<math> \mathbb{E}[X_t\mid\mathbf{x}_{t,i}] = \mathbf{x}_{t,i}^{\mathsf T}\boldsymbol{\theta}. </math>

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

<math> 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} }. </math>

Такой подход позволяет переносить информацию между действиями с похожими признаками. Он использовался, в частности, в исследованиях рекомендательных систем и персонализации новостного контента.^[1]

Sliding-Window UCB

В нестационарной среде старые наблюдения могут перестать соответствовать текущим распределениям. Sliding-Window UCB использует только последние <math>w</math> наблюдений или последние <math>w</math> временных шагов.

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

Discounted UCB

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

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

Байесовские и модельные варианты

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

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

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

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

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

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

Другая ошибка состоит в применении 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»

UCB