Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets

기술 요약: 일반 볼록 집합에서의 온라인 재고 최적화를 위한 최적의 히든 타겟 학습(Hidden-Target Learning)

문제 정의
본 논문은 물리적 재고 제약 조건이 있는 용량 집합 $Y \subseteq \mathbb{R}^n_+$로부터 주문 상한 벡터 $y_t$를 선택하는 온라인 재고 최적화(Online Inventory Optimization, OIO) 문제를 다룹니다. 표준 온라인 볼록 최적화(Online Convex Optimization, OCO)와 달리, OIO는 "물리적 메모리(physical memory)"를 특징으로 합니다. 즉, 시점 $t$에서의 가용 행동 집합 $J_t = Y \cap \{y \mid y \succeq x_t\}$는 현재 재고 상태 $x_t$에 의존합니다. 재고는 이월되므로, 학습자는 단순히 $Y$ 위로 경사 하강법(gradient step)을 투영(projection)할 수 없습니다. 만약 투영된 결과가 현재 재고 수준보다 낮다면 물리적으로 불가능하기 때문입니다. 환경은 적대적인 수요 $d_t$와 손실 함수 $\ell_t$를 선택하며, 학습자는 비교 대상 시퀀스에 대해 동적 또는 정적 후회(regret)를 최소화하는 것을 목표로 합니다.

MaxCOSD (Hihat et al., 2023)와 같은 기존 연구는 적응형 사이클을 사용하여 일반 볼록 용량 집합을 다루었으며, 균등 확률 양의 수요(Uniformly Probably Positive Demand, UPPD) 조건 하에서 $\tilde{O}(\sqrt{T/\mu})$의 정적 후회를 달성했습니다. 그러나 $1/\mu$ (여기서 $\mu$는 공통 수요 충격의 확률)에 대한 이러한 의존도는 차후 개선의 여지가 있었으며, 기존의 히든 타겟(hidden-target) 방식은 제품별 "판매 소진(sell-out)" 분석에 의존해야 했기에 선형 용량 제약에 국한되어 있었습니다.

방법론: 노름 정렬 히든 타겟 투영 (Norm-Aligned Hidden-Target Projection)
저자들은 특정 기하학적 프레임워크를 활용한다면, 히든 타겟 $z_t$를 유지하고 이를 가용 집합 $J_t$로 투영하는 단순한 원칙이 일반 볼록 집합에 대해서도 충분하다는 것을 제안합니다.

1. 알고리즘: 학습자는 기본 온라인 학습 알고리즘(예: 온라인 경사 하강법)에 의해 생성된 히든 타겟 시퀀스 $z_t \in Y$를 유지합니다. 구현된 행동은 $y_t = \text{Proj}_{J_t}^{\|\cdot\|}(z_t)$이며, 이는 특정 노름 $\|\cdot\|$에 의해 측정된 $z_t$의 $J_t$로의 투영입니다.
2. 노름 정렬 원칙 (Norm Alignment Principle): 핵심적인 방법론적 기여는 투영 노름, 큐 상태 측정, 그리고 타겟 이동 메트릭이 모두 동일한 허용 가능한 노름 $\|\cdot\|$을 사용해야 한다는 요구 사항입니다. 허용 가능한 노름은 $\ell_\infty$ 노름을 지배합니다 (즉, $\|x\|_\infty \le \|x\|$).
3. 기하학적 큐 감소 (Geometric Queue Reduction): 분석의 핵심은 "타겟-구현 간극(target-implementation gap)"을 $q_t = \|z_t - y_t\|$로 정의하는 것입니다. 저자들은 다음과 같은 경로적 기하학적 재귀(Lindley 큐)를 증명합니다:
   $$q_{t+1} \le [q_t + \|z_{t+1} - z_t\| - d^{\min}_t]_+$$
   여기서 $d^{\min}_t = \min_i d_{t,i}$는 공통 수요입니다.
   • 해석: 간극은 하나의 1차원 큐처럼 진화합니다. 히든 타겟의 이동($z_{t+1} - z_t$)은 "도착(arrival)" 역할을 하고, 공통 수요($d^{\min}_t$)는 "서비스(service)" 역할을 합니다.
   • 의의: 이 감소는 복잡한 상태 의존적 가용성 문제를 추가적인 스위칭 비용(switching cost)이 있는 표준 OCO 문제로 변환합니다. 이를 통해 이전 연구들이 곡선형 볼록 집합으로의 확장을 가로막았던 제품별 회계 방식이나 선형 제약의 한계를 극복하고 일반화할 수 있습니다.

주요 기여 및 결과

1. 볼록 손실에 대한 최적의 정적 후회:
   기본 학습자로 온라인 경사 하강법(OGD)을 사용할 경우, 본 논문은 $\tilde{O}(\sqrt{T/\mu})$의 정적 후회를 달もの합니다. 이는 일반 볼록 집합에 대한 기존의 최선 성능인 $O(1/\mu)$를 $O(1/\sqrt{\mu})$로 개선한 것입니다. 저자들은 이에 부합하는 하한 $\Omega(\sqrt{T/\mu})$를 증명하여, UPPD 하에서 이 비율이 미니맥스 최적(minimax optimal)임을 입증했습니다.

2. 강볼록 손실에 대한 폴리로그(Polylogarithmic) 후회:
   $\alpha$-강볼록 손실에 대해, 동일한 프레임워크는 $\tilde{O}(\log(T/\mu))$의 후회 경계치를 제공합니다. 이는 일반 용량 집합을 가진 적대적 OIO에서 폴리로그 후회가 가능한지에 대한 열린 질문을 해결합니다.

3. 개선된 동적 후회:
   본 방법은 비교 대상의 유클리드 경로 변화량 $P_{T,2}$에 의존하는 동적 후회 보장을 제공하며, 이는 기존 히든 타겟 분석에서 사용되었던 $\ell_1$ 변화량 $P_{T,1}$과 대조됩니다. 이를 통해 명시적인 $n^{1/4}$ 인자를 제거하고 밀집된 비교 대상 이동에 대한 경계를 정교화했습니다. 저자들은 알려진 변화량에는 표준 OGD를, 알려지지 않은 변화량에는 평활화된 OGD(Smoothed OGD, SOGD)를 사용하여 이러한 결과를 달성했습니다.

4. 미러 디센트(Mirror Descent)를 통한 기하학 민감형 정교화:
   본 프레임워크는 강볼록 정규화 항을 가진 온라인 미러 디센트(OMD)로 확장됩니다. 이를 통해 용량 집합 $Y$의 특정 기하학적 구조와 그래디언트의 듀얼 노름에 적응하는 후회 경계치를 얻을 수 있습니다. 예를 들어, 선형 제약에 엔트로피 정규화를 사용하면 그래디언트가 좌표별로 조밀한 경우 유클리드 투영에 비해 차원 $n$에 대한 의존성을 개선할 수 있습니다.

5. 차원 독립적 보장:
   결과는 표준 OCO 관점에서 차원으로부터 자유롭습니다. 차원 $n$은 명시적인 곱셈 인자(예: $n^{1/4}$)로서가 아니라 문제 파라미터(예: $Y$의 직경 또는 그래디언트 상한)를 통해서만 포함됩니다.

의의 및 주장
본 논문은 "히든 타겟 투영" 원칙이 노름 정렬된 큐(norm-aligned queues)를 통한 기하학적 분석과 결가될 때, 단순한 경험적 휴리스틱이나 선형 제약에 국한된 것이 아니라 일반 볼록 OIO 모델 전체에 대해 이론적으로 최적임을 주장합니다.

• 이론적 통합: 본 연구는 물리적 가용성 제약을 기본 학습 알고리즘으로부터 분리할 수 있음을 보여줌으로써 재고 제어를 표준 OCO와 통합합니다. 재고 레이어는 기본 학습자가 재고 역학을 이해할 필요 없이, 학습에 스위칭 비용을 부과하는 큐 클리어링 메커니즘 역할을 합니다.
• 장애물 해결: 제품별 오차에 대한 보존 항등성(conservation identity)의 부재로 인해 큐잉 분석을 일반 볼록 집합으로 확장하는 데 걸림돌이 되었던 문제들을, 상태를 허용 가능한 노름에서의 단일 기하학적 거리로 측정함으로써 우회할 수 있음을 입증했습니다.
• 실험적 검증: 합성 데이터 및 실제 M5 예측 대회 데이터를 이용한 실험을 통해, 제안된 HT-OGD 알고리즘이 선형 및 곡선형 용량 설정 모두에서 MaxCOSD 및 DDM(제품별 방식)보다 우수한 성능을 보임을 확인하여 이론적 후회 경계의 개선을 검증했습니다.

저자들은 학습(히든 타겟의 학습)과 물리적 가용성 강제(노름 정렬된 큐를 통한 실행)를 분리하는 이 모듈형 템플릿이, 상태 의존적 제약을 가진 미래의 온라인 문제들을 위한 견고한 프레임워크를 제공한다고 결론짓습니다.