Алгоритм «Исследуй, затем фиксируй» ⇐ Васина Википедия

[wiki_en]

«Исследуй, затем соверши» (ETC) — это алгоритм решения задачи «Многорукий бандит», в котором вам нужно найти компромисс между исследованием и эксплуатацией.

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

Задача «Многорукий бандит»|Задача «Многорукий бандит» — это последовательная игра|последовательная игра, в которой один игрок должен на каждом ходу выбирать между K действиями (оружием). За каждой рукой a находится неизвестное распределение \nu_a, которое лежит в наборе \mathcal{D}, известном игроку (например, \mathcal{D} может быть набором нормального распределения|распределения Гаусса или распределения Бернулли|распределения Бернулли).

На каждом ходу t игрок выбирает (тянет) руку a_t, затем он получает наблюдение X_t распределения \nu_{a_t.

=== Минимизация сожалений ===

Цель состоит в том, чтобы свести к минимуму сожаление во время T, которое определяется как
: R_T := \sum_{a=1}^K \Delta_a \mathbb{E}[N_a(T)]
где
* \mu_a := \mathbb{E}[\nu_a] — среднее значение руки a
* \mu^* := \max_a \mu_a — наивысшее среднее значение
* \Delta_a := \mu^* - \mu_a
* N_a(t) — количество подъёмов руки a вверх для поворота t

Игрок должен найти алгоритм, который на каждом ходу выбирает t, какую руку тянуть, основываясь на предыдущих действиях и наблюдениях (a_s,X_s)_{s < t, чтобы минимизировать сожаление R_T.

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

== Алгоритм ==

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

Существуют адаптации алгоритма, их можно найти в литературе по другим настройкам.

=== Псевдокод ===

Игрок выбирает М
'''для''' каждой руки '''i''' '''делаю''':
выберите руку '''i''' M раз
обновить эмпирическое среднее значение mu['''i''']
'''за''' от МК+1 до Т '''до''':
выберите руку '''a''' с самым высоким средним темпиральным значением mu['''a''']

== Теоретические результаты ==

Когда все плечи являются 1-субгауссовыми, при выборе исследования каждого рукава M раз сожаление в момент времени T проверяется
:
R_T \leq M \sum_{i = 1}^K \Delta_i + (T - M K) \sum_{i=1}^K \Delta_i \exp\left( -\frac{M \Delta_i^2}{4} \right)


Мы можем рассматривать первый член как стоимость разведки
:
M \sum_{i = 1}^K \Delta_i
А второй член — это цена недостаточного исследования, ведущая к вероятности отсутствия оптимальной руки в качестве руки с самым высоким эмпирическим средним значением.
:
(T - M K) \sum_{i=1}^K \Delta_i \exp\left( -\frac{M \Delta_i^2}{4} \right)
Увеличение M увеличивает первый член и уменьшает второй член. Наилучший возможный M должен зависеть от (\Delta_i)_i, который неизвестен игроку.

Для двух рукавов с гауссовским распределением дисперсии 1 было доказано, что ETC не может достичь асимптотического оптимального сожаления уравнения Лая-Роббинса.



|last1=Нет
|first1=Гуанью
|last2=Агарвал
|first2=Мридул
|last3=Умравал
|first3=Абхишек Кумар
|last4=Аггарвал
|first4=Ванит
|last5=Куинн
|first5=Кристофер Джон
|title=Алгоритм «исследуй-затем-фиксируй» для субмодульной максимизации при полнобандитской обратной связи
|book-title=Неопределенность в искусственном интеллекте
|страницы=1541–1551
|год=2022
|publisher=PMLR


|last1=Джин
|first1=Тяньюань
|last2=Сюй
|first2=Панорамирование
|last3=Сяо
|first3=Сяокуй
|last4=Гу
|first4=Цюаньцюань
|title=Двойное исследование-затем-фиксация: асимптотическая оптимальность и не только
|book-title=Конференция по теории обучения
|pages=2584–2633
|год=2021
|publisher=PMLR


|last1=Гаривье
|first1=Орельен
|last2=Кауфман
|first2=Эмили
|last3=Латтимор
|first3=Тор
|title=О стратегиях «исследуй-затем-используй»
|book-title=Достижения в области нейронных систем обработки информации 29
|год=2016


|last1=Латтимор
|first1=Тор
|last2=Сепешвари
|first2=Чаба
|title=Бандитские алгоритмы
|год=2020
|publisher=Издательство Кембриджского университета




Алгоритмы
Теория принятия решений
Последовательные методы
Алгоритмы и методы оптимизации
Стохастическая оптимизация
Теория игр

Подробнее: https://en.wikipedia.org/wiki/Explore-t ... _algorithm