전문가 조언을 활용한 예측: 다수 전문가 환경에서 상시 후회가 고정 시간 상수에 일치함
Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
한국어 초록
전문가 조언을 활용한 예측(prediction with expert advice)은 온라인 학습(online learning)의 근본적인 문제입니다. 시간 범위(time horizon) $T$가 사전에 알려져 있을 때, $n$명의 전문가에 대한 미니맥스 누적 후회(minimax cumulative regret)는 점근적으로 $\sqrt{\frac{T \ln n}{2}}$입니다. 이는 $T$에 맞추어 조정된 학습률을 사용하는 곱셈 가중치 업데이트(Multiplicative Weights Update) 알고리즘을 통해 달성되며, 타이트한(tight) 것으로 알려져 있습니다. 반면 후회 상한(regret bound)이 모든 시점 $t$에서 동시에 성립해야 하는 경우, 기존에 알려진 최선의 보장은 $\sqrt{2}$배 더 나쁜 $\sqrt{t \ln n}$이었으며, 이 $\sqrt{2}$ 계수가 필수적인지는 알려지지 않은 채로 남아 있었습니다. 본 연구에서는 이것이 필수적이지 않음을 보입니다. 본 논문에서는 시간 범위에 대한 사전 지식을 요구하지 않으면서도, 누적 후회가 모든 $t \ge 1$에 대해 동시에 $R_t \le \bigl(1 + O(\sqrt{\ln \ln n / \ln n})\bigr)\sqrt{t \ln n / 2}$를 만족하는 알고리즘을 제시합니다.
원문 초록
Prediction with expert advice is a fundamental problem in online learning. When the time horizon $T$ is known in advance, the minimax cumulative regret over $n$ experts is asymptotically $\sqrt{\frac{T \ln n}{2}}$. This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to $T$, and is known to be tight. If instead the regret bound is required to hold simultaneously at every time $t$, the best known guarantee has been $\sqrt{t \ln n}$---a factor of $\sqrt{2}$ worse---and it has remained unknown whether this factor of $\sqrt{2}$ is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies $R_t \le \bigl(1 + O(\sqrt{\ln \ln n / \ln n})\bigr)\sqrt{t \ln n / 2}$ simultaneously for every $t \ge 1$.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2609.27206v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems
일반 함수 근사 하에서의 최적·효율적 문맥적 조합 세미-밴딧
Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation
예산 지출 조절과 학습의 최적 페이싱
Optimally Pacing Budget Spending and Learning
본 논문에서는 적대적 환경(adversarial setting)에서 임의의 예산 조절(budget-pacing) 전문가 집단에 대한 예산 제약 온라인 학습의 준최적(near-optimal) 리그릿 상한(regret bound)을 규명합니다. 구체적으로, 임의의 $F$개 전문가 집단과 후보 예산 페이싱 스케줄이 주어졌을 때, 누적 지출이 이 스케줄과 거리 $D$ 이내로 유지되는 모든 전문가에 대해 $O(D \sqrt{\log F}+ \sqrt{T\log F})$의 리그릿을 달성하는 완전 정보(full-information) 알고리즘을 제시하며, 이는 Braverman 등(2025)이 제시한 하한과 일치합니다. 나아가 학습자가 이용 가능한 현재 옵션의 보상과 비용을 관측할 수 있는 다양한 온라인 자원 할당 문제로 본 기법이 확장됨을 보이고, 분수 할당(fractional allocation)이 허용될 때 $O(D\sqrt{\log F})$ 리그릿 상한을 확립합니다. 이는 우리가 아는 한 이러한 과제에서 $o(\sqrt{T})$ 보장을 달성할 수 있는 최초의 알고리즘입니다.
다중 스케일 행렬 가중치를 통한 온라인 역 선형 최적화의 정밀 후회 상한
Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
고정된 알려지지 않은 선형 효용(utility)을 갖는 온라인 역 선형 최적화를 연구한다. 각 라운드에서 환경(environment)은 컴팩트 행동 집합을 제시하고, 학습자(learner)는 그 집합에서 행동(action)을 추천하며, 환경은 동일한 집합 위에서 효용을 최대화하는 행동을 반환한다. 효용 벡터와 행동이 $d$차원 유클리드 단위 구(unit ball) 안에 있을 때, 시간 지평(time horizon)을 알 필요 없이 모든 시간 지평에 대해 기대 후회(regret)---최적 행동 대비 누적 효용 부족분---가 $O(\sqrt d)$인 무작위 알고리즘을 제시한다. $d$에 대한 의존성은 $T\ge d$인 지평에 대한 알려진 $\Omega(\sqrt d)$ 하한에 의해 상수 배수까지 최적이다. 우리 알고리즘은 기하학적으로 간격을 둔 스케일에서 다항식 특징(feature) 공간上的 행렬 곱셈 가중(matrix multiplicative weights)을 유지한다. 선형 프로그램(linear program)을 풀어 추천 분포를 선택하고, 이용 가능한 행동과 피드백 행동을 비교하여 점수 행렬을 갱신한다. 유리수 oracle 출력과 피드백 행동 하에서, 선형 최적화 oracle에 상대적으로 계산 가능한 구현이 $O(\sqrt d)$ 후회 상한을 유지한다. 차원, 지평, 입력 길이에 대해 다항 시간 실행 복잡도로 동일한 rate를 달성할 수 있는지는 열려 있다.
스폰서 검색 시장을 위한 적응형 광고 부하 설계: 증거, 이론, 배포
Adaptive Ad Load Design for Sponsored Search Markets: Evidence, Theory, and Deployment
광고 부하(ad-load) 설계는 스폰서 검색에서 공급 측의 핵심 의사결정이다. 스폰서 슬롯을 늘리면 수익을 높일 수 있지만, 자연 검색 결과를 밀어내고 사용자 결과를 악화시킬 수 있다. 우리는 안드로이드 앱 스토어에서 수행한 대규모 무작위 현장 실험을 통해 이 트레이드오프를 연구했으며, 500만 명 이상의 사용자가 1개부터 6개까지의 스폰서 슬롯에 노출되었다. 광고 부하를 늘리면 수익이 최대 43% 증가하지만, 총 검색 전환은 최대 5% 감소하고 일일 참여도는 최대 2.2% 감소한다. 이러한 평균 효과는 상당한 이질성을 가린다. 추가 슬롯은 광고 전환율이 높은 쿼리에서 큰 수익 증가를 만들지만, 전환율이 낮은 쿼리에서는 한계 수익이 거의 없거나 음수이다. 이 트레이드오프는 브랜드 광고주 존재와 같이 광고주 구성이 변함에 따라 쿼리 내에서도 이동한다. 이러한 발견에 동기를 받아, 우리는 새로운 적응형 알고리즘인 탐험(exploration) 보강 국소 적응형 광고 부하(exploration-augmented Locally Adaptive Ad Load, e-LAAL)를 설계하고 배포했다. e-LAAL은 최근 결과를 사용해 광고 부하 권장값을 갱신하는 모델(model)-free 쿼리 수준 의사결정 규칙인 LAAL과, 지지(support)를 유지하고 고정 정책 반사실(counterfactual) 벤치마크를 제공하는 정적 탐험(exploration) arm을 결합한다. 우리는 e-LAAL 아키텍처에 대한 유한 시간 동적 후회(dynamic-regret) 보장을 제공한다. 2,230만 명의 사용자와 7,760만 건의 검색을 처리하는 플랫폼 수준의 프로덕션 배포에서 e-LAAL은 배포된 정적 벤치마크 대비 실증적 수익–전환 트레이드오프를 개선하고, 균일한 정적 벤치마크 및 과거 쿼리 의존적 정적 벤치마크를 능가한다.
데이터 기반 블록 교체 스케줄링
Data Driven Block Replacement Scheduling
우리는 \textit{블록 교체 정책(block replacement policy)} 하에서 $N$대의 독립 동형 기계를 유지·관리하기 위한 데이터 기반 알고리즘을 개발한다. 이 정책에서는 각 기계가 고장 시 교체되고, 모든 기계가 길이 $k$의 정규 간격으로 일괄 교체된다. 수명 분포가 알려지지 않은 경우 운영 데이터로부터 비용을 최소화하는 간격 $k^*$를 학습하는 것이 목표이다. 각 의사결정 시점마다 운영자는 $k \in \{1, 2, \ldots, K\}$를 선택하고, 그 결과 고장 이력(완전 수명과 우측 검열(right-censored) 수명의 혼합)을 관측하며, 갱신 함수(renewal function)에 의해 결정되는 단위 시간당 비용을 부담한다. 이를 확률적 다중 팔 밴딧(stochastic multi-armed bandit)으로 형식화하고, $O(K \log T)$ 후회(regret)를 달성하는 Hoeffding 및 Bernstein 기반 하한 신뢰 구간(lower-confidence-bound) 알고리즘을 제안하며, 이는 Lai--Robbins 하한과 일치한다. 블록 교체에 고유한 중첩 관측(nested observation) 성질을 활용한 상관 변형(correlated variants)은 $O((K-k^*)\log T)$ 후회를 달성하고, 차선 arm $k < k^*$에 대한 직접 pull은 $O(1)$번만 필요하다. 보완적으로 Kaplan--Meier 갱신 알고리즘은 검열 데이터로부터 수명 분포를 비모수적으로 추정하여, 거의 확실(almost-sure)한 정책 일관성을 달성하고 장기 구간에서 실증적으로 거의 0에 가까운 추가 후회를 보인다. 또한 평균 비용 MDP 두 가지를 분석한다. 경과 시간(time-elapsed) 형식화는 임의의 수명 분포에 대해 블록 교체가 해당 정책 클래스 내에서 최적임을 보이고, 연령 벡터(age-vector) 형식화는 증가하는 고장률(increasing failure rate) 분포 하에서 단조 임계값(monotone threshold) 구조를 증명하며 gold-standard 비용 벤치마크를 제공한다. 수치 실험은 이론적 순서를 확인하고, 최적 블록 교체와 연령 의존(age-dependent) 교체 사이의 구조적 비용 격차를 밝힌다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.