Beyond the Lower Bound: Bridging Regret Minimization and Best Arm Identification in Lexicographic Bandits
Created by
Haebom
Category
Empty
저자
Bo Xue, Yuanyu Wan, Zhichao Lu, Qingfu Zhang
개요
다중 목표 의사 결정 문제에서 계층적 선호도를 가진 경우, 사전식 밴딧(lexicographic bandits)은 우선 순위에 따라 여러 목표를 최적화하는 데 자연스러운 프레임워크를 제공합니다. 본 연구는 이러한 환경에서 후회를 최소화하는 것과 최적의 팔을 식별하는 것 사이의 격차를 해소하고자 합니다. 두 가지 제거 기반 알고리즘을 제안하며, 첫 번째 알고리즘은 목표 우선 순위에 따라 순차적으로 팔을 제거하고, 두 번째 알고리즘은 각 라운드에서 모든 목표로부터 보상 정보를 활용하여 교차 목표 종속성을 효과적으로 활용합니다.
시사점, 한계점
•
시사점:
◦
사전식 밴딧 환경에서 후회 최소화와 최적 팔 식별 사이의 격차를 해소하는 알고리즘 개발.
◦
단일 목표 밴딧 알고리즘과 유사한 복잡도 및 후회 경계를 달성하는 알고리즘 제시.
◦
교차 목표 종속성을 활용하여 단일 목표 밴딧 문제의 알려진 하한보다 뛰어난 성능을 보이는 알고리즘 개발.
