Bellman Certificates를 통한 다중 비서 문제(Multi-Secretary Problem)의 타이트한 하한(Tight Lower

요약

다중 비서 문제(Multi-Secretary Problem)에서 지지 집합 간격(support gaps)이 존재할 때 발생하는 가법적 후회(additive regret)의 하한을 연구합니다. Bellman Certificates를 활용하여 기존의 $O((\log T)^2)$ 상한이 타이트함을 증명했습니다.

핵심 포인트

• 지지 집합 간격이 있는 유계 밀도 분포에서 후회가 $(\log T)^2$ 차수로 성장함을 증명
• Bellman Certificates를 사용하여 벨만 재귀의 완화된 해를 통한 하한 도출
• 네트워크 수익 관리 모델 등 연속적 보상 사례에 대한 이론적 근거 제공