Adaptive Frontier Exploration on Graphs with Applications to Network-Based Disease Testing
Authors: Davin Choo
Yuqi Pan
Tonghan Wang
Milind Tambe
Alastair van Heerden
Cheryl Johnson
Venue: NeurIPS 2025 poster ()
Keywords: sequential decision making
graphs
branching bandits
gittins index
network-based testing
public health
Primary area: optimization
TL;DR: We develop a policy for adaptive exploration on a graph under frontier constraint that is optimal for trees based on Gittins index, and show how we can apply it to network-based testing in public health settings

Abstract: We study a sequential decision-making problem on a $n$-node graph $\mathcal{G}$ where each node has an unknown label from a finite set $\mathbf{\Omega}$, drawn from a joint distribution $\mathcal{P}$ that is Markov with respect to $\mathcal{G}$. At each step, selecting a node reveals its label and yields a label-dependent reward. The goal is to adaptively choose nodes to maximize expected accumulated discounted rewards. We impose a frontier exploration constraint, where actions are limited to neighbors of previously selected nodes, reflecting practical constraints in settings such as contact tracing and robotic exploration. We design a Gittins index-based policy that applies to general graphs and is provably optimal when $\mathcal{G}$ is a forest. Our implementation runs in $\mathcal{O}(n^2 \cdot |\mathbf{\Omega}|^2)$ time while using $\mathcal{O}(n \cdot |\mathbf{\Omega}|^2)$ oracle calls to $\mathcal{P}$ and $\mathcal{O}(n^2 \cdot |\mathbf{\Omega}|)$ space. Experiments on synthetic and real-world graphs show that our method consistently outperforms natural baselines, including in non-tree, budget-limited, and undiscounted settings. For example, in HIV testing simulations on real-world sexual interaction networks, our policy detects nearly all positive cases with only half the population tested, substantially outperforming other baselines.

Adaptive Frontier Exploration on Graphs with
Applications to Network-Based Disease Testing
Davin Choo" Harvard University davinchoo@seas. hhrvardd. edu
Yuqi Pan" Harvard University
Tonghan Wang
Harvard University twangl0g harvard. edu
yuqipangg. harvard
Milind Tambe
Alastair van Heerden
Harvard University
University of Witwatersrand
tambe@seas. harvard. edu
Wits Health Consortium
alastair. vanheerdendvits..cc .a
Cheryl Johnson
World Health Organization
johnsonc@who. int
Abstract
We study sequential socision-making problem n-node graph G where each node has an unknown label from a finite set Ω drawn from a joint distribution P that is Markov with respect to G. At each step, selecting node reveals its label and yields a label-dependent reward. The goal is to adaptively choose nodes maximize expected accumulated discounted rewards. We impose frontier exploration constraint, where actions are limited to neighbors of previously selected nodes, reflecting practical constraints in settings such as contact tracing and robotic exploration. We design a Gittins index-based policy that applies to general graphs and provably optimal when & forest. Our implementation runs 2 time while using Onn ( oracle calls to P and Onn² (S2]) space. Experiments on synthetic and real-world graphs show that our method consistently outperforms natural baselines, including in non-tree, budget-limice limited, and undiscounted settings. For example, HIV testing simulations on real-world sexual interaction networks, our policy detects nearly all positive cases with only half the population tested, substantially outperforming other baselines.
Introduction
We study a sequential decision-making problem on a graph G. where each node has an unknown discrete label from Ω. 'he labels follow a joint distribution P, which we assume is specified by Markov random field (MRF) defined over G [KF09]. When we act on node, its label revealed and we receive a label-dependent reward. Crucially, the entire process is history--ensiitiv:: label realizations are stochastic and depend on previously observed labels, a setting that naturally arises in Bayesian adaptive planning [GKI1]. I]. In this paper, we study setting where actions are subject to frontier exploration constraint: the first node in each connected component is selected based on pre- pre-nee priority rule, and subsequent actions are restricted to neighbors of previously selected nodes. This constraint reflects realistic settings where local neighborhood information becomes accessible only through exploration, as in active search on graphs [GKX 12], robotic exploration
'Equal contribution
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

[KK14], and cybersecurity applications [LCH 25]. The objective is then to maximize the expected accumulated discounted reward over time by sequentially selecting nodes to act upon.
Definition 1 (The Adaptive Frontier Exploration on Graphs (AFEG) problem). An AFEG instance defined by a triple (G, P, where 9 = [X. E) graph, P is a joint distribution over node labels that is Markov with respect to G, and 3 E (0, 1) is a discount factor. The process unfolds over n = | time steps, with the state St at time t consisting of the current frontier and the revealed labels. Acting
frontier node reveals its label, grants a label-dependent reward, and updates beliefs about other nodes via Bayesian inference under P. The goal is to compute a policy я that maps each
state frontier node, maximizing the expected total discounted reward:
arg max
P(X = S.-1) ((Xx(()-))) VE
where X ()) is the node selected by policy at time t, and .() is the label-dependent reward.
While the optimal policy can be computed via dynamic programming. it is intractable for general graphs due to the exponential state space. A natural strategy is to leverage adaptive submodularity, which guarantees that greedy policies achieve a (1 l/eo-approiimation [GKI1]. Unfortunately, the objective in AFEG is not adaptively submodular in general: for instance, in disease detection, observing an infected neighbor can increase the marginal benefit of testing a node, violating the diminishing returns property of adaptive submodularity.
Our problem is closely related to the setting of active search on graphs [GKX* 12, WGS13, JMC 17, JMA+18], where the goal is to identify as many target-labeled nodes as possible under a fixed budget, without exploration constraints. Since exact optimization is intractable, these works focused on practical heuristics such as search space pruning. AFEG differs in two key respects: (i) we impose a frontier constraint, and (ii) we consider an infinite-horizon objective with discounting, rather than a fixed budget. These differences are not merely technical but they enable provable optimality in meaningful special cases, particularly when the input graph is a forest. Forest structures naturally arise in several relevant domains, including transmission trees in contact tracing [KFH06] and recruitment trees in respondent-drive with guarantees on forests can be efficiently applied to sparse real-world interaction graphs, such as sexual contact graphs, which tend to be tree-like in practice; see Section 4.3.
sampling [Hec97, GS09]. Moreover, algorithms
1.1 Motivating application: network-based disease testing
A key motivating example of AFEG is saworr-based infectious disease testing where the goal is to identify infected individuals as early as possible. In particular, we focus diseases that transmitted through person-to-person contact", e.g., sex, exposure of blood through injecting drug use, or birth, where interaction information can be collected through interviews. In this context, frontier testing is both natural and operationally motivated: test outcomes substantially alter beliefs about neighboring individuals, making sequential expansion along the frontier an efficient strategy.
Public health motivation. The 95-95-95 HIV targets proposed by UNAIDS [UNA22] aim for 95% of people with HIV to know their status, 95% of those receive treatment, and 95% of treated individuals to achieve viral suppression - aligned with UN Sustainable Development Goal 3.3 [Nat]. Yet, the 2024 UNAIDS report [UNA24] reveals that the "first 95" remains the most elusive, with roughly one in seven people living with HIV still undiagnosed, and there continues to be 1.3 million new infections every year. Studies have shown that virally suppressed individuals will not infect others [CCM+11 11, RCB+ 16, BPP+ 18), leading to the U=U (undetectable = untransmittable) campaign [oAD19, OG20J. Thus, the faster we can detect infected individuals, the faster they can be enrolled onto treatment and limit the spread of the disease. To address this gap, the WHO recommends network-based testing strategies to reach underserved populations [Org24a]. These include partners and biological children of people with HIV, as well as those with high ongoing HIV risk. Network-based interventions have shown effectiveness have also been explored for other infectious diseases beyond HIV [JSK 17, MWBDM*22 25]; see also [C] for WHO-commissioned systemic review on social network- based HIV testing.
South Africa [JPC+ 19] and
2This is in contrast to illnesses like flu where transmission can oceur to a room full of strangers.
'The human immunodeficiency virus (HIV) attacks the immune system and can lead to AIDS, It remains a major global health issue, having claimed over 42 million lives to date [Org24b].

---

4
(Gender: Age: 21, Drug use: Y....)
Alice
R
(Gender: M. Age: 23, Drug use: N....)
Charlic
Bob
Co Gender: M.
Xa
Age:
Drug use: Y.
Denise
XD
Cp = (Gender: F, Age: 22, Drug use: N....)
Figure Illustration of how a real-world transmission graph (left) can be framed as an AFEG instance (right). Here, the joint distribution P over the labels XA.Xn Xc, Xp E {+, may depend on the covariates C, CB, R2 and underlying interaction graph structure.
model the network based disease testing problem into AFEG instance. Firstly, we use the network G as is, where nodes represent individuals and edges represent sexual interactions. Each node has binary infection status (infected not) that drawn from some underlying joint distribution P on X over the labels 5 = {+, -]. where P may depend on the individual covariates and graph structure. The reward for testing individual X and revealing status b E {0, } is then r(X, b) = b. See Fig. 1 for an illustration. The goal is of trying to identify infected individuals as early as possible implicitly enforced by the presence of any discount factor 3 < 1. Importantly, discounting reflects both practical constraints such as sudden funding cuts [UNA25] and clinical importance of early diagnosis, which improves patient outcomes and limits transmission [CCM* 11]. See also [RN21] for other natural justifications for using discount factors 33 in modeling long-term policy rewards. While transmission graphs of sexually transmitted diseases are not truly forests and may have high-degree nodes (e.g., sex workers), empirical studies have also shown that such transmission graphs are often sparse and exhibit tree-like structure [BMS04, YJM+13, WKPF+ 17]. Finally, to apply the infinite horizon framework of AFEG in our finite testing setting, we give zero subsequent rewards after every individual has been already tested.
Fig. 1 illustrates how
1.2 Our contributions
Contribution 1: Gittins index-based policy for AFEG and new results for branching bandits. In Section 3, we show that when G is forest, AFEG can be modeled as branching bandit problem, for which Gittins index policies are known to be optimal [KO03]. We provide a novel characterization of Gittins indices for discrete branching bandits using piecewise linear functions, and develop
practical implementation that runs in On | time while using O(n [S2(2) oracle calls to P and (n (2l) space. Our policy also works for general non-tree AFEG instances, but without optimality guarantees. Despite this, it demonstrates strong performance in experimental evaluations.
Contribution 2: Formalizing network-based disease testing as an AFEG instance. As shown in Section 1.1, network-based infectious disease testing can be cast as an instance of AFEG. To our knowledge, this is the first formal framework to model frontier-based testing as sequential decision- making on probabilistic graph model for principled exploitation of network effects in diseases such HIV. In Appendix C, propose method to learn parameters from past disease data to define joint distribution P on new interaction networks so as to define new AFEG instances.
Contribution 3: Empirical evaluation. We evaluate our Gittins index -ased policy on synthetic datasets and show that it performs strongly even settings where is not provably optimal, including non-trees and finite-horizon scenarios. Our approach outperforms other baselines on public-use real-world sex interaction graphs on sexually transmitted diseases (Gonorrhea, Chlamydia, Syphilis, HIV, and Hepatitis) from ICPSR [MR1] I]. For instance, in one of our experiments Fig. 5), our method identifies almost all infected individuals while other baselines would only detect about 80%, in expectation, if we only have the testing budget to only test half of the population.
HIV testing (see
Preliminaries
Notation. We use lowercase letters scalars, uppercase letters for random variables, bold letters for vectors or collections, and calligraphic letters for structured objects such as graphs and probability

---

distributions. Unordered sets are denoted with braces (e.g., {-}), and ordered tuples with parentheses (e.g.. (+)) For any set A. let |A| denote its cardinality. We use R20 for non non-negative reals, N for the natural numbers, and N~o N (0). For any E Nyo, we define [r] == (I..... ..... J. For a vector x = (01,.. Tn,, we use x; = 2h and x- = (x1,..... -;-1 #i........ Fn) to denote the vector without the i-th coordinate. We also employ standard asymptotic notations such as (-) and (2()).
In this work, we consider joint distributions over n discrete variables X = [_X J structured by an undirected graph G = (x, Ej. Each variable X; takes values from a finite set of labels n = (u fu...... 2|sa }: in the binary case, Ω = f00 1}. For any node X E X, let N()) S X denote its neighbors in G, and let V(g) denote the vertex set. As standard in the literature of graphical models, we will use X E X to refer to both the node and its associated random variable, so expressions like X= denote the event that variable X takes on label value E Ω2 A tree is connected acyclic graph, and forest is a collection of disjoint trees. A rooted tree designates one node as the root and orients all edges away from it. In a directed rooted tree, we denote the parent and children of X by Pa(X) and Ch(X respectively, with pa( (X) ) as the realization of its parent(s). Note that in rooted trees, Pa(X)
if and only if X is the root. The most standard and general way to model a joint distribution P that is Markov with respect to a graph 9 is via Markov Random Field (MRF) [KF09]. An MRF is an undirected graphical model in which nodes represent random variables and edges encode conditional dependencies. It satisfies the local Markov property: each variable is conditionally independent of all others given its neighbors. See Appendix for additional background.
AFEG bears some resemblance to Bayesian multi-armed bandits (MABs), where Gittins index policies are optimal under assumptions like arm independence and aufinite-horizer discounted rewards [Gi179, GGW11J. However, key differences prevent a reduction of AFEE to a standard MAB: (i) each arm (node) can be selected at most once; (ii) the set of available actions changes dynamically due to the frontier constraint; and (iii) action outcomes are correlated through the graph structure and joint distribution P. As such, closer abstraction is the branching bandit model [Wei88, Tsi94, KO03], where actions dynamically activate new options, closely mirroring frontier expansion in AFEG. While Gittins index policies are known to be optimal for branching bandits [KO03], no efficient method has been proposed to compute them in general. Indeed, Gittins indices are underused in practice due to perceived computational intractability in all but simple settings [Sco10. MKLL Edw Bdw19]. Our work addresses this gap by presenting the first efficient implementation of Gittins- based policies in discrete branching bandits with history-depende rewards, enabling their use in structured settings like network-based disease testing. Related index-based techniques for classic MABs are reviewed in [CM14], but do not extend to branching structures. [MK23] studied a disease-spread model in which infections propagate sequentially along parent-child links from known root, and showed that it reduces to the branching- bandit bandit model of [Wei88]. In contrast, our setting assumes no known source: infection statuses are jointly distributed over the network, and testing can start at any node under a frontier constraint. This makes their model ill-suited for our AFEG setting, where correlations cannot be captured by single infection tree.
Our work is also related to well-studied areas such as reinforcement learning, active search on graphs, and influence maximization. In addition, there is substantial body of prior work on network-based HIV testing and transmission modeling. We provide a detailed review of these topics in Appendix A.
3 A Gittins index-based policy for the AFEG problem
We propose policy, GITTINS, for the AFEG problem that is based on Gittins indices. In Section 3.1, we show that when the input graph G is a forest, AFEG reduces exactly to the branching bandit framework [Wei88, Tsi94, KO03), under which GITTINS is provably optimal. While [KO03] estab- lished the existence of an optimal Gittins index policy, they did not characterize the index explicitly nor provide an efficient method for computing it. In Section 3.2, we prove that the key recursive functions involved in computing the index are piecewise linear, which enables practical and efficient computation. The implementation of GITTINS and its runtime analysis is given in Section 3.3.
3.1 Reduction to branching bandits for tree-structured instances
In the branching bandit model [Wei88, Tsi94, KO03], project is represented as a rooted tree, where each node corresponds to an action. Selecting a node yields a stochastic immediate reward and activates its children to be available for future selection. A node is available if it is the root

---

descendant of a previously selected node. Under the frontier exploration constraint of AFEG, forest naturally induces a collection of rooted trees; see Fig. 2. The problem then reduces a branching bandit instance by treating each leaf as if it can be selected infinitely many times with zero reward, or equivalently, by appending an infinite chain of zero-reward nodes to each leaf. At each timestep, the available actions correspond to the current frontier: nodes adjacent to those already selected. Crucially, due to the Markov property of P. selecting a node X only affects posterior beliefs over its descendants, preserving the conditional independence structure required by the branching bandit formulation. When G is a forest, the problem decomposes across connected components, allowing Gittins indices to be computed independently for each rooted tree.
Fromier
X
X
X
Figure 2: Reduction to branching bandit 8 nodes with root X1. After acting on {Xi, X3), the frontier is {X2, X4, Xe). Note that we have P(22 x1, = ( x1) by the Markov property.
To define the Gittins index, we assume the reward r rXx, v) for revealing label Ω at node X is bounded by some finite 7, i.e. -00 < - - <((X v) < < co, and introduce a retirement option with one-off reward m. This enables recursive characterization of the index: at any step, the policy can choose to continue exploring, or stop acting and receive an one-off fixed reward of m. Since rewards are upper bounded by F, the maximum attainable reward is most F FF+ + fB r-3
So, when m > I-3. any optimal policy should choose the retirement action and quit.
To define the Gittins index, let us first define two recursive functions & and 4 as per [KO03]. For any non-root node X X, label b Ω and value 0 m S 1-9-
(x,(mm) max m, Σ P(X = Pa(X) b) [r(X, + 3 (m)) (I)
eEft
If X is the root, we define (x,x(m) = max m. Even P(X = 1) [r(X, + B (enn(x,
For any subset of nodes S E X, label v E Ω2 and value 0 S m S T-3-
II
ddy (k) dk 8k
if +
S (m)
= T-8
(2)
m
if S =
We will only invoke Eq. (2) with = Ch(X) for some node X. The interpretation here is that 6x,6 represents the total expected value of this subtree rooted at X when its parent Pa(X) has label b E Ω while accounting for option of taking the retirement option m at each step, and (cn(X), represents the value of the collection of subtrees rooted at the children of X, excluding X itself. i..., the contributions from the children of X, conditioned on X having label & E Ω. For example, for Xi in Fig. 2, this refers the subtrees rooted at X2, X3, and X4. Using these notation, the Gittins index g( X, b) for node X given (a(X)= = is then defined as
F
g(X,0) b) min E
1-
0,
(x, 2
That is, ((X,b) represents the "fair value" of the subtree rooted at X, given that its parent has label E Ω. The parent's label matters because the posterior distribution over X's label is updated conditionally based the value of b. Theorem 3, which follows from Theorem of [KO03] with appropriate changes in notation, establishes that the GITTINS policy is optimal when G is a forest.
*There are several equivalent ways proving the optimality Gittins indices in classic non-brane non-branching setting, e.g., the original stopping problem formulation [Git74], retirement option process formulation [Whi80]. restart-ine state formulation [KV] prevailing charge formulation [Web92], state space reduction [Tsi94], etc. The branching bandit optimality proof of [KO03] builds [Whi80]'s retirement option formulation.
5

---

Definition 2 (The GITTINS policy; Algorithm 1). The GITTINS policy pre-computes all g(X, 6) values given G and P. then repeatedly acts on the node in the frontier with the largest index value. Theorem 3. GITTINS is optimal for the AFEG problem when 9 is a forest.
3.2 Properties of discrete branching bandits
We prove that the recursive functions dx a (m) and PCL(X), (m) are piecewise linear in m. This facilitates an efficient implementation of GITTINS, which we give in Algorithm 1.
Lemma 4. For any node X E X and label b E Q (x,((m) is a non-decreasing piecewise linear function over m E [0,7/(1- 3
The proof intuition behind Lemma 4 is to perform induction from the leaves to the root while recalling that piecewise functions on a fixed domain range are closed under addition, multiplication, differentiation, and integration. This later allows us to bound the running time for computing our GITTINS policy in Theorem 6 as the number of pieces in the function changes additively as we combine piecewise functions, e.g. #pieces(Ji + f2) S #pieces(J1) + #-peccesS22..
We also prove additional properties of the + function which crucial in algorithm for efficiently manipulating the piecewise linear functions to compute the recursive functions @ and D, and may be of independent interest to resaerchers of Gittins index.
Proposition 5. For any non-leaf node X and label b:
(c (m) = (cn(x),, + (m) for some piecewise linear (c)
(c)()), (m) m if and only if m 2 maXyech(x) () b(Y,
The first term in the expression (C)( (m) 4 x (0) () (m) can be interpreted as the original maximized reward for the descendants of X while the second term is the additional reward afforded by the retirement option m. Mcanwhile, we observe that the minimum m such that Cx)( (m) is the essentially the largest Gittins index among nodes Ch(X).
Full proofs of Lemma and Proposition 5 are deferred to Appendix F.I.
3.3 Extension to general graphs
On general graphs where G is not forest, dependencies across frontier nodes may violate the branching bandit assumptions. Nevertheless, we heuristically apply GITTINS by treating each connected component as a tree (c.g., minimum spanning tree) and ignoring edges that violate the acyclicity requirement. This restricts the fronticr to a subtree at each step.
Algorithm provides pseudocode describing this, where Line is the heuristic which drops edges when G is not forest graph. As any tree restriction works here, one natural option to compute the breadth-firs first search (BFS) tree as it minimizes the height to the root, reducing any artificial frontier given in Theorem 6.
constraint due to tree projection. The runtime complexity Algorithm
At first glance, one may think that the running time of Algorithm would dependent exponentially on the maximum depth d of the induced rooted trees, even if all operations involving piecewise linear functions can be done in O(1) time. This is because the definitions of Eq. (1) and Eq. (2) tell us that the function σx, depends on all Φz functions, for all descendants Z of and labels S. However, our next result show that we can in fact obtain a polynomial run time that is independent of the maximum depth d of the induced rooted trees; this is why any tree restriction works on Line 5.
Theorem 6. Given graph G (X, E) and oracle access to joint distribution P. the Gittins indices can be computed in Onn². 5t time while using O(n | oracle calls to P via Algorithm The ? (n space for storing O(n [ intermediate piecewise linear functions.
space complexity is O(n²
The proof outline of Theorem is as follows: we first use induction (from the leaves towards the root) to argue that, for any node X, the set of functions (óx,ehie can be computed using ([
'The focus is on the recursive cost of computing Gittins indices and the oracle access assumption is meant to abstract away the computational cost of computing quantities like P(- -). As our setting assumes that P is pairwise MRF defined over tree-structured graph, such inference is tractable via the junction tree algorithm.

---

Algorithm Setting up the GITTINS policy.
1: Input: Graph 9 = (X, E), Joint distribution P over X that is Markov to G
2: Output: Gittins index value g X, b) for all X E X and
3: for each connected component H of G do
4: Compute root node Xooot from priority rule
> e.g. Xroot = argmaxx, EV(()) P(X; = 1)
5: Compute any tree of H. rooted Xroot
Heuristic for non-trees
6:
for node X; ((H) from leaf towards root, and label b E 52 do
For Xoot, set b = 0
7:
if X; is leaf then Compute ((X,, (),)))(m) = max {m, Bm + P(X=1 Pa(X) r)(,))())
8:
9:
else
10:
Compute *c (m) via Eq. (2) and Proposition 5 Compute (m.) via Eq. (1)
11:
Store ((X,,, b) for future computation
13: Compute {g(X., b)]xexxbee) according to Eq. (3), using previously stored 6 values Reminder: For root nodes, we set b
14: return {g(X, b)} xEX
oracle calls to P and ( m1, [Ch(X))) operations on piecewise linear functions, as long as we store intermediate functions { YECh(X). along the way. Then, we argue that the maximum time to perform any piecewise linear function operation in Algorithm I is upper bounded by O(n [2)). Our claim follows by summing over all nodes X and using the upper bound cost of operating on piecewise linear function. See Appendix F.1 for the full proof.
We also provide worked example of how to compute Gittins index by manipulating & and & in Appendix B. This computation is implemented Python and the source code is available on our Github.
4 Experiments
We benchmark our proposed GITTINS policy against several natural baselines - RANDOM, GREEDY, DQN, and OPTIMAL- on both synthetic and real-world graphs to evaluate performance on AFEG. To reflect the network-based disease testing application discussed in Section 1.1, we consider binary node labels, and define the immediate reward to be if and only if the revealed label is positive. As such, it is natural to define the first node in every connected component as the node with the highest marginal probability of being positive amongst all nodes in that connected component.
Benchmarked policies. Given a problem instance (G, (. state in AFEG consists of the current set of frontier nodes and the revealed labels of previously tested nodes.
RANDOM: Selects random node from the frontier without using any state information.
GREEDY: Selects the frontier node with the highest posterior probability of being positive, conditioned on the currently observed labels.
DQN: Implements a deep Q-network baseline [MKS+15 15], using the NNConv architecture from PyTorch Geometric [FL19]. This model applies a message-passing GNN with edge- conditioned weights [GSR* + 17] to capture graph structure and node covariates.
OPTIMAL: Computes the action that maximizes the expected total discounted reward for each possible state via brute-force dynamic programming. This method is tractable only on small graphs due to the combinatorial explosion of the state space.
GITTINS: Our proposed method, described in Algorithm 1, which is provably optimal when the underlying graph g is a forest. We use breadth- firttt search (BFS) trees Line 5.
Since AFEG and these policies are agnostic to how the joint distribution P is defined, we defer the details of how P is defined to Appendix E. That is, one may read the experimental section assuming access to some P oracle. For reproducibility, all code is provided on our Github repository
4.1 Experiment 1: On tree inputs, GITTINS works well even in finite horizon settings
We evaluated the policies against a family of randomly generated synthetic trees on n E {10, 50, 100) nodes across various discount factors 8 E (0.5, 0.7, 0.9}. We only run OPTIMAL for small n = 10
on- graphs
7

---

instances, where the plots for OPTIMAL and GITTINS exactly overlap as expected. For = 10, we exactly compute the expectation by weighting accumulated discounted rewards of each of the 2 realizations by its probability. For E (50, 100), we compute Monte Carlo estimates by sampling 200 random realizations from P. For each setting of (n, 1), we generated 10 random trees and plot the mean (+: std. enr.) of the expected accumulated discounted rewards over time for each policy. Fig. 3 shows a subset of our results for 3 = 0.9; see Appendix for the full experimental results.
Expocted accumulatod discounted revares
Random
Greedy
DUNPolicy
Gittins ... Optimal
10 nodes, 0.9
50 nodes, , 0.9
100 nodes, f 0.9
Number of tests
Figure 3: Subset of synthetic tree imput results. GITTINS consistently beats other baselines at every fixed budget, c.g., vertical line indicates performance when only half the nodes can be acted upon.
Interestingly, while GITTINS only proven to be optimal with respect the expected accumulated discounted rewards, i.e., the rightmost slice of each plot, we see that consistently outperforms all other baselines every fixed timestep. For example, if we only have a fixed budget of being only to act on half the nodes (visualized by drawing a vertical line at the midpoint of the experiment), the GITTINS plot lies above the others.
4.2 Experiment 2: Gittins performance degrades gracefully for non-trees
Here, investigate the degradation of GITTINS as a heuristic as the input graph deviates from tree in a controlled manner. Using the same setup as Section 4.1, we see that the attained expected accumulated discounted reward of GITTINS degrades relative GREEDY as we add more edges to tree, as expected. Note that in the rightmost graph of Fig. 4, 10 additional edges is more than 20% additional edges compared to the original
49 tree edges.
Creedy
DOWNACY
(50 mode gmephe
fecter B-
edges
edges
edges
edges
edges
2
50
26
Figure 4: Synthetic experiment: the initial performance gains of GITTINS over GREEDY and DQN diminishes as we progressively add edges to 10 random 50-node trees with discount factor 3 0.9.
4.3 Experiment 3: Real-world sexual interaction graphs
Beyond experiments on synthetic graphs, we also evaluated the policies on real-world sexual inter- action networks derived from a de-identified, public-use dataset released by ICPSR [MR11]². This dataset was originally collected to examine how partnership networks influence the transmission of sexually transmitted and individuals (c.g.. whether the individual is unemployed or homeless, etc), and reported statuses for sexually transmitted diseases: Gonorrhea, Chlamydia, Syphilis, HIV, and Hepatitis.
infections. It includes reported sexual edges, covariates of each
"This de-identified, public-use dataset is publicly available for download at https: :/www. icpsr umi ch. wdw/veb/ICPSR//eeee stt.i// 222140 upon agreeing to ICPSR's terms of use. IRB is not required: see Appendix E.

---

For each disease, we fit parameters as described in Appendix C and use these parameters to define P for each AFEG instance on these real-world sexual interaction graphs. To be precise, we define P to be a pairwise MRF over the transmission network g, and P is parameterized by vectors 01 E TR22+2d and 02 E TR 1+45d where E N the the dimension of the covariates. Since the role of the discount factor 3 E (0, 1) in AFEG is to encourage early identification of infected individuals, any value in that range is technically valid. To better reflect practical scenarios where timely detection is important across the entire population, we use 3 = 0.99 in our experiments and report results in terms of fraction of positive cases detected. In Appendix E, we explain in further detail how we pre-process the dataset, produce joint distributions P for each graph for the experiments.
Our experimental results on real-worke graphs is given in Fig. 5. As these graphs are large, we do not run OPTIMAL and use 200 Monte Carlo simulations to estimate the expected performance of each policy. To enable evaluation on larger graphs while preserving network structure, we applied a principled subsampling strategy based on connected components to preserve topological properties of the original network more faithfully than node-level subsampling. For each disease-specific dataset, we randomly shufiled the connected components and then greedily aggregated them into new graph until the total number of nodes exceeded a specified threshold т. Due to the sparsity of the graphs, the resulting subsampled graphs contain approximately nodes as desired. To balance computational feasibility with dataset representativeness, we set T = 300. For the graph statistics of the full and subsampled real-world interaction graphs, see Table 1 and Table 2 in Appendix E.
Throughout all experiments, we consistently see that GITTINS outperforms or competitive with the other baselines both in terms of expected fraction of positive cases detected and for any fixed timestep, even when the input is not forest. For example, when limited to testing only half the population in the HIV experiment, GITTINS identifies nearly all infected individuals whereas other baselines detect only about 80%, in expectation. In terms of running time, observe that GREEDY and DQN become computationally intractable large real-world graphs.' DQN incurs significant training overhead due to fitting graph neural network for each (9, P,,) instance while GREEDY computationally expensive during rollout, requiring Σi= (n + 1) E O(n²) calls to the P oracle per Monte Carlo sample." 10 In contrast, GITTINS is efficient in both policy training (index computation) and rollout (selecting the frontier node with highest index), making it highly practical for real-world instances.
4.3.1 Noisy access to the underlying distribution
In practice, we do not have access to the true underlying distribution P. Instead, we would likely only obtain an noisy version Q of P and have to make adaptive testing decisions based on Q. Recalling P is parameterized by vectors 0₁ and 02, we define a noisy distribution Q. defined by noisy versions 01 and 02 of 0 and 02. where we add random noise that scales proportionally with the magnitude of each coordinate In the following experiments for 5 E {0, 0.25, 0.5, 0.75, 1}. That is, for a parameter value of æ, we add random noise of [-8x, Ex] to it. Fig. 6 illustrates the empirical performance of various policies on the HIV dataset when they only have access to Qe while the Monte Carlo evaluation and evolution of the statuses are based on P; see Appendix E for the plots for all the other diseases. Unsurprisinly, all policies degrade towards the performance of the RANDOM baseline as e increases since Qe becomes less informative with respect to the true underlying distribution P.
5 Conclusion and discussion
We introduced and studied the adaptive frontier exploration graphs problem (Definition 1), framework for sequential decision makiin with label-dependent rewards under a frontier exploration constraint. Our Gittins index-based policy (Algorithm 1) is provably optimal on trees, runs in polynomial time, and demonstrates strong
eeeegremiiiiiii empirical performance on general graphs.
$ AAll experiments were performed on a personal laptop (Apple MacBook 2024, M4 chip, 16GB memory). 9This is why we had to subsample up to 300 nodes when performing our empirical evaluation. RANDOM and GITTINS are able "0venn if we optimize the implementation of GREEDY to only recompute marginal positive probabilities for nodes in the same connected component as the previously tested node, it still incurs huge rollout time on graphs with large connected components. The timings in Fig. 5 are for this optimized GREEDY implementation.
fast on larger graphs but comparing only these two policies is interesting.

---

Groady
DONPaicy
Groedy
DONPolicy
Feet posttive canes detected
Policas with 9- 0.99
Gonorhee sex interection graph
Polic with f 0.99
Chiamydia sex interaction graph
Frontier tircled
Frunbir circled
Fraction population
Ransom -.- Greedy
DOMPolicy
Gitinn
Random
--* Greedy
DQWPolicy
Gittins
Syphilis interaction graph
interaction graph
Thert onettonn posetive coves denee
pa nettooed
Frontler roots are circled red
Frontler roots are circed in
Praction poculstonn tested
Fraction of pocuiation tosted
Cready
DQNPPllicy
Time, rounded to nearest second
Gonerrhea
Chlanydia
Syphilis
HIV
Heparitis
Treetoon pos tive caren detected
Policies with
Hopatitis sax Interaction graph
RANDOM
0
0
0
GREEDY
0
DQN
2197
GUTTINS
8
32
24
RANDOM
0::00
0::00
0=
0=
0:::0
GREEDY
12:1:0
10.10
1164
810 1.3
15
DQN
GITTINS
0.2:0
0:::0
Top: Policy training time, trained once all 200 rollouts
Bodiom: Single Mosse Carlo millont time, reported in mein + std. err.
population teated
Figure 5: Experimental results for Gonorrhea, Chlamydia, Syphilis, HIV, and Hepatitis from sub- sampling connected components till we have at least 300 nodes. The vertical dashed line indicates performance when only half the individuals can be tested.
Policions with f 0.99
DONPulcc
(A Cander over 16 nun)
0.25
Fraction of population tested, Vertical detted lines Indicate 25%, 50% and 75% percentage of total population being bostod.
Figure 6: Experiments on the HIV dataset where policies only have access noisy version Q. of the underlying distribution P on the HIV dataset. Error bars illustrate the standard error due to 10 random instantiations of Q. for each corresponding value of e.
Broader impact and fairness. This work is motivated by public health challenges, where limited resources and reduced funding [UNA25] highlight the need for more efficient testing strategies. The AFEG framework supports targeted, adaptive exploration of interaction networks, guided by joint distribution P can incorporate domain knowledge. It also enables fairness-awe aware interventions through reward shaping, allowing practitioners to prioritize specific subpopulations within the same decision-making framework. Our proposed Gittins index-based policy operates within this flexible setup, making suitable for responsible and context-aware deployment. Additional discussion of limitations and fairness considerations is provided in Appendix D.
10

---

Acknowledgments and Disclosure of Funding
This work was supported by ONR MURI N00014-24-1-2742. The findings and conclusions in this report are those of the authors and do not necessarily represent the official position of the WHO. Davin would like to thank Bryan Wilder, Amulya Yadav, and Chun Kai Ling for their nhought-provoleee technical discussions, and Eric Rice, Geoff Garnett, Samuel R. Friedman, and Ashley Buchanan for generously sharing their domain expertise on HIV testing and transmission.
References
[ADGR * 19] Lucie Abeler-Dönee Dörner, Mary K. Grabowski, Andrew Rambaut, Deenan Pillay, and Christophe Fraser. PANGEA-HIV 2: Phylogenetics And Networks for Generalised Epidemics Africa. Current Opinion in HIV and AIDS, 14(3):173-180 2019.
[AKN06] Pieter Abbeel, Daphne Koller, and Andrew Y. Ng. Learning Factor Graphs in Polynomial Time & Sample Complexity. Journal of Machine Learning Research (JMLR), 7:1743- 1788, 2006.
[Bes75] Julian Besag. Statistical Analysis of Non-Lattice Data. Journal of the Royal Statistical Society Series D: The Statistician, 24(3):179-195, 1975.
[BMKK 21] Basmattee Boodram, Mary Ellen Mackesy-Amiti Aditya Khanna. Bryan Brickman, Harel Dahari, and Jonathan Ozik. A meta-analysis of 20 years of data on people who inject drugs in metropolitan Chicago to inform computational modeling. medRxiv preprint, 2021.
[BMS04] Peter S. Bearman, James Moody, and Katherine Stovel. Chains of Affection: The Structure of Adolescent Romantic and Sexual Networks. American journal of sociology, 110(1):44-99) 91, 2004.
[BPP+ 18] Benjamin R Bavinton, Angie N Pinto, Nittaya Phanuphak, Beatriz Grinsztejn, Garrett P Prestage, Iryna B Zablotska-Manos, Fengyi Jin, Christopher K Fairley Richard Moore, Norman Roth, and al. Viral suppression and HIV transmission in serodiscordant male couples: an international, prospective, observational, cohort study. The Lancet HIV, 5(8) e447, 2018
[CCM+11] Myron S. Cohen, Ying Q. Chen, Marybeth McCauley, Theresa Gamble, Mina C. Hosseinipour, Nagalingeswaran Kumarasamy, James G. Hakim, Johnstone Kumwenda, Beatriz Grinsztejn, Jose H. S. Pilotto, and et al. Prevention of HIV-1 Infection with Early Antiretroviral Therapy. New England journal of medicine, 365(6):493-50) 505.999555500000 2011.
[Cli90] Peter Clifford. Markov Random Fields in Statistics. Disorder in physical systems: volume in honour of John M. Hammersley, pages 19-32, 1990.
(CLJ+24) Annabelle Choong, Yi Ming Lyu, Cheryl C. Johnson, Rachel Baggaley, Magdalena Barr-DiChiara, Muhammad S. Jamil, Nandi I.. Siegfried, Christopher K. Fairley, Eric F. Chow, Virginia Macdonald, and Jason. Ong- Social network-based approaches to HIV testing: systematic review and meta-analysis. Journal of the International AIDS Society (JIAS), 276))33 2024.
[CM14] Jhelum Chakravorty and Aditya Mahajan. Multi-Armed Bandits, Gittins Index, and Its Calculation. Methods and Applications of Statistics in Clinical Trials: Planning. Analysis, and Inferential Methods, 6-:41-4455,. 2014.
[Ew 19] James Edwards. Practical Calculation of Gittins Indices for Multi-armed Bandits. arXiv preprint arXiv:1909.05077 2019.
[FHA+98] Homayoon Farzadegan, Donald R Hoover, Jacqueline Astemborski, Cynthia M Lyles, Joseph B Margolick, Richard B Markham, Thomas C Quinn, and David Vlahov. Sex differences in HIV-1 viral load and progression to AIDS. The Lancet, 352 151001551 1998.

---

[FL19] Matthias Fey and Jan E. Lenssen. Fast Graph Representation Learning with Py- Torch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[GGWI1] John Gittins, Kevin Glazebrook, and Richard Weber. Multi-armed Bandit Allocation Indices. John Wiley & Sons, 2011.
[Git74] John Gittins. dynamic allocation index for the sequential design of experiments. Progress in Statistics, pages 241-266, 1974.
[Git79] John C. Gittins. Bandit Processes and Dynamic Allocation Indices. Journal of the Royal Statistical Society Series B: Statistical Methodology, 41(2):148-164, 1979.
[GKI1] Daniel Golovin and Andreas Krause. Adaptive Submodularity: Theory and Ap- plications in Active Learning and Stochastic Optimization. Journal of Artificial Intelligence Research (JAIR), 42:427-486, 2011.
[GKX+12 12] Roman Garnett, Yamuna Krishnamurthy, Xuehan Xiong, Jeff Schneider, and Richard Mann. Bayesian Optimal Active Search and Surveying. In International Conference on Machine Learning (ICML), page 843-850, 2012.
[GS09] Sharad Goel and Matthew J. Salganik. Respondent-driven sampling as Markov chain Monte Carlo. Statistics in Medicine, 28(17):220--222, 2009.
[GSR 17] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural Message Passing for Quantum Chemistry. In International Conference on Machine Learning (ICML), pages 1263-1272, 2017.
[HC71] John M. Hammersley and Peter Clifford. Markov fields on finite graphs and lattices. Unpublished manuscript, 46, 1971.
[Hec97] Douglas D. Heckathorn. Respondent-Drive Sampling: A New Approach to the Study of Hidden Populations. Social Problems, 44(2):174-199, 1997.
[Jay57] Edwin T. Jaynes. Information Theory and Statistical Mechanics. Physical review, 106(4):620, 1957.
[JM+ 18] Shali Jiang, Gustavo Malkomes, Matthew Abbott, Benjamin Moseley, and Ro- man Garnett. Efficient nonmyopic batch active search. In Advances in Neural Information Processing Systems (NeurIPS), pages 1099-1109, 2018
[JCC 17] Shali Jiang, Gustavo Malkomes, Geoff Converse, Alyssa Shofner, Benjamin Mose- ley, and Roman Garnett. Efficient Nonmyopic Active Search. In International Conference on Machine Learning (ICML), pages 1714-1723. 2017.
[JPC 19] Makhahliso Jubilee, Faith Jiyeong Park, Knowledge Chipango, Kenoakae Pule, Albert Machinda, and Noah Taruberekera. HIV index testing improve HIV positivity rate and linkage to care and treatment of sexual partners, adolescents and children of PLHIV in Lesotho. PLoS One, 14(3)=e0212762 2019.
[JSK + 17] David Juher, Joan Saldaña, Robert Kohn, Kyle Bernstein, and Caterina Scoglio. Network-Centric Interventions Contain the Syphilis Epidemic in San Francisco. Scientific reports, 7(1):6464, 2017.
[KF09] Daphne Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT press, 2009.
[KFH06] Don Klinkenberg, Christophe Fraser, and Hans Heesterbeek. The Effectiveness of Contact Tracing in Hmerging Epidemics. PloS One, 1(1):e12, 2006.
[KK14] Matan Keidar and Gal A. Kaminka. Efficient frontier detection for robot exploration. The International Journal of Robotics Research (IJRR), 33(2):215-236, 2014.
12

---

[KKTO3] David Kempe, Jon Kleinberg, and Eva Tardos. Maximizing the Spread of Influ- ence through Social Network. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 137-146, 2003.
[KO03] Godfrey Keller and Alison Oldale. Branching bandits: sequential search process with correlated pay-offs. Journal of Economic Theory, 113(2)300--315, 2003,
[KV187] Michael N. Katehakis and Arthur F. Veinott Jr. The Mrlti-Armed Bandit Problem: Decomposition and Computation. Mathematics of Operations Research, 12(2):262- 268, 1987.
[LC Chun Kai Ling, Jakub Cerny, Chin Hui Han, Christian Kroer, and Garud lyengar. How Deep Is Your Defense-in-Deptte Hardening Cybersecurity Network Control Against Adaptive Attackers. AAAI 2025 Workshop on Artificial Intelligence for Cyber Security (AICS), 2025.
[MGDGO25] Heather Mattie, Ravi Goyal, Victor De Gruttola, and Jukka-Pekka Onnela. A Review of Network Models for HIV Spread. Journal of Acquired Immune Deficiency Syndromes (JAIDS), pages 309-320, 2025.
[MK23] Michela Meister and Jon Kleinberg. Optimizing the order of actions in model of contact tracing. PNAS Nexus, 2g3)ppg 2023.
[MKLL12] Benedict C. May, Nathan Korda, Anthony Lee, and David S, Leslie. Optimistic Bayesian Sampling in Contextual- Bandit Problems. Journal of Machine Learning Research (JMLR), 13(1):2069-210 2012.
[MKS* 15] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, and et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529 53335993553--1- 2015.
[MR11] Martina Morris and Richard Rothenberg. HIV Transmission Network Metastudy Project: An Archive of Data From Eight Network Studies, 1988-2001 (ICPSR 22140). ICPSR Data Holdings, 2011. Available at https: /twp::///www... icpar. umich. edu/ wwwp//ccss/sttuies/ssssessss 2214: 20222114//mmmrrry summary.
IMBDDM 25] Aliza Wonroe-Wise, Magdalena Barr-DiChiara, Antons Mozalevskis, Busisiwe Msimanga, Maeve Brito de Mello, Kafui Senya, Niklas Luhmann, Cheryl Case Johnson, and Rachel Baggaley. Can network-based testing services have an impact beyond testing for HIV? Sexual Health, 22(2), 2025.
[Nat] United Nations. Goal Good Health and Well-being Targets and Indicators. Avail- able at https://sdgs un org/ goals/ haalss/goalltt goall#t and indicators.
[oAD19] National Institute of Allergy and Infectious Diseases. uctabl==Untansmittabe (U=U), or Treatment as Prevention, 2019. Available at https: //ww:. httpp://wwww.iidddd............t nih, www/diseasss- condittoooooiiiio///oooooooco treatment-preventionn
HIV Unde-
[OG20] Rose McKeon Olson and Robert Goldstein. ing stigma and empowering people living with HIV, 2020. https://www. health harvard .ew.arddddu/bblgg////o uu- ending-stigma Low.
U=U: End-
Available
at
[Org24a] World Health Organization. Consolidated guidelines on differentiated HIV testing services. World Health Organization, 2024. Available at https: //tp::///wwwww.. who. int/
[Org24b] World Health Organization. HIV and AIDS: Fact Sheet, 2024. Available at https://wwer who http:///wwwww.loiiiaaaearrroooa/ fact- ceaitts/ettal//iiii
[Put14] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic
Programming. John Wiley & Sons, 2014.
13

---

[RCB 16] Alison J. Rodger, Valentina Cambiano, Tina Bruun, Pietro Vernazza, Simon Collins, Jan van Lunzen, Giulio Maria Corbelli, Vicente Estrada, and al. Sexual Activity Without Condoms and Risk of HIV Transmission in Serodifferent Couples When the HIV-Positive Partner Is Using Suppressive Antiretroviral Therapy. JAMA, 316(():171-181, 2016.
[RN21] Stuart Russell and Peter Norvig. Artificial Intelligence: Modern Approach. Pearson Education, 4th edition, 2021.
[Rot09] Richard Rothenberg. HIV transmission networks. Current Opinion in HIV and AIDS, 4(4):260- 2600000266,2220 2009.
[Sco10] Steven L. Scott. A modern Bayesian look the multi-armed bandit. Applied Stochastic Models in Business and Industry, 26(6):639-658, 2010.
[Scu18] Eileen P. Scully. Sex Differences in HIV Infection. Current HIV/AIDS Reports,
15: 15:136-146, 2018.
[SMSM99] Richard S. Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy Gradient Methods for Reinforcement Learning with Function Approximation. In Advances in Neural Information Processing Systems (NeurIPS), page 1057-1063, 1999.
[Tsi94] John N. Tsitsiklis. A Short Proof of the Gittins Index Theorem. The Annals of Applied Probability, pages 194-199, 1994.
[UNA22] UNAIDS. Political Declaration HIV and AIDS: Summary of 10 Targets, 2022. Available at https://www. unaids org/ //t////eeerreee//eeeeee /oc.eeetssdduccs/////cm.e 2022/poli http://pllttiaa-eeelaaaattt....p swwpraryiionuurar---aooa targesss
[UNA24] UNAIDS. 2024 global AIDS report The Urgency of Now: AIDS at Crossroads,
2024. Available at https: htpp:://www... http//wwwm/tt una.ds. www.ia..anggaaa........... www//eeoouree//occuuuuu
9024/global-aids-ppeee 2024.
[UNA25] UNAIDS. Impact of US funding cuts on the global AIDS response - 28 March 2025 update, 2025, Accessed: 28 April 2025.
[WD92] Christopher J.C.H. Watkins and Peter Dayan. Q-Learning, Machine Learning, 8:279-292, 1992.
[Web92] Richard Weber. On the Gittins Index for Multiarmed Bandits. The Annals of Applied Probability, pages 1024-1033, 1992.
[Wei88] Gideon Weiss. Branching Bandit Processes. Probability the Engineering and Informational Sciences, 2(3):269-272) 1988.
[WGS13] Xuezhi Wang, Roman Garnett, and Jeff Schneider. Active Search on Graphs. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 731-738, 2013.
[Whi80] Peter Whittle. Multi-Armed Bandits and the Gittins Index. Journal of the Royal Statistical Society: Series B (Methodological), 42(2):143-149, 1980.
[WJ08] Martin J. Wainwright and Michael I. Jordan. Graphical Models, Exponential Families, and Variational Inference. Foundations and Trends@ in Machine Learning, 1(1-2):1-305, 2008
[WKPF+ 17] Joel O. Wertheim, Sergei L. Kosakovsky Pond, Lisa A. Forgione, Sanjay R. Mehta, Ben Murrell, Sharmila Shah, Davey M. Smith, Konrad Scheffler, and Lucia V. Torian. Social and Genetic Networks of HIV-1 Transmission in New York City. PLoS Pathogens, 1006000, 2017.
14

---

[WLK 23] Leslie D. Williams, Eunhye Lee, Kathleen Kristensen, Mary Ellen Mackesy-Ane Amiti, and Basmattee Boodram. Community- Network-, and Individual-level Predictors of Uptake of Medication for Opioid Use Disorder among Young People who Inject Drugs and Their Networks: Multilevel Analysis. Drug and Alcohol Dependence, 244:109782, 2023.
[WOVH" 18] Bryan Wilder, Laura Onasch- Vera, Juliana Hudson, Jose Luna, Nicole Wilson, Robin Petering. Darlene Woo, Milind Tambe, and Eric Rice. End-to-End Influence Maximization the Field. In International Conference Autonomous Agents and Multiagent Systems (AAMAS), pages 1414-1422, 2018.
[Wul2] Nailong Wu. The Maximum Entropy Method, volume 32. Springer Science & Business Media, 2012.
[XFL*21] Yang Xiang, Kayo Fujimoto, Fang Li, Qing Wang. Natascha Del Vecchio, John Schneider, Degui Zhi, and Cui Tao. Identifying influential neighbors in social networks and venue affiliations among young MSM: a data science approach to predict HIV infection. AIDS, 55:$65-S73 2021.
[Y]M*13] A. M. Young. A. B. Jonas, U. L. Mullins, D. S. Halgin, and J. R. Havens. Network Structure and the Risk for HIV Transmission Among Rural Drug Users. AIDS and Behavior, 17(7):2341-233 2013.
[YWR* 17] Amulya Yadav, Bryan Wilder, Eric Rice, Robin Petering, Jaih Craddock, Amanda Yoshioka-Maxwell, Mary Hemler, Laura Onasch- Vera, Milind Tambe, and Darlene Woo. Influence Maximization in the Field: The Arduous Journey from Emerging to Deployed Application. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 150-158, 2017.
[ZLG03] Xiaojin Zhu, John Lafferty, and Zoubin Ghahramani. Combining Active Learning and Semi- supervuped Learning Using Gaussian Fields and Harmonic Functions. ICML 2003 Workshop on The Continuum from Labeled to Unlabeled Duta, 2003.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Experimental results given in Section 4. Full proof' given in Appendix F and further experimental results are given Appendix
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss limitations in Appendix D
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

Justification:
Full proofs are given in Appendix F
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide our code in the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
17

---

Answer: [Yes]
Justification: We provide our code on Github. However, we do not release the ICPSR dataset used in Section 4, accordance to the terms of use. Interested researchers can individually obtain the de-identified public-use dataset at https: //wps::/www../ www.wicpaaee iiparrpr...... umi edu/web/ICPSH wtt.II/////uuis///22222 after agreeing with their terms of use.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //ipp..cccccc /pwps.cccppullcc/eee.ec http:/publccgguudeeeeeee /CoeeS/ ismiissiie cniooiic) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We give experimental details in Appendix E and also provide our code on Github.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification:
We draw standard error bars in our plots where suitable.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
18

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All experiments were performed on a personal laptop (Apple Macbook 2024, M4 chip, 16GB memory).
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics attpp://neurre cttp:ppp.cppppppppe hctppullic/thhccccteeeeeeeeeeeee
Answer: [Yes]
Justification:
We read and follow it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss this in Section and in Appendix D.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
19

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification: We do not release the ICPSR dataset used in Section 4, as accordance to the terms of use. Interested researchers can individually obtain the de-identified public-use dataset at https: / //www icpar. umi ch. Cttp//ICSSS///ttteee ealuuieeee2240000 22140 after agrecing with their terms of use.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We cited the ICPSR dataset used in Section 4, as accordance to the terms of
use.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
20

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datastss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does involve crowdsourcing or research with human subjects. relies solely on secondary analysis of de-identified public-use dataset.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
supplemental material is fine, but if the main contribu-
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The de-identified, public-use dataset used in Section 4 is publicly available for download at https://wwe icppr. umi ch, aat///eb/IC/ http///tudiese/211112 upon agreeing to ICPSR's terms use. IRB approval was not required.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
21

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We only use LLM to improve the writing of some sentences.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: httpp:://neuripass ct/ / for what should or should not be described.
22

---

A Further related work
Markov Random Fields (MRF). By the Hammersley- theorem [HC71, Cli90], an MRF has the form: P(x) ž IIce (x(x)), where C is the set of cliques in G. VC is a non-negative potential function over clique C, X is the realization nodes in C, and Z is the normalizing constant. Altemntively, MRFs can be represented using factor graphs, which are bipartite graphs connecting variable nodes to factor nodes. Each factor fy maps a subset X, of variables to a non- negative value. The joint distribution is then P(x) = Ž II (x,). While both representations are equivalent, factor graphs make inference structure explicit and are often used in algorithmic implementations. Exact inference in MRFs is known to be intractable in general, with complexity scaling exponentially in the treewidth of 9 [WI08, KF09J. While the definition of AFEG is does not necessitate the use of MRFs in general, any joint distribution P that is Markov with respect to G works, we find that it is a reasonable model in our disease testing application (Section 1.1) where real-world sex interaction graphs are often of low treewidth (see Section 4).
Reinforcement learning (RL). Sequential decision- decision-making classically modeled using Markov decision processes (MDPs) [Put14], and solved using reinforcement learning (RL) techniques. Promi- nent algorithms include Q-learning [WD92], policy gradient methods [SMSM99], and deep RL approaches like deep Q-networks (DQN) IMKS 15]. In principle, AFEG can be cast as an MDP, but doing so leads to an exponentially large state space: the agent must track both which nodes have been selected and their revealed labels. This complexity makes direct application of off-the-shelf RL methods impractical in our setting with customization and heavy finetuning.
Active search on graphs. As discussed in Section 1, AFEG is related to active search on graphs [GKX* 12, WGS13, JMC 17, JMA* + 18]. which aims identify as many target nodes as possible under a budget. However, these works do not impose frontier constraint while searching over binary labels, and typically assume a relaxed Gaussian random field model [ZLGG3] for tractable inference. In contrast, our formulation models the joint distribution explicitly as an MRF While exact inference generally intractable, many real-world graphs - especially sexual contact networks have low treewidth, making structured modeling with MRFs feasible in practice (see Section 4).
Influence maxinization. Another well-studied sequential decision problem on graphs is influence maximization, where the goal is to select seed nodes to maximize influence spread under stochastic propagation models such as the independent cascade or linear threshold [KKT03]. This framework has been applied to health interventions, such as selecting peer leaders to disseminate information in HIV prevention efforts among homeless youth [YWR 17, WOVH 18]. While both influence maximization and AFEG involve decisions on graphs, their objectives differ: the former focuses on maximizing long-term diffusion, whereas AFEG emphasizes label-driven, reward- maximiiini sequential actions under uncertainty and exploration constraints.
Network-based HIV testing and transmission modeling. HIV transmission dynamics have been extensively studied through network-based models, where individuals are represented as nodes and edges denote reported sexual or social contacts [Rot09, MGDGO25). Such networks can constructed from contact tracing, respondent-driven sampling (RDS), or molecular surveillance data [Hec97, GS09, ADGR + 19]. While existing research have used methods such as generalized estimating equations, mixed effects regression, graph attention networks have been used to fit transmission probabilities using parameters [BMAK* MMAK+21. 21, WLK+ XFL+21], they do not model and consider the sequentiality of assigning tests to individuals.
B Worked example of Gittins computation for branching bandits
Recall the recursive formulas of & and & for the Gittins index computation, from Eq. (1) and Eq. (2) respectively. For convenience, we reproduce them below. For 0 S m S T-3
@x,((m) = max m, Σ P(X= = Pa(X) =) b) [r(X,)) + (0Cm
veft
Ody. 2k
dk I +
$s.((m) =
I-3
mm
lYes
m7
if S
23

---

These (x))(m) values, for all labels b E S2, can be pre-computed before we execute our Gittins method via recursion from the leaves. Then, the corresponding Gittins value for node X given realized parent value of b E Ω is simply min(m E [-3 @x,(m)) 2 m.)
In the rest of this section, we will work through the Gittins index computation on the rooted tree (X, E) shown in Fig. 7 with 3 0.9 and the following joint distribution
P(X = x) = Z
II exp (1 (X,,X;)EE
where Z is the normalizing constant and 1zu=zz is the indicator function of whether the realized values of X; and X, agree. In terms of our pairwise MRF representation, P can be represented with Qunary (0,0) 0) and pairwise (0, 1, 0, 1). For non-root node X E X, we have
P(X Pa(X) = 0) 1+e
(5)
P(X Pa(X) = 1)
(6)
With 8 = 0.9 and F = 1, we have 0 - m S
F
= 10.
1-3
Xo
X1
X2
X3
Figure 7: Example rooted tree = (X, E) over 4 nodes X = (Xo, X1, X2,
B.1
Computing @ for leaf nodes
Consider leaf node X3. For S m S I-3-
Φxg,o(m) max m, PX33 0 X, = 0) [r(X3, 0) + o
+P(33 1| X₂ 0) [r(Xa, + 34. (m)]
m. (1- (1-1te) - [r(Xs, 0) + 300,0(mm +
max
1 (+te)
[r(Xss 1) 30 [m)]
(By Eq. (5) and Eq. (6)
(1t))
max m. 1
10 + 6ml + (ite)
[1 + 3m]
1 +
(By definition r and since T (m) = (m.) = m)
= max
m, 3m +
1 1+e
In other words, we have
Bm T46
if <
10
xx..0(m)
Tte
m
if m
2
T46
10
By similar computations, we obtain
Bm +
if
@x,. =
Ite
Ite
m
if m 2
1tc
10c
24

---

Fig. 8 illustrates the piecewise functions Φx,.0 and @x,.1 To represent these functions efficiently, we can track the changepoints and the linear pieces. For instance, the changepoint _10 in @x the changepoint 10c in 1x I. and the slope coefficient and intercept in the y equation formula.
I+e
linear
Itc
Piecewise linea function ox,
Precewise linear function 6x ((m)
10
10
y
y
0,9m IFc
y - 0.9m
14c
10e
y olm)(m)
y= 99,,,
10
112
1.00
10
1+6
148
Figure 8: Illustration of the piecewise linear functions xx and @xa,1
By symmetry of P in our example, one can check that 0x,,0 xx o and ox,,1 0x211
B.2 Computing @ for non-leaf nodes
Now, let consider the non-leaf node X2. For S m S I-3-
(m))0(m) = max m. P(X, 0 X, = [rrrrr(2,),,) 0) - 3 [xsho(m)]
PP222
Xy = -) [r(X2, 1) + 3 (Xs). }
11111 max m. (1- 1--1te) ) [0+ 3 [m) +
[1 + 8 (xa). [x))
1
(By Eq. (5), Eq. (6), and definition of r)
Let us compute the function c ((xa).((m) Observe that
T ((xs).((m)
F
II
(ky
dk 10
d 0 dk S
10
Ök
Ok
YE(Xa)
Fig. 9 illustrates the piecewise linear function oxx.0 and corresponding piecewise constant function
(oxx.o()) Meanwhile, Fig. 10 shows visualization of & (x,).0 (m) 10
10
dk.
0k
Piecewise linear function o(R)
Piecewise constant function Ab
4h. d1
y 0.9k
Ox, olk)
0.9
114 0
16
10
0
10
10
0o o o(k)
Figure 9: Illustration of the piecewise linear functions Φx and
8h
25

---

Arca under from =
Area under Maaal from
Arca under
from k
4oa almb - 10- [ 1 dk
(
Pipu. of40
1.10094
Figure 10: Visualization of 4 ((xs).0(m) 10
10 Bixx
o (R)
dk
0k
In order to efficiently compute and represent + (Xa). (m)) we turn to Proposition 5: $ (xx).o & ((x,).0 (0) + h(m), for some piecewise linear function h. Observe that ((x)),0 is just constant while we showed in our proof that h((m) - o(k) dk. Intuitively, the idea is to first
0k
compute h(m) by integrating (k) over the entire domain range of 0 S S 1-3 then 8k "push the curves upwards" until the maximum value hits T-8- For our example, one can compute $ (xx)). (0) = (1 B) Ite
10 and derive that
{ (o(xs),0(0) + 3m
if m S
10 I+c
$ (xx))o(m)
((xsst.(0) + m
if m 2
10
T+c
See Fig. 11 for an illustration.
Mooceise constant function tb. MlI
110
Piecewise functior 1
10
Osen (IT) - of0 +im))
0.9
U08
0pi. a/01
172
10
172
10
172
10
Figure 11: Illustration of how to apply Proposition to compute & ((xx),u(m)
Using Proposition 5 in a similar manner for (1xx),.1m) (m), we get 1 (x,),1 (0) (1 - (3
10e and
Ite
(1(xs). + 3m 2 ((xs)). + m
if m <
10c
T (Xss) (m)
m 2
10e
Ttc.
Continuing our calculations from above, we see that Φxx.0 max(m,, fx,.0 (m)), where
fxa.0mm) = 1 1
[+e) [o + 3 (m))
+
[] + 3 (xx).
1 1
18 + 3(1 - (1+e)z
20c
+
i - Itc
10
Itc
Ite + 3(1 - 99 [1+e}=
10c
1
if Ite
10
< m
10c
Tte
Itc
3m + Itc
if 2 10c
Itc
So,
xx2,0(m)= max (m, (m))
33 + 3(1 - B) 20c +
(1+ejz Ite
1
if m < Itc
e9 Ite m + 3 - () [1+0)=
10c + T
if 10.
< m v
8(1 8)
(1+0) + 14c
10
Ite
102
1+
if m
8(1 8
2
10c
FIT
26

---

The piecewise function (m) can be computed in the same way.
8pmm + B(1 B)
10:1+e" (I+c)*
if m
10 Itc
Itc
8(1-8) 8) 10c2
(x)) =
Ateg² Ite + 3(1 ()
[Ite]² +
10
I-c
if 10
Itf
I <
1- 1T
[1 1
3(1- 0]
10.2
m
if m
[++03
1443
146
Finally, for labels b L2 compute 6x,.6 b in similar fashion, with the only non-trivial computation being II IYECk(X.) (ky,.(k) dk, where Ch(X)) = [2} and E Ω. Here, we take the product ak of the corresponding piecewise constant functions before integrating it to obtain the corresponding piecewise linear function h(m).
B.3 Bounding the number of pieces
Throughout our computation, we relied heavily on the fact that the recursive functions & and & can be computed by manipulating piecewise linear functions. Here, show that the number of pieces we need to manipulate scales reasonably with the size of the input rooted forest g = (X, E). A key part of the proof relies the following observation:
Observation Multiplying by constants, adding constants, differentiation, and integration do not affect the number of changepoints in piecewise linear functions.
Towards formal proof, let us define some additional notation. For any node X X. let Tx denote the subtree rooted at X and |xx| denote the number of nodes in this subtree, excluding X itself. Meanwhile, for any piecewise linear function f. we write e(f) and #(J) to denote the set and number of changepoints required to represent f respectively, i.e., #()) (e(s)]. That is, # counts the number of cases in the function representation, minus 1. For instance, #(xx,) I 1 for any leaf node X E X due to the maximization against the linear function y m.
Lemma 8. For any arbitrary node E and label E St we have #(xx)) S 1 | Txx
Observe that the upper bound of Lemma is independent of the actual label b E Ω. The intuition behind this independence been in Eq. (1) where b only affects a multiplicative scaling via the conditional distribution value, which by itself does not affect the number of changepoints: see Observation 7. An important implication of Lemma is that the maximum number of changepoints we ever need to manipulate for rooted tree rooted at Xyoot in G is at most [S2] X
Proof of Lemma 8, We prove the claim by induction over the tree structure, starting from the leaves. Base case (X is a leaf node): Then, Ch(X) = 9 and #(xx a) S 1.
Inductive case (X is non-leaf node): Recall Eq. (1) and Eq. (2) for Ch(X) + 0:
(x,((m) = max
m
Σ
P(X = Pa(X) = b) [r(X,0) + 3 [X
eeft
1-
(ky, dk
(CL(x),((m)) =
3
Ok
YECh(X)
- Pa(X) =) [r(X,)) + BBCx(x).. we can rewrite (x,((m) as &x (x)) = max (m. Σ Es o (m)) For any two distinct labels b, 8' E Ω Ob- servation tells that the set of changepoints Φx and Φx,w differ by at most one, depending on depending on where the intersection y occurs for each label. That is,
Defining Ix (m)
|s(xx,) (((xx)) 51
(7)
27

---

So,
))
#(dx,)) {max] m, Σ gx
(By Eq. (1))
veR2
21+ # Σ 9x
(Due maximization with y m)
=1+ # (gx
# (PC)(X)..)
(By Observation 7)
=1+ U
U
# #
(By Eq. (2))
(X)
=1+ U
U
#(0r,e)
(Switching the ordering of the unions)
YECH(X)VER
U
[2 - + max NEE2
# #(dr;.))
(Applying Eq. (7) over all [2] labels)
(eCh(X)
51+ Σ
(1S2) - (1+ + |S2| [Ty)))
(xC
(By induction hypothesis and replacing U with D
= =1+ [ Σ
(1+ ITl)
(Rearranging)
YεCh())
[2] Txl
(By definition of [xxl and (yy)
C Application to network-based disease testing
In this section, we explore the application of network-based disease testing motivated in Section I where the goal is to identify infected individuals given knowledge of their interaction network; see Fig. for illustration. Here, each node represents an individual with binary infection status (infected or not), and edges represent sexual interactions. Frontier testing is a natural operational constraint: test outcomes significantly influence beliefs about neighboring individuals, making it efficient to expand testing along the observed frontier.
Building upon our notations in Section 2, a joint distribution Po parameterized by 0 is written as (x(x) = PX = I1,...,
... X, x,,) for Ω
C.1 MRF-based joint model of infection status
We model the joint distribution over n individuals' infection statuses using a pairwise MRF defined the interaction graph G (X, E), where each node X; represents individual with binary latent variable X; E {0, indicating its HIV status, and each edge (X,,X) E E indicates reported sexual interaction. Each individual also has associated covariates c! E Rd and the joint distribution over all statuses X (X1...., X.,) is defined in terms of unary and pairwise potential functions (I,)) for each individual i, and di,(I,, for each edge {i.}} E E, with
1 < < j S "1:
(1:.)) = exp (T (1 e)) and (x,,) exp (0) f2 f2 J. cl0) c(),6()))
for some feature mapping functions fi {0, x pd 22+2d and f2 {0, 1)2 x 2d - 4++ and parameters 0, E 2 24 and 82 E R44 We adopt the maximum entropy principle [Jay57,
!l For notational simplicity, write fa(o,, 2i, ct), ()) mean f2(21, 2,, " c(0)) for any i j.
28

---

wJ08, Wu12] to parameterize these factors, with feature maps fi and fz defined as monomials up to quadratic terms of the covariate variables while respecting symmetry:
f1(2,, (1. -,,, 21, ac of (..ccf))
R2+2d
(8)
15, ,00,)) -1,,0100,, xe)ar + x;(11 xz), (1 - ri)(1 - -zj);
2, cf (6) ,r,, _(()) R4+5d (9)
where v:
: 10, x R² + 12 is defined as
b,,, c+ ditddable ablcaalcctt a) (1- (1- (1aa)((--))))
The joint probability is then:
a exp Σ
Po, 0g (X =X
[T)
Σ (. {iJ}EE
(10)
2(01, 02)
where z(0,, 02) is the partition function. This formulation encodes both individual risk via covariates and dependency via pairwise interactions, capturing correlation in infection status across the network. To reduce model complexity and reflect data limitations, we use parameter sharing, i.e. all unary (resp. pairwise) factors share the same parameters 0, (resp. 02). Although exact inference in general MRFs is intractable, the sexual contact networks we consider are typically sparse, bipartite, or even tree-structured as contact tracing studies where efficient inference algorithms apply [KF09]. Therefore, we assume access to an inference oracle, and focus on the primary challenge: adaptive sequential testing under frontier constraints.
At each time step t = {1. n.. we select an untested individual to test on the frontier and observe their HIV status. Recalling the definition of A FFEG (Definition 1), we can model the interaction network as G. and each test as acting on a node in G. The reward function for testing individual X and revealing status b {0, 1} is simply r r(X, b) b. and any discount factor /3 (0, 1) would encourage identifying HIV+ individuals as early as possible. Importantly, discounting reflects both practical constraints such as sudden funding cuts [UNA25] and clinical importance of early diagnosis, which improves patient outcomes and limits transmission [CCM+ 11]. See also [RN21] for other natural justifications for using discount factors 3 in modeling long-term policy rewards. Finally, to apply the infinite horizon framework of AFEG in our finite testing setting, we simply zero subsequent rewards after every individual has been already tested.
C.2 Learning the distributional parameters from data
To apply our model to a new population with unknown HIV statuses, we must first estimate the parameters of the joint distribution described in Appendix C.I. We assume access historical dataset in which both the covariates and true HIV statuses are known. Classical approaches to MRF parameter learning such as [AKN06] typically assume access to multiple independent samples drawn from a fixed graphical model. Unfortunately, in our case, we only have access to only single observed realization of infection statuses in our past data. This means that the maximum likelihood estimation (MLF) distribution P that describes the dataset is simply the degenerate point distribution that places full probability mass on the single realization.
To learn a mcaningful but non-degenerate transmission probabilities, we consider an intuitive way to model the joint probabilities based on factor graph induced by the input graph structure. More specifically, we define unary factor potentials for each individual node and pairwise factor potentials for each edge present in the graph, governed by global parameters 0 and 6g respectively. The hope is that this simple formulation serves as a regularization allows us to recover meaningful disease-specinss parameters that we can define joint distributions P new interaction graphs for the same disease.
We adopt a maximum likelihood estimation (MI.) approach to learn these 0₁ and 02 parameters with respect to this single realization under the MRF model: 0* arg maxe, &g log Pxx; 81, 0z). However,
29

---

exact MLE is intractable in general due to the partition function z(01, 82), whose computation requires summing over all 2 configurations of node labels. To sidestep this difficulty, we instead optimize the pseudo-likelihood [Bes75], which approximates the joint likelihood by the product of conditional distributions for each node given its neighhors:
Po, 0g (x)
oo (x)
II Po. 8, (X, 2; x
II Pe. 0, (X, 0,x-1) + Pe, 0, (X,
(11)
This objective is tractable and differentiable with respect to 01 and 82, and can be efficiently optimized using gradient-based methods. Once learned, these parameters can be used to define a new factor graph for any unseen population with known covariates and network structure, thereby guiding the adaptive testing policy.
In general, a closed-form solution for the maximum pseudolikelihood estimator is unlikely to exist due to the nonlinear dependence of the local conditional distributions on the parameters. However, as the following lemma shows, we can derive closed-form gradients and rely optimization methods to compute parameter estimates for 01 and 02.
mudientt-ased
Lemma 9. Let G (X, E) be graph over nodes, where each node X; E X has binary label x; E {0, covariates E RR,, and neighborhood N(X.). Define feature maps fi fa ci) and f2( Ij, Ci, Cÿ) as per Eq. (8) and Eq. (9) respectively, shared parameters O, E R2+2d and 0g E TR.d and the joint probability as per Eq. (10). Then, the log-pseudoliketihood gradients are:
Ölog Po, og (x)
at ( -=(00c
001
i Ölog Po, 0, (x) 002
Σ
(f2(1, 25, 00, ,, f2(0, xÿ f2, cl cl),)
(X,)(X,)
where the common coefficient 0: = I; Po,,0 (X; x-4) can be computed efficiently without computing z(01, 22) for all E [n]]
The full proof of Lemma 9 is given in Appendix F.2. Note that parameter fitting may not necessary recover the exact dynamics of the underlying real-world problem in general. That is, Pa a. * P in
general, where 01 and A₂ are produced parameter estimates assuming the the MRF model defined in Appendix C.1 and P is the true unknown underlying joint probabilities (which may even lie outside the model class defined by Appendix C.I), As such, we also provide an error analysis Appendix F.3 to bound the loss of the attainable discounted accumulated reward of an optimal policy computed on Po,ōo while being executing on P.
D Further discussions
D.1 Broader impact
central motivation of this work is the urgent need for resource-efficient strategies in global public health. In the face of constrained resources and diminishing funding for disease control programs [UNA25], optimizing the allocation of testing efforts increasingly critical. Our framework enables targeted, adaptive exploration of interaction networks, and is particularly well-suited to settings where prior data can inform transmission structure through learned distribution P. possibly handcrafted by domain experts. This balance between data-driven structure and real-time adaptivity makes the AFEG framework a compelling tool for improving public health decision-makinn
D.2 Limitations
While our framework makes several modeling assumptions to enable tractable inference and principled decision making, these also define the scope within which our results apply. Each of these extensions below presents a well-motivated and technically rich research challenge building on the foundation establish.
First, we assume that the interaction graph known and fixed. This is reasonable assumption in many structured public health applications, such contact tracing or intervention planning, where
30

---

the network is elicited or constructed from prior data. However, generalizing our methods to handle uncertain or dynamically evolving graphs is promising direction for future work.
Second, our paper is focused on P oracles. One way to model this is via MRRs: in Appendix C.I, discuss how to model network-based disease testing using pairwise Markov Random Fields with shared parameters, which provide a flexible yet interpretable model class for encoding local dependencies in infection status. A more complicated model could be designed and used based on further inputs from domain experts. It is also worth noting that while exact inference of MRFs is tractable on sparse graphs (as motivated by real- world sexual networks), scaling to larger or denser networks may require approximate inference or amortized learning approaches. One can also consider relaxing to Gaussian random fields [ZLG03], as per the literature of active searching on graphs; see Appendix A.
Third, our theoretical guarantees for the GITTINS policy currently limited to tree-structured graphs; nonetheless, our empirical results demonstrate that it performs competitively even on graphs with low moderate treewidth.
Finally, while exact inference is tractable on sparse graphs (as motivated by real-world sexual networks), scaling to larger or denser networks may require approximate inference or amortized learning approaches.
D.3 Fairness considerations
notable advantage of our AFEG framework is its flexibility accommodate fairness constraints or objectives in sequential decision making. Since our model maintains posterior beliefs over individual infection risks via probabilistic graphical model, fairness fairness-aware aware modifications can be naturally incorporated at the policy level. For example, one can enforce demographic parity by requiring individuals from different subpopulations to have equal testing probabilities over time, or impose group-specific constraints on exposure or false negative rates. More generally, fairness can be encoded through soft constraints or regularization terms in the policy objective, via hard constraints within the selle-see mechanism. Notably, fairness interventions can also be incorporated directly through the reward function. To prioritize historically underserved groups, one could upweight successful identifications among protected populations for instance, by defining r(X, b) b-a Ippootcctdd for some a > Since GITTINS policies depend only on the reward structure and not group identity per se, such node-depentee reward shaping modifications preserve optimality guarantees on trees and maintain empirical performance on general graphs. Furthermore, Bayesian formulation allows dynamic reweighting calibration more data is revealed, enabling adaptive policies that balance efficiency and equity. Exploring how to systematically integrate such graph exploration is promising direction for future
faimess interventions into work, particularly in public health settings where equitable resource allocation is essential.
E Experimental details and more experimental results
While we do not release the ICPSR dataset, in accordance with its terms of use, interested researchers may independently access it via https: /wwww//wwwww// i icpar. umi ch, edu/ holu/web/Ti III/IICSS////S stte//ttuiiss eal 40. To facilitate reproducibility, our experimental scripts and the code used for data preprocessing and parameter estimation are available on our Github repository
E.1 Defining joint probability distribution P in our experiments
As described in Section 4, all of our experiments are modeled after the network-based disease testing application discussed in Section 1.1, where node labels are binary and a reward is received if and only if the revealed label indicates a positive diagnosis. Accordingly, the joint distribution P over node labels follows the pairwise MRF formulation described in Appendix C. Since the covariates in our real-world dataset [MR1] 1 are categorical, we apply one-hot encoding to transform them into binary vectors. For consistency, our synthetic experiments also use binary covariates.
12 Pttttps://giteee wwt.ttttbbb.oo///oooeeeetteeteet htggg//wwww..e//ccaaaaa////////a wertrtiiiiieooiieeeeeeeeeee poentier-explorde oenooooo-o----eeee on- graphs "Tiis de-identified. public-use dataset is available at
icpprr umich. wdw/web/ wewp/IIIR//
studies/22 /2114 under ICPSR's terms of use. No IRB approval was required for our of this data.
31

---

Synthetic experiments in Section 4.1 and Section 4.2. For each instance, we sample random parameters 0, 22 and 02 E R++5d and assign each node a random binary covariate vector of dimension d. The joint distribution P is then defined according to Eq. (10). Since all policies are agnostic to the choice of d, we fix
to keep computation time manageable.
Constructing P from the real-world dataset in Section 4.3. The real-world dataset comprises collection of network-based surveys across eight studies, each recording disease statuses for five sexually transmitted infections (Gonorrhea, Chlamydia, Syphilis, HIV, and Hepatitis). We first filtered the data retain only edges denoting reported sexual interactions and excluded individuals with missing or ambiguous disease status labels. Because the covariates are shared across diseases but transmission dynamics differ. we aggregated data across studies and split by disease. See Table I for dataset summary statistics. For covariates, we used categorical survey responses capturing demographic and behavioral factors relevant to disease transmission such as gender* homelessness, sex work involvement, etc. A total of 17 categorical variables were one-hot encoded into binary 72. We then applied the parameter fitting procedure from Appendix F.2 to estimate 0 E 2R2 and 0g E 1 for each discase-specific dataset, and constructed the corresponding pairwise MRF P using Eq. (10).
vectors of dimension
Table I: Summary statistics of real-world sexual interaction graphs [MR1]]. Approximate treewidth obtained by computing tree decomposition using networkx's breewidth_min_ft solnnfill__aa in. The graphs for Gonorrhaa and Chlamydia are identical but the infection rates are different, i.c., not everyone is infected with both diseases.
Sexually transmitted disease Gonorrhea
Chlamydia
Syphilis
HIV
Hepatitis
Number of infected Number of individuals
66
963
44
88
117
2079
2079
542
778
1732
Number of edges
1326
1326
519
793
1260
Diameter of graph Approximate tree width
8
8
12
13
24
1
16
16
E.2 Full results for Section 4.1
As described in Section 4.1, evaluated the policies against familly of randomly generated
synthetic trees on n E {10, 50, 100} nodes across various discount facotrs 3 E {0.55 0.7, 0.9). Fig. in Section 4.1 shows only the figures with discount factor 3 = 0.9. See Fig. 12 for the full 3 x plot.
E.3 Full results for Section 4.2
As described Section 4.2, we progressively add random non-tree edges to the synthetic trees to observe the change in relative performance of our policies. Across all experiments, we consider discount factor of 3 = 0.9 and add {0, 2, 4, 6, 8, 10} extra edges to each graph. Fig. 4 in Section 4.2 shows only the figures for seem like a small number, recall that trees have n edges. So, adding edges correspond to adding roughly 100%, 20%, and 10% adding additional edges to each graph for n E {10, 50, 100} respectively.
50; see Fig. 13 for results on E {10, 1003. While 10 edges may
E.4 Full results for Section 4.3
Table 2 provides the summary statistics of the subsampled real-world graphs which our experiments Fig. are based on.
In the main paper, we showed empirical results for when policies only have access to a noisy version Oe of the true underlying distribution P for the HIV dataset. Fig. 14 shows the results for all diseases.
MSee [FHA+98, Scul8] for evidence on gender differences in HIV susceptibility.
32

---

Greedy
DONPolicy
Optimel
nodes, A= 0.5
10 nodes, B 0.7
nodes, f 0.9
4.0
1.4
3.5
1.8
1.6
2.0
Expocted sccumulattdd discountes rowards
1.0
1.0
4
10
6
5
10
nodes,
8 0.5
50 nodes, = 0.7
50 nodes, == 0.9
1.0
1.6
1.4
2.0
1.5
1.0
1.0
15
22
43
50
100
nodes. 8= 0.5
100
nodes.
8= 0.7
100 nodes, 8 0.9
2.0
1.8
1.4
2.0
1.2
1.5
29
43
58
72
86
100
15
43
58
72
86
100
15 29
58
86
100
Number tests
Figure 12: Full experimental results for synthetic tree experiments.
Table 2: Summary statisties of subsampled real-world sexual interaction graphs from [MR11]. CC stands for connected component, Max. depth refers to the maximum BFS tree depth for GITTINS, and approximate treewidth is obtained by using networkx's 's treewidth, fittis_mmm__fll_______
Disease
# Nodes
# Edges
Forest?
Diameter
# CC
Max. depth
Apx. treewidth
Gonorrhea
300
195
5
105
3
Chlamydia
300
195
/
5
105
4
Syphilis
433
456
X
12
97
9
16
HIV
305
390
X
12
39
8
16
Hepatitis
300
184
125
5
2
33

---

Ransem
Drondy
DONNER
Optnal
extra edges
2 extra eóges
extra edges
extra edges
evera edges
10 estra edges
Sandbrn
DOMSSae
mode gropfo
water p-
extra edges
2 extra edees
extra edges
extra esges
extra edges
10 eatro edges
Narbo of L0S
(105 rode gricts with discest Seowor Pa 3%0
0 extra edges
2 E0TER edgss
Eett'a edges
extra edges
estra edges
extra e0ges
15
Nambarr of tob
Figure 13: Full experimental results for synthetic non-tree experiments. Observe that the relative performance gains of GITTINS over other baselines decreases we deviate from tree. Furthermore, the small n 10 (top row) instances where we can run OPTIMAL, we see that GITTINS is no longer optimal more non-tree edges are added, as expected.
34

---

Policiis ran with 6- 0.99
Rancoo
Growdy
DONPisiic
Gitlins
STInONN erter over 10 numi
E- 0.0
0.25
0.5
0.75
1-1.0
Fraction population
percentage totai population being testod.
Policiass ran with 6 0.99
Rancom
Groedy
DONPulic
Gittins
STAN2N- erter 15 nUNK
0.0
0.25
0.5
0.75
1-1.0
population
percentage total population being tested.
Policias ran with B- 0.99
Rancom
Groedy
DOMPolcy
Gittins
dtaneee errer over 15 nune)
0.0
0.25
0.5
0.75
1=0
Fraction population detted indicate 50%, parcentage total population being tested.
Policias ran with B 0.99
Rancom
Graedy
DOMPolicy
Gittins
danncer over 15 nunn)
0.0
0.23
0.5
0.75
1=10
Fraction population detted indicate 50%, parcentage total population being tosted.
Policias ran with B 0.99 Grocdy
Rancom
DONPolicy
Gittins
Shincer eeror oue 10 nunn)
0.0
0.25
= 0.5
0.75
1=10
Fraction population detted indicate 50%, parcentage total population being tostod.
Figure Experiments on the datasets of all diseases where policies only have access noisy version Q. of the underlying distribution P on the HIV dataset. Error bars illustrate the standard error due to 10 random instantiations of Q₂ for each corresponding value of e.
35

---

F Deferred proof details
E.1 Gittins proofs
Lemma 4. For any node X E X and label b E L, (x.o(m) is a non-decreasing piecewise linear function over m E [0,7/(1 B)].
Proof Let us induct on the nodes from the leaf towards the root while recalling definitions of & and from Eq. (1) and Eq. (2) respectively.
Base case (X is a leaf): For any E [0, L-g. we have (cn(x),((m)) = @0.((m) = m, and so
P(X = Pa(X) = b) (F(e) + + 3 (c)( }
xx,(mm = max m7,
VE
P(X = Pa(X) = b) [r(e) + Bm]
max
max
m, Bm
Σ BE
P(X= = Pa(X) = r(00}
Since Even P(X = o Pa(X) b) r(v) is a constant with respect to m, we see that ox (m) is non-decreasing with respect to m. Furthermore, since m and 3m Even P(X = v Pa(X) -(() are both linear functions in m. combining them via the max operator into (x.) yields piecewise linear function of m with at most 2 pieces.
Inductive case (X is a not leaf): Set S Ch(X) in Eq, (2). Consider ( for arbitrary 8k Y E Ch(X) and label b Ω. By induction hypothesis, we know that dv.a (k) piecewise linear function in k, and (k) 0k
is piecewise constant function in k. Thus, the product of Πyeca(x). (k) is piecewise constant function, and the integral - Il agy dk 8k
a piecewise linear function of m. Therefore, since r-3 is a constant with respect to m, we have that Pcn(x),)(mL) is piecewise linear function of m. Finally, similar to the base case argument above, we see that (m) is non-decreasing with respect to m and Φxx (m) is a piecewise linear function of m because the P(X- e Pa(X)= = b) and r(u) terms constants with respect m. As a remark, if X is the root, we simply replace P(X = Pa(X)= = b) with P(X = v) in the above argument.
Proposition 5. For any non-leaf node X and label b:
PC)()), (m) = &cn(x),, + hem(x), for some piecewise linear (C,(x),) (m).
&cL(x), (m) if and only if maxy (CxX))C(X))(()
Proof. For the first item, recall that showed that f e B dk is piecewise linear function of m in the proof in Lemma 4. Defining this function (cn(x),(m)) Eq. (2) yields (m)) f + h) So, (8, = r + hca(x),6()), which is a constant since (cc(x))&(0)) with respect to m.
For the second item, we recall the following fact from [Whi80] that aex 8k EE33" J. where the expectation is taken under the optimal policy when given fallback option m and T is the optimal stopping time for node X. Since
(0, 1), we see that B[is"] S with equality if and only if when T O, which happens only when m 2 g(X, b). So, the product in Eq. (2) HYECc(() @dy dk < 8k
1 with equality if and only if k > maXyeCh(X) bY, Meanwhile, when the product equals to
1, get (m)( I-B fr dk Therefore, Pcn(x),((m)
if and only if
m 2 maxyecιxx (Y,
For convenience of proving Theorem 6, let us recall Eq. (1) and Eq. (2) from the main text:
36

---

To define the Gittins index, let us first define two recursive functions & and Q.
per [KO03]. For any non-root node X X, label 6 52 and value m S I-8
(xxo(m) max m, P(x = Pa(X) = ()) (00))
(1)
If X is the root, we define 0x,o(m) max m, m,EvED P(X v) [r(X, 2) +
3 (on(x),o(m)) For any subset of nodes S X, label E Q2 and value
0 0- m S T-3
a dk if + # if 0 (2)
sm)
T-B
YEs
m
We will only invoke Eq. (2) with S = Ch(X) for some node X.
Theorem Given graph G = (X, E) and oracle access to joint distribution P, the Gittins indices
can be computed in O(n² ()2 time while using O(n [S2(2) oracle calls to P via Algorithm 1. The
space complexity is On ( space for storing On (22 intermediate piecewise linear functions.
Proof. Without loss of generality, may assume that there is only one rooted tree since the computation for each connected component is independent For instance, if there are components and the i-th component has n; nodes, then the overall complexity is O n |12 S O -|22
Throughout this proof, we assume that any conditional probability value can be obtained in constant time via oracle access to P. Now, recalling the definitions of Eq. (1) and Eq. (2), and Lemma 4, know that the computation of and + involve manipulating piecewise linear functions. The proof outline is as follows: we first use induction to argue that for any node X, the set of functions (ox,)ten can be computed using (( oracle calls to P and O max(1, (Ch(X)I)) opera- tions on piecewise linear functions. Then, we argue that the maximum time to perform any piecewise linear function operation in Algorithm is upper bounded by O(n (S)).. Our claim follows by summing over all nodes X and using the upper bound cost of operating on piecewise linear function.
By inducting on the nodes from the leaf towards the root, we first show that the set of functions (ox,&) best best can be computed using (( oracle calls to P and 0( max(1, (1, (Ch(X)I)) opera- tions on piecewise linear functions, as long as we store intermediate functions (vy,)l along the way. As a reminder, in this part of the proof, we are abstracting away the computation cost for manipulating pieces piecewise functions and focus on counting the number of operations on piecewise functions; we will later upper bound the computational cost for each of these operations.
Base case (X is a leaf): Recall from the proof of Lemma 4 that the function dxxo defined as
(x,((m) max {
m, 3m
Σ P(X = Pa(X) b) ((..))rr((X11 r(x,u)
vE
for any label value b E S2 Since EvEn P(X=0 Pa(X) = b) -r(,, can be computed in ((
oracle calls P, the function Φx,6 can be computed with O()) further operations on piecewise linear functions. So, the set of functions {øx,, hee can be computed in (( oracle calls to P and (( operations on piecewise linear functions.
Inductive case (X is not leaf, i.e. (h(X)= + (): Suppose all children nodes Y E Ch(X) of X have computed and stored their piecewise linear functions Φy,, for all possible values v E Ω.
Fix an arbitrary label b E S2 To compute 4x.s we need O(Ch((XII operations on piecewise linear functions differentiate each Φy function, and then multiply them together. Integrating
Theee focus is on the recursive cost of computing Gittins indices and the oracle access assumption is meant to abstract away the computational cost of computing quantities like P(- (-1-) -). As our setting assumes that P is a pairwise MRF defined over tree-structured graph, such inference is tractable via the junction tree algorithm.
37

---

this resultant function and subtracting it from the constant - function requires only an additional O(1) operations piecewise linear functions. Thus, computing all functions (PCCn())6)beB) costs O(ICh(X) |(2)) operations on piecewise linear functions.
I-3
Fix an arbitrary label E S. To compute @x,b, we need manipulate the set of functions (PC)(x), JvEn. More precisely, we use O(1) operations to scale each (cn(X), function by constant B, add the constant r(X,, v) function to each of them, and multiply again by the constant value P(X-
Pa(X) = b). Note that each P(X = v Pa(X) b) can be obtain in a single call to the P oracle, i.e. a total of O([22) calls. A further O(122)) operations on piecewise linear functions suffice to sum these manipulated functions up and take the maximum against the linear m function. So, the entire set of functions {6x.0 bbbnn can be computed in 0(122 oracle calls to P and O([ [Ch(X)l) operations on piecewise linear functions.
Intermediate conclusion: By the inductive argument above, we showed the set of functions ben
{dx,,) been can be computed using 0(12)2) 2) oracle calls to P and O(max (1, Ch(X))} -[21) opera- tions on piecewise linear functions for any node X. Summing across all nodes, this incurs O [S2|²) oracle calls to P and O([22| Exex max(1, L1 (Ch(X)I)) operations on piecewise linear functions.
It remains to argue that any operation on piecewise linear function in Algorithm requires O(n (S2]) time. First, observe that the computation time for any piecewise function operation depends on the number of pieces. Let denote the number of pieces in piecewise function f by #pieces( f)- Any addition or multiplication operation of two piecewise linear functions f and g creates new piecewise linear function such that #pieces(h) S #pieces(f) + #pieces(g). Differentiating and integrating a piecewise linear function do not change the number of pieces. Finally, taking the max of a piecewise linear against a linear function can at most increase the number of pieces by 1. From Lemma& 8, we know that the maximum number of pieces in any piecewise linear operation involving in the computation of Algorithm 1 at most On |S2)).
Putting together everything, we see that Algorithm incurs O(n [2(2] oracle calls to P and 0( Exex x max [1,[Ch(XX [Ch(X)])) operations on piecewise linear functions. Since each operation
on piecewise linear functions costs at most O(n [S2]), Algorithm runs in O(n². (S2(²) time while using (n [s2 oracle calls to P.
O
F.2 Parameter fitting
For convenience of proving Lemma 9, let us recall Eq. (11) from Appendix C.2:
po, (x) Pe, e, = 0, x1) + P0,00(( (X, 1, x,)
(x) II Pa. 02 (X, 24 x))
where
Po. (X X
x) z(01, 02)
1
exp Σ
0 f(() Σ
0, 2( {L,))E
and
(x(x))= exp (TT (I,, (())) and (1,((1,);))) exp (0) f2 c00,66)))) c(.))
Lemma 9. Let G = E) be a graph over n nodes, where each node X, E X has binary label x, E 1), covariates c, E Rdd, and neighborhood N(X.). Define feature maps fi c.) and fz 12,, Ci, C,) as per Eq. (8) and Eq. (9) respectively, shared parameters 02 E R222d and 02 R54d and the joint probability as per Eq. (10). Then, the log pseudoiikelihood gradients are:
Ölog Po, o0,0 (x)
n
Σ
(
ai
00,
i Ölog Po (x)
Σ
(0) - x., ,0,00.,)))))
a4
002
(XEN(X.)
38

---

where the common coefficient a; (X, = 1 x-1) can be computed efficiently without computing z(0), 82) for all E [nl]
Proof. Let define the terms and Bud for y E [n] and E 10.
a
= log
22) po, (x))
Σ 8 (I
Σ 0g fe c0 cl
(i,)ER
Badb log
O2) Po, b, b,x-1)
-00,000,c()))
Σ 120, cl0)
(iJEE y=
0 fi c()) +
Σ
02 f2 az, c(0) ,(0))
(WEE
Observe that
exp(B). exp(B + exp B
Po (X,, = x-))
(12)
Let us consider their partial differentation with respect to 01 and 02. We will use these later.
0A
0 fi )
(13)
00,
00,
T=1
Σ Si (1:;, c(0))
0A
E 00g S2( c(0) cl0)
(14)
802
002
(JilEE
Σ ail,, (()))))))))
=
(WiE
00. fi(b, c.)
000 fi c
(15)
08,
00,
001
-l,(b,c, Σ
fi
a
000 f2(b, Fj, c((v), cl.))
00,- f2(11, Fj, Hj, (l0)) c(0))
Σ
(16)
08:2
0022
062
(ijEEE y=1
{i,)eE vE(())
Σ
fa(b,2,,c (0) (00)))))) Σ f2(2,, 2i, e c(())
(LE)E (g(())
Now, re-expressing Po (x) in terms of and B5. we have
(x)
exp(A)
Po or (x) II Pa, 02 (X: x.) Po (X, 1, x.x
exp By) + exp (B))
Fix an index y E [n] and define Wy,
exp( (xp(BB)) so that Po og (x) 11 W,, i.e.
exp A)
log Pe, (x) = -n= log W
39

---

Let us differentiate with respect to 81. For any [nd,, we see that
log W
00,
0A
@log(exp(BB) + exp((.)))
001
00,
0A
i @exp(By))
@exp(By)) +
001
exp(Bx) + (
001
001
04
Bg)
OB
exp(B!))
aB,
y
001
(g)) exp( B,)
001
exp
Bg) + (x.p(B)))) 001
0A
0B
(1
Po (x, =1 x x))
Po (x, = x x)=))
1
(By Eq. (12))
001
00,
001
n
Σ [1 c4) - = 1
f1(0,cy)) Σ [1
$74
n
- Po., (X,, = 1 1110)) fi(l,c,) + +Σ f((x,:))
(By Eq. (13) and Eq. (15))
= ff Cw) - o -1|x,)))) 1110xx)))f - Po (X, = x (x,)xxx)) fi(1, cy) (xy Por,0 (X, = x-y) cgy c0,)
(Since By E {0, 1))
Summing over all y E [n], we get
0 PoL.o (x)
Olg Wy
1 (s, Po,.0((X = x-y)) (Ji(1, (1
00,
00,
1=1
yielding the first statement as desired, where ay (zy. - Po,,, 02 (X, = x-,g))
For the second statement, we do the same analysis but use Eq. (14) and Eq. (16) instead of Eq. (13)
and Eq. (15). Note that the second summation E(d)eE gets cancelled out as in the above analysis *Ø((J}
while the first summation
Eisle exactly corresponds to Σx,eN(X.> g=1
F33 Robustness to model misspecification
We analyze how errors in the learned graphical model impact the quality of the resulting policy in an AFEG instance. Specifically, we derive a bound on the discrepancy between the optimal state-action value functions of the learned and the true Markov decision processes (MDPs), capturing how inaccuracies in the estimated joint distribution Po affect decision quality.
Recall that an AFEG instance is defined by triple (G. P. B), where = (X, E) is a graph, P is a joint distribution over binary node labels Markov with respect to G, and / E (0, 1) is discount factor. At each time step f, the state S, records the current frontier and the set of revealed labels. policy л selects a node from the frontier and receives a label-dependent reward.
We consider two MDPs defined over the same state space S, action mapping A restricts valid actions to untesed frontier nodes, and discount factor 3, but differing in the distribution used infer infection status:
2 that
The learned MDP M = (S, A, P, Rt, is defined using an estimated model P. obtained via pseudo-likelihood. The expected reward for testing node E A(s)) is
f((s, = P(X. = 8),
and the transition kernel P uses this posterior to sample binary outcome.
40

---

The true MDP M' = (S, RR is induced by the ground distribution P, with
R(s,a) P(X, = | s),
and transitions P differing from P only in the Bernoulli parameter used for Xa-
We define the maximum reward and transition discrepancies:
max ( - R(s, a){,
P(s' 8, - P(s' s,,)
ER
Ep
max sES, oEA(s), s'ES
#ES, aEA(a)
Since rewards are probabilities, set Rinax
We are interested bounding the worst-case deviation in optimal Q-values:
1 lor sES, aEA(s)
max
[hr a) - (i,
This is because the Q'-function encodes the expected total discounted reward starting from state and taking action a, and thus directly characterizes the long-term value of testing each node. Therefore, small bound on ||Q Qi ao ensures that the policy derived from the learned model will perform nearly as well the optimal policy under the true model, in terms of accumulated reward. The following bound shows that the suboptimality of the learned policy is controlled by the maximum error in posterior infection probabilities and transition dynamics, with greater sensitivity as B - 1. Lemma 10. Let M and M' be defined as above, and let ER,EP denote the maximal reward and transition discrepancies. Then:
ER + 38max 11th - Qhrllo 1
1- (1 - 3)2 EP.
In particular, since Ramax 1,
3
10 - lhrllo I
R +
1 - $ 8p
1-
Proof. Let TM and T Mr denote the Bellman optimality operators for MDPs M and M' respectively.
For any function Q S x A - IR, define:
(TM
R(s,a) + P a, max Q(s(,a))
s'ES
The same holds for the operator Tar. We also know that the operators TMs and Tw both A-contractions under the supremum norm:
I Q' S BIQQ Q' and | Q' s sB11Q Qo
Now, let Qir and Qi: be the fixed points of TMs and Thi respectively. Then,
|1Q - Qir = 1T Tar Vur:iirlll ol
(Qis and Qir are fixed points) IT Thr Qir lloo + QhTM -TM (Triangle inequality)
IT Th. + +31105s Qirloo (Contraction property of T )
Rearranging, we get
- 11-3) - 1b < TI TM TM.Qurll 1irl loc
(17)
As the difference 7M Qh - Q's Ilae captures how much the two MDPs rewards and transitions differ, we will analyze and bound for (Tx Q), (Tar a) for some fixed Q:
(T,r))ss,a) ()s,)
= =(R(s,a) ((s, 3 Σ ((s' 1 P(s' 8, a)) max Q(s',a')
Taking absolute values and using the definition of eR and EP, we get
(T,,) (TMrQ)(s, SER + [
41

---

Therefore,
[TrrQ Qlo Snn + 3erl1Q
In partieular, setting Q Qia and using the bound || 10r Rmax/ B), we that
RRmax
QM QM.llo Sent +
Ep
1 1- 3
Plugging into Eq. (17), we get
BR
(1 (1-B)lIQ%) - lar SEn
1 B EP
Thus,
ER
3 Rmax
110 Qir _
+
1 3
(1 B)2
as desired.
42


Reviews:
[{"review_id": "EkuLAtm9i5", "reviewer": "Reviewer_PxU7", "summary": "Consider the problem of sequential decision making on a graph, where the arms that can be pulled are only be neighbours of previously pulled arms. This is the frontier of exploration. Specifically, this paper addresses the \"Adaptive Frontier Exploration on Graphs\" (AFEG) problem, a sequential decision-making task relevant to high-impact applications like network-based disease testing. \n\nThe core contribution is a novel, efficient, polynomial-time algorithm for computing the Gittins index policy, which is provably optimal for AFEG instances on tree-structured graphs. The authors connect this deep theoretical result to a pressing real-world problem, demonstrating on real-world HIV interaction networks that their method can improve testing efficiency compared to strong baselines, including a DQN (deep Q net) approach. The work is technically deep, rigorously presented, and its claims are backed by strong empirical evidence.", "questions": "- Are real world graphs truly forests (for which the optimality results hold)? In the real world, are people not fully connected to each other?\n- Where does this come from (line 701 in appendix) $θ_1 \\in R^{2+2d}$ and $θ_2 \\in R^{4+5d}$\n- How valid is the assumption on non-decreasing piecewise linear function?", "limitations": "Please include a more detailed limitations section in your work. Since this paper has potential to be applied to medical domains, it would be prudent to state the limitations in greater detail to potential users.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "### Strengths\n1. One of the papers I was excited to read, and I've been reading MAB papers for a long time! Very interesting and practical problem formulation.\n2. The paper's primary contribution is arguably proving the first poliynomial time algorithm for the provably optimal policy in discrete branching bandits. This is a foundational contribution to the MAB and RL literature, with implications beyond the disease testing/contact tracing problem.\n3. I was very impressed with the empirical results which indicate that nearly all HIV-positive individuals were identified by testing only half the population in the ICPSR dataset, and for example works better than DQN (deep Q networks). Given decreasing medical and research budgets, this could be an important method to release to real-world use cases.\n\n### Weakness\n\nThe model assumes an oracle access to joint probability distribution P, which can provide answers about the conditional probability distributions over Bayesian Nets. \n\nNote: But in Appendix B in the paper, they convert the weakness into a strength by actually building this oracle out from a model using maximum pseudo-likelihood estimation (MPLE). This makes the oracle assumption plausible. Yet the authors acknowledge that such a parameter fitting may not recover the exact real world dynamics (Line 631).", "was_revised": true, "final_justification": "maintain score.", "rebuttal": "Thank you for your time and thoughtful feedback on our submission. We sincerely appreciate your comments and the opportunity to address your concerns. Below, we respond to the main points raised in the review and will incorporate a version of this discussion into our revised manuscript.\n\n# Oracle access to underlying probability distribution $\\\\mathcal{P}$\n\nWe agree that the assumption of oracle access to $\\mathcal{P}$ may not always hold in practice. In real-world settings, such as modeling the spread of sexually transmitted infections (STIs), it is reasonable to approximate the distribution $\\mathcal{P}$ using a pairwise Markov Random Field (MRF) over the contact network $\\mathcal{G}$. As you kindly noted, we outline in Appendix B how the parameters $\\theta$ of such a model can be estimated from historical data via maximum pseudo-likelihood estimation (MPLE). In addition, Appendix E.3 contains an analysis of how errors in estimating $\\mathcal{P}$ affect decision quality.\n\nIn the original submission, we assumed that $\\mathcal{P}\\_{\\theta}$ (estimated via MPLE) was the ground truth. In response to your comment, we have conducted additional experiments during the rebuttal period to assess robustness when the policy only has access to a noisy version $\\mathcal{Q}\\_{\\theta}$ of the true distribution $\\mathcal{P}_{\\theta}$.\n\nWe perturbed the learned parameters $\\theta$ with noise of magnitude $\\varepsilon \\in \\\\{0.1, 0.3, 1\\\\}$ to simulate distributional mismatch, while keeping the evaluation grounded in the original $\\mathcal{P}\\_{\\theta}$. For reference, in the HIV setting, we have $\\ell_{\\infty}(\\theta_{\\text{unary}}) = 1.43$ and $\\ell_{\\infty}(\\theta_{\\text{pairwise}}) = 1.75$. Thus, $\\varepsilon = 1$ constitutes a significant perturbation.\n\nSince plots and external URLs are disallowed, we summarize our results in tabular form, reporting the expected undiscounted reward over a random subset of approximately 300 nodes in the HIV network (following the format in Appendix D.3). We focus on *undiscounted* reward as it better reflects the practical goals of maximizing the number of infected individuals detected under a fixed testing budget. For clarity, we **bold** the best-performing methods for each budget level.\n\n**Expected *undiscounted* reward for $\\mathcal{Q}_{\\theta, 0.1}$ on HIV network**\n\n| Percentage of nodes tested | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | 100% |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| Random | 6.1 | 11.4 | 16.0 | 19.4 | 22.3 | 24.6 | 26.6 | 28.2 | 29.8 | **31.6** |\n| Greedy | **20.1** | 25.8 | 26.6 | 26.8 | 27.0 | 27.5 | 30.1 | 31.0 | 31.2 | **31.6** |\n| DQN | 15.7 | 22.7 | 25.4 | 26.6 | 27.0 | 27.3 | 27.9 | 28.2 | 29.9 | **31.6** |\n| Gittins | **20.1** | **28.4** | **29.4** | **30.5** | **30.9** | **31.2** | **31.3** | **31.6** | **31.6** | **31.6** |\n\n**Expected *undiscounted* reward for $\\mathcal{Q}_{\\theta, 0.3}$ on HIV network**\n\n| Percentage of nodes tested | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | 100% |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| Random | 6.1 | 11.5 | 16.0 | 19.5 | 22.3 | 24.8 | 26.6 | 28.3 | 29.8 | **31.6** |\n| Greedy | **19.2** | 25.7 | 26.4 | 26.8 | 27.0 | 27.6 | 30.1 | 31.0 | 31.2 | **31.6** |\n| DQN | 8.1 | 14.3 | 22.4 | 24.3 | 25.6 | 26.4 | 27.9 | 29.0 | 30.0 | **31.6** |\n| Gittins | 19.1 | **25.8** | **28.6** | **30.3** | **30.8** | **31.1** | **31.3** | **31.6** | **31.6** | **31.6** |\n\n**Expected *undiscounted* reward for $\\mathcal{Q}_{\\theta, 1}$ on HIV network**\n\n| Percentage of nodes tested | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | 100% |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| Random | 5.8 | 11.4 | 13.7 | 19.8 | 22.5 | 24.7 | 26.4 | 28.1 | 29.7 | **31.6** |\n| Greedy | **16.6** | **22.3** | **23.8** | **24.8** | **26.7** | 27.6 | **30.1** | **30.8** | 31.2 | **31.6** |\n| DQN | 3.4 | 9.9 | 11.6 | 14.7 | 17.1 | 21.3 | 23.8 | 27.1 | 28.9 | **31.6** |\n| Gittins | 16.5 | 22.2 | **23.8** | **24.8** | 26.1 | **28.6** | 29.7 | 30.6 | **31.5** | **31.6** |\n\nFrom this preliminary set of experiments, we see that our proposed method (Gittins) remains competitive while the performance of all policies degrade as $\\mathcal{Q}_{\\theta,\\varepsilon}$ becomes less representative of $\\mathcal{P}$ due to larger $\\varepsilon$ values. In our revision, we plan to conduct a broader suite of such experiments across all the disease networks and report them in the appendix.\n\n# Structure of real-world graphs\n\nWe agree that real-world graphs are not truly forests (see Line 210). However, empirical studies have shown that STI transmission graphs are often sparse and exhibit tree-like structure (e.g., [1,2,3]). While certain high-degree nodes (e.g., sex workers) may exist, the network as a whole is far from fully connected. We refer to Appendix D.2 for an empirical evaluation of how performance degrades as the graph departs from tree structure.\n\n[1] Peter Bearman, James Moody, Katherine Stovel. *Chains of affection: The structure of adolescent romantic and sexual networks*. American Journal of Sociology, 2004.\n\n[2] Joel Wertheim, Sergei Kosakovsky Pond, Lisa Forgione, Sanjay Mehta, Ben Murrell, Sharmila Shah, Davey Smith, Konrad Scheffler, Lucia Torian. *Social and Genetic Networks of HIV-1 Transmission in New York City*. PLoS Pathogens, 2017.\n\n[3] A M Young, A B Jonas, U L Mullins, D S Halgin, J R Havens. *Network structure and the risk for HIV transmission among rural drug users*. AIDS and Behavior, 2013.\n\n# $\\theta_1$ and $\\theta_2$\n\n$\\theta_1$ and $\\theta_2$ are the parameter vectors of the unary and pairwise potentials in the pairwise-MRF model described in Appendix B.1. These parameters correspond to feature maps $f_1$ and $f_2$ from Equations (4) and (5), which consist of monomials (up to second order) of the covariate features. The construction respects symmetry and the maximum entropy principle, ensuring proper dimension alignment between features and parameters.\n\n# Non-decreasing piecewise linear function\n\nThe non-decreasing piecewise linearity is **not** an assumption but a provable property of the Gittins index computation, as shown in Lemma 4 (line 192) and Proposition 5 (line 201). The detailed proof appears in Appendix E.1.\n\n# Limitations\n\nAs mentioned in Section 5, we have provided additional discussion on broader impact and limitations in Appendix C."}, {"review_id": "E7Ey8mdqFE", "reviewer": "Reviewer_DJzd", "summary": "This work considers the problem of sequential decision-making over a graph where each node is associated with a label from a finite set of labels and a label-dependent \nreward whose distribution is given by a Markov model. The goal is to find the optimal policy that collects the maximum expected discounted reward. The work investigates an action constraint defined here as the adaptive frontier exploration on graphs (AFEG) constraint where the next node to visit in the graph has to be chosen from the set of non-visited neighbours of the already visited nodes. The authors model network based disease testing using this framework motivating such a model in scenarios where tested individuals might be interviewed to trace contact with other individuals so that these individuals can subsequently be tested. The problem of network based disease testing is an important problem in public health and studies have shown better algorithms lead to better outcomes. In light of this, the current work reformulates AFEG as a branching bandit problem and proves optimality of Gittins index when the disease network is a forest. In case of general graphs, the authors use the BFS tree of the graph to run the Gittins index based policy, thus providing a heuristic for the general case. Moreover, the authors show that their algorithm runs in time polynomial in the size of the graph and the number of elements in the label space. Finally, the work demonstrates empirically the performance of Gittins index based policy for synthetic as well as real-world disease network datasets. The experiments show that Gittins index based policy is generally faster than other baselines while giving superior or competitive performance.", "questions": "See weaknesses above. Minor suggestion: please consider changing the notation $X_{\\pi(S_t)}$ that indicates both label and the node currently. It would help the reader if this notation was disambiguated.", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. The formulation of network based disease testing as an AFEG problem is interesting. Network based disease testing is an important problem in public health and has shown merits in multiple studies. Therefore, this work is an important contribution in the literature of network based disease testing.\n\n2. The computational efficiency results for Gittins index based policy which is generally intractable due to the curse of dimensionality is another novel aspect of the work.\n\n3. The experiments performed are extensive with several real-world disease datasets considered on top of synthetic experiments. In most of the experiments on real data, the Gittins index based policy is either slightly superior or competitive. The experiment set up is also natural and well motivated.\n\n4. Lastly, the writing is very clear and cogent with good organization and discussions making it easy for the reviewer to understand the work. Overall it was a pleasure to read.\n\nWeaknesses:\n\n1. Firstly, Theorem 1 is not very novel. It is a straightforward adaptation of the work [1]. Moreover, the guarantee works for the forest case which though is a good starting point, is theoretically a limiting assumption and may not hold in real world networks. However, to the authors’ defence the Gittins index based policy on the BFS tree of general graphs seems to give good empirical performance. Here however the question is why BFS tree and not other trees? This work might benefit if the authors can give provable guarantees on the global graph when Gittins based policy is run on an appropriately chosen tree of the graph.\n\n2. The work considers a case where the label space is finite. The main computational result (Theorem 6) also banks on this assumption. This may be limiting in scenarios where richer data is available, for example in disease networks, not just discrete labels but also real valued intensity may be available. While general label spaces may be hard to compute, it would be interesting to see some generalization, for example, can it be done for continuous label spaces with an $\\varepsilon$-discretization where the computational efficiency scale as $poly \\log (\\frac{1}{\\varepsilon}$ whereas the optimal policy over the discretization may differ by $\\varepsilon$ from optimal?\n\n3. The current work relies on access to the graph structure and the distribution $\\mathcal{P}$. While the assumption on graph structure is still fine, the assumption of access to distribution $\\mathcal{P}$ exactly is a limiting one. Particularly, one of the baselines considered is DQN which relies only on sample access to $\\mathcal{P}$. Instead of assuming exact oracle for $\\mathcal{P}$, it would be interesting to see the theory developed for sample access to the distribution. Indeed, a more reinforcement learning style with finite sample convergence guarantees will be useful to the work. This is because currently the work uses existing data to first learn an approximate $\\mathcal{P}$ and then use it for policy. However, this learning step makes certain strong structural assumptions which may be bypassed if an RL style algorithm can be given.\n\n4. Figure 14 seems to show that the DQN policy is much better than the Gittins policy with the later having constant suboptimal gap for all the disease networks considered. This is in contradiction to the experimental results in the remaining paper. Moreover, the motivation for the smaller dataset created by subsampling with threshold $\\tau = 300$ is not clear. Indeed, Fig. 14 result on the full dataset seems contradictory to the result on this subsample. Moreover, the authors’ algorithm does not seem to provide much performance benefit over greedy/DQN in the low $\\beta$ regime on synthetic dataset. In light of this, it is not clear why the authors do not repeat experiments with low $\\beta$ on the real world dataset.\n\n[1] Godfrey Keller, Alison Oldale. Branching bandits: a sequential search process with correlated pay-offs, Journal of Economic Theory, Volume 113, Issue 2, 2003, Pages 302-315.", "was_revised": true, "final_justification": "One of the claimed primary contribution of this work is the theoretical results, which does not appear novel and has been observed in the existing literature. Moreover, one of the theorems (Thm 6) seems to mis-specify the required conditions for the theorem to hold. However, to the authors' credit, the experimental results on real-world datasets seem promising. Therefore, I am inclined towards a borderline reject since although the theoretical parts are not novel, the experimental parts are promising and merits further research.", "rebuttal": "Thank you for your time and thoughtful feedback on our submission. We sincerely appreciate your comments and the opportunity to address your concerns. We will incorporate a version of this discussion into our revised manuscript.\n\n# Theorem 3 and novelty\n\nWe acknowledge that Theorem 3 is a direct consequence of Theorem 1 from [KO03]. We clarified this in the main text (Line 184). Our primary contribution in Section 3.1 is to establish that the connection that Gittins indices for branching bandits provide an optimal solution to AFEG instances when the input graph is a forest. Additionally, while [KO03] proves optimality, it does not provide an efficient computation method. Our contributions go further in two ways:\n\n1. Proving new structural properties of the Gittins computation (Lemma 4 and Proposition 5)\n2. Developing a polynomial-time algorithm with an accompanying implementation to compute Gittins indices (Theorem 6)\n\n# BFS tree projection\n    \nWe selected the BFS tree projection to minimize the depth of the induced tree, preserving proximity between nodes and root. This ensures that options at the frontier are not artificially constrained by long detours due to us removing edges to invoke Gittins.\n\nFor example, consider the graph made of a small cycle $v_0 - v_1 - v_2 - v_0$ and a large cycle $v_1 - v_2 - v_3 - \\ldots - v_k - v_1$, where $k \\gg 3$. Suppose $v_0$ is the root. The induced BFS tree will keep the path $v_0 - v_2$ while another induced tree that removes edges $v_0 - v_2$ and $v_1 - v_2$, resulting in $v_2$ being reachable from the root only via a very long path $v_0 - v_1 - v_k - \\ldots - v_3 - v_2$. It would be interesting to investigate different tree projections for other approaches when there is no frontier exploration constraint.\n    \n# Extending to continuous label space\n\nWe believe discrete labels are already meaningful in many applications, particularly in health domains. For example, positive/negative test results, or coarser categorical risk levels (e.g., low/medium/high), are common in practice.\n\nThat said, we agree this is an important and interesting extension. However, even under $\\varepsilon$-discretization, the analysis is nontrivial. This is because the function $\\phi$ can have non-continuous derivatives, and $\\Phi$ aggregates these through products and integrals. This makes bounding policy errors with respect to discretization challenging.\n    \n# Oracle access to underlying probability distribution $\\\\mathcal{P}$\n\nWe agree that the assumption of oracle access to $\\mathcal{P}$ may not always hold in practice. In real-world settings, such as modeling the spread of sexually transmitted infections (STIs), it is reasonable to approximate the distribution $\\mathcal{P}$ using a pairwise Markov Random Field (MRF) over the contact network $\\mathcal{G}$. As you kindly noted, we outline in Appendix B how the parameters $\\theta$ of such a model can be estimated from historical data via maximum pseudo-likelihood estimation (MPLE). In addition, Appendix E.3 contains an analysis of how errors in estimating $\\mathcal{P}$ affect decision quality.\n\nIn the original submission, we assumed that $\\mathcal{P}\\_{\\theta}$ (estimated via MPLE) was the ground truth. In response to your comment, we have conducted additional experiments during the rebuttal period to assess robustness when the policy only has access to a noisy version $\\mathcal{Q}\\_{\\theta}$ of the true distribution $\\mathcal{P}_{\\theta}$.\n\nWe perturbed the learned parameters $\\theta$ with noise of magnitude $\\varepsilon \\in \\\\{0.1, 0.3, 1\\\\}$ to simulate distributional mismatch, while keeping the evaluation grounded in the original $\\mathcal{P}\\_{\\theta}$. For reference, in the HIV setting, we have $\\ell_{\\infty}(\\theta_{\\text{unary}}) = 1.43$ and $\\ell_{\\infty}(\\theta_{\\text{pairwise}}) = 1.75$. Thus, $\\varepsilon = 1$ constitutes a significant perturbation.\n\nSince plots and external URLs are disallowed, we summarize our results in tabular form, reporting the expected undiscounted reward over a random subset of approximately 300 nodes in the HIV network (following the format in Appendix D.3). We focus on *undiscounted* reward as it better reflects the practical goals of maximizing the number of infected individuals detected under a fixed testing budget. For clarity, we **bold** the best-performing methods for each budget level.\n\n**Expected *undiscounted* reward for $\\mathcal{Q}_{\\theta, 0.1}$ on HIV network**\n\n| Percentage of nodes tested | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | 100% |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| Random | 6.1 | 11.4 | 16.0 | 19.4 | 22.3 | 24.6 | 26.6 | 28.2 | 29.8 | **31.6** |\n| Greedy | **20.1** | 25.8 | 26.6 | 26.8 | 27.0 | 27.5 | 30.1 | 31.0 | 31.2 | **31.6** |\n| DQN | 15.7 | 22.7 | 25.4 | 26.6 | 27.0 | 27.3 | 27.9 | 28.2 | 29.9 | **31.6** |\n| Gittins | **20.1** | **28.4** | **29.4** | **30.5** | **30.9** | **31.2** | **31.3** | **31.6** | **31.6** | **31.6** |\n\n**Expected *undiscounted* reward for $\\mathcal{Q}_{\\theta, 0.3}$ on HIV network**\n\n| Percentage of nodes tested | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | 100% |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| Random | 6.1 | 11.5 | 16.0 | 19.5 | 22.3 | 24.8 | 26.6 | 28.3 | 29.8 | **31.6** |\n| Greedy | **19.2** | 25.7 | 26.4 | 26.8 | 27.0 | 27.6 | 30.1 | 31.0 | 31.2 | **31.6** |\n| DQN | 8.1 | 14.3 | 22.4 | 24.3 | 25.6 | 26.4 | 27.9 | 29.0 | 30.0 | **31.6** |\n| Gittins | 19.1 | **25.8** | **28.6** | **30.3** | **30.8** | **31.1** | **31.3** | **31.6** | **31.6** | **31.6** |\n\n**Expected *undiscounted* reward for $\\mathcal{Q}_{\\theta, 1}$ on HIV network**\n\n| Percentage of nodes tested | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | 100% |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| Random | 5.8 | 11.4 | 13.7 | 19.8 | 22.5 | 24.7 | 26.4 | 28.1 | 29.7 | **31.6** |\n| Greedy | **16.6** | **22.3** | **23.8** | **24.8** | **26.7** | 27.6 | **30.1** | **30.8** | 31.2 | **31.6** |\n| DQN | 3.4 | 9.9 | 11.6 | 14.7 | 17.1 | 21.3 | 23.8 | 27.1 | 28.9 | **31.6** |\n| Gittins | 16.5 | 22.2 | **23.8** | **24.8** | 26.1 | **28.6** | 29.7 | 30.6 | **31.5** | **31.6** |\n\nFrom this preliminary set of experiments, we see that our proposed method (Gittins) remains competitive while the performance of all policies degrade as $\\mathcal{Q}_{\\theta,\\varepsilon}$ becomes less representative of $\\mathcal{P}$ due to larger $\\varepsilon$ values. In our revision, we plan to conduct a broader suite of such experiments across all the disease networks and report them in the appendix.\n\n# Clarification regarding figure 14\n    \nThank you for pointing this out. The figure in question does **not** show DQN outperforming Gittins. Due to a rendering error, the legend was mislabeled. In this instance, Gittins corresponds to the yellow curve, and DQN results were omitted because each training run exceeded a full day. We will correct this in the final version.\n\n# Low $\\beta$ on real-world dataset\n\nAs noted in Lines 286–289, our goal for real-world scenarios is to identify as many positive cases as possible under a fixed testing budget. The discount factor $\\beta$ is simply a tool to emphasize early discoveries; any $\\beta \\in (0,1)$ is valid. However, smaller $\\beta$ values heavily penalize late discoveries, which can be counterproductive when detection at any point is valuable.\n\nTo illustrate this, we re-ran HIV experiments under $\\beta = 0.1$ and $\\beta = 0.99$ and report the undiscounted performance in both cases. For easier comparison, we **bold** the largest reward attained at each level of budget available.\n\n**Expected *undiscounted* reward for $\\beta = 0.1$ on HIV network**\n\n| Percentage of nodes tested | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | 100% |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| Random | 6.1 | 11.0 | 15.2 | 18.5 | 21.3 | 23.5 | 25.6 | 28.0 | 30.0 | **31.6** |\n| Greedy | 17.7 | **22.4** | **23.0** | 23.3 | 23.4 | 29.2 | 30.1 | **31.1** | **31.2** | **31.6** |\n| DQN | 16.9 | 22.2 | 22.9 | 23.2 | 23.7 | 24.2 | 24.8 | 30.6 | 31.2 | **31.6** |\n| Gittins | **17.8** | **22.4** | **23.0** | **29.2** | **29.8** | **30.6** | **30.9** | 31.0 | 31.0 | **31.6** |\n    \n**Expected *undiscounted* reward for $\\beta = 0.99$ on HIV network**\n\n| Percentage of nodes tested | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | 100% |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| Random | 6.0 | 11.6 | 15.7 | 19.1 | 21.7 | 23.9 | 25.9 | 28.1 | 30.0 | **31.6** |\n| Greedy | 17.7 | 22.4 | 23.0 | 23.3 | 23.4 | 29.2 | 30.1 | 31.1 | 31.2 | **31.6** |\n| DQN | 13.9 | 18.3 | 21.3 | 26.2 | 27.7 | 28.5 | 29.8 | 30.2 | 30.8 | **31.6** |\n| Gittins | **19.0** | **26.9** | **29.5** | **30.6** | **30.9** | **31.2** | **31.3** | **31.6** | **31.6** | **31.6** |\n    \nGittins maintains strong performance across the board and achieves higher coverage than baselines even when $\\beta$ is small. However, note that a small $\\beta$ effectively \"zeroes out the reward\" for an identification many steps in the future, resulting in degradation of policies that optimize long-term performance (such as DQN and Gittins).\n\n# Notation Overload\n\nWe appreciate the reviewer's suggestion regarding potential ambiguity in our notation. We follow standard conventions in the graphical models literature, where variables and nodes are often used interchangeably, and the graph structure implicitly defines the factorization of the joint distribution. In this setting, it is common to use a symbol like $X$ to refer to both the node and its associated random variable, so that expressions like $X = v$ denote the event that variable $X$ takes value $v$. That said, we understand that readers from other communities may find this notation unfamiliar, and so we will include a brief remark early in the paper clarifying this convention to aid accessibility."}, {"review_id": "mEqrR430pV", "reviewer": "Reviewer_EBjH", "summary": "Motivated by network-based disease testing, the paper formalizes Adaptive Frontier Exploration on Graphs (AFEG) as a sequential decision problem on a probabilistic graph. When the graph is a forest, the proposed Gittins index-based policy for AFEG has a provable convergence guarantee. Experiments on both synthetic and real-world graphs show the superiority of the proposed method.", "questions": "1. The definitions of two potential functions $\\phi_{X,b}$ and $\\Phi_{S,b}$ in Eq. 1 and 2 are confusing me, although there are some attempts of explanation on L176-178. What is the difference between these potentials?\n2. I am curious why the author only uses a single-step DQN as a deep RL comparison, but omits more recent graph RL or planning methods (e.g., policy-gradient, Monte-Carlo tree search). Why were they not considered?", "limitations": "1. Optimality only holds for forests and relies on exact $\\mathcal{P}$\n2. Scalability to a very large graph is limited.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "# Strengths\n1. The problem of network-based disease testing is important. The proposed AFEG model correctly captures realistic locality constraints (e.g., contact-tracing). \n2. The piecewise-linear analysis of the recursive value functions appears original to me and leads to the first practical algorithm for discrete branching-bandit indices.\n\n# Weaknesses \n1. Assumed access to the joint distribution $\\mathcal{P}$. I think the $\\mathcal{P}$ is usually learned from data in practice. How sensitive are results to model misspecification? Empirical ablations with learned vs. true $\\mathcal{P}$ would strengthen the work.\n2. Scalability to very large graphs. $\\mathcal{O}(n^2 |\\Omega|^2)$ is quadratic on $n$. Can sparsity or incremental computation be exploited to reach web-scale graphs?", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort for reviewing our work, and for your thoughtful feedback. We appreciate the opportunity to address your concerns in this rebuttal and we will add a version of the discussion below in our revision.\n\n# Oracle access to underlying probability distribution $\\\\mathcal{P}$\n\nWe agree that the assumption of oracle access to $\\mathcal{P}$ may not always hold in practice. In real-world settings, such as modeling the spread of sexually transmitted infections (STIs), it is reasonable to approximate the distribution $\\mathcal{P}$ using a pairwise Markov Random Field (MRF) over the contact network $\\mathcal{G}$. As you kindly noted, we outline in Appendix B how the parameters $\\theta$ of such a model can be estimated from historical data via maximum pseudo-likelihood estimation (MPLE). In addition, Appendix E.3 contains an analysis of how errors in estimating $\\mathcal{P}$ affect decision quality.\n\nIn the original submission, we assumed that $\\mathcal{P}\\_{\\theta}$ (estimated via MPLE) was the ground truth. In response to your comment, we have conducted additional experiments during the rebuttal period to assess robustness when the policy only has access to a noisy version $\\mathcal{Q}\\_{\\theta}$ of the true distribution $\\mathcal{P}_{\\theta}$.\n\nWe perturbed the learned parameters $\\theta$ with noise of magnitude $\\varepsilon \\in \\\\{0.1, 0.3, 1\\\\}$ to simulate distributional mismatch, while keeping the evaluation grounded in the original $\\mathcal{P}\\_{\\theta}$. For reference, in the HIV setting, we have $\\ell_{\\infty}(\\theta_{\\text{unary}}) = 1.43$ and $\\ell_{\\infty}(\\theta_{\\text{pairwise}}) = 1.75$. Thus, $\\varepsilon = 1$ constitutes a significant perturbation.\n\nSince plots and external URLs are disallowed, we summarize our results in tabular form, reporting the expected undiscounted reward over a random subset of approximately 300 nodes in the HIV network (following the format in Appendix D.3). We focus on *undiscounted* reward as it better reflects the practical goals of maximizing the number of infected individuals detected under a fixed testing budget. For clarity, we **bold** the best-performing methods for each budget level.\n\n**Expected *undiscounted* reward for $\\mathcal{Q}_{\\theta, 0.1}$ on HIV network**\n\n| Percentage of nodes tested | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | 100% |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| Random | 6.1 | 11.4 | 16.0 | 19.4 | 22.3 | 24.6 | 26.6 | 28.2 | 29.8 | **31.6** |\n| Greedy | **20.1** | 25.8 | 26.6 | 26.8 | 27.0 | 27.5 | 30.1 | 31.0 | 31.2 | **31.6** |\n| DQN | 15.7 | 22.7 | 25.4 | 26.6 | 27.0 | 27.3 | 27.9 | 28.2 | 29.9 | **31.6** |\n| Gittins | **20.1** | **28.4** | **29.4** | **30.5** | **30.9** | **31.2** | **31.3** | **31.6** | **31.6** | **31.6** |\n\n**Expected *undiscounted* reward for $\\mathcal{Q}_{\\theta, 0.3}$ on HIV network**\n\n| Percentage of nodes tested | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | 100% |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| Random | 6.1 | 11.5 | 16.0 | 19.5 | 22.3 | 24.8 | 26.6 | 28.3 | 29.8 | **31.6** |\n| Greedy | **19.2** | 25.7 | 26.4 | 26.8 | 27.0 | 27.6 | 30.1 | 31.0 | 31.2 | **31.6** |\n| DQN | 8.1 | 14.3 | 22.4 | 24.3 | 25.6 | 26.4 | 27.9 | 29.0 | 30.0 | **31.6** |\n| Gittins | 19.1 | **25.8** | **28.6** | **30.3** | **30.8** | **31.1** | **31.3** | **31.6** | **31.6** | **31.6** |\n\n**Expected *undiscounted* reward for $\\mathcal{Q}_{\\theta, 1}$ on HIV network**\n\n| Percentage of nodes tested | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | 100% |\n| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |\n| Random | 5.8 | 11.4 | 13.7 | 19.8 | 22.5 | 24.7 | 26.4 | 28.1 | 29.7 | **31.6** |\n| Greedy | **16.6** | **22.3** | **23.8** | **24.8** | **26.7** | 27.6 | **30.1** | **30.8** | 31.2 | **31.6** |\n| DQN | 3.4 | 9.9 | 11.6 | 14.7 | 17.1 | 21.3 | 23.8 | 27.1 | 28.9 | **31.6** |\n| Gittins | 16.5 | 22.2 | **23.8** | **24.8** | 26.1 | **28.6** | 29.7 | 30.6 | **31.5** | **31.6** |\n\nFrom this preliminary set of experiments, we see that our proposed method (Gittins) remains competitive while the performance of all policies degrade as $\\mathcal{Q}_{\\theta,\\varepsilon}$ becomes less representative of $\\mathcal{P}$ due to larger $\\varepsilon$ values. In our revision, we plan to conduct a broader suite of such experiments across all the disease networks and report them in the appendix.\n\n# Scalability and runtime\n\nWe appreciate the concern regarding scalability. While the worst-case runtime of our Gittins index computation is $O(n^2 |\\Omega|^2)$, this is tractable in our target applications. In our datasets, $|\\Omega| = 2$ (binary test outcome), and graph sizes are typically $n \\leq 10,000$ in public health studies (see [1,2,3]). As shown in Figure 5 and Appendix D.4, our method runs efficiently in practice and is the fastest among all considered baselines on larger graphs. Additionally, as noted on Lines 134–140 of our paper, we believe this is the first work to present an efficient method for computing Gittins indices in discrete branching bandits with history-dependent rewards.\n\n[1] Peter Bearman, James Moody, Katherine Stovel. *Chains of affection: The structure of adolescent romantic and sexual networks*. American Journal of Sociology, 2004.\n\n[2] Joel Wertheim, Sergei Kosakovsky Pond, Lisa Forgione, Sanjay Mehta, Ben Murrell, Sharmila Shah, Davey Smith, Konrad Scheffler, Lucia Torian. *Social and Genetic Networks of HIV-1 Transmission in New York City*. PLoS Pathogens, 2017.\n\n[3] A M Young, A B Jonas, U L Mullins, D S Halgin, J R Havens. *Network structure and the risk for HIV transmission among rural drug users*. AIDS and Behavior, 2013.\n\n# Clarification of $\\phi_{X, b}$ and $\\Phi_{Ch(X),b}$\n    \nThank you for raising this point. We agree that the distinction between $\\phi_{X, b}$ and $\\Phi_{\\text{Ch}(X), b}$ could be clearer. To clarify:\n\n- $\\phi_{X, b}$ represents the expected value of the subtree rooted at node $X$, given that its parent has label $b$.\n- $\\Phi_{\\text{Ch}(X), b}$ captures the expected value of the subtree *excluding $X$ itself*. That is, the contributions from the children of $X$, conditioned on $X$ having label $b$.\n\nWe will make this distinction more explicit in our revision and improve the explanation in Lines 176–178.\n\n# Choice of deep RL baseline\n    \nWe appreciate the question regarding our choice of a single-step DQN as the deep RL baseline. While more recent graph-based RL and planning methods (e.g., policy gradient, Monte Carlo Tree Search) are indeed promising, they are generally data- and compute-intensive.\n\nIn our problem application domain of disease testing, the available data is often limited to a few hundred/thousand individuals with one label each. This makes it challenging to effectively train more complex models. Additionally, such methods often require significant computational resources (e.g., GPU clusters), which are typically unavailable to public health agencies.\n\nGiven these constraints, we focused on lightweight baselines like greedy and DQN that are both implementable and deployable in practice. As shown in Figure 5 and Appendix D.4, our method achieves strong performance while remaining efficient and practical."}, {"review_id": "hTJLN8U0mQ", "reviewer": "Reviewer_ALF3", "summary": "The authors propose the adaptive frontier graph exploration problem, whereby one wants to explode the nodes of a graph in which each node has a label, each label a reward. The goal is to maximize total expected (discounted) reward. The formulation essentially combines a Markov decision process with dynamic graph exploration. \n\nThey develop a Gittins-index approach, proving that their algorithm is optimal in the case of trees, and showing experimentally that it performs well in more complicated, real-world graphs based on disease networks. They also prove several new results concerning the computational tractability of the Gittins-index in their setting.", "questions": "1. Does the agent know the structure of the graph a priori? There are flavors of the graph exploration problem where the graph structure has to be discovered by exploring. \n\n2. I find the formulation of $\\pi^*$ a bit confusing. You seem to be using $X_\\pi$ to denote both the node itself and the node’s label (otherwise how can we have $X_\\pi = v$?). But the reward function treats $X_\\pi$ as the node itself, not the label. (Eg  in the public health example at the bottom of page 2 you treat $X$ as an individual). I’m not sure you should necessarily change anything, but if you agree with this, it might be worth commenting on. \n\n3. Is it realistic to assume that n is known in advance? In the public health example, it seems you might start exploring and only decide to stop based on what you find, or external factors such as budget etc. But it doesn’t seem likely that you’d commit to only testing n = 10,000 and, regardless of the outcomes, stop after that. \n\n4. You say: “Our work addresses this gap by presenting the first efficient implementation of Gittins-based policies in  discrete branching bandits with history-dependent rewards, enabling their use in structured settings like network-based disease testing.” (Pg 4). How general are the structured settings that you’re alluding to? If very general, one wonders why you’re focused on adaptive graph exploration the first place, and didn’t write the paper about the more general setting of discrete branching bandits. A sentence or two about this would be helpful for readers like me, who aren’t extremely familiar with this area. \n\n5. In Figure 4, it’s interesting that greedy outperforms DQN in ~half the experiments. This seems counterintuitive? Also, if you increase the number of extra edges, does the Gittins performance ever fall below greedy and/or DQN, or do they simply converge? \n\n**Minor comments**: \n- Researchers typo in line 200.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths \n- Good results, both on synthetic data and real-world data \n- Well motivated problem setting. The authors did a good job (modulo one complaint below) of tying the formalism back to a real world setting. \n- New results on the computational tractability of the Gittins-index. \n- Well written \n\n# Weaknesses \n- The mathematical details are a bit hard to follow for a non-expert in the area. The Gittins formulation in particular is not intuitive, nor do the authors spend that much time providing intuition. But I understand that space constraints make this challenging. \n- I find the generality of the result a bit hard to parse (see below). It seems that they solve a problem that may be more general than adaptive graph exploration. (This is a minor weakness; could even be a strength if addressed.) \n- I'd like to see the experimental results stretched a bit more - when does their algorithm start being worse than its competitors? Surely there are some scenarios in which it is not the best.", "was_revised": true, "final_justification": "Maintaining my original score.", "rebuttal": "Thank you for your time and effort for reviewing our work, and for your thoughtful feedback. We appreciate the opportunity to address your concerns in this rebuttal and we will add a version of the discussion below in our revision.\n\n# Gittins index computation example\n\nWe agree that the mathematical details of Gittins index computation can be difficult to follow, especially without prior familiarity. To provide better intuition, we will add the following worked example (with illustration) to the appendix of our revision. (Note: We're sorry that the \"align\" and \"cases\" are not rendering well on OpenReview...)\n\n> Consider a graph G on 7 nodes with edges $\\mathbf{E} = \\bigg\\\\{ \\\\{X_0, X_1\\\\}, \\\\{X_0, X_2\\\\}, \\\\{X_0, X_3\\\\}, \\\\{X_2, X_4\\\\}, \\\\{X_2, X_5\\\\}, \\\\{X_3, X_6\\\\} \\bigg\\\\}$. Let $X_0$ be the root node in this graph.\n\n> Consider the following simple joint binary distribution $\\mathcal{P}$ which assigns higher probabilities to realizations where adjacent nodes have the same status:\n$$\n\\mathcal{P}(x)\n= \\frac{1}{Z} \\prod_{\\{X_i, X_j\\}} \\exp \\left( 1_{X_i = X_j} \\right)\n$$\nwhere $1_{X_i = X_j}$ is the indicator whether the statuses of adjacent nodes $X_i$ and $X_j$ agree. One can verify that we have $\\mathcal{P}(u = 1 \\mid v = 0) = \\frac{1}{1+e}$ and $\\mathcal{P}(u = 1 \\mid v = 1) = \\frac{e}{1+e}$ for any non-root node $u$ with parent $v$.\n\n> Now, suppose the discount factor $\\beta = 0.9$ and we have a reward equal to the binary label for each node. Then, the largest reward $\\overline{r} = 1$ and $0 \\leq m \\leq \\frac{\\overline{r}}{1-\\beta} = 10$.\n\n> Our Gittins computation begins from the leaves. For instance, let us consider the leaf node $X_4$. When parent node $X_2 = 0$, one can verify that\n$$\n\\begin{align}\n\\phi_{X_4, 0}(m)\n&= \\max \\left\\\\{ m, \\mathcal{P}(X_4 = 0 \\mid X_2 = 0) \\cdot \\left[ 0 + \\beta \\cdot \\Phi_{\\emptyset, 0}(m) \\right] + \\mathcal{P}(X_4 = 1 \\mid X_2 = 0) \\cdot \\left[ 1 + \\beta \\cdot \\Phi_{\\emptyset, 0}(m) \\right] \\right\\\\}\\\\\n&= \\max \\left\\\\{ m, \\left( 1 - \\frac{1}{1+e} \\right) \\cdot \\beta \\cdot m + \\frac{1}{1+e} \\cdot \\left[ 1 + \\beta \\cdot m \\right] \\right\\\\}\\\\\n&= \\max \\left\\\\{ m, \\beta m + \\frac{1}{1+e} \\right\\\\}\n\\end{align}\n$$\nThat is, $\\phi_{X_4, 0}(m)$ is the following piecewise linear function:\n$$\n\\phi_{X_4, 0}(m) =\n\\begin{cases}\n\\beta m + \\frac{1}{1+e} & \\text{if $m \\leq \\frac{10}{1+e}$}\\\\\nm & \\text{if $m \\geq \\frac{10}{1+e}$}\n\\end{cases}\n$$\n\n> Meanwhile, when parent node $X_2 = 0$, one can verify that\n$$\n\\begin{align}\n\\phi_{X_4, 1}(m)\n&= \\max \\left\\\\{ m, \\mathcal{P}(X_4 = 0 \\mid X_2 = 1) \\cdot \\left[ 0 + \\beta \\cdot \\Phi_{\\emptyset, 0}(m) \\right] + \\mathcal{P}(X_4 = 1 \\mid X_2 = 1) \\cdot \\left[ 1 + \\beta \\cdot \\Phi_{\\emptyset, 0}(m) \\right] \\right\\\\}\\\\\n&= \\max \\left\\\\{ m, \\left( 1 - \\frac{e}{1+e} \\right) \\cdot \\beta \\cdot m + \\frac{e}{1+e} \\cdot \\left[ 1 + \\beta \\cdot m \\right] \\right\\\\}\\\\\n&= \\max \\left\\\\{ m, \\beta m + \\frac{e}{1+e} \\right\\\\}\n\\end{align}\n$$\nThat is, $\\phi_{X_4, 1}(m)$ is the following piecewise linear function:\n$$\n\\phi_{X_4, 1}(m) =\n\\begin{cases}\n\\beta m + \\frac{e}{1+e} & \\text{if $m \\leq \\frac{10e}{1+e}$}\\\\\nm & \\text{if $m \\geq \\frac{10e}{1+e}$}\n\\end{cases}\n$$\n\n> Due to symmetry in $\\mathcal{P}$, all the leaf nodes have exactly the same $\\phi_{X_{leaf}, b}$ functions for $b \\in \\{0,1\\}$.\n\n> Now, let us consider the computation of the function $\\Phi_{\\{X_4, X_5\\}, 0}$, which is required for the computation of $\\phi_{X_2, \\cdot}$. From Equation (2), we know that this involves the product of function derivatives $\\frac{\\partial \\phi_{X_4, 0}(k)}{\\partial k} \\cdot \\frac{\\partial \\phi_{X_5, 0}(k)}{\\partial k}$. From above, one can check that this evaluates to the following piecewise *constant* function:\n$$\n\\begin{cases}\n\\beta^2 & \\text{if $k \\leq \\frac{10}{1+e}$}\\\\\n1 & \\text{if $k \\geq \\frac{10}{1+e}$}\n\\end{cases}\n$$\nwhose integration from $0$ to $m$ yields the following piecewise linear function $h(m)$:\n$$\nh(m) =\n\\begin{cases}\n\\beta^2 m & \\text{if $k \\leq \\frac{10}{1+e}$}\\\\\nm - \\frac{10}{1 + e} (1 - \\beta^2) & \\text{if $k \\geq \\frac{10}{1+e}$}\n\\end{cases}\n$$\nUsing Proposition 5, we can derive that\n$$\n\\begin{align}\n\\Phi_{\\{X_4, X_5\\}, 0}(m)\n&= h(m) + 10 - h(10)\\\\\n&= h(m) + \\frac{10}{1+e}(1 - \\beta^2)\\\\\n&=\n\\begin{cases}\n\\beta^2 m + \\frac{10}{1+e}(1 - \\beta^2) & \\text{if $k \\leq \\frac{10}{1+e}$}\\\\\nm & \\text{if $k \\geq \\frac{10}{1+e}$}\n\\end{cases}\n\\end{align}\n$$\n\n> One can continue this computation up the rooted tree. Using our Gittins computation code, this produces\n$$\n\\phi_{X_0, \\emptyset} =\n\\begin{cases}\n0.4783 m + 2.6423 & \\text{if $0 \\leq m \\leq 2.6894$}\\\\\n0.5984 m + 2.3193 & \\text{if $2.6894 \\leq m \\leq 3.5900$}\\\\\n0.6461 m + 2.1479 & \\text{if $3.5900 \\leq m \\leq  4.1452$}\\\\\n0.7118 m + 1.8756 & \\text{if $4.1452 \\leq m \\leq 6.5088$}\\\\\nm & \\text{if $m \\geq 6.5088$}\n\\end{cases}\n$$\n\n# Stretching the experimental results\n\nThank you for this suggestion. During the rebuttal period, we conducted additional experiments where policies are evaluated on noisy approximations $\\mathcal{Q}\\_{\\theta}$ of the true underlying joint distribution $\\mathcal{P}\\_{\\theta}$. These experiments shed light on when and how performance degrades due to model mismatch. Due to character limits, we refer you to the rebuttals to other reviewers for full results, and we will include this expanded analysis in our revision.\n\n# Does the agent know the graph structure?\n\nYou are correct that our optimality guarantees assume full knowledge of the interaction graph $\\mathcal{G}$. In real-world disease testing, $\\mathcal{G}$ is often revealed incrementally: individuals are tested as they visit clinics, are interviewed by public health staff, and may refer peers via voucher programs. A practical strategy is to let this process run for a fixed period, yielding a partial observation of $\\mathcal{G}$, after which AFEG can then be applied to this discovered subgraph to guide the allocation of limited testing resources. This staged approach fits naturally into our framework. Extending our method to fully online graph discovery is a compelling direction for future work.\n\n# Notation Overload\n\nWe appreciate the reviewer's suggestion regarding potential ambiguity in our notation. We follow standard conventions in the graphical models literature, where variables and nodes are often used interchangeably, and the graph structure implicitly defines the factorization of the joint distribution. In this setting, it is common to use a symbol like $X$ to refer to both the node and its associated random variable, so that expressions like $X = v$ denote the event that variable $X$ takes value $v$. That said, we understand that readers from other communities may find this notation unfamiliar, and so we will include a brief remark early in the paper clarifying this convention to aid accessibility.\n\n# Knowing $n$ in advance\n\nYes, we consider the setting where the structure of the interaction graph $\\mathcal{G}$ is first obtained before testing decisions are made. Once $\\mathcal{G}$ is known, the total number of nodes $n$ is fixed, and we can plan whom to engage subject to a testing budget. Exploring settings with uncertain or dynamic $\\mathcal{G}$ is an interesting future direction.\n\nImportantly, our method does **not** require knowing the exact number of tests (i.e., the testing budget) in advance. Note that AFEG policies continually select an untested node given observed outcomes of tested nodes, and as a result could be seen as \"anytime policies\". That is, these AEFG policies can be executed sequentially and stopped at any point as resources are exhausted. In our experiments, we plot the cumulative performance of each policy as testing progresses, i.e., the total reward attained after testing 10%, 20%, …, up to 100% of the population. To assess performance under a specific budget, one can take a vertical slice of the plot at the desired percentage. For ease of comparison, we highlight the 50% mark with a dotted line in the figures in our submission, but any vertical slice yields a valid comparison. Each policy thus defines a full budget-performance tradeoff curve, and our method is not tuned for any particular testing threshold.\n\n# Generality of our result, and its relation with AFEG and branching bandits\n\nThank you for this observation. AFEG is a structured formulation that reflects real-world network testing constraints, particularly the frontier condition. While AFEG instances are not necessarily trees, one of our key contributions (Section 3.1) is to show that Gittins index policies are optimal for AFEG when the input graph is a forest.\n\nAs noted on Lines 134–140, although Gittins index policies are known to be optimal for branching bandits [KO03], no efficient implementation had been proposed previously. We believe our work is the first to provide a polynomial-time, polynomial-space implementation of Gittins indices in discrete branching bandits with history-dependent rewards, enabling their use in structured problems such as network-based disease testing.\n\nBy \"structured settings\", we mean other domains where the problem can be reduced to a branching bandit formulation, e.g., tree-based search under uncertainty or structured sequential diagnosis. We focused on AFEG due to our public health motivating application, but agree it would be worthwhile to explore more general applications in future work.\n\n# Figure 4 and Greedy versus DQN\n\nThank you for highlighting this. We observe that greedy outperforms DQN in some experiments, which can seem counterintuitive. One likely explanation is that DQN requires significant data to train and can overfit or underperform when training data is sparse or environments are not sufficiently varied. In contrast, greedy policies exploit strong local heuristics, which can be quite effective in certain structured networks."}]

Author rebuttal:

Meta-review: Summary: This paper introduces the Adaptive Frontier Exploration on Graphs (AFEG) problem, motivated by network-based disease testing, and develops an efficient Gittins index-based policy for it. The authors prove the policy is optimal for tree-structured graphs and demonstrate its strong empirical performance against baselines on both synthetic and real-world public health data.

Strengths: The paper's main strengths, as noted by all reviewers, are its practical problem formulation, its extensive empirical results on a real-world application, and its delivery of the first practical, polynomial-time algorithm for computing Gittins indices in this important class of branching bandit problems.

Weaknesses: The main weakness, highlighted during a detailed discussion with one reviewer, is that the core mathematical property (piecewise linearity) enabling the algorithm is a straightforward derivation from prior work, raising valid questions about the depth of the theoretical novelty.

Reasons for Decision: The decision to accept this paper is based on the judgment that its significant algorithmic contribution outweighs the concerns about pure theoretical novelty. The authors successfully designed the first efficient and practical algorithm for a problem that has been theoretically understood but computationally unsolved for two decades. This non-trivial leap from theory to a usable method, supported by an application and empirical evidence, constitutes a valid contribution to the field.

Discussion Process: While a high-level debate on the definition of novelty with one reviewer remained unresolved, the discussion supports the view that the paper's main contribution is a non-trivial algorithmic advance. The authors also successfully addressed other concerns, such as the assumption of oracle access to the data distribution. The authors will be expected to revise Theorem 6 in the final version to more precisely state their assumptions about the underlying probabilistic model, as discussed during the review process.
Decision: Accept (poster)