Стохастические бандиты для оптимизации бюджета на нескольких платформах в интернет-рекламе

Мы рассматриваем задачу системы интернет-рекламы, которая стремится оптимально распределить бюджет рекламодателя на кампанию между несколькими платформами, не зная ценности показа рекламы пользователям этих платформ. Мы моделируем эту сложную практическую задачу как задачу стохастических бандитов с рюкзаками за T раундов назначения ставок, где множество рук задаётся множеством различных m-кортежей ставок, а m — число платформ. Мы модифицируем алгоритм, предложенный Badanidiyuru и др. [11], и распространяем его на случай нескольких платформ, получая алгоритмы как для дискретных, так и для непрерывных пространств ставок. В частности, для дискретных пространств ставок мы предлагаем алгоритм с регретом [выражение отсутствует], где OPT — эффективность оптимального алгоритма, которому известны распределения. Для непрерывных пространств ставок регрет нашего алгоритма равен [выражение отсутствует]. В этом частном случае данная граница улучшает результат Sankararaman и Slivkins [34] в режиме OPT [выражение отсутствует] T, который имеет место в рассматриваемом практическом приложении. Во-вторых, мы доказываем нижнюю границу для дискретного случая и нижнюю границу Ω(m^{1/3}B^{2/3}) для непрерывного случая, почти совпадающую с верхними границами. Наконец, используя набор реальных данных крупной интернет-рекламной компании с несколькими рекламными платформами, мы показываем, что наши алгоритмы превосходят распространённые эталонные методы и удовлетворяют требованиям, предъявляемым в реальном практическом приложении.