일반 볼록 집합에서의 온라인 재고 최적화를 위한 최적의 숨겨진 목표 학습 (Optimal Hidden-Target Learning)

온라인 재고 최적화 (Online Inventory Optimization, OIO)는 물리적 메모리가 있는 온라인 볼록 최적화 (Online Convex Optimization)입니다. 재고 이월 (inventory carryover)로 인해 실행 가능한 행동 집합 (feasible action set)이 과거에 의존하게 됩니다. 확률적 재고 학습 (stochastic inventory learning)과 최근 단일 선형 용량 제약 조건 하의 OIO에서 사용된 자연스러운 원리는, 온라인 학습자 (online learner)가 선택한 숨겨진 목표 (hidden target)를 유지하고 이를 현재 실행 가능한 주문-업-투 (order-up-to) 집합으로 투영 (projection)하여 실행하는 것입니다. 본 논문에서는 이 단순한 원리가 임의의 유계 볼록 용량 집합 (bounded convex capacity sets)에서의 OIO에 대해 최적임을 증명합니다. 온라인 경사 하강법 (Online Gradient Descent, OGD)을 기본 학습기로 사용할 때, 이 방법은 일반 볼록 집합에서의 OIO에 대해 기존에 알려진 최선의 후회 보장 (regret guarantee)을 공통 수요 확률 (common-demand probability)에 대한 역수 (inverse) 의존성에서 역 제곱근 (inverse-square-root) 의존성으로 개선하며, 우리는 이에 부합하는 하한 (lower bound)을 증명합니다. 동일한 원리는 강볼록 손실 (strongly convex losses)에 대해 최초의 다항 로그 (polylogarithmic) 후회 보장을 제공하며, 일반 볼록 용량 집합에서 유클리드 경로 변동 (Euclidean path variation)에 적응하는 최초의 동적 후회 (dynamic regret) 보장을 제공합니다. 분석 과정에서 노름 정렬 원리 (norm alignment principle)를 도입합니다. 즉, 적절한 상태 변수 (state variable)는 투영과 동일한 노름 (norm)으로 측정된 숨겨진 목표로부터 실행 가능한 집합까지의 거리입니다. 노름 정렬 하에서, 이 거리는 목표 이동을 도착 (arrival)으로, 공통 수요를 서비스 (service)로 하는 스칼라 큐 (scalar queue)로서 경로를 따라 진화합니다. 이러한 1차원 큐 제어 (one-dimensional queue control)로의 환원은 상태 의존성 (state dependence)을 해결하고, 기존의 제품별 접근 방식 (productwise approaches)으로는 도달할 수 없었던 일반 볼록 용량 집합으로 보장을 확장합니다. 합성 데이터 및 실제 재고 데이터를 이용한 실험을 통해 이론을 입증합니다.