A Tale of Two Cities: Pessimism and Opportunism in Offline Dynamic Pricing

기술적 요약: 두 도시의 이야기: 오프라인 동적 가격 책정에서의 비관주의와 기회주의

문제 제기
본 논문은 가격 공간에 대한 역사적 데이터의 불완전한 커버리지가 존재하는 환경에서의 오프라인 동적 가격 책정 문제를 다룬다. 많은 실제 응용 분야에서 기업들은 광범위한 실험에 따르는 비용이나 위험을 감당할 수 없어, 잠재적으로 최적일 수 있는 특정 후보 가격을 포함한 일부 가격이 전혀 관측되지 않는 데이터셋이 생성된다. 완전한 커버리지나 부분적 커버리지 가정 (최적 정책의 행동이 데이터에 반드시 포함되어야 함) 에 의존하는 표준 오프라인 강화 학습 (RL) 방법론들은 이러한 "커버리지 부재" 환경에서는 실패한다. 최적 가격이 누락되면 수요와 Q-함수가 더 이상 점 (point) 식별되지 않게 되어, 표준 추정량들이 비최적이거나 적용 불가능해진다. 저자들은 수요가 가격에 대해 비증가적이라는 근본적인 경제적 규칙성을 활용하여, 데이터 커버리지 가정이 전혀 없는 상태에서 작동하는 통계적으로 타당한 오프라인 동적 가격 책정 프레임워크를 개발하는 것을 목표로 한다.

방법론
저자들은 가격에 대한 수요의 단조성 (monotonicity) 을 이용하여 관측되지 않은 가격의 가치를 경계화 (bound) 하는 비모수적 부분 식별 프레임워크를 제안한다.

1. 부분 식별 프레임워크:
   모수적 모델을 통한 외삽 대신, 이 방법은 관측되지 않은 가격 $a$에서 수요 분포 함수 $F_t(d|a)$에 대한 구간 경계를 구성한다. 이러한 경계는 관측된 가장 가까운 하위 가격 ($a^L_t$) 과 상위 가격 ($a^U_t$) 에서의 관측된 수요 분포로부터 유도된다. 구체적으로, 관측되지 않은 가격 $a$에 대해 조건부 누적분포함수 (CDF) 는 $F_t(d|a^L_t) \le F_t(d|a) \le F_t(d|a^U_t)$로 경계화된다. 표본 오차를 고려하기 위해 저자들은 Dvoretzky–Kiefer–Wolfowitz 부등식에서 유도된 신뢰구간을 사용하여 이러한 경계를 정제함으로써, 실제 CDF 가 높은 확률로 구성된 구간 내에 있도록 보장한다.

2. 의사결정 규칙:
   이 프레임워크 내에서 저자들은 순차적 커버리지 부재 환경에 맞춘 두 가지 명확한 동적 의사결정 규칙을 수립한다.

   • 비관적 정책 (Pessimistic Policy): 이 정책은 최악의 경우 수익을 극대화한다. 가능한 수요 분포의 신뢰집합 (confidence set) 위에서 Q-함수를 최소화함으로써 구성된 Q-함수의 하한을 극대화하는 가격을 선택한다. 이 접근법은 관측되지 않은 가격에 대한 불확실성이 상당할 때 하방 위험에 대한 보호를 제공한다.
   • 기회주의적 정책 (Opportunistic Policy): 이 정책은 최선의 실현 가능한 대안에 대한 최악의 경우 후회 (regret) 를 최소화한다. 수익의 하한에 초점을 맞추는 비관적 접근법과 달리, 기회주의적 접근법은 미지의 수요가 최악의 경우 실현될 때 최선의 대안 행동에 비해 어떤 행동이 초래할 수 있는 최대 후회를 고려한다. 이를 통해 기업들은 덜 탐험된 가격에서 발생할 수 있는 상방 기회를 추구할 수 있다.

3. 알고리즘:
   저자들은 역방향 귀납법 (동적 프로그래밍) 을 사용하여 두 가지 정책 모두에 대한 효율적인 알고리즘을 개발한다. 핵심 계산 단계는 구성된 신뢰집합 내에서 최악의 경우 Q-값 (비관적 정책의 경우) 또는 최악의 경우 후회 (기회주의적 정책의 경우) 를 찾기 위해 선형 계획법을 푸는 것을 포함한다.

주요 기여

1. 커버리지 부재 프레임워크: 본 논문은 데이터 커버리지 가정 없이도 유효한 최초의 오프라인 동적 가격 책정 기법을 제시한다. 최적 가격이 오프라인 데이터에서 누락되었을 때 정책 학습을 위한 부분 식별 프레임워크를 도입하며, 수요, 정책 클래스, 또는 Q-함수 클래스에 대한 모수적 제약을 부과하지 않는다.
2. 이론적 보장: 저자들은 비관적 및 기회주의적 정책에 대한 유한 표본 후회 (regret) 경계를 수립한다. 이 경계는 관측된 가격에 대한 추정 오차를 포착하는 한 항과 관측되지 않은 최적 가격으로 인해 발생하는 추가 비용을 정량화하는 다른 항으로 분해된다.
   • 최적 가격이 커버될 때, 후회는 $O_p(\sqrt{\log N / N})$의 표준 속도로 회복된다.
   • 커버리지가 실패할 때, 결과는 부분 식별 하에서 학습하는 데 드는 정확한 비용을 정량화하며, 경계가 엄밀 (attainable) 함을 보여준다.
3. 관리적 매핑: 이 프레임워크는 기업의 위험 태도에서 가격 책정 정책으로의 실용적인 매핑을 제공한다. 수익 안정성을 추구하는 기업 (비관적 정책) 과 잠재적 이익을 위해 측정된 위험을 감수하려는 기업 (기회주의적 정책) 을 구분한다.

결과
저자들은 시뮬레이션과 항공기 티켓 가격 책정과 관련된 실제 데이터 적용을 통해 방법론을 평가한다.

• 시뮬레이션: 다양한 누락 데이터 메커니즘을 가진 포아송 (Poisson) 및 음이항 (Negative Binomial) 수요 모델을 사용하여, 제안된 방법들을 표준 오프라인 RL 베이스라인 (Greedy, Vanilla Pessimistic, Conservative Q-Learning, Batch-Constrained Q-learning) 과 비교한다. 결과는 제안된 기회주의적 방법이 특히 행동 정책이 비최적이거나 데이터 커버리지가 희소한 시나리오에서 베이스라인을 종종 능가함을 보여준다. 기회주의적 방법은 누락된 가격이 있더라도 오라클 최적 정책과 유사한 성능을 자주 달성한다. 정제된 비관적 방법 또한 여러 경우에서 일반 비관적 접근법보다 우수한 성과를 보인다. 주목할 점은 기회주의적 방법만이 최적인 관측되지 않은 가격을 선택할 수 있는 유일한 방법인 반면, 비관적 베이스라인 (대부분의 경우 정제된 버전 포함) 은 이러한 가격들을 배제하는 경향이 있다는 것이다.
• 실제 데이터 적용: 특정 가격 포인트가 과소 대표된 Expedia 항공 티켓 데이터 (JFK 에서 CLT 로) 분석에서, 기회주의적 방법은 몬테카를로 시뮬레이션에서 가장 높은 경험적 총수익을 달성했다. 정제된 비관적 방법은 CQL 보다 약간 낮은 성적으로 3 위를 기록했으며, 일반 비관적 접근법은 가장 낮은 수익을 기록했다. 기회주의적 접근법은 특정 상태에서 관측되지 않은 가격 포인트를 성공적으로 선택한 반면, CQL 은 그렇지 못했다.

의의 및 주장
본 논문은 순차적 커버리지 부재 환경에서 오프라인 동적 가격 책정과 부분 식별 사이의 간극을 해소한다고 주장한다. 기존 오프라인 RL 방법론들은 최적 가격이 역사적 데이터에서 완전히 누락될 수 있는 가격 책정 문제에는 부적절하다고 논증한다. 수요의 단조성을 활용함으로써, 제안된 프레임워크는 모수적 가정에 의존하지 않고 관측된 데이터의 지지 (support) 를 넘어선 정책 학습을 가능하게 한다. 저자들은 그들의 후회 경계가 엄밀하고 속도 최적 (rate-optimal) 이라고 강조한다. 관리적 측면에서 이 연구는 의사결정자에게 세련된 도구를 제공하여, 하방 보호를 위한 보수적 전략 (비관주의) 과 잠재적 이익을 위한 공격적 전략 (기회주의) 사이에서 위험 감수성과 자원 가용성에 따라 선택할 수 있게 한다. 본 논문은 단일 전략이 다른 전략을 일관되게 능가하지는 않지만, 선택은 특정 상황과 기업의 위험 및 불확실성에 관한 전략적 목표에 달려 있다고 결론짓는다.