온라인 일반화 평균 복지 극대화: 샘플을 통한 준최적 후회 달성
Online Generalized-Mean Welfare Maximization: Achieving Near-Optimal Regret from Samples
한국어 초록
본 연구에서는 이질적인 선호도를 지닌 $n$명의 에이전트(agent)에게 순차적으로 도착하는 $T$개의 아이템을 공정하게 온라인으로 배분하는 문제를 다루며, $p\in (-\infty, 1)$에 대해 에이전트들의 시간 평균 효용의 $p$-평균으로 정의되는 일반화 평균 복지(generalized-mean welfare)를 극대화하는 것을 목표로 합니다. 먼저 독립동일분포(i.i.d.) 도착 모델을 고려하여, 복지를 극대화하는 정수 배분을 근시안적으로 선택하는 순수 탐욕(pure greedy) 알고리즘이 $\widetilde{O}(1/T)$의 평균 후회(average regret)를 달성함을 보입니다. 중요하게도, 선행 연구와 달리 본 알고리즘은 분포에 대한 사전 지식을 요구하지 않으며 온라인 샘플만을 사용하여 최적의 후회율을 달성합니다. 이어 i.i.d. 도착을 넘어 시간에 따라 변하는 독립 분포를 갖는 비정상(nonstationary) 모델을 연구합니다. 분포에 대한 추가 데이터가 없을 경우, 모든 온라인 알고리즘은 $Ω(1)$의 평균 후회를 겪을 수밖에 없다고 알려져 있습니다. 우리는 임의의 비정상성이 존재하는 상황에서도 각 분포로부터 얻은 단 하나의 과거 샘플만으로 최적의 $\widetilde{O}(1/T)$ 평균 후회율을 회복하기에 충분함을 보입니다. 제안하는 알고리즘은 재해결(re-solving) 패러다임에 기반하며, 남은 아이템들이 해당 기간에 과거에 관측되었던 아이템일 것이라 가정하고 그에 따른 복지 극대화 문제를 풀어 매 기간의 결정을 도출합니다. 마지막으로, 과거 샘플의 정확도를 왜곡할 수 있는 분포 변화(distribution shift)를 고려하고, 제안한 재해결 알고리즘의 성능이 이러한 변화에 대해 강건(robust)함을 입증합니다.
원문 초록
We study online fair allocation of $T$ sequentially arriving items among $n$ agents with heterogeneous preferences, with the objective of maximizing generalized-mean welfare, defined as the $p$-mean of agents' time-averaged utilities, with $p\in (-\infty, 1)$. We first consider the i.i.d. arrival model and show that the pure greedy algorithm -- which myopically chooses the welfare-maximizing integral allocation -- achieves $\widetilde{O}(1/T)$ average regret. Importantly, in contrast to prior work, our algorithm does not require distributional knowledge and achieves the optimal regret rate using only the online samples. We then go beyond i.i.d. arrivals and investigate a nonstationary model with time-varying independent distributions. In the absence of additional data about the distributions, it is known that every online algorithm must suffer $Ω(1)$ average regret. We show that only a single historical sample from each distribution is sufficient to recover the optimal $\widetilde{O}(1/T)$ average regret rate, even in the face of arbitrary non-stationarity. Our algorithms are based on the re-solving paradigm: they assume that the remaining items will be the ones seen historically in those periods and solve the resulting welfare-maximization problem to determine the decision in every period. Finally, we also account for distribution shifts that may distort the fidelity of historical samples and show that the performance of our re-solving algorithms is robust to such shifts.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
다중 스케일 행렬 가중치를 통한 온라인 역 선형 최적화의 정밀 후회 상한
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를 달성할 수 있는지는 열려 있다.
정적·시간 가변 노출 하한을 갖는 불일치 반올림 공정 밴딧
Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors
최소 노출 제약은 추천, 콘텐츠 큐레이션, 규제된 할당에서 각 공급자, arm, 또는 그룹이 집계적으로만이 아니라 기간 내에 보장된 노출을 받아야 할 때 발생한다. 우리는 정확한 노출 하한을 갖는 확률적 밴딧(stochastic bandits)을 연구하고, 핵심 대상은 반올림 문제임을 보인다. 분수 공정 스케줄이 정수 pull로 실현되며, 노출 오차는 정확히 불일치 벡터(discrepancy vector)이다. 주요 기여는 시간 가변 하한을 갖는 블록 단위 모델이다. BDQ-UCB는 모든 블록 하한을 결정적으로 만족하며, horizon $T$가 아닌 비필수 예산 $R$에 의해 지배되는 공정 regret을 갖고, 높은 확률에서 regret $O(\sqrt{KR\log(KT)})$를 달성한다. MOSS 잔차(residual) 변형은 $O(\sqrt{KR})$를 달성하고, 일치하는 하한이 양의 필수 노출(mandatory exposure)에서도 minimax rate $Θ(\sqrt{KR})$를 제공한다. kl-UCB$^{++}$ 잔차 규칙은 instance-dependent 최적성을 추가한다. 이 정식화는 겹치는 그룹 하한에 필수적이다. arm별 반올림은 그룹 크기에 대해 $Ω(s)$만큼 그룹 제약을 위반할 수 있는 반면, Beck--Fiala 영공(null-space) 반올림은 블록 예산 내에서 모든 그룹 하한을 만족하며 위반을 arm degree $t$ 미만으로 유지하고, 동일한 $R$-매개변수 regret과 UCB를 결합한다. 학습된 그룹 계획에 대해, 우리는 disjoint system을 $\widetildeΘ(\sqrt{KT})$에서 닫고, 겹침 하에서 naive index 규칙이 실패하는 이유를 설명하는 이중 원장(dual-ledger) 분해를 제시하며, 초기 cover-slack 조건 하에서 pathwise feasible한 plan-sampling 규칙을 증명하고 조건부 $\widetilde O(\sqrt{KT})$ 보장을 달성하되, 조건 없는 겹침 rate는 열어둔다. 합성 하한, MovieLens-100k 장르 노출, 배포 스트레스 테스트에 대한 실험은 penalty tuning 없이 정확한 feasibility를 보여주며, tuned Lagrangian baseline과 경쟁력 있는 regret을 보인다.
다목적 생성형 추천 시스템을 위한 확률적 프림-듀얼 디코딩
Stochastic Primal-Dual Decoding for Multiobjective Generative Recommender Systems
최근 추천 시스템(RS)의 발전은 생성 모델링을 통해 상당한 성능 향상을 보여주었다. 실무에서 추천은 종종 슬레이트 — 항목의 순서 있는 목록 — 구성을 포함하며, 이는 관련성을 넘어 항목 속성에 정의된 제약이나 공정성 제약과 같은 다중 목표를 만족해야 한다. 기존 다목적 접근법은 생성형이 아닌 설정을 위해 설계된 후처리 기법에 의존하거나, 보조 목표를 모델 학습에 직접 통합한다. 전자는 생성형 RS의 순차적 특성을 명시적으로 고려하지 않으며, 후자는 대규모 시스템에서 종종 비현실적이다. 우리는 기본 모델을 수정하거나 재학습하지 않고도 다목적 슬레이트 생성을 지원하도록 자회귀(autoregressive) 생성형 RS를 보강하는 경량의 추론 시점 디코딩 층을 제안한다. 디코딩을 온라인 제약 최적화(optimization) 문제로 공식화하며, 항목이 순차적으로 선택되고, 관련성과 보조 목표 간 트레이드오프가 잔여 제약 여유(constraint slack), 즉 각 목표를 얼마나 더 만족해야 하는지에 따라 동적으로 조정된다. 이는 생성 과정에서 관련성과 보조 목표의 균형을 맞추는 확률적 프림-듀얼 근사 기법을 통해 구현된다. 우리는 제약 위반과 후회(regret)에 대한 이론적 보장을 제공하고, 광범위한 오프라인 실험과 실제 추천 시스템에서의 대규모 온라인 A/B 실험을 통해 제안 방법을 평가한다. 결과는 다목적 트레이드오프에서 일관된 개선을 보여주며, 사용자 만족도 손실 없이 보조 목표에서 +1.8%의 향상을 달성한다.
데이터 기반 블록 교체 스케줄링
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) 교체 사이의 구조적 비용 격차를 밝힌다.
밴딧에서 공정성의 대가: 엄밀한 미니맥스 특성화
Price of Fairness in Bandits: A Tight Minimax Characterization
밴딧 문제에서 표준 후회(regret) 최소화 알고리즘은 탐험을 상각 비용으로 취급하며, 이는 임상 시험과 같은 설정에서 초기 참가자에게 불공정한 사전(ex-ante) 손실을 노출시킬 수 있다. 최근 연구는 일반화된 $p$-평균을 통해 라운드별 기대 보상의 시퀀스를 평가함으로써 이 문제를 다루며, 이는 공리주의적 후생($p=1$), 내시 후생($p\to0$), 로얼스식 공정성($p\to-\infty$) 사이를 보간한다. $p\ge0$에 대해서는 엄밀한 보장이 알려져 있지만, 엄격한 공정 체제 $q=-p>0$는 음의 거듭제곱 평균이 가장 작은 라운드별 보상에 의해 지배되기 때문에 여전히 해결되지 않았다. 비음 평균을 갖는 $σ$-sub-Gaussian 보상에 대해, 기존 최상의 알고리즘은 균일 초기 탐험에 의존하여 후회 $O(k^{(q+1)/2}/\sqrt{T})$를 달성했으며, 유일한 일반적인 하한은 고전적인 $Ω(σ\sqrt{k/T})$였다. 따라서 $k$에 대한 추가적 의존성이 엄격한 공정성에 내재적인 것인지, 아니면 균일 탐험의 인공물인지는 불분명했다. 우리는 엄격한 공정성의 정확한 다항식적 대가를 밝힘으로써 이 간극을 메운다. 건초더미 속 바늘(needle-in-haystack) 구성을 사용하여, 우리는 알고리즘 독립적 하한 $Ω(σ\sqrt{k^{\max(1,q)}/T})$를 증명한다. $q>1$에 대해, 이는 $k^{q/2}$의 페널티가 정보량론적으로 불가피함을 보여준다. 그다음 \textsf{UCB-HARE}(Harmonic Anchored Rank Exploration, 조화 앵커 순위 탐험)을 제안하는데, 이는 균일 탐험을 인증된 양의 평균 앵커로 보호된 역가중 조화 순위 일정으로 대체한다. 그 후회는 $\widetilde{O}(σ\sqrt{k^{\max(1,q)}/T})$이며, 로그 요인을 제외하면 하한과 일치한다. 합성 인스턴스에 대한 실험이 \textsf{UCB-HARE}가 균일 탐험 베이스라인보다 개선됨을 확인하며, $q$가 커질수록 이득이 증가한다.
배려적 선제: 지속적 공유 환경에서 장기 과업 계획 개선
Courteous Anticipation: Improving Long-Lived Task Planning in Persistent Shared Environments
토론
이 논문과 연결된 포럼 글이 아직 없습니다.