부분 피드백 환경에서의 맥락적 선형 최적화를 위한 결정 중심 온-정책 학습
Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback
한국어 초록
결정 중심 학습(Decision-focused learning, DFL)은 단독 예측 정확도가 아니라 하위(downstream) 의사결정 품질을 최적화하여 예측 모델을 학습시키는 방법이다. 맥락적 선형 최적화(contextual linear optimization)의 경우, 기존 DFL 방법 대부분은 오프라인 데이터와 목적 비용 벡터(cost vector)에 대한 완전한 관측을 가정한다. 본 연구에서는 표준 밴딧(bandit) 피드백 설정을 일반화하여, 부분 피드백 하에서의 순차적 맥락적 선형 최적화를 위한 온-정책(on-policy) 학습 방법을 개발한다. 이 방법은 조건부 분포에서 비용 벡터 예측을 샘플링하고 그 결과로 생성된 하위 선형 최적화 문제를 해결하는 확률적 예측 후 최적화(predict-then-optimize) 정책을 학습한다. 이 분포 모델을 업데이트하기 위해, 두 가지 구성 요소로 이루어진 하이브리드 그래디언트(gradient) 추정기를 도입한다. 첫 번째 구성 요소는 점수 함수(score function) 추정기로, 불편(unbiased)이지만 분산이 클 수 있는 정책 그래디언트(policy gradient) 추정값을 제공한다. 두 번째 구성 요소는 결정 중심 플러그인(plug-in) 구성요소로, 잠재 비용 벡터에 대한 보조적인 nuisance 추정값을 이용해 하위 최적화 구조를 활용하며, 이 추정값이 개선될수록 더 많은 정보를 제공하게 된다. 평균 제곱 정책 그래디언트 노름(norm)에 대해 O(T^-1/2) 경계를 증명하며, 이는 표준 비convex SGD의 수렴 속도와 일치한다. top-k 선택, 최단 경로, 조합 가격결정(combinatorial pricing), 그리고 실제 데이터 기반 에너지 스케줄링 벤치마크에서의 실험 결과, 밴딧 피드백 하에서 이 하이브리드 그래디언트 접근법은 네 가지 벤치마크 모두에서 맥락적 밴딧(contextual bandit) 베이스라인보다, 그리고 세 가지 벤치마크에서 선형 톰슨 샘플링(linear Thompson sampling)보다 더 낮은 평균 누적 후회(regret)를 달성하며, 더 풍부한 조건부 생성 비용 모델(conditional generative cost model)에서도 작동함을 보인다. 코드는 https://github.com/Joeyetinghan/on-policy-bandit-dfl 에서 확인할 수 있다.
원문 초록
Decision-focused learning (DFL) trains predictive models by optimizing downstream decision quality rather than standalone prediction accuracy. For contextual linear optimization, most existing DFL methods assume offline data and full observations of the objective cost vector. We develop an on-policy learning method for sequential contextual linear optimization under partial feedback, generalizing the standard bandit feedback setting. Our method learns a stochastic predict-then-optimize policy that samples a cost-vector prediction from a conditional distribution and solves the resulting downstream linear optimization problem. To update this distributional model, we introduce a two-component hybrid gradient estimator. The first component is a score function estimator, which provides an unbiased but potentially high-variance policy gradient estimate. The second is a decision-focused plug-in component that uses an auxiliary nuisance estimate of the latent cost vector to exploit the downstream optimization structure, becoming more informative as the estimate improves. We prove an O(T^-1/2) bound on the average squared policy-gradient norm, matching the standard non-convex SGD rate. Experiments on top-k selection, shortest path, combinatorial pricing, and a real-data energy-scheduling benchmark show that, under bandit feedback, the hybrid gradient approach achieves lower mean cumulative regret than the contextual-bandit baselines on all four benchmarks and than linear Thompson sampling on three, and that it also works with richer conditional generative cost models. Code is available at https://github.com/Joeyetinghan/on-policy-bandit-dfl.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
복잡계 알고리즘 설계를 위한 환경으로서의 네트워크 월드 모델
Network World Models as Environments for Algorithm Design on Complex Systems
환경(environment)을 시뮬레이션하고 행동에 따라 환경이 어떻게 변화하는지 예측하는 월드 모델(world model)은 로보틱스와 같은 현실 세계 응용 분야에서 점점 더 많이 활용되고 있습니다. 복잡계 또한 행동의 효과가 즉각적으로 나타나지 않기 때문에 동일한 도구를 필요로 합니다. 캠페인을 위해 시드 노드를 설정하거나 전염병에 대비해 노드를 면역화하는 것은 그 자체만으로는 거의 변화를 일으키지 않으며, 중요한 것은 이후 단계들에 걸쳐 펼쳐지는 결과입니다. 특정 태스크에서 기대 성능을 극대화하도록 이러한 행동을 선택하는 알고리즘을 설계하는 것은 본질적으로 반복적인 과정이며, 모든 후보 알고리즘은 자신이 도출하는 결과에 따라 점수가 매겨져야 합니다. 이러한 결과를 얻는 작업은 시뮬레이션에 의존해 왔으나, 다수의 샘플링된 궤적(trajectory)에 걸쳐 후보들을 평가할 때 그 비용이 병목 현상을 유발합니다. 본 논문에서는 시간에 따른 개입 하에서 네트워크의 확산 역학을 학습하고, 각 행동을 네트워크에 적용하며, 그에 따른 결과를 예측하는 행동 조건부 네트워크 월드 모델을 제안합니다. 이 모델은 코딩 에이전트(agent)가 전체 롤아웃(rollout) 피드백, 행동 수준의 기여도(credit), 대안적 개입에 대한 반사실적 탐침(counterfactual probe)을 활용하여 실행 가능한 알고리즘을 설계하고 개선하는 알고리즘 설계 루프 내에서 고속 평가기 역할을 수행합니다. 8개의 네트워크 태스크와 5개의 확산 모델에 걸쳐, 설계된 알고리즘은 141개 설정 중 138개에서 보고된 가장 강력한 기준선(baseline)과 대등하거나 이를 능가하는 동시에 몬테카를로(Monte Carlo) 시뮬레이션 대비 최대 14.5배 빠른 롤아웃을 가능하게 합니다. 코드는 논문 채택 시 공개될 예정입니다.
다중 스케일 행렬 가중치를 통한 온라인 역 선형 최적화의 정밀 후회 상한
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를 달성할 수 있는지는 열려 있다.
재해결 없이 온라인 선형 계획을 위한 자원 적응형 확률적 경사하강법
Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving
대규모 언어 모델(LLM) 추론과 검색 서비스의 확대는 온라인 선형 계획 문제의 규모를 키우며, 계산적으로 효율적인 알고리즘을 요구한다. 본 연구는 확률적 온라인 선형 계획을 위한 자원 적응형 확률적 경사하강법(RASGD)을 제안한다. 이 알고리즘은 요청 하나와 현재 재고(inventory)만으로 자원 가격을 갱신하며, 자원 m개에 대해 도착(arrival)마다 O(m) 연산과 메모리만 필요하고 LP나 표본 평균 최적화(sample-average optimization)는 사용하지 않는다. 핵심은 재해결(re-solving)에서 쓰이는 현재 자원 가격 책정 로직을 1차 SGD 갱신으로 표현하는 것이다. 각 도착마다 이중 목적(dual objective)의 잔여 재고 허용량(allowance)을 갱신하고, 스텝 크기(stepsize)는 초기에는 학습을 위해 작아지다가 이후에는 재고 조정 속도에 맞추어 커진다. 표준 비퇴화(non-degeneracy) 조건 하에서 알고리즘은 모든 표본 경로(sample path)에서 실행 가능(feasible)하며, 실현된 분수적 후견 최적(realized fractional hindsight optimum) 대비 O(\log T) 기대 후회(expected regret)를 달성한다. 이는 분포를 알고 계산 제약이 없는 정책에 대한 하한과 일치한다. 분석은 변화하는 자원 수준에서 최적 가격을 추적하지 않고, 고정 참조 가격 주변의 곡률(curvature)을 재고 안정성(inventory stability)으로 전환한다. 수치 실험에서 RASGD는 도착마다 LP 재해결과 견줄 만한 후회를 달성하고, 시험한 1차 기준선(first-order baselines)보다 나으면서 1차 방법의 계산 효율은 유지한다. 이 결과는 RASGD가 대규모 OLP에서 높은 할당 품질을 계산 효율적으로 달성하는 접근임을 보여준다.
You Can Trade Your Experience in Distributed Multi-Agent Multi-Armed Bandits
시뮬레이션은 코드가 담당하고, 평가는 Jev가 담당한다
Code Owns the Simulation, Jev Owns the Evaluation
Jev와 같은 판단 모델(judgment model)은 단 한 번의 호출로 추론 텍스트 없이 설명된 각 선택지에 대한 확률을 반환합니다. 이러한 특징 덕분에 에이전트의 행동 선택 층(layer)으로서 매력적이지만, 어떤 결정을 신뢰할 수 있는지는 명확하지 않습니다. 본 연구에서는 인지 반사 테스트, 일회성 행렬 게임, 텍스트 게임 ALFWorld 및 로봇 제어에서 Jev를 테스트하고 뚜렷한 경계를 발견했습니다. Jev는 입력에 설명된 내용으로부터 올바른 선택지를 판단할 수 있을 때 성공하며, 이를 본 연구에서는 평가(evaluation)라고 부릅니다. 구체적으로, Jev는 직관에 반하는 인지 반사 테스트(Cognitive Reflection Test) 문제의 99%를 해결합니다. 그러나 올바른 선택지가 상대방의 행동이나 먼저 달성해야 하는 하위 목표와 같이 시뮬레이션(simulation, 즉 입력에 없는 내용을 예측하는 것)에 의존할 때는 실패합니다. 게임에서 Jev는 상대방의 행동이 주어지지 않기 때문에 합리적인 상대가 무작위로 행동하는 것처럼 차선으로 플레이합니다. ALFWorld에서 Jev는 작업 설명에 언급된 사물이나 장소를 지칭하는 명령을 선호합니다. 예를 들어, "서랍에 깨끗한 칼을 넣어라"라는 작업이 주어지면, Jev는 싱크대에서 칼을 먼저 씻는 대신 씻지 않은 칼을 서랍으로 곧장 가져갑니다. 놀랍게도 이러한 실패 중 다수는 지식의 부족 때문이 아닙니다. 상대가 무엇을 할지 별도로 질문을 받으면 Jev는 대개 정확하게 답하며, 상대의 행동이 주어지면 적절하게 대응합니다. Jev가 실패하는 것은 단 한 번의 호출로 시뮬레이션을 수행하고 이에 기반한 평가까지 동시에 처리해야 할 때입니다. 이는 예측이나 시뮬레이션을 코드가 수행하도록 할 것을 시사합니다. ALFWorld의 미리보기(lookahead)나 로봇 제어의 물리 시뮬레이션과 같이 코드가 이를 제공하면, Jev는 일반적인 평가 능력을 통해 전문가 수준의 제어기가 됩니다.
StoreBench: 자율 운영자 에이전트의 평가 및 학습을 위한 라이브 커머스 환경
StoreBench: A Live-Commerce Environment for Evaluating and Training Autonomous Operator Agents
강화학습(RL) 환경은 이제 사후 학습(post-training)에서 대규모 언어 모델(LLM)의 역량을 향상시키는 주요 수단이 되었으나, 대부분의 에이전트 벤치마크는 여전히 정적입니다. 즉, 에이전트가 행동할 때만 환경이 변화하고, 보상은 최종적인 판정으로 주어지며, 통과 기준은 자의적으로 설정됩니다. 본 논문에서는 에이전트가 프로덕션 수준의 상거래 백엔드에서 중간 규모의 온라인 의류 매장을 운영하며 불확실성 속에서 장기 계획 수립 및 경제적 판단력을 시험받는 라이브 커머스 환경인 StoreBench를 소개합니다. 고객은 24시간 내내 주문하고, 공급업체는 가격을 재책정하거나 공급에 실패하며, 시장 충격은 부분적인 예고만 있거나 예고 없이 발생합니다. 에이전트는 실제 인간 운영자가 사용하는 것과 동일한 29개의 판매자 도구를 통해 행동하며, 취해진 행동의 함수로 시뮬레이션 시간을 계산하는 윈도우 기반 운영 예산 하에서 작동하므로 모델 지연 시간이 시뮬레이션 시간에 영향을 미칠 수 없습니다. 통과 임계값은 스크립트 기반 앵커 정책을 기준으로 보정되었고, 보상은 다양한 보상 해킹 목록에 대비해 강화되었으며, 일련의 행동이 주어지면 모든 에피소드가 동일하게 재현됩니다. 본 연구에서는 추론 노력을 일치시킨 상태에서 세 가지 월드 시드에 걸쳐 30~45일 및 시뮬레이션된 1년 전체에 해당하는 11개 시나리오를 바탕으로 7개의 프론티어 LLM을 평가합니다. 평균적으로 스크립트 기반 스마트 트리아지(smart-triage) 정책에 필적하는 모델은 없었습니다. 최고 성능을 보인 DeepSeek-V4-Pro는 휴리스틱의 97% 대비 49%의 태스크-시드 셀을 통과했습니다. 동일한 도구와 예산을 사용하여 작업한 인간 전문가는 모든 모델보다 높은 점수를 기록했습니다(평균 종합 점수 0.708 대 0.700). Claude Code 하네스 기반의 시뮬레이션된 1년 전체에 걸쳐 대다수 모델은 극적인 성능 향상을 보입니다. GRPO 사후 학습 실행에서 서로 다른 5개의 태스크로만 학습된 Qwen3.5-27B는 홀드아웃(held-out) 평가 태스크에서의 평균 종합 점수를 0.136에서 0.373으로 향상시켰습니다. 본 연구에서는 학습 분할용 예시 태스크 5개, 샘플 궤적 10개, 점수 측정 및 검증 툴링을 공개하며, 벤치마크 오염을 방지하기 위해 전체 환경과 평가 스위트는 비공개로 유지합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.