arXiv:2604.00241v2 cs.LG

분산 최소화 및 위험 회피 다중 팔 밴딧을 위한 소프트맥스 그래디언트 정책

Softmax gradient policy for variance minimization and risk-averse multi armed bandits

Gabriel Turinici

제출 2026-09-24

한국어 초록

다중 팔 밴딧(MAB) 문제를 위한 알고리즘은 순차적 의사결정에서 핵심적인 역할을 하며, 이론적으로와 수치적으로 광범위하게 연구되어 왔다. 대부분의 고전적 접근법은 기대 보상이 가장 높은 팔을 식별하는 것을 목표로 하는 반면, 우리는 분산이 가장 낮은 팔을 선택하는 것을 목표로 하는 위험 인식(risk-aware) 설정에 초점을 맞춘다. 이는 잠재적으로 높지만 불확실한 수익보다 안정성을 선호한다. 의사결정 과정을 모델링하기 위해 정책의 소프트맥스 매개변화를 고려하고, 최소 분산(또는 최소 위험) 팔을 선택하기 위한 새로운 알고리즘을 제안하며 자연스러운 조건 하에서 그 수렴을 증명한다. 이 알고리즘은 선택된 팔의 분포에서 두 번의 독립적인 추출을 사용하여 목적 함수의 불편 추정량을 구성한다. 우리는 이러한 알고리즘의 실용적 거동을 보여주는 수치 실험을 제공하고 구현 선택에 대한 안내를 제시한다. 이 설정은 또한 평균 보상을 최대화하는 것과 그 분산을 최소화하는 것 사이에 상충 관계가 있는 일반적인 위험 인식 문제도 포괄한다.

원문 초록

Algorithms for the Multi-Armed Bandit (MAB) problem play a central role in sequential decision-making and have been extensively explored both theoretically and numerically. While most classical approaches aim to identify the arm with the highest expected reward, we focus on a risk-aware setting where the goal is to select the arm with the lowest variance, favoring stability over potentially high but uncertain returns. To model the decision process, we consider a softmax parameterization of the policy; we propose a new algorithm to select the minimal variance (or minimal risk) arm and prove its convergence under natural conditions. The algorithm constructs an unbiased estimate of the objective by using two independent draws from the selected arm's distribution. We provide numerical experiments that illustrate the practical behavior of these algorithms and offer guidance on implementation choices. The setting also covers general risk-aware problems where there is a trade-off between maximizing the average reward and minimizing its variance.

제출 이력

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

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

함께 살펴볼 논문

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

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

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

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

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

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.22201v2eess.SY공통 태그 Stochastic Optimization, Sequential Decision Making

KL 발산을 통한 궤적 정규화 확률적 최적 제어

Trajectory-Regularized Stochastic Optimal Control via KL Divergence

우리는 표준 확률적 최적 제어(SOC)에 제어된 궤적 분포와 기준 궤적 분포 사이의 쿨백-라이블러(KL) 발산을 증강한 궤적 정규화 확률적 최적 제어(TRSOC)를 소개한다. 기르사노프 정리를 활용하면 궤적 KL은 2차 드리프트 불일치 페널티로 단순화되어 동적 계획법(DP) 구조를 보존하는 수정된 실행 비용을 산출한다. 우리는 이에 대응하는 해밀턴-야코비-벨만(HJB) 방정식을 유도하고 최적 정책을 특성화한다. 선형-2차(LQ) 설정에서 이 정식화는 증강된 제어 비용을 갖는 닫힌 형태의 해를 허용한다. 실험을 통해 정규화 매개변수가 성능 중심 행동과 기준 보존 행동 간의 절충(trade-off)을 유도함을 보이며, 여기에는 오프라인 데이터로부터 학습된 기준 동역학을 사용하는 경우가 포함된다.

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

Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes

자연 정책 그래디언트(NPG)는 신뢰 영역 정책 최적화(Trust Region Policy Optimization) 및 근위 정책 최적화(Proximal Policy Optimization)와 같이 널리 사용되는 방법의 기반이 되는, 잘 정립된 강화학습 알고리즘이며, 이들 방법 모두 강력한 실증적 성공을 보여주었다. 본 논문에서는 동역학이 알려져 있고 수평선 의존적 전이 커널(horizon-dependent transition kernels)을 갖는 유한 수평선 마르코프 결정 과정(Markov Decision Processes)에서 정확한 NPG를 연구한다. 이 설정에서 해당 알고리즘에 대한 최초의 유한 시간 수렴 보장을 제공하며, 상수 및 증가하는 학습률(step size) 체제를 모두 고려한다. 상수 학습률 $η_t=η$에 대해, NPG가 $t$회 반복 후 $\mathcal{O}(H^{2}/t)$의 속도로 아선형(sublinear) 수렴함을 증명한다. 여기서 $H$는 수평선 길이이다. 또한 이 상수 학습률 분석을 전체 지지(full support) 투영 분포 하의 정확한 모집단 투영 오라클(population-projection oracle)에서의 선형 MDP로 확장하여, 테이블(tabular) 설정과 동일한 아선형 속도를 재현한다. 더 나아가 증가하는 학습률에 대해서는, 이 알고리즘이 문제 의존 상수 $\vartheta_ρ> 1$에 대해 $\mathcal{O}\left(\left(1-\frac{1}{\vartheta_ρ}\right)^t\right)$의 선형 수렴 속도를 달성함을 증명하며, $η_0>0$ 및 $H \geq 2$인 형태 $η_t=η_0(H/(H-1))^t$의 수평선만 의존하는(horizon-only) 강건 스케줄(robust schedule)이 동일한 기하(geometric) 속도를 달성한다.

arXiv:2607.19357v1cs.AI공통 태그 Stochastic Optimization, Sequential Decision Making

다목적 생성형 추천 시스템을 위한 확률적 프림-듀얼 디코딩

Stochastic Primal-Dual Decoding for Multiobjective Generative Recommender Systems

최근 추천 시스템(RS)의 발전은 생성 모델링을 통해 상당한 성능 향상을 보여주었다. 실무에서 추천은 종종 슬레이트 — 항목의 순서 있는 목록 — 구성을 포함하며, 이는 관련성을 넘어 항목 속성에 정의된 제약이나 공정성 제약과 같은 다중 목표를 만족해야 한다. 기존 다목적 접근법은 생성형이 아닌 설정을 위해 설계된 후처리 기법에 의존하거나, 보조 목표를 모델 학습에 직접 통합한다. 전자는 생성형 RS의 순차적 특성을 명시적으로 고려하지 않으며, 후자는 대규모 시스템에서 종종 비현실적이다. 우리는 기본 모델을 수정하거나 재학습하지 않고도 다목적 슬레이트 생성을 지원하도록 자회귀(autoregressive) 생성형 RS를 보강하는 경량의 추론 시점 디코딩 층을 제안한다. 디코딩을 온라인 제약 최적화(optimization) 문제로 공식화하며, 항목이 순차적으로 선택되고, 관련성과 보조 목표 간 트레이드오프가 잔여 제약 여유(constraint slack), 즉 각 목표를 얼마나 더 만족해야 하는지에 따라 동적으로 조정된다. 이는 생성 과정에서 관련성과 보조 목표의 균형을 맞추는 확률적 프림-듀얼 근사 기법을 통해 구현된다. 우리는 제약 위반과 후회(regret)에 대한 이론적 보장을 제공하고, 광범위한 오프라인 실험과 실제 추천 시스템에서의 대규모 온라인 A/B 실험을 통해 제안 방법을 평가한다. 결과는 다목적 트레이드오프에서 일관된 개선을 보여주며, 사용자 만족도 손실 없이 보조 목표에서 +1.8%의 향상을 달성한다.

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

데이터 기반 블록 교체 스케줄링

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) 교체 사이의 구조적 비용 격차를 밝힌다.

토론

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