예산 제약이 있는 차별적 경매에서의 입찰 학습

우리는 매 라운드 효용이 가치(value)에서 자본 비용 파라미터인 $α$($α ext{는 } [0,1] ext{ 범위}$)를 곱한 지불액을 뺀 값과 동일한 단일 입찰자를 대상으로 하는 다중 단위 차별적 (pay-as-bid) 경매에서의 반복적 입찰을 연구합니다. 입찰자는 총 예산 $B$의 제약 조건 하에 $T$ 라운드 동안 누적 효용을 최대화하는 것을 목표로 합니다. 이 문제는 예산이 없는 경우에도 도전적입니다. 행동 공간(action space)이 입찰자의 최대 수요인 $M$에 대해 지수적으로 증가하며, 가치 벡터(context)가 시간에 따라 변하기 때문입니다. 단위별 효용 분해를 활용하여, 우리는 유향 비순환 그래프(directed acyclic graph, DAG)에서의 최단 경로를 기반으로 하는 다항 시간(polynomial-time) 학습 알고리즘을 개발하였으며, 완전 정보(full-information) 및 밴딧 피드백(bandit feedback) 환경 모두에서 서브리니어 후회(sublinear regret)를 얻었습니다. 밴딧 설정에서, 완전한 교차 학습(cross-learning) 덕분에 후회는 컨텍스트의 수와 무관합니다. 즉, 실현된 컨텍스트 하에서 선택된 행동의 효용을 관찰함으로써 모든 반사실적(counterfactual) 컨텍스트 하에서의 동일한 행동에 대한 효용을 알 수 있습니다. 예산 제약이 있는 경우, 평균 정규화된 라운드당 예산 $ρ=rac{B}{MT}<1$일 때, 우리는 결합된 원-쌍대(primal-dual) 알고리즘을 설계합니다. 이 알고리즘에서 DAG 기반 절차는 원 문제(primal) 업데이트를 위해 쌍대 조정된(dual-adjusted) 에지 가중치를 사용하며, 온라인 경사 하강법(online gradient descent)은 쌍대 변수(dual variable)를 업데이트하여 $ρ$-근사 서브리니어 후회를 산출합니다. 마지막으로, 라운드당 시간 및 공간 복잡도가 컨텍스트의 수와 무관한 구현 방식을 제시하여, 크거나 심지어 무한한 컨텍스트 공간으로의 확장성을 가능하게 합니다.