Алгоритм типа UCB для обучения экспертов с ограничением по бюджету

Во многих современных приложениях система должна динамически выбирать между несколькими адаптивными алгоритмами обучения, которые обучаются онлайн. Примеры включают выбор модели в потоковых средах, переключение между торговыми стратегиями в финансах и оркестрацию нескольких агентов контекстных бандитов или обучения с подкреплением. На каждом раунде обучающаяся система должна выбрать один предиктор среди $K$ адаптивных экспертов для формирования прогноза, имея возможность обновить не более $M \le K$ из них при фиксированном бюджете обучения.

Мы рассматриваем эту задачу в стохастической постановке и представляем M-LCB — вычислительно эффективный мета-алгоритм в стиле UCB, обеспечивающий гарантии регрета в любой момент времени. Его доверительные интервалы строятся непосредственно из реализованных потерь, не требуют дополнительной оптимизации и точно отражают свойства сходимости лежащих в основе экспертов.

Если каждый эксперт достигает внутреннего регрета $\widetilde{O}(T^{\alpha})$, то M-LCB обеспечивает общий регрет, ограниченный

$$\widetilde{O}\!\left(\sqrt{\tfrac{KT}{M}} \,+\, (K/M)^{1-\alpha}\, T^{\alpha}\right).$$

Насколько нам известно, это первый результат, устанавливающий гарантии регрета при одновременном обучении нескольких адаптивных экспертов в условиях бюджетных ограничений на каждый раунд. Мы иллюстрируем фреймворк двумя представительными случаями: (i) параметрические модели, обучаемые онлайн со стохастическими потерями, и (ii) эксперты, которые сами являются алгоритмами многоруких бандитов. Эти примеры показывают, как M-LCB расширяет классическую парадигму бандитов на более реалистичный сценарий координации состоятельных самообучающихся экспертов при ограниченных ресурсах.