Нижняя граница Лай-Роббинса ⇐ Васина Википедия

[wiki_en]

Нижняя граница Лая-Роббинса дает асимптотическую нижнюю границу сожалений, которые должен испытывать любой равномерно хороший алгоритм в стохастической задаче «Многорукий бандит|многорукий бандит». Оригинальный результат был доказан Цзе Люн Лаем|Це Люнг Лаем и Гербертом Роббинсом|Гербертом Роббинсом в 1985 году для параметрического экспоненциального семейства|экспоненциальных семейств. Более поздняя работа распространила это утверждение на более общие классы дистрибутивов.

== Проблема с многоруким бандитом ==

Задача «Многорукий бандит|Задача многорукого бандита» (MAB) – это последовательная игра|последовательная игра, в которой игрок должен совмещать исследование (чтобы учиться) и эксплуатацию (чтобы заработать).

Игрок выбирает среди K действий (оружий) с неизвестными распределениями \nu = (\nu_1,\dots,\nu_K). Предполагается, что игрок знает класс распределений \mathcal{D}, такой, что для каждого k имеется \nu_k\in\mathcal{D} (например, \mathcal{D} может быть семейством нормального распределения|распределения Гаусса или распределения Бернулли|распределения Бернулли).

В каждом раунде t=1,\dots,T игрок выбирает (тянет) руку a_t и получает награду X_t\sim\nu_{a_t.

Обозначаем
* N_a(t):=\sum_{s=1}^t\mathbf{1}_{\{a_s=a\ количество раз, когда рука a была вытянута в первых t раундах,
* \mu(\nu):=(\mu_1,\dots,\mu_K) означает вектор плеча, где \mu_k=\mathbb{E}_{X\sim\nu_k}[X],
* \mu^*:=\max_a \mu_a высшее среднее значение
* \Delta_a:=\mu^*-\mu_a\ge 0 зазор между плечами a.

Рукав a с \mu_a=\mu^* называется «оптимальным плечом»; в противном случае это «субоптимальная группа».

Цель состоит в том, чтобы «минимизировать сожаление» на горизонте T, определяемом
:R_T:= \sum_{a=1}^K \Delta_a\,\mathbb{E}[N_a(T)].

Интуитивно, сожаление — это (ожидаемый) полный проигрыш по сравнению с всегда разыгрываемой оптимальной рукой:
:\text{regret}=\sum_{a}\ (\text{стоимость игры }a)\times(\text{количество игр }a\text{ воспроизводится}).

Алгоритм MAB — это (возможно, рандомизированная) политика, которая в каждом раунде t выбирает руку a_t, используя наблюдения, полученные на предыдущих ходах.

=== Интуитивный пример ===
Предположим, фермер должен каждый год выбирать один из K сортов семян для посева. Каждый сорт k имеет неизвестную среднюю урожайность \mu_k. Если бы фермер знал лучший сорт (со средним значением \mu^*), он бы сажал его каждый год; на самом деле он должен попробовать разные сорта, чтобы узнать, какой из них лучше. Совокупное сожаление по истечении T лет измеряет общую ожидаемую потерю урожая из-за несовершенства знаний.

'''Примечания'''
# Модель выше представляет собой «стохастическую» MAB; существуют также состязательные варианты.
# Можно рассмотреть настройку «фиксированного горизонта» (известный T) или настройку «в любое время» (неизвестный T).

== Нижняя граница Лай-Роббинса ==

Теорема дает правильное количество времени, в течение которого нам следует провести неоптимальную руку k, чтобы отличить, находимся ли мы в экземпляре с \nu_k или с \tilde{\nu}_k, где \tilde{\nu}_k таков, что \tilde{\mu}_k > \mu^*.

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

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

=== Согласованность (равномерно хорошие алгоритмы) ===

Пусть \mathcal{D} — класс вероятностных распределений и рассмотрим K рук с распределениями вознаграждений
\nu = (\nu_1,\dots,\nu_K) \in \mathcal{D}^K.
Алгоритм называется «непротиворечивым» (также называемым «равномерно хорошим») на \mathcal{D}^K, если для каждого экземпляра \nu \in \mathcal{D}^K ожидаемое сожаление R_T(\nu) растет субполиномиально:
:\forall \alpha > 0, \qquad
R_T(\nu) = o(T^\alpha)
\quad \text{as } T \to \infty

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

=== Формальная нижняя граница ===

Для любого неоптимального плеча a.
Для распределения \nu_a \in \mathcal{D} и порога x определите
:\mathcal{K}_{\inf}(\nu_a, x, \mathcal{D})
:= \inf \Bigl\{
\operatorname{KL}(\nu_a, \nu') :
\nu' \in \mathcal{D},
\ \mu' > x
\Bigr\
где \operatorname{KL}(\cdot,\cdot) обозначает расхождение Кульбака–Лейблера|Расхождение Кульбака–Лейблера.

Тогда для любого алгоритма, согласованного на \mathcal{D}^K и для каждого экземпляра
\nu \in \mathcal{D}^K, каждое неоптимальное плечо a удовлетворяет
:\mathbb{E}_\nu[N_a(T)]
\ge
\frac{\ln T}{\mathcal{K}_{\inf}(\nu_a, \mu^*, \mathcal{D})}
+ o(\ln T)

Следовательно, сожаление удовлетворяет
:R_T(\nu)
\ge
\влево(
\sum_{a:\,\mu_a < \mu^*}
\frac{\Delta_a}{\mathcal{K}_{\inf}(\nu_a, \mu^*, \mathcal{D})}
\справа)
\ln Т
+ o(\ln T)

В оригинальной статье 1985 года этот результат был установлен для экспоненциальных семейств; более поздняя работа показала, что оценка справедлива при гораздо более слабых предположениях относительно \mathcal{D}.

=== Интуиция ===

Согласованность предполагает, что для каждого \nu количество подходов оптимального рычага должно быть большим. Это означает, что \mu^* оценивается очень точно. Цель состоит в том, чтобы определить для неоптимальной группы k, сколько выборок необходимо, чтобы с соответствующим уровнем уверенности быть уверенным, что \mu_k < \mu^*. Для этого мы используем так называемый «самый запутанный экземпляр»: экземпляр, близкий к \nu, такой, что рука k является оптимальной. Мы определяем его как \tilde{\nu} так, что для всех a \neq k, \tilde{\nu}_a = \nu_a и \tilde{\nu}_k выбирается так, что \tilde{\mu}_k > \mu^*. Цель состоит в том, чтобы определить, сколько выборок руки k требуется, чтобы отличить, находимся ли мы в экземпляре с \nu_k или с \tilde{\nu}_k с точки зрения расстояния \operatorname{KL.

== Алгоритмы достижения нижней границы Лая-Роббинса ==

Известно несколько алгоритмов достижения асимптотической нижней границы Лая-Роббинса
при определенных предположениях относительно класса распределения вознаграждения \mathcal{D}.
Следующий список суммирует неисчерпывающий список алгоритмов, соответствующих нижней границе.

== Расширение на другие проблемы ==

=== Структурированный бандит ===

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

=== Лучшая идентификация руки (BAI) ===

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

=== Обучение с подкреплением (RL) ===

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

== См. также ==

* Многорукий бандит|Многорукий бандит
* Верхняя доверительная граница|Верхняя доверительная граница
* Доверительный интервал|Доверительный интервал



|last=Майяр
|first=Одалрик-Амбрим
|title=Математика статистического последовательного принятия решений
|год=2019
|type=Кандидатская диссертация
|institution=Университет Лилля, наук и технологий


|last=Кауфман
|first=Эмили
|title=Вклад в оптимальное решение нескольких бандитских проблем
|год=2020
|type=Кандидатская диссертация
|institution=Университет Лилля


|last1=Могилы
|first1=Тодд Л.
|last2=Лай
|first2=Цзе Люн
|title=Асимптотически эффективный адаптивный выбор законов управления в неуправляемых цепях Маркова
|journal=SIAM Journal по контролю и оптимизации
|год=1997
|объем=35
|номер=3
|страницы=715–743
|издатель=СИАМ


|last1=Гаривье
|first1=Орельен
|last2=Кауфман
|first2=Эмили
|title=Оптимальная идентификация лучшей руки с фиксированной достоверностью
|год=2016
|класс=math.ST
|eprint=1602.04589


|last1=Бун
|first1=Виктор
|last2=Майяр
|first2=Одалрик-Амбрим
|title=Нижняя граница сожаления при передаче марковских процессов принятия решений
|год=2025
|класс=cs.LG
|eprint=2501.13013


|last1=Латтимор
|first1=Тор
|title=Уточнение уровня уверенности для оптимистичных бандитских стратегий
|journal=Журнал исследований машинного обучения
|год=2018
|объем=19
|число=20
|страницы=1–32
|url=http://jmlr.org/papers/v19/17-513.html


|last1=Агравал
|first1=Шипра
|last2=Гоял
|first2=Навин
|title=Анализ выборки Томпсона для задачи о многоруком бандите
|journal=Материалы 25-й ежегодной конференции по теории обучения
|editor1=Маннор, Ши
|editor2=Сребро, Натан
|editor3=Уильямсон, Роберт С.
|год=2012
|объем=23
|series=Материалы исследований машинного обучения
|pages=39.1–39.26 |publisher=PMLR
|url=https://proceedings.mlr.press/v23/agrawal12.html


|last1=Коуэн
|first1=Уэсли
|last2=Хонда
|first2=Джунья
|last3=Катехакис
|first3=Майкл Н.
|title=Обычные бандиты неизвестных средств и различий
|journal=Журнал исследований машинного обучения
|год=2018
|объем=18
|номер=154
|страницы=1–28
|url=http://jmlr.org/papers/v18/15-154.html


|last1=Бодри
|first1=Дориан
|last2=Кауфман
|first2=Эмили
|last3=Майяр
|first3=Одалрик-Амбрим
|title=Подвыборка для эффективного непараметрического исследования бандитов
|год=2020
|класс=stat.ML
|eprint=2010.14323




|last1=Каппе
|first1=Оливье
|last2=Гаривье
|first2=Орельен
|last3=Майяр
|first3=Одалрик-Амбрим
|last4=Мунос
|first4=Реми
|last5=Штольц
|first5=Жиль
|title=Верхние доверительные границы Кульбака-Лейблера для оптимального последовательного распределения
|journal=Анналы статистики
|год=2013
|страницы=1516–1541


|last1=Гаривье
|first1=Орельен
|last2=Хадиджи
|first2=Хеди
|last3=Менар
|first3=Пьер
|last4=Штольц
|first4=Жиль
|title=KL-UCB-переключатель: Оптимальные границы сожаления для стохастических бандитов как с точки зрения зависимости от распределения, так и с точки зрения отсутствия распределения
|journal=Журнал исследований машинного обучения
|объем=23
|номер=179
|год=2022
|страницы=1–66


|last1=Лай
|first1=TL
|last2=Роббинс
|first2=Герберт
|title=Асимптотически эффективные правила адаптивного распределения
|journal=Достижения прикладной математики
|объем=6
|номер=1
|страницы=4–22
|год=1985
|doi=10.1016/0196-8858(85)90002-8
|url=https://dx.doi.org/10.1016/0196-8858%2885%2990002-8


|last1=Риу
|first1=Чарльз
|last2=Хонда
|first2=Джунья
|title=Бандитские алгоритмы на основе выборки Томпсона для ограниченного распределения вознаграждения
|book-title=Материалы 31-й Международной конференции по теории алгоритмического обучения
|editor1-last=Конторович
|editor1-first=Арье
|editor2-last=Новый
|editor2-first=Гергели
|series=Материалы исследований машинного обучения
|объем=117
|страницы=777–826
|местоположение=
|publisher=PMLR
|год=2020
|url=https://proceedings.mlr.press/v117/riou20a.html


|last1=Хонда
|first1=Джунья
|last2=Такемура
|first2=Акимичи
|title=Неасимптотический анализ нового бандитского алгоритма для полуограниченных вознаграждений
|journal=Журнал исследований машинного обучения
|объем=16
|номер=113
|pages=3721–3756
|год=2015
|url=http://jmlr.org/papers/v16/honda15a.html


|last1=Хонда
|first1=Джунья
|last2=Такемура
|first2=Акимичи
|title=Асимптотически оптимальный бандитский алгоритм для моделей с ограниченной поддержкой
|book-title=COLT
|страницы=67–79
|год=2010


|last1=Бодри
|first1=Дориан
|last2=Пескерель
|first2=Фабьен
|last3=Дегенн
|first3=Реми
|last4=Майяр
|first4=Одалрик-Амбрим
|title=Быстрые асимптотически оптимальные алгоритмы для непараметрических стохастических бандитов
|journal=Достижения в области нейронных систем обработки информации
|объем=36
|pages=11469–11514
|год=2023




Подробнее: https://en.wikipedia.org/wiki/Lai-Robbins_lower_bound