온라인 재고 최적화를 위한 숨은 목표 학습의 최적성 증명

한줄 요약

온라인 재고 최적화 문제에서 숨은 목표를 유지하고 투영하는 단순한 원리가 일반 볼록 집합에 대해 최적임을 증명했다.

풀어야 하는 문제

온라인 재고 최적화는 물리적 메모리(재고 이월)로 인해 실행 가능한 행동 집합이 과거에 의존하는 온라인 볼록 최적화 문제이다. 기존 연구는 단일 선형 용량 제약 하에서만 최적성을 보였으나, 일반 볼록 용량 집합에 대한 최적 알고리즘과 후회 하한이 알려져 있지 않았다.

접근 방법

온라인 학습자가 선택한 숨은 목표를 유지하고, 이를 현재 실행 가능한 주문-업-투 집합에 투영하는 원리를 사용한다. 기본 학습자로 온라인 경사 하강법을 사용하며, 노름 정렬 원리를 도입하여 숨은 목표에서 실행 가능 집합까지의 거리를 스칼라 큐로 축소한다. 이를 통해 1차원 큐 제어 문제로 변환하여 상태 의존성을 해결한다.

결과·기여

일반 볼록 용량 집합에 대해 후회 보장을 기존 역수 의존성에서 역제곱근 의존성으로 개선하고, 하한 일치를 증명했다. 강볼록 손실에 대해 첫 번째 다대수적 후회 보장을, 일반 볼록 집합에 대해 첫 번째 동적 후회 보장을 제공한다. 합성 및 실제 재고 데이터 실험으로 이론을 뒷받침한다.