예산 제약이 있는 차별적 경매에서의 입찰 학습
Learning to Bid in Discriminatory Auctions with Budget Constraints
한국어 초록
우리는 라운드당 효용이 가치에서 α(α∈[0,1]은 자본 비용 매개변수)를 결제액에 곱한 값을 뺀 것과 같은 단일 입찰자를 대상으로, 다중 단위 차별적(pay-as-bid) 경매에서의 반복 입찰을 연구한다. 입찰자는 총 예산 B의 제약 하에 T 라운드에 걸친 누적 효용의 최대화를 목표로 한다. 이 문제는 예산이 없는 경우에도 어렵다: 행동 공간이 입찰자의 최대 수요량 M에 대해 지수적이며, 가치 평가 벡터(컨텍스트)가 시간에 따라 변화하기 때문이다. 단위 간 효용 분해를 활용하여, 우리는 방향성 비순환 그래프(DAG)의 최단 경로에 기반한 다항 시간 학습 알고리즘을 개발하고, 완전 정보 및 밴딧 피드백 모두에서 준선형 후회(regret)를 달성한다. 밴딧 설정에서는 완전 교차 학습(complete cross-learning)으로 인해 후회가 컨텍스트 수에 독립적이다: 실현된 컨텍스트 하에서 선택한 행동의 효용을 관측하면 모든 반사실적 컨텍스트에서 동일한 행동의 효용이 드러나기 때문이다. 예산 제약이 있는 경우, 평균 정규화된 라운드당 예산 ρ=B/(MT)<1일 때, 우리는 결합 원시-쌍대(primal-dual) 알고리즘을 설계한다. 이 알고리즘에서 방향성 비순환 그래프 기반 절차는 원시 갱신에 쌍대 조정 에지 가중치를 사용하고, 온라인 경사하강법이 쌍대 변수를 갱신하여 ρ-근사 준선형 후회를 달성한다. 마지막으로, 라운드당 시간 및 공간 복잡도가 컨텍스트 수에 독립적인 구현을 제시하여 크거나 심지어 무한한 컨텍스트 공간으로의 확장을 가능하게 한다.
원문 초록
We study repeated bidding in multi-unit discriminatory (pay-as-bid) auctions for a single bidder with per-round utility equal to value minus $α$ times payment, where $α\in[0,1]$ is a cost-of-capital parameter. The bidder aims to maximize cumulative utility over $T$ rounds subject to a total budget $B$. The problem is challenging even without budgets: the action space is exponential in $M$, the maximum demand of the bidder and the valuation vector (context) varies over time. Exploiting a decomposition of utility across units, we develop polynomial-time learning algorithms based on shortest paths in a directed acyclic graph, obtaining sublinear regret under both full-information and bandit feedback. In the bandit setting, the regret is independent of the number of contexts due to complete cross-learning: observing the utility of the chosen action under the realized context reveals the utility for the same action under all counterfactual contexts. With budget constraints, when the average normalized per-round budget $ρ=\frac{B}{MT}<1$, we design a coupled primal-dual algorithm in which the DAG-based procedure uses dual-adjusted edge weights for primal updates, while online gradient descent updates the dual variable, yielding $ρ$-approximate sublinear regret. Finally, we give implementations whose per-round time and space are independent of the number of contexts, enabling scalability to large or even infinite context spaces.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.29252v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
적응적 실험에서 정책 개선 가치에 대한 추론
Inference on the Value of Policy Improvement in Adaptive Experiments
본 논문에서는 적응적으로 수집된 데이터 환경에서 정책 개선 가치(VPI, Value of Policy Improvement)에 대한 점근적 정규 추정량(asymptotically normal estimator)을 개발합니다. 특정 군집 내 최적 처치 정책의 가치와 기준선(baseline) 정책 가치 간의 격차로 정의되는 이 값은 맞춤형 처치 정책을 도입할 가치가 있는지 여부를 측정합니다. VPI에 대한 추정량을 구축하는 것은 고정된 정책의 가치를 추정하는 것보다 본질적으로 더 어렵습니다. 이는 적응적 실험과 연관된 상관 데이터 및 감소하는 성향(decaying propensities)을 다루어야 할 뿐만 아니라, 최적 정책이 유일하지 않을 때 기저 피추정량(estimand)의 비정칙성(non-regularity) 또는 경로별 미분 불가능성(lack of pathwise differentiability)도 모든 추정량이 함께 처리해야 하기 때문입니다. 본 연구에서 제안하는 추정량은 과거 데이터에 대해 가중 경험적 후생 극대화(weighted empirical welfare maximizing) 정책을 순차적으로 적합한 후, 미래 샘플에 대해 역성향 가중치(inverse propensity weighting)를 적용하여 이를 평가하는 방식으로 작동합니다. 우리는 최적 정책이 유일하다고 가정하지 않으며, 기저의 이질적 처치 효과에 대한 마진(margin) 가정도 두지 않습니다. 추정량 분석의 핵심적인 난점은 정책 학습을 통해 발생하는 후회(regret)가 추정량의 표준 오차보다 점근적으로 작음을 보이는 것입니다. 우리는 감소하는 성향 조건 하에서 정책 학습의 더 빠른 후회율(regret rate)을 입증함으로써 이를 달성하였으며, 이는 독립적으로도 유의미한 가치를 지닐 수 있습니다. 합성 및 준합성 데이터의 혼합을 통해 추정량의 포함 확률(coverage)을 평가할 뿐만 아니라, Caria 등이 요르단에서 진행한 구직 지원 프로그램의 효과 평가 적응적 실험에서 VPI를 추정하는 데에도 이를 적용합니다. 본 연구의 추정치는 최적 정책이 유일하다고 가정한 이들의 계층적 베이지안(hierarchical Bayesian) 분석 결과보다는 전반적으로 보수적이지만, 여전히 시리아 난민 집단 내에서 개인화가 지닌 이점을 입증합니다.
지속적 후보 집합을 활용한 선형 밴딧 가속화
Accelerating Linear Bandits with Persistent Candidate Sets
행동의 수가 $K$개로 매우 큰 고정된 집합을 갖는 선형 밴딧(linear bandit)에서는 완전 낙관적 점수 산출(exhaustive optimistic scoring)로 인해 라운드당 $\mathcal{O}(K)$회의 점수 평가가 필요하여 행동 선택 비용이 커질 수 있습니다. 본 논문에서는 $k$개의 활성 행동을 유지하고 매 라운드마다 나머지 $K-k$개 행동 중에서 $q$개의 도전자(challenger)를 균등하게 표본추출하는 Persistent Candidate LinUCB(\textsc{PC-LinUCB})를 제안합니다. 이 $k+q$개의 후보에 대해서만 점수를 평가함으로써, \textsc{PC-LinUCB}는 라운드당 점수 평가 횟수를 $\mathcal{O}(k+q)$로 줄입니다. 고정된 신뢰 수준에서 표준 선형 밴딧 학습 항과 $\mathcal{O}\left((K-k)\log(K-k)/q\right)$ 차수의 추가적 탐색 비용(discovery cost)으로 구성된 문제 독립적(problem-independent) 및 문제 의존적(problem-dependent) 고확률 후회 경계(regret bound)를 증명합니다. 특히, 이 추가 비용은 시간 지평(horizon)에 따라 증가하지 않습니다. 고정된 간격(gap)과 충분히 긴 시간 지평에 대해 균등 도전자 표본추출 조건 하에서 $\Omega\left((K-k)/q\right)$ 후회 하한을 도출하여, 부분 후보 접근 자체가 불가피한 후회 비용을 수반함을 보여줍니다. 실험 결과, \textsc{PC-LinUCB}는 유사한 수준의 후회를 유지하면서 LinUCB의 속도를 대폭 가속하며, 지속적 후보 메커니즘이 LinUCB를 넘어 다른 알고리즘으로도 확장될 수 있음을 보입니다.
시간적 근접성을 넘어서: 강화학습에서의 신용 할당을 위한 설명적 월드 모델
Beyond Temporal Proximity: Explanatory World Models for Credit Assignment in Reinforcement Learning
생성형 추천 시스템(Generative Recommenders)은 결정 이후 수백 또는 수천 번의 상호작용이 지난 뒤에야 나타나는 결과를 최적화하기 위해 점점 더 강화학습(Reinforcement Learning, RL)을 활용하고 있다. 표준 강화학습은 명시적인 관련성이 아니라 시간적 근접성에 따라 보상을 전파하며, 이로 인해 멀리 떨어져 있지만 중요한 행동에 할당되는 신호가 약화되고 샘플 비효율성의 원인이 된다. 우리는 설명(explanation)을 사용하여 실현된 결과에 그럴듯하게 기여했을 이전 사건들을 식별하는 귀속(attribution) 프레임워크인 설명적 월드 모델(Explanatory World Models, EWM)을 소개한다. 우리는 프론티어 언어 모델을 사용하여 EWM을 구체화하고, 할인되지 않은 에피소드 리턴(undiscounted episode return)을 보존하면서 보상을 재귀적으로 재분배하는 보수적인 계층적 연산자(hierarchical operator)를 통해 그 설명을 학습 신호로 사용한다. 무엇이 유용한 설명을 구성하는지를 조사하기 위해, 우리는 Halpern의 실제 인과관계(actual causation), Lombrozo의 설명적 단순성(explanatory simplicity), Deutsch의 변형하기 어려운 설명(hard-to-vary explanations)에서 영감을 받은 세 가지 상호 보완적인 변형을 구체화한다. 우리는 두 가지 통제된 장기 호라이즌(long-horizon) 강화학습 벤치마크, 공개된 순차적 추천(sequential-recommendation) 벤치마크, 그리고 산업 규모의 생성형 추천 시스템에서 EWM을 평가한다. Crafter와 WordCraft에서 EWM은 PPO와 LaRe를 크게 상회하며, 보상이 가장 지연될 때 가장 큰 성능 향상을 보인다. KuaiRand에서 EWM은 오프라인에서 SFT와 LaRe를, 온라인에서 A2C를 상회한다. 마지막으로, 산업용 생성형 추천 시스템에 대한 오프라인 평가에서 EWM은 재현율(Recall)을 상당히 개선하고 행동 대리 지표(behavioral proxies)를 증가시킨다. 이러한 결과는 설명이 지연된 결과로부터 학습하기 위한 구조화되고 재사용 가능한 신용(credit)을 제공할 수 있음을 시사한다.
고차원 금융 회귀에서 몬테카를로 트리 탐색을 통한 $L_0$ 특징 선택
$L_0$ Feature Selection via Monte Carlo Tree Search in High-Dimensional Financial Regression
특징(feature) 선택은 수많은 엔지니어링된 변수와 예측 변수 간의 강한 상관관계로 인해 모델(model)의 안정성과 해석 가능성이 저하되는 고차원 금융 회귀에서 핵심적인 문제입니다. 희소 회귀(sparse regression)에는 $L_1$ 정규화(regularization)(Lasso)가 널리 사용되지만, 정보성 신호가 상관관계를 갖는 변수들에 걸쳐 분산되어 있을 때는 수축(shrinkage) 특성이 제약으로 작용할 수 있습니다. 정확한 희소 회귀(exact sparse regression)는 이러한 수축을 피하지만 계산상 다루기 어려운 조합 최적화(combinatorial optimization) 문제를 해결해야 하며, 일반적으로 표본 외(out-of-sample) 오차가 아닌 표본 내(in-sample) 오차를 최소화하도록 적합됩니다. 본 논문에서는 일반화된 중첩 롤아웃 정책 적응(GNRPA)을 적용한 몬테카를로 트리 탐색(Monte Carlo Tree Search) 기반의 특징 선택 프레임워크를 제시합니다. 특징 선택을 순차적 의사결정 과정으로 정식화하며, 후보 부분집합은 학습(training) 오차 대신 표본 외 검증(validation) 성능을 기준으로 점수가 매겨집니다. 또한 본 방법은 부분집합 크기와 다중공선성을 고려하는 사전식 순서화 목적함수(lexicographic objective)를 지원합니다. 저자들은 시장, 거시경제 및 팩터 데이터를 포괄하는 1,072개의 엔지니어링된 특징으로부터 NASDAQ-100 지수의 주간 수익률을 설명하는 동시적 설명 회귀(contemporaneous explanatory regression) 과제에서 이 접근법을 연구합니다. 이는 다중공선성 환경에서의 부분집합 선택의 가치를 별개의 문제인 예측적 전망(forecasting)과 분리합니다. 이 과제에서 제안된 방법은 최적화된 Lasso 기준선(baseline)보다 더 높은 표본 외 설명력을 가진 희소 특징 부분집합을 식별하여, Lasso의 0.6313 대비 0.6961의 표본 외 $R^2$에 도달합니다. 이러한 결과는 몬테카를로 트리 탐색이 금융 회귀의 희소 설명적 특징 선택에서 볼록 정규화(convex regularization)의 실용적인 대안임을 시사하며, 표본 외 적합도만큼 투명성이 중요한 팩터 귀속(factor attribution) 및 위험 분해에 잠재적 가치가 있습니다.
에너지 전환에서의 가치 창출을 위한 전략적 투자 의사결정: 강화학습 기반 접근법
Strategic Investment Decision Making for Value Creation in Energy Transition: A Reinforcement Learning Approach
기후 변화라는 전 지구적 과제는 2015년 파리 협정과 같은 국제적 합의에 따라 CO2 배출량을 감축하기 위한 중대한 조치들을 이끌어냈습니다. 너무 느리게 대응하면 향후 손실과 평판 훼손을 초래할 수 있는 반면, 너무 빠르게 움직이면 기술적 미성숙으로 인한 많은 재생에너지 프로젝트의 한계 수익성이나 잠재적 손실로 인해 주주 가치를 위협할 수 있습니다. 이러한 복잡한 전환 과정을 헤쳐나가기 위해 에너지 기업은 불확실성 속에서 의사결정의 유연성을 통해 가치 창출을 극대화하는 순차적 의사결정(SDM) 전략을 도입해야 합니다. 이를 지원하기 위해 본 연구에서는 2050년까지의 동적인 에너지 환경을 모델링하는 맞춤형 시뮬레이션 환경을 개발했습니다. 이를 기반으로 석유 및 가스, 재생에너지, CO2 감축의 세 가지 부문에 자금을 배분하기 위한 다양한 포트폴리오 관련 의사결정 전략을 탐색하는 다기준 SDM 프레임워크를 설계했습니다. 이는 생산량, 에너지 가격 및 비용의 불확실성을 고려하면서 전환 과정에서 가치를 극대화하는 것을 목표로 합니다. 이 프레임워크는 이익 극대화, CO2 사회적 비용 최소화, 재생에너지 부문에서의 경쟁 우위 확보라는 세 가지 목표를 가집니다. 본 연구는 정의된 SDM 프레임워크 내에서 최적의 투자 정책을 도출하기 위해 강화학습(RL)의 활용 가능성을 평가합니다. 에이전트의 순차적 의사결정은 석유 및 가스 생산량, 재생에너지 발전량, CO2 배출량, 수익과 같은 핵심 변수에 영향을 미침으로써 가상의 동적 환경을 형성합니다. 반복적인 상호작용을 통해 강화학습 알고리즘은 상태 공간을 탐색하고 불확실성 하에서 최적의 정책을 학습합니다. 본 연구는 강화학습 전략을 수동으로 정의된 일련의 기준선 정책들과 비교 평가하였으며, 적응성과 장기적 가치 창출 측면에서 일관되게 우수한 성능을 보임을 확인했습니다.
지수적으로 더 적은 공간으로 계획을 탐색하는 방법 학습
Learning How to Search for Plans with Exponentially Less Space
계획(plan)에 대한 휴리스틱 탐색(heuristic search)은 휴리스틱이 거의 완벽하더라도 지수적으로 많은 상태를 저장할 수 있다. 우리는 대신 탐색 제어(search control)를 학습하는데, 이는 도메인별로 하나씩 작성되는 인덱시컬 정책(indexical policy)으로서, 객체를 담는 레지스터(register)와 규칙을 순서화하는 모드를 갖는 일반화된 정책(generalized policy)이다. 우리는 객체를 레지스터에 적재하고 백트래킹 지점을 표시하는 choose 규칙을 추가하는데, 이 지점에서는 하나의 후보만으로 충분하다. 그 외의 모든 규칙은 가능한 모든 결과에 대해 작동해야 하며 탐색을 필요로 하지 않는다. 우리의 주요 결과는, 무한 실행을 배제하는 구조적 종료성(structural termination)이 객체 수에 대한 다항식으로 모든 실행을 제한한다는 것이다. 그러면 깊이 우선 절차(depth-first procedure)는 상태 공간이 얼마나 크더라도 방문한 상태의 목록 없이 다항식 공간(polynomial space) 안에서 계획을 찾아낸다. 그 대가는 시간이며, 이는 실행 과정에서의 실제 선택 횟수인 선택 깊이(choice depth)에 대해서만 지수적이다. 따라서 이러한 정책이 풀 수 있는 모든 클래스는 NP에 속하며, 선택 깊이가 상수일 때는 P에 속한다. 우리는 종료성을 증명하고 학습 과제를 검증하며 선택 깊이를 작게 유지하는 반례 기반(counterexample-guided) 루프에서 언어 모델로 이러한 정책들을 학습시킨다. 학습된 정책을 사용하여, 이 절차는 IPC 2023 Learning Track과 Autoscale Agile 스위트의 1,890개 테스트 과제 중 1,709개를 풀어내며, 이는 LAMA, BFWS, Levitron보다 더 많고, 그중 대부분을 1초와 100MiB 이내에 해결한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.