다단계 차가 경매 설계를 위한 강화학습 접근법

섹션별 상세

다단계 차가 경매 환경을 마르코프 결정 과정(MDP)으로 모델링하여 판매자의 현재 행동이 입찰자의 미래 가치 평가에 미치는 전이 효과를 체계적으로 고려한다.

입찰자가 판매자의 학습 정책을 조작하기 위해 일부러 낮은 가격을 써내는 부정직한 입찰 문제를 해결하기 위해 '버퍼 기간(Buffer Periods)' 기술을 도입한다.

버퍼 기간과 낮은 전환 비용을 가진 강화학습 기법을 결합하여 입찰자가 기만적 행위로 얻을 수 있는 잉여 이득을 제한함으로써 정직한 입찰을 유도한다.

시장 노이즈 분포에 대한 사전 정보가 없는 상황에서도 별도의 순수 탐색 단계 없이 수익 후회를 최소화할 수 있는 새로운 알고리즘 구조를 설계했다.

수익 함수가 비선형적이고 직접 관측되지 않는 한계를 극복하기 위해 경매의 구조적 특성을 활용하여 불확실성을 제어하는 LSVI-UCB 확장 방식을 적용했다.

제안된 CLUB 알고리즘은 에피소드 수 K에 대해 시장 노이즈를 알 때 O(H^2.5√K), 모를 때 O(H^3√K)의 수익 후회를 달성함을 이론적으로 증명했다.

차가 경매(Second-Price Auction): — 가장 높은 가격을 제시한 입찰자가 낙찰받되, 실제 지불 금액은 두 번째로 높은 입찰가로 결정되는 경매 방식이다. 입찰자들이 자신의 진정한 가치를 입찰하도록 유도하는 특성이 있어 경매 이론에서 널리 사용된다.
예약 가격(Reserve Price): — 판매자가 물건을 판매하기 위해 수용할 수 있는 최소 가격이다. 입찰가가 이 가격보다 낮으면 낙찰이 이루어지지 않으며, 판매자의 수익 극대화를 위한 핵심 최적화 변수로 작용한다.
후회 최소화(Regret Minimization): — 알고리즘이 선택한 전략의 결과와 사후적으로 판명된 최적 전략의 결과 차이를 최소화하는 목표이다. 강화학습이나 온라인 학습에서 알고리즘의 성능을 평가하는 핵심 지표로 활용된다.
최소제곱 가치 반복 기반 상한 신뢰 구간(LSVI-UCB): — 선형 함수 근사를 사용하는 강화학습 알고리즘으로, 불확실성이 높은 행동에 가중치를 두어 탐색과 활용의 균형을 맞춘다. 복잡한 상태 공간에서 효율적인 정책 학습을 가능하게 한다.