Реоптимизация позволила улучшить алгоритмы контекстных бандитов с ограничениями
В задачах контекстных бандитов с ограничениями (Contextual Bandits with Knapsack) лицо, принимающее решения, распределяет поступающих клиентов по продуктам, каждый из которых расходует ограниченные ресурсы. Доход от назначения неизвестен заранее и зависит от признаков клиента и продукта, а цель — минимизировать потери дохода относительно идеальной политики, знающей функцию вознаграждения.
Исследователи предложили естественное расширение семейства алгоритмов Upper-Confidence-Bound (UCB) и применили к нему технику реоптимизации. Такой подход позволяет пересчитывать оптимальное распределение ресурсов по мере поступления данных, что делает алгоритм простым и практичным.
В статье показано, что благодаря реоптимизации средний регрет (потеря дохода по сравнению с оптимальной политикой) составляет O((ln T)^3 / T), где T — горизонт. Это заметно лучше классической оценки O(1/?T), характерной для близких задач динамического ценообразования, также использующих реоптимизацию.
Авторы подчёркивают простоту предложенного алгоритма: он опирается на стандартные UCB-оценки и не требует сложных вычислительных процедур. Это делает метод привлекательным для практических применений, где ресурсы ограничены и решения нужно принимать онлайн.
Работа доступна на arXiv в разделе машинного обучения (cs.LG). Точная дата публикации и имена авторов в аннотации не указаны, но препринт уже получил статус new (новое поступление).
Подобные задачи встречаются в онлайн-рекламе, управлении доходами, рекомендательных системах и других областях, где нужно одновременно изучать спрос и оптимизировать расход ресурсов. Улучшение теоретических гарантий может привести к более эффективным практическим алгоритмам.
