우리는 각각 특정 비용으로 질의할 수 있는 n개의 독립적인 확률 변수와 관련된 기본적인 확률적 선택 문제를 연구합니다. 허용 오차 수준이 주어졌을 때, 목표는 모든 확률 변수에 대해 최소 예상 비용으로 -근사 최소(또는 최대) 값을 찾는 것입니다. 이 문제에 대한 해답은 적응형 질의 순서로, 다음 질의의 선택이 이전에 관찰한 값에 따라 달라질 수 있습니다. 목표가 -최소값을 찾는 것인지 -최소화를 찾는 것인지에 따라 두 가지 변형이 나타납니다. 모든 질의 비용이 균일할 때, 두 가지 변형 모두에 대해 4-근사 알고리즘을 제공합니다. 질의 비용이 비균일할 때, -최소값에 대해 5.83-근사 알고리즘을 제공하고, -최소화에 대해 7.47-근사 알고리즘을 제공합니다. 우리의 모든 알고리즘은 비적응형 정책에 의존하여 고정된 질의 순서를 수행하므로, 해당 '적응성' 간극에 대한 상한도 제공합니다. 우리의 분석은 알고리즘과 최적의 정책에서 중지 확률을 연관시키며, 주요 단계는 특정 확률적 지배 속성을 증명하고 활용하는 것입니다.
Al-Thani 외 연구진(수요일)이 이 문제를 연구했습니다.