매개변수적 예언자 부등식(Parametric Prophet Inequalities)을 위한 점근적 최적 학습

우리는 미지의 매개변수 $θ$를 가진 지수 유형의 매개변수적 가족(parametric family)에서 추출된 독립 항등 분포(i.i.d.) 보상을 갖는 예언자 부등식(prophet inequalities)에서의 학습을 연구합니다. 이 클래스에는 지수(exponential), 파레토(Pareto), 그리고 유계 지원(bounded-support) 거듭제곱 가족(power-family) 분포가 포함됩니다. 우리는 먼저 이 가족에 대한 최적의 완전 정보 점근적 경쟁비(full-information asymptotic competitive ratio)를 규명합니다. 무계 지원(unbounded-support) 사례의 경우 극한값은 $ {\left(θ/({θ-c_+})\right)^{c_+/θ}}/ {Γ(1-c_+/θ)}$인 반면, 유계 지원(bounded-support) 사례의 경우 극한값은 $1$입니다. 그런 다음 우리는 온라인 학습을 위한 신뢰 기반 동적 계획법(confidence-based dynamic-programming) 정책을 제안합니다. 명시적인 매개변수 구조를 활용함으로써, 이 정책은 외부의 오프라인 샘플 없이 온라인 관측값만을 사용하여 동일한 최적 점근적 경쟁비를 달성합니다. 나아가 우리는 표준적인 예시들에 대해 분포별 수렴 속도(convergence rates)를 도출합니다. 마지막으로, 합성 인스턴스(synthetic instances)에 대한 수치 실험을 통해 우리 알고리즘의 성능을 입증합니다.