arXiv:2511.20413v2 math.OC

BOCO: 의사결정 중심 온라인 학습을 위한 베이지안 온라인 문맥 최적화

BOCO: Bayesian Online Contextual Optimization for Decision-Focused Online Learning

Zhuojun Xie, Adam Abdin, Yiping Fang

제출 2026-09-24

한국어 초록

\emph{의사결정 중심 학습}(decision-focused learning, DFL)은 예측 정확도만이 아니라 하위 의사결정을 최적화하도록 예측 모델을 학습시킨다. 최근 연구들이 이 패러다임을 스트리밍 데이터가 있는 온라인 환경으로 확장했지만, 기존의 온라인 DFL 방법은 일반적으로 점 추정치(point estimate)를 유지하며, 그래디언트 기반 업데이트를 위해 미분 가능한 최적화 층이나 문제별 대리 손실(surrogate loss)이 필요하다. 그 결과 데이터가 제한된 상황에서는 불안정할 수 있고, 이질적인 최적화 문제 전반에 적용하기도 어렵다. 본 논문에서는 모델 매개변수에 대한 의사결정 중심 사후분포(posterior)를 유지하는 프레임워크인 베이지안 온라인 문맥 최적화(Bayesian Online Contextual Optimization, \texttt{BOCO})를 제안한다. \texttt{BOCO}는 의사결정을 처방할 때 그 사후분포로부터 얻은 예측들을 집계함으로써 매개변수의 불확실성을 반영한다. 변화하는 환경에서 이 사후분포를 추적하기 위해, 미분 불가능한 문제를 위한 순차 몬테카를로(sequential Monte Carlo) 샘플러와 미분 가능한 문제를 위한 함수 공간 Stein 변분 경사하강법(function-space Stein variational gradient descent) 알고리즘, 두 가지 입자 기반 추론 알고리즘을 개발한다. 두 가지 실제 과제 모두에서 \texttt{BOCO}는 두 가지 빈도주의(frequentist) 온라인 DFL 기준선 대비 누적 평균 후회(running mean regret)와 시간적 후회 변동성(temporal regret variability)을 줄인다. 전체 구간(full horizon)에서 최고 성능의 빈도주의 기준선과 비교했을 때, BOCO는 누적 평균 후회와 시간적 후회 변동성을 배낭 문제(knapsack)에서 각각 6.9%와 6.3%, 에너지 스케줄링에서 각각 49.3%와 38.1% 감소시킨다. 이러한 이득은 데이터 스트림 초반에 더 크게 나타나며, 이는 데이터가 제한적일 때 매개변수 불확실성을 반영하는 것이 이점이 된다는 점과 부합하는 양상이다.

원문 초록

\emph{Decision-focused learning} (DFL) trains predictive models to optimize downstream decisions rather than prediction accuracy alone. While recent studies have extended this paradigm to online settings with streaming data, existing online DFL methods generally maintain a point estimate, while their gradient-based updates require either a differentiable optimization layer or a problem-specific surrogate loss. Consequently, they can be unstable under limited data and difficult to apply across heterogeneous optimization problems. We introduce Bayesian Online Contextual Optimization (\texttt{BOCO}), a framework that maintains a decision-focused posterior over model parameters. \texttt{BOCO} aggregates the resulting predictions when prescribing decisions, thereby accounting for parameter uncertainty. To track this posterior in evolving environments, we develop two particle-based inference algorithms: a sequential Monte Carlo sampler for nondifferentiable problems and a function-space Stein variational gradient descent algorithm for differentiable problems. Across both real-world tasks, \texttt{BOCO} reduces running mean regret and temporal regret variability relative to two frequentist online DFL baselines. At the full horizon, relative to the best frequentist baseline, BOCO reduces running mean regret and temporal regret variability by 6.9\% and 6.3\% on knapsack and by 49.3\% and 38.1\% on energy scheduling, respectively. The gains are larger early in the data stream, a pattern consistent with a benefit from accounting for parameter uncertainty when data are limited.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2511.20413v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2610.03312v1cs.AI공통 태그 Scheduling, Sequential Decision Making, Combinatorial Optimization

동적 환경에서의 최적 계획 수립

Optimal Planning in a Dynamic World

배경: 본 논문에서는 실행 가능한 상태나 행동의 집합이 시간에 따라 변하는 환경에서의 계획 수립(planning) 문제를 다룹니다. 예를 들어, 이동하는 장애물 사이에서의 경로 계획 문제(흔히 SIPP로 알려짐)에서는 장애물이 이동함에 따라 특정 위치에 머무를 수 있는 가능 여부가 달라질 수 있습니다. 또는 특정 기차에 탑승하는 행동은 기차가 역에 정차해 있는 동안에만 실행 가능합니다. 이러한 동적 특성으로 인해 최적 계획과 그 수행 시간은 실행이 언제 시작되는지에 따라 달라질 수 있습니다. 실제 환경에서는 계획 수립이 완료되거나 다른 에이전트(agent)의 승인이 날 때까지 실행 시작 시간을 알 수 없는 경우가 많습니다. 그러나 기존의 계획 수립 연구 대부분은 이러한 동적 특성을 무시하거나 시작 시간이 사전에 알려져 있다고 가정합니다. 이는 상태와 행동의 실행 가능성을 평가하기는 수월하게 만들지만, 일부 응용 분야에서는 비현실적입니다. 목표: 본 논문에서는 시작 시간이 알려져 있다는 가정을 완화합니다. 임의 시작 시간 계획 수립(any-start-time planning) 설정을 정의하고 이를 위한 알고리즘을 제시합니다. 방법: 시작 시간의 함수로서 최적 계획을 간결하게 인코딩하는 복합 도착 시간 함수(compound arrival time function, cATF)라는 자료구조를 제안합니다. 또한 스칼라 비용 대신 간선을 따라 함수를 전파하여 cATF를 구성하는, 휴리스틱 그래프 탐색 기반의 범용 계획 수립 알고리즘을 제공합니다. 결과: cATF의 크기가 문제 크기에 대해 최대 선형임을 증명합니다. SIPP의 특정 문제에 대한 구현체를 바탕으로 한 실험적 평가에 따르면, 어려운 문제에서 재계획(replanning)에 의존하는 에이전트는 실패하는 경우가 빈번한 반면, cATF를 사용하는 임의 시작 시간 알고리즘은 실행 시작 시간이 확정되면 최적 계획을 신속하게 조회할 수 있음을 보여줍니다. 결론: 시간 의존적 계획에 대한 효율적인 표현과 추론을 가능하게 함으로써, 본 연구는 동적 환경에서의 계획 수립을 위한 토대를 제공합니다.

arXiv:2609.26978v1stat.ML공통 태그 Stochastic Optimization, Sequential Decision Making, Combinatorial Optimization

다중 스케일 행렬 가중치를 통한 온라인 역 선형 최적화의 정밀 후회 상한

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를 달성할 수 있는지는 열려 있다.

arXiv:2609.28263v1cs.LG공통 태그 Stochastic Optimization, Sequential Decision Making, Combinatorial Optimization

재해결 없이 온라인 선형 계획을 위한 자원 적응형 확률적 경사하강법

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에서 높은 할당 품질을 계산 효율적으로 달성하는 접근임을 보여준다.

arXiv:2607.23316v2cs.NE공통 태그 Scheduling, Combinatorial Optimization

학생 학습 자원 배분을 위한 유전 알고리즘

A genetic algorithm for student academic resource allocation

개별 학생에게 학습 자원을 최적으로 배분하는 것은 학습자 다양성을 다루고 공평한 교육 성과를 촉진하는 데 필수적이다. Erasmus+ KA220-SCH 프로젝트의 틀 안에서, 본 논문은 고등학교 수학 학생을 위한 교육 자료 선택을 엄격한 학습 시간 제약을 따르는 0-1 이진 조합 최적화(optimization) 문제로 모델링한다. 이 공식화의 NP-hard 복잡도를 고려할 때, 자원 카탈로그가 확대될수록 정확한 해법은 계산적으로 다루기 어려워진다. 이 과제를 해결하기 위해, 우리는 이진 결정 공간을 효과적으로 탐색하기 위해 특화된 제약 복구 메커니즘과 통합된 유전 알고리즘(Genetic Algorithm)을 제안한다. 10회의 독립 실행에 걸친 실험적 평가는 빠른 수렴, 높은 해 품질, 그리고 서로 다른 기본 시드에 걸친 강한 알고리즘적 안정성을 보여준다. 이 결과는 중등 교육에서 실시간 의사결정 지원 시스템을 위한 메타휴리스틱(metaheuristic) 접근법의 실용적 유용성을 확인한다.

arXiv:2610.13571v1cs.LG공통 태그 Scheduling, Sequential Decision Making

TCP 확인응답을 위한 동시 경쟁비 및 리그렛 보장

Simultaneous Competitive and Regret Guarantees for TCP Acknowledgment

본 연구는 TCP 확인응답(acknowledgment)에 대한 동시 경쟁비(competitive ratio) 및 리그렛(regret) 보장을 다룬다. 각 확인응답은 대기 중인 모든 패킷을 처리하며, 목표는 총 확인응답 비용과 대기 비용의 합을 최소화하는 것이다. 결정론적(deterministic) 온라인 알고리즘으로는 경쟁비 $2$보다 더 나은 성능을 달성할 수 없다는 것이 잘 알려져 있다. $k$개의 무작위화된(randomized) 온라인 전문가(expert)와 $0<\varepsilon<1$가 주어졌을 때, 우리는 실현된 총 비용이 오프라인 최적 비용 $\mathrm{OPT}$의 $(2+\varepsilon)$배를 항상 넘지 않으며, 실현 비용이 가장 작은 전문가에 대한 기대 리그렛이 $O(\sqrt{\mathrm{OPT}\log(k+1)}+\log(1/\varepsilon))$인 무작위화된 온라인 알고리즘을 구성한다. 이 알고리즘은 패킷 수나 $\mathrm{OPT}$에 대한 사전 지식을 요구하지 않는다. 우리의 알고리즘은 전문가 간 전환 비용(switching cost)을 제어하며, 허용된 경쟁비 한계와 현재 비용 사이의 격차를 이용하여 언제 학습할지를 결정한다. 또한 우리는 $k\ge 2$일 때 이 리그렛 한계가 $\mathrm{OPT}$, $k$, $\varepsilon$에 대해 점근적으로(asymptotically) 최적임을, 그리고 하위선형(sublinear) 리그렛을 위해서는 $\varepsilon>0$이 필요함을 보이는 하한(lower bound)을 증명한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.