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

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