스무딩 온라인 학습에 적용 가능한 효율적인 온라인 비례 샘플링

Efficient Online Proportional Sampling with Applications to Smoothed Online Learning

본 연구에서는 고차원 영역에서 σ-스무딩 적대자에 대한 효율적인 온라인 비례 샘플링 문제를 다룹니다. 샘플링 분포는 시간 경과에 따라 동적으로 변화하는 가중 함수에 의해 유도되며, 이는 일련의 조각화된 파티션으로 정의됩니다. 이러한 설정은 주체-대리 게임(예: 가격 결정 및 계약 설계), 알고리즘 구성 및 매개변수 튜닝을 포함한 광범위한 응용 분야를 포괄합니다. 핵심적인 과제는 유도된 파티션이 시간이 지남에 따라 점점 더 복잡해짐에 따라 효율적인 데이터 구조를 유지하는 것입니다. 직관적으로, $d$ 차원에서 $t$ 단계까지 하위 영역의 수는 $O(t^d)$로 증가할 수 있습니다. 본 연구에서는 축 평행 초평면으로부터 구조화된 불연속성을 갖는, 효율적인 업데이트 및 비례 샘플링을 지원하는 데이터 구조를 설계했습니다. σ-스무딩 적응형 적대자에 대해, 당사의 데이터 구조의 깊이에 대한 $O(rac{ ext{σ}}{ ext{T}})$ 경계를 유도했으며, 랜덤 순서 적대자에 대해서는 $O( ext{log T})$ 경계를 유도했습니다. 이는 해당 문제 클래스에 대한 최초의 결과입니다. 본 연구에서는 이 프레임워크를 조각화된 보상을 갖는 온라인 학습에 적용하여 완전 정보 및 밴딧 피드백 하에서 효율적인 후회 없는 알고리즘을 개발했으며, 검증 가능한 서브선형 후회 보장을 제공합니다.

We study the problem of efficient online proportional sampling from a high-dimensional domain under a $σ$-smoothed adversary, where the sampling distribution is induced by a dynamically evolving weight function defined over a sequence of piecewise-structured partitions. This setting captures a broad range of applications, including principal-agent games (e.g., pricing and contract design), and algorithm configuration and parameter tuning. The central challenge is maintaining an efficient data structure as the induced partition grows increasingly complex over time -- naively, the number of subregions can grow as $O(t^d)$ by round $t$ in $d$ dimensions. We design a data structure that supports efficient updates and proportional sampling while avoiding the cost of explicitly maintaining this exponential growth, where the discontinuities are structured from axis-parallel hyperplanes. Under a $σ$-smoothed adaptive adversary, we prove a tight $O(\sqrt{σT})$ bound on the depth of our data structure, and an $O(\log T)$ bound under a random-order adversary -- to our knowledge, the first such results for this class of problems. We apply this framework to online learning with piecewise-structured rewards, obtaining efficient no-regret algorithms under both full-information and bandit feedback, with provable sublinear regret guarantees.