Prescribe-then-Select: Adaptive Policy Selection for Contextual Stochastic Optimization

기술적 요약: 처방 후 선택 (Prescribe-then-Select, PS)

문제 설정
본 논문은 결정자가 행동을 선택하기 전에 공변량 (맥락) $X$를 관측한 후, 실현 가능한 집합 $Z$에서 행동 $z$를 선택하여 기대 비용 $E[c(z, Y) | X=x]$를 최소화하는 맥락형 확률적 최적화 (Contextual Stochastic Optimization, CSO) 문제를 다룹니다. 여기서 $Y$는 불확실한 확률 변수입니다. 본 연구에서 다루는 설정의 핵심 제약 조건은 모든 맥락 실현에 대해 결정이 **강제 실현 가능성 제약 (hard feasibility constraints, 정수성 제약 등을 포함할 수 있음)**을 만족해야 한다는 점입니다.

저자들은 중요한 과제를 식별했습니다: 많은 CSO 설정에서 단일 후보 정책이 전체 공변량 공간에 걸쳐 균일하게 우월하지 않습니다. 서로 다른 모델링 패러다임 (예: 점 예측 대 분포 추정) 은 종종 이질적인 성능을 보이며, 특정 영역 (예: 저분산 영역 대 고분산 영역) 에서는 탁월한 성능을 발휘하지만 다른 영역에서는 성능이 저하됩니다. 기존 정책 선택 방법들은 제약이 있는 설정에서 실패하는 경우가 많은데, 그 이유는 실현 가능한 정책들을 평균화한다고 해서 반드시 실현 가능한 결과가 보장되지 않기 때문이며, 엔드 투 엔드 (end-to-end) 학습 접근법은 계산적 부담과 느린 후회 (regret) 수렴을 겪을 수 있기 때문입니다.

방법론: 처방 후 선택 (Prescribe-then-Select, PS)
저자들은 실현 가능성 제약을 위반하지 않으면서 주어진 맥락에 대해 최상의 정책을 적응적으로 선택하도록 설계된 모듈식 2 단계 프레임워크인 **처방 후 선택 (Prescribe-then-Select, PS)**을 제안합니다.

1. 처방 (라이브러리 구축):
   첫 번째 단계는 서로 다른 모델링 가정 하에서 공변량을 실현 가능한 결정으로 매핑하는 다양한 후보 정책 라이브러리 $\Pi_M = \{\pi_1, \dots, \pi_M\}$를 구축합니다. 본 논문은 세 가지 방법 군을 활용합니다:

   • 표본 평균 근사 (Sample Average Approximation, SAA): 공변량을 무시하고 과거 시나리오에 대한 결정적 최적화를 수행합니다.
   • 점 예측 정책 (Point-Prediction Policies, PPt): $E[Y|X]$를 추정하기 위해 예측 모델 (예: kNN, 랜덤 포레스트, 신경망) 을 적합시키고, 이 점 추정치를 사용하여 결정적 최적화를 수행합니다.
   • 예측 - 처방 정책 (Predictive-Prescriptive Policies, PP): 예측 모델 (예: kNN, 랜덤 포레스트) 을 사용하여 가중치 표본 평균 근사를 위한 가중치를 생성함으로써 조건부 분포 $f_{Y|X}$를 효과적으로 근사합니다.

2. 선택 (메타 정책 학습):
   두 번째 단계는 특정 관측 공변량 $x$에 대해 최적의 후보 정책을 선택하는 메타 정책을 학습합니다.

   • 메커니즘: 메타 정책은 **최적 정책 트리 (Optimal Policy Trees, OPT)**의 앙상블로 구현됩니다. 매개변수적 결정 규칙과 달리, OPT 는 공변량 공간을 축 정렬 영역으로 분할하고 각 영역에 특정 정책 인덱스를 할당합니다.
   • 학습: OPT 는 K-폴드 교차 검증을 통해 학습됩니다. 각 폴드에서 후보 정책들은 학습 분할로 훈련되고, 홀드아웃 (held-out) 폴드에서의 표본 외 비용이 계산되어 "비용 테이블"이 생성됩니다. 그런 다음 OPT 는 이 테이블에 기반한 경험적 비용을 최소화하도록 훈련되어, 공변량 공간의 어느 영역에서 어떤 정책이 최적으로 작동하는지 학습합니다.
   • 추론: 추론 시, 폴드와 무작위 시드 전반에 걸쳐 훈련된 트리 앙상블이 투표하여 최종 정책 인덱스를 선택한 후, 이를 적용하여 결정을 생성합니다.

주요 기여

1. 공식화: 표준 앙상블 평균화가 종종 실현 불가능한 강제 실현 가능성 제약 하의 CSO 에서 정책 선택 문제를 공식적으로 정의했습니다.
2. 프레임워크: 정책 생성과 정책 선택을 분리하는 처방 후 선택 프레임워크를 도입했습니다. 이를 통해 최종 결정이 실현 가능성을 유지하면서도 다양하고 잠재적으로 양립할 수 없는 모델링 패러다임을 통합할 수 있습니다.
3. 데이터 기반 선택: 이 접근법은 완전히 데이터 기반이며, 교차 검증된 비용 테이블을 사용하여 공변량 공간을 분할하고 각 영역에 가장 효과적인 정책을 할당하는 메타 정책 (최적 정책 트리) 을 학습합니다.

실험 결과
저자들은 다중 제품 뉴스보이 (multi-product newsvendor) 문제와 2 단계 선적 계획 (two-stage shipment planning) 문제라는 두 가지 벤치마크 문제에서 PS 를 평가했습니다. 두 작업 모두 이질성을 유발하기 위해 명백한 수요 세그먼트 (예: 휴일 급증, 계절적 추세) 를 가진 합성 데이터를 활용했습니다.

• 이질성: 실험은 단일 정책이 균일하게 우월하지 않음을 확인했습니다. 성능은 세그먼트와 학습 크기에 따라 크게 변합니다 (예: 점 예측 방법은 저분산 세그먼트에서 탁월한 성능을 발휘하는 반면, 예측 - 처방 방법은 고분산 또는 불연속 영역에서 우세합니다).
• 성능 향상: 이질적인 영역에서 PS 는 항상 최상의 단일 후보 정책보다 일관되게 우수한 성과를 냅니다. 이러한 향상은 통계적으로 유의미하며, 특히 학습 데이터가 제한적이거나 공변량 공간에 서로 다른 정책이 최적인 명확한 영역이 존재할 때 두드러집니다.
• 수렴: 단일 정책이 균일하게 우세한 영역 (또는 학습 크기 $N$이 매우 커져 한 정책이 명확하게 우월해짐) 에서 PS 는 그 우세한 정책으로 수렴하며, 최상의 단일 정책에 비해 무시할 수 있는 수준의 후회를 초래합니다.
• 계산 효율성: 메타 정책 학습의 오버헤드는 후보 정책에 대한 근본적인 최적화 문제를 해결하는 비용에 비해 미미합니다.

의의 및 주장
본 논문은 PS 가 여러 고품질 처방 모델이 가능한 의사결정 환경에 대해 실용적이고 위험이 낮은 접근법을 제공한다고 주장합니다. 각 인스턴스에 가장 적합한 정책을 선택하기 위해 맥락 정보를 활용함으로써, PS 는 복잡한 엔드 투 엔드 학습을 요구하거나 실현 가능성 제약을 위반하지 않으면서 이질성을 활용하여 최상의 단일 정책보다 성능을 향상시킵니다. 이 프레임워크는 "만능 (one-size-fits-all)" 모델이 최적이 아닌 복잡한 의사결정 환경에 적응할 수 있도록 다양한 정책을 유연하게 통합할 수 있는 모듈식 솔루션으로 제시됩니다. 저자들은 일부 기본 정책이 점근적으로 최적일지라도, PS 는 가장 효과적인 모델로 맥락을 동적으로 라우팅함으로써 유한 표본 설정에서 상당한 이점을 제공한다고 지적합니다.