한국어 초록
본 논문에서는 적대적 환경(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})$ 보장을 달성할 수 있는 최초의 알고리즘입니다.
원문 초록
We establish near-optimal regret bounds for budget-constrained online learning against arbitrary classes of budget-pacing experts in the adversarial setting. In particular, given any class of $F$ experts and a candidate budget pacing schedule, we provide a full-information algorithm which obtains regret $O(D \sqrt{\log F}+ \sqrt{T\log F})$ against all experts whose cumulative spending stays within distance $D$ of this schedule, matching lower bounds established by Braverman et al. (2025). We additionally show that our technique extends to various problems in online resource allocation, where the learner gets to see the rewards and costs of the current options available to them, and establish $O(D\sqrt{\log F})$ regret bounds when fractional allocation is allowed. This is the first algorithm we are aware of which can achieve $o(\sqrt{T})$ guarantees for such tasks.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems
다중 스케일 행렬 가중치를 통한 온라인 역 선형 최적화의 정밀 후회 상한
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를 달성할 수 있는지는 열려 있다.
전문가 조언을 활용한 예측: 다수 전문가 환경에서 상시 후회가 고정 시간 상수에 일치함
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}$를 만족하는 알고리즘을 제시합니다.
Provably Optimal Learning Algorithms for Assistance Games
본 논문은 지원 게임(assistance games) 프레임워크의 온라인 변형을 연구한다. 이 설정에서 정보를 가진 에이전트와 정보를 갖지 않은 에이전트가 공통 보상 함수를 최적화하기 위해 $T$ 타임스텝에 걸쳐 반복적으로 상호작용한다. 정보를 가진 에이전트(인간)는 세계의 잠재 상태를 관찰하는 반면, 정보를 갖지 않은 에이전트(어시스턴트)는 인간의 행동만을 관찰한다. 우리는 반복적 지원 게임에 대한 최초의 증명 가능한 효율적 학습 알고리즘을 제시한다. 우리는 지원 후회(assistance regret)의 개념을 도입한다: 이는 누적 상호작용 효용과, 잠재 상태를 행동 쌍으로 매핑하는 사후 최적 결합 정책의 누적 효용 사이의 차이다. 우리는 인간과 어시스턴트 모두를 위한 분산형 알고리즘을 제시하며, 이 알고리즘은 행동 및 상태 공간의 크기에 대해 다항식 실행 시간으로 $\widetilde{O}(T^{3/4})$의 $(1-1/e)$-근사 지원 후회율을 달성한다. 이 알고리즘은 일반적이며, 특히 어시스턴트를 위한 임의의 무후회(no-regret) 알고리즘을 수용한다. 우리는 $(1-1/e)$보다 더 나은 후회 근사 인수를 달성하는 것이 계산적으로 난해함을 증명한다. 나아가, 공유 랜덤 문자열을 사용하는 유사 분산형(pseudo-decentralized) 설정에서 이러한 범용 무후회 알고리즘을 특화하여 로그 인수까지 최적인 $\widetilde{O}(T^{1/2})$의 율을 달성하는 방법을 제시한다.
선형 밴딧을 위한 자기일치 교란
Self-Concordant Perturbations for Linear Bandits
우리는 적대적 선형 밴딧(adversarial linear bandits) 설정을 고려하고, 완전 정보(full-information) 설정에서 알려진 Follow-the-Regularized-Leader(FTRL)와 Follow-the-Perturbed-Leader(FTPL) 간 연결을 확장하여 두 방법을 잇는 통합 알고리즘 프레임워크를 제시한다. 이 프레임워크 안에서 FTRL 기반 SCRiBLe 알고리즘에서 이전에 사용된 자기일치(self-concordant) 장벽의 역할을 반영하는 확률 분포군인 자기일치 교란(self-concordant perturbations)을 도입한다. 이 아이디어를 바탕으로 자기일치 정규화(self-concordant regularization)와 효율적인 확률적 탐험(stochastic exploration)을 결합하는 새로운 FTPL 기반 알고리즘을 설계한다. 우리 접근법은 $d$차원 하이퍼큐브와 $\ell_2$ 볼 모두에서 $\mathcal{O}(d\sqrt{n \ln n})$의 후회(regret)를 달성한다. $\ell_2$ 볼에서는 SCRiBLe가 달성한 후회 경계와 일치한다. 하이퍼큐브의 경우, 이는 기존 방법들 대비 $\sqrt{d}$만큼 개선되며, 로그 계수(logarithmic factors)를 제외하면 최적 경계(optimal bound)와 일치한다.
Blackwell Approachability와 Gradient Equilibrium의 동등성
Blackwell Approachability and Gradient Equilibrium are Equivalent
그래디언트 균형(GEQ)은 최근 도입된 온라인 최적화(optimization) 프레임워크로, 오프라인 최적화의 1차 정상성(first-order stationarity)을 일반화하고 온라인 conformal prediction과 같은 문제를 추상화한다. GEQ는 후회 최소화(regret minimization)와 같은 알려진 온라인 학습(online learning) 프레임워크와 놀라운 유사성을 보이지만, 기존 연구는 GEQ 오류와 regret이 비교 불가능한 목표임을 보여 주었으며, GEQ가 더 넓은 온라인 학습 지형에서 어떻게 자리 잡는지에 대한 정확한 이해는 여전히 열려 있다. 본 연구에서는 GEQ가 알고리즘적 의미에서 Blackwell approachability와 동등함을 보인다. 즉, Blackwell approachability 문제는 블랙박스 GEQ 오라클에 대한 질의(query)만으로 항상 풀 수 있으며, 오라클의 오류율(error rate)에 대한 점근적(asymptotic) 손실 없이 역방향도 성립한다. approachability, regret minimization, calibration 사이의 알려진 동등성과 합치면, 이 결과는 GEQ가 이들 프레임워크와도 동등함을 시사한다. 우리의 환원(reduction)은 효율적이며, 낙관성(optimism)과 강한 적응성(strong adaptivity)과 같은 정교한 보장을 regret minimization에서 GEQ로 전달하는 데 사용할 수 있다. 또한 GEQ에 대한 필요충분 조건을 규명하고, 제약이 없는(unconstrained) 및 제약이 있는(constrained) 의사결정 집합(decision set)을 갖는 GEQ의 서로 다른 개념들 사이의 환원을 확립한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.