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

Мы рассматриваем контекстных бандитов с линейными ограничениями (CBwLC) — разновидность контекстных бандитов, в которой алгоритм использует несколько ресурсов при наличии линейных ограничений на их суммарное потребление. Эта задача обобщает контекстных бандитов с ограничениями типа рюкзака (CBwK), допуская ограничения на упаковку и покрытие, а также положительное и отрицательное потребление ресурсов. Мы предлагаем первый алгоритм для CBwLC (или CBwK), основанный на регрессионных оракулах. Алгоритм прост, вычислительно эффективен и статистически оптимален при слабых предположениях. Кроме того, мы получаем первые гарантии стремящегося к нулю сожаления для CBwLC (или CBwK), выходящие за рамки стохастической среды. Мы обходим сильные результаты о невозможности, полученные в предыдущих работах, выявляя более слабый и, вероятно, более справедливый эталон для сравнения. Наш алгоритм основывается на LagrangeBwK (Immorlica et al., FOCS 2019) — лагранжевой технике для CBwK — и SquareCB (Foster and Rakhlin, ICML 2020) — регрессионной технике для контекстных бандитов. Наш анализ использует присущую обеим техникам модульность.