Гарантии «лучшего из многих миров» для онлайн-обучения с рюкзаками

Мы изучаем задачи онлайн-обучения, в которых лицо, принимающее решения, стремится максимизировать ожидаемое вознаграждение, не нарушая конечное множество из m ресурсных ограничений. Формулируя процесс обучения на подходящем пространстве смесей стратегий, мы устанавливаем сильную двойственность для лагранжевой релаксации исходной задачи оптимизации даже в общем случае, когда функции вознаграждения и потребления ресурсов могут быть невыпуклыми. Затем мы предлагаем первую универсальную для множества режимов («лучшего из многих миров») схему для этой постановки, обеспечивающую гарантии отсутствия сожалений при стохастических, состязательных и нестационарных входных данных. В стохастическом случае наша схема дает такие же гарантии сожалений, как и ранее известные результаты. В то же время, когда бюджеты растут как минимум линейно по горизонту времени, она позволяет получить постоянный коэффициент конкурентоспособности в состязательном случае, что улучшает наилучшую известную верхнюю границу O(log m log T). Кроме того, наша схема позволяет лицу, принимающему решения, работать с невыпуклыми функциями вознаграждения и затрат. Мы приводим два теоретико-игровых применения нашей схемы, чтобы дополнительно продемонстрировать ее гибкость. В частности, мы показываем, что ее можно использовать для реализации механизмов управления темпом расходования бюджета в повторяющихся аукционах первой цены.