본 논문은 노드의 레이블이 알려지지 않은 n개 노드 그래프 G에서 순차적 의사결정 문제를 연구합니다. 각 노드의 레이블은 유한 집합 Σ에서 그래프 G에 대해 Markov 속성을 갖는 결합 분포 P로부터 추출됩니다. 각 단계에서 노드를 선택하면 해당 노드의 레이블이 공개되고 레이블에 따라 보상이 주어집니다. 목표는 기대 누적 할인 보상을 극대화하기 위해 노드를 적응적으로 선택하는 것입니다. 선택된 노드의 이웃에만 행동이 제한되는 선구 탐색 제약 조건을 부과하며, 이는 접촉 추적 및 로봇 탐색과 같은 실제 제약 조건을 반영합니다. 일반 그래프에 적용되는 Gittins index 기반 정책을 설계하며, G가 숲일 때 최적임이 증명됩니다. 구현은 O(n²⋅|Σ|²) 시간에 실행되며 P에 대한 O(n⋅|Σ|²) 오라클 호출과 O(n²⋅|Σ|) 공간을 사용합니다. 합성 및 실제 그래프에 대한 실험 결과, 비트리, 예산 제한 및 할인되지 않은 설정을 포함하여 제안된 방법이 기본 방법보다 일관되게 성능이 우수함을 보여줍니다. 예를 들어, 실제 성적 상호 작용 네트워크에 대한 HIV 검사 시뮬레이션에서 제안된 정책은 인구의 절반만 검사하여 거의 모든 양성 사례를 감지하며 다른 기본 방법보다 성능이 훨씬 뛰어납니다.
