Лучший бандитский алгоритм?

Самым известным бандитским алгоритмом является верхний предел доверия (UCB), который популяризировал этот класс алгоритмов. С тех пор я предполагаю, что теперь есть лучшие алгоритмы. Каков текущий лучший алгоритм (с точки зрения либо эмпирической производительности, либо теоретических границ)? Является ли этот алгоритм оптимальным в некотором смысле?

В статье из NIPS 2011 («Эмпирическая оценка отбора проб Томпсона») в экспериментах показано, что отбор проб Томпсона побеждает UCB. UCB основан на выборе рычага, который обещает самое высокое вознаграждение при оптимистических предположениях (то есть, разница в вашей оценке ожидаемого вознаграждения высока, поэтому вы тянете рычаги, которые вы не знаете хорошо). Вместо этого, выборка Томпсона является полностью байесовской: она генерирует конфигурацию бандита (то есть вектор ожидаемых вознаграждений) из апостериорного распределения, а затем действует так, как если бы это была истинная конфигурация (то есть она тянет рычаг с наибольшим ожидаемым вознаграждением).

Байесовское контрольное правило (« Принцип минимальной относительной энтропии для обучения и действия », JAIR), обобщение выборки Томпсона, выводит выборку Томпсона из теоретико-информационных принципов и причинно-следственных связей. В частности, показано, что Байесовское контрольное правило является оптимальной стратегией, когда вы хотите минимизировать KL между вашей стратегией и (неизвестной) оптимальной стратегией и если вы принимаете во внимание причинные ограничения. Причина, по которой это важно, заключается в том, что это можно рассматривать как расширение байесовского вывода на действия: байесовский вывод может быть продемонстрирован как оптимальная стратегия прогнозирования, когда вашим критерием эффективности является KL между оценщиком и (неизвестным) истинным распределением.

UCB действительно близок к оптимальному в стохастическом случае (с точностью до логарифмического T-коэффициента для игры T-раунда) и до разрыва в неравенстве Пинскера в более проблемно-зависимом смысле. Недавняя работа Audibert и Bubeck удаляет эту зависимость от журнала в худшем случае, но имеет худшую оценку в благоприятном случае, когда разные руки имеют хорошо разделенные награды.

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

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

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

Текущий уровень техники можно подытожить так:

• $R_T = O(\frac{K \log T}{\Delta})$
• $\tilde{R}_T = O(\sqrt{T K \log K})$
• контекст: это сложно

$T$$K$$\Delta$