2025-11-11T09:55:09.434704

UCB-type Algorithm for Budget-Constrained Expert Learning

Latypov, Suvorikova, Kroshnin et al.

In many modern applications, a system must dynamically choose between several adaptive learning algorithms that are trained online. Examples include model selection in streaming environments, switching between trading strategies in finance, and orchestrating multiple contextual bandit or reinforcement learning agents. At each round, a learner must select one predictor among $K$ adaptive experts to make a prediction, while being able to update at most $M \le K$ of them under a fixed training budget. We address this problem in the \emph{stochastic setting} and introduce \algname{M-LCB}, a computationally efficient UCB-style meta-algorithm that provides \emph{anytime regret guarantees}. Its confidence intervals are built directly from realized losses, require no additional optimization, and seamlessly reflect the convergence properties of the underlying experts. If each expert achieves internal regret $\tilde O(T^Î±)$, then \algname{M-LCB} ensures overall regret bounded by $\tilde O\!\Bigl(\sqrt{\tfrac{KT}{M}} \;+\; (K/M)^{1-Î±}\,T^Î±\Bigr)$. To our knowledge, this is the first result establishing regret guarantees when multiple adaptive experts are trained simultaneously under per-round budget constraints. We illustrate the framework with two representative cases: (i) parametric models trained online with stochastic losses, and (ii) experts that are themselves multi-armed bandit algorithms. These examples highlight how \algname{M-LCB} extends the classical bandit paradigm to the more realistic scenario of coordinating stateful, self-learning experts under limited resources.

academic

예산 제약이 있는 전문가 학습을 위한 UCB형 알고리즘

기본 정보

논문 ID: 2510.22654
제목: UCB-type Algorithm for Budget-Constrained Expert Learning
저자: Ilgam Latypov, Alexandra Suvorikova, Alexey Kroshnin, Alexander Gasnikov, Yuriy Dorn
분류: cs.LG (기계학습), cs.MA (다중에이전트 시스템)
발표 시간: 2025년 10월 28일 (사전인쇄본)
논문 링크: https://arxiv.org/abs/2510.22654

초록

많은 현대 응용에서 시스템은 여러 온라인 훈련 적응형 학습 알고리즘 간에 동적으로 선택해야 합니다. 예를 들어 스트림 환경에서의 모델 선택, 금융에서의 거래 전략 전환, 그리고 여러 맥락 강盗 문제 또는 강화학습 에이전트의 조율이 있습니다. 각 라운드에서 학습자는 K개의 적응형 전문가 중 하나를 선택하여 예측을 수행해야 하며, 동시에 고정된 훈련 예산 내에서 최대 M≤K개의 전문가만 업데이트할 수 있습니다.

본 논문은 확률적 설정에서 이 문제를 해결하며, 임의 시간 후회 보장을 제공하는 계산 효율적인 UCB 스타일 메타 알고리즘인 M-LCB 알고리즘을 제안합니다. 신뢰 구간은 실현된 손실에서 직접 구성되며 추가 최적화가 필요 없고, 기저 전문가의 수렴 특성을 자연스럽게 반영합니다. 각 전문가가 내부 후회 Õ(T^α)를 달성하면 M-LCB는 전체 후회 경계 Õ(√(KT/M) + (K/M)^(1-α)T^α)를 보장합니다.

연구 배경 및 동기

문제 정의

현실의 많은 응용은 여러 자기학습 전문가 간의 동적 선택을 필요로 합니다:

추천 시스템: 여러 예측기를 병렬로 실행하고 사용자 피드백에 따라 업데이트
금융 플랫폼: 시장 메커니즘의 진화에 따라 거래 전략 간 전환
대규모 온라인 서비스: 맥락 강盗 문제 또는 강화학습 알고리즘 조합 관리

핵심 과제

기존 방법의 한계:

고전적 다중 팔 강盗 문제(MAB): 정적 또는 적대적 보상 분포를 가정하며 팔의 학습 능력을 고려하지 않음
전문가 알고리즘: 일반적으로 완전한 피드백이 필요하며 전문가의 학습률을 고려하지 않음
기존 방법: 각 라운드 훈련 예산 제약 하에서 동시에 학습하는 여러 전문가를 관리하는 문제를 충분히 해결하지 못함

연구 동기

본 논문은 이 공백을 메우고 예측과 선택적 훈련을 통합하는 절차를 제안하며, 고정된 라운드별 계산 예산 제약을 고려합니다.

핵심 기여

새로운 UCB형 메타 알고리즘(M-LCB): 제한된 라운드별 학습 예산 M(M≤K)을 고려하여 K개의 자기학습 전문가 풀을 관리하는 새로운 알고리즘 제안
계산 효율성: 실현된 손실에서 직접 신뢰 경계를 구성하는 방법 제공으로 계산 효율적이며 비용이 많이 드는 보조 최적화 회피
이론적 분석: 전문가 개별 수렴률에 따른 메타 알고리즘 성능 추정. 전문가 후회가 Õ(n^α)일 때 전체 후회는 Õ(√(KT/M) + (K/M)^(1-α)T^α)
다중 게임 강盗 문제 확장: M-LCB가 다중 게임 강盗 문제 설정으로 확장 가능함을 증명

방법 상세 설명

작업 정의

결정 공간 U: 전문가 제안의 공간
환경 공간 E: 확률적 결과 공간
손실 함수: ℓ : U×E → R₊
전문가 명세: 각 전문가 k는 튜플(Wₖ,Hₖ,Aₖ,gₖ,υₖ)로 지정
- Wₖ: 상태/매개변수 공간
- Hₖ: 이력 공간
- Aₖ: 온라인 학습 알고리즘
- gₖ: 상태에서 제안으로의 매핑
- υₖ: 안전 제안 생성기