제한된 피드백 환경에서의 효율적인 온라인 컨포멀 선택 (Efficient Online Conformal Selection with

우리는 에이전트가 사전 지정된 목표 확률 $\phi$로 적어도 하나의 "성공"을 식별할 수 있도록 옵션의 최소 부분 집합을 선택해야 하는 컨포멀 선택 (conformal selection) 문제를 다룹니다. 전통적인 온라인 컨포멀 예측 (online conformal prediction)은 관찰된 시퀀스에 대한 타당성 (validity)을 유지하는 데 집중하는 반면, 특히 제한된 피드백 (limited feedback) 상황에서 이러한 선택의 자원 비용을 최소화하는 것 (효율성, efficiency)은 여전히 중요한 과제로 남아 있습니다. 본 연구에서는 가장 제한적인 "밴딧 (bandit)" 피드백이 주어지는 설정을 고려하며, 적절한 제어 파라미터 (control parameter) 또는 쌍대 변수 (dual variable)에 적용된 단순한 적응형 컨포멀 추론 (Adaptive Conformal Inference, ACI) 업데이트 규칙이 적대적으로 타당하며 (adversarially valid), 임의의 입력 시퀀스(따라서 분포 변화 (distribution shifts) 상황 포함)에 대해 평균적으로 성공 목표가 달성됨을 보장할 뿐만 아니라, 확률적으로 효율적이며 (stochastically efficient), 적절한 확률적 벤치마크에 대해 $i.i.d.$ 입력 시 서브리니어 (sublinear) 효율성 후회 (efficiency regret)를 달성함을 입증합니다. 우리는 통합적인 알고리즘 기법과 Lyapunov 함수를 포함하는 분석적 프레임워크를 통해, 에이전트에게 제공되는 밴딧 (bandit) 및 세미-밴딧 (semi-bandit) 피드백을 포착하는 표준 모델 하에서 이러한 보장들을 보여줍니다. 우리의 접근 방식은 이전 연구보다 더 복잡한 설정을 다루면서도 훨씬 적은 피드백을 요구하며, 우리의 결과는 제한된 피드백을 가진 효율적인 온라인 학습 (online learning)과 분포 불가지론적 불확실성 정량화 (distribution-free uncertainty quantification) 사이의 새로운 이론적 가교를 제공합니다.