Алгоритмы с логическим или сублинейным сожалением для контекстных бандитов с ограничениями

Мы исследуем контекстных бандитов с ограничениями на бюджет и время, которых называем контекстными бандитами с ограничениями. Ограничения на время и бюджет существенно усложняют компромисс между исследованием и использованием, поскольку порождают сложное взаимное влияние контекстов во времени. Такие эффекты взаимосвязи затрудняют получение оракульных решений, предполагающих известную статистику бандитов. Для получения необходимых представлений мы сначала изучаем системы с единичной стоимостью и известным распределением контекстов. Если ожидаемые награды известны, мы разрабатываем приближение оракула, называемое адаптивным линейным программированием (Adaptive Linear Programming, ALP), которое обеспечивает почти оптимальность и требует лишь упорядочивания ожидаемых наград. Благодаря этим весьма желательным свойствам мы затем объединяем ALP с методом верхней доверительной границы (upper confidence bound, UCB) в общем случае, когда ожидаемые награды априори неизвестны. Мы показываем, что предложенный алгоритм UCB-ALP обеспечивает логарифмическое сожаление, за исключением некоторых граничных случаев. Кроме того, мы разрабатываем алгоритмы и получаем аналогичные результаты анализа сожаления для более общих систем с неизвестным распределением контекстов и неоднородными стоимостями. Насколько нам известно, это первая работа, показывающая, как достичь логарифмического сожаления в контекстных бандитах с ограничениями. Кроме того, эта работа проливает свет на исследование вычислительно эффективных алгоритмов для общих контекстных бандитов с ограничениями.