Время эффективный способ реализации Multi-Armed-Bandits?

Question

Я занимаюсь исследованием проблемы многорукого бандита (МАБ) с прибл. 1 миллион вооружений Напротив, число итераций, конечно, намного больше, около 10-20 миллионов.

Большинству MAB-алгоритмов требуется оператор argmax (argmax пространства действия), который должен выполняться на каждой итерации, чтобы выбрать текущий рычаг (который максимизирует данный критерий выбора). Независимо от выбранного языка программирования для реализации, эта процедура / этот оператор argmax во всем пространстве действия (1 миллион рук) занимает очень много времени.

Есть ли у кого-нибудь идеи о том, как реализовать алгоритмы MAB в эффективный по времени способ?

Answer 1

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

average + sqrt(2 ln N / n_i)

Откладывая пока среднее вознаграждение, второй член зависит от общей суммы. количество выборок (N), которое является одинаковым для всех плеч, и общее количество образцов данного плеча (n_i). Таким образом, для всех рукавов, отобранных за одно и то же количество раз, второе слагаемое будет одинаковым.

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

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