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.

Gittins index computation example

We 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...)

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.

Consider the following simple joint binary distribution $\mathcal{P}$ which assigns higher probabilities to realizations where adjacent nodes have the same status:

where $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$.

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$.

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

That is, $\phi_{X_4, 0}(m)$ is the following piecewise linear function:

Meanwhile, when parent node $X_2 = 0$, one can verify that

That is, $\phi_{X_4, 1}(m)$ is the following piecewise linear function:

Due to symmetry in $\mathcal{P}$, all the leaf nodes have exactly the same $\phi_{X_{leaf}, b}$ functions for $b \in \{0,1\}$.

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:

whose integration from $0$ to $m$ yields the following piecewise linear function $h(m)$:

Using Proposition 5, we can derive that

One can continue this computation up the rooted tree. Using our Gittins computation code, this produces

Stretching the experimental results

Thank 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.

Does the agent know the graph structure?

You 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.

Notation Overload

We 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.

Knowing $n$ in advance

Yes, 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.

Importantly, 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.

Generality of our result, and its relation with AFEG and branching bandits

Thank 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.

As 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.

By "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.

Figure 4 and Greedy versus DQN

Thank 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.

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.

Oracle access to underlying probability distribution $\\mathcal{P}$

We 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.

In 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}$.

We 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.

Since 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.

Expected undiscounted reward for $\mathcal{Q}_{\theta, 0.1}$ on HIV network

Expected undiscounted reward for $\mathcal{Q}_{\theta, 0.3}$ on HIV network

Expected undiscounted reward for $\mathcal{Q}_{\theta, 1}$ on HIV network

From 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.

Scalability and runtime

We 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.

[1] Peter Bearman, James Moody, Katherine Stovel. Chains of affection: The structure of adolescent romantic and sexual networks. American Journal of Sociology, 2004.

[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.

[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.

Clarification of $\phi_{X, b}$ and $\Phi_{Ch(X),b}$

Thank 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:

• $\phi_{X, b}$ represents the expected value of the subtree rooted at node $X$, given that its parent has label $b$.
• $\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$.

We will make this distinction more explicit in our revision and improve the explanation in Lines 176–178.

Choice of deep RL baseline

We 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.

In 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.

Given 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.

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.

Theorem 3 and novelty

We 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:

1. Proving new structural properties of the Gittins computation (Lemma 4 and Proposition 5)
2. Developing a polynomial-time algorithm with an accompanying implementation to compute Gittins indices (Theorem 6)

BFS tree projection

We 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.

For 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.

Extending to continuous label space

We 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.

That 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.

Oracle access to underlying probability distribution $\\mathcal{P}$

We 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.

In 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}$.

We 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.

Since 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.

Expected undiscounted reward for $\mathcal{Q}_{\theta, 0.1}$ on HIV network

Expected undiscounted reward for $\mathcal{Q}_{\theta, 0.3}$ on HIV network

Expected undiscounted reward for $\mathcal{Q}_{\theta, 1}$ on HIV network

From 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.

Clarification regarding figure 14

Thank 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.

Low $\beta$ on real-world dataset

As 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.

To 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.

Expected undiscounted reward for $\beta = 0.1$ on HIV network

Expected undiscounted reward for $\beta = 0.99$ on HIV network

Gittins 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).

Notation Overload

We 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.

I would like to thank the authors for their clarifications. I believe the contribution of this paper to be primarily experimental, specifically, formulating network-based disease testing as an AFEG (branching bandit) problem and applying Gittins-index based algorithm to this problem for real world datasets. The theoretical aspects of this work are not that novel, therefore, the contribution 1 of the paper bears less weightage to me. I feel that focusing and strengthening contribution 2 and 3 will be more beneficial to the current work. The detailed concerns are as follows.

Theorem 3 and novelty: Lemma 4 is already observed as a remark by KO03 in their proof of theorem 1 (see the paragraph between eqn 2 and 3). Proposition 5 does not seem related to the current paper, and indeed the authors mention it as some additional properties they prove. Therefore, the theoretical contribution of this work is marginal. The only important theoretical contribution I feel this paper makes is Theorem 6. However, once the authors note Lemma 4 (observation in KO03), this follows directly via a dynamic programming argument. Moreover, in the proof of Theorem 6, the authors assume “any conditional probability value can be obtained in constant time via oracle access to P” (line 802-803) whereas in the theorem statement, the assumption is oracle access to joint distribution P. Can the authors lay out how to construct a conditional probability model in constant time out of a joint distribution? Otherwise, the theorem statement is misleading.

Continuous Label Space: Note that $\phi$ is a piecewise linear function with finitely many pieces, so even if its derivative is non-continuous, it is piecewise constant. With the other theoretical results in the paper seeming limited to me, I would like to encourage the authors to investigate this direction as an interesting theory question.

Experimental Results: The experimental results are promising even under perturbed $\theta$. However, note that this does not fully address my concern, which was regarding an (Gittins-index based) algorithm that works with sample access to the distribution. The current set of experiments presented by the authors in the rebuttal only backs up their theory in Appendix E.3 (Lemma 8), which was never my concern. To reiterate, this work might benefit from an algorithm that can work with samples from the distribution to construct (noisy) Gittins index.

Continuous label space

We agree that extending the framework to continuous label spaces is an interesting direction for future work. Our current focus addresses discrete label settings, and already generalizes beyond the binary case of our real-world motivation of disease testing. Further extensions to continuous domains would be valuable, but are beyond the natural scope of this work and not necessary to demonstrate the strength of our current contributions.

Sample-based access vs. model-based estimation

Thank you for clarifying this point. Developing Gittins-like policies that operate directly from sample-based access is indeed an interesting direction. Our current approach uses a learned model to compute exact indices and achieves strong empirical performance. Exploring sample-based variants is complementary to our framework, but beyond the intended scope of this paper.

Final remarks

We appreciate your interest in directions such as continuous label spaces and sample-based estimation. While we agree that these are intellectually interesting, we respectfully view these as natural next steps, rather than missing components of the current paper. The core contribution of this work --- its problem formulation, structural reduction, efficient algorithm design, and strong empirical performance --- is, in our view, already substantial and meets the bar for publication on its own merit. Requiring these additional components would significantly broaden the scope beyond what is typical for a single conference paper.

References

[1] Avrim Blum, Nika Haghtalab, Ariel D. Procaccia. "Learning optimal commitment to overcome insecurity". NeurIPS, 2014.

[2] Blog post by Ariel D. Procaccia: https://agtb.wordpress.com/2012/06/17/is-game-theory-useful/

[3] Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, Ariel D. Procaccia. "Commitment Without Regrets: Online Learning in Stackelberg Security Games". EC, 2015.

[4] A more recent work: Maria-Florina Balcan, Kiriaki Fragkia, and Keegan Harris. "Learning in Structured Stackelberg Games". arXiv, 2025.

[5] Aditya Mate, Jackson A. Killian, Haifeng Xu, Andrew Perrault, Milind Tambe. "Collapsing bandits and their application to public health intervention". NeurIPS, 2020.

[6] Dexun Li, Pradeep Varakantham. "Efficient resource allocation with fairness constraints in restless multi-armed bandits". UAI, 2022.

[7] Archit Sood, Shweta Jain, Sujit Gujar. "Fairness of Exposure in Online Restless Multi-armed Bandits". AAMAS, 2024.

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.

Oracle access to underlying probability distribution $\\mathcal{P}$

We 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.

In 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}$.

We 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.

Since 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.

Expected undiscounted reward for $\mathcal{Q}_{\theta, 0.1}$ on HIV network

Expected undiscounted reward for $\mathcal{Q}_{\theta, 0.3}$ on HIV network

Expected undiscounted reward for $\mathcal{Q}_{\theta, 1}$ on HIV network

From 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.

Structure of real-world graphs

We 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.

[1] Peter Bearman, James Moody, Katherine Stovel. Chains of affection: The structure of adolescent romantic and sexual networks. American Journal of Sociology, 2004.

[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.

[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.

$\theta_1$ and $\theta_2$

$\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.

Non-decreasing piecewise linear function

The 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.

Limitations

As mentioned in Section 5, we have provided additional discussion on broader impact and limitations in Appendix C.