Adaptive Frontier Exploration on Graphs with Applications to Network-Based Disease Testing

• URL: http://arxiv.org/abs/2505.21671v3
• Date: Tue, 28 Oct 2025 20:04:11 GMT
• Title: Adaptive Frontier Exploration on Graphs with Applications to Network-Based Disease Testing
• Abstract summary: We study a sequential decision-making problem on a $n$-node graph $mathcalG$ where each node has an unknown label.<n>We design a Gittins index-based policy that applies to general graphs and is provably optimal when $mathcalG$ is a forest.
• Score: 28.977968088499566
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  We study horizon-free regret for finite-horizon time-homogeneous Markov decision processes with $A$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$.<n>We prove a regret upper bound [tilde O(sqrtSAK+S8A3)] with failure probability $$, where $K$ is the number of episodes and $tilde O(sqrtSAK+S3K)$ hides $mathsfpoly
  arXiv  Detail & Related papers  (2026-07-22T07:42:19Z)
• Quantum Algorithm for Identifying Hidden Graphs: Spectral Theory and Numerical Evidence [0.0]
  We give a quantum algorithm for identifying a hidden $d$-regular base graph $G$ on $n$ vertices from access to an obfuscated version of it.<n>Our algorithm is conceptually simple: a continuous-time walk on $G_rm spire$, followed by a single Hadamard test at a classically pret*$.
  arXiv  Detail & Related papers  (2026-05-11T20:44:32Z)
• Detection of local geometry in random graphs: information-theoretic and computational limits [4.67223325681232]
  We study the problem of detecting local geometry in random graphs.<n>We introduce a model $mathcalG(n, p, d, k)$, where a hidden community of average size $k$ has edges drawn as a random geometric graph.<n>All remaining edges follow the Erds--Rényi model $mathcalG(n, p)$.
  arXiv  Detail & Related papers  (2026-03-25T17:20:01Z)
• Asymptotically perfect seeded graph matching without edge correlation (and applications to inference) [2.313664320808389]
  We present the OmniMatch algorithm for seeded multiple graph matching.<n>We demonstrate the effectiveness of our algorithm across numerous simulations and in the context of shuffled graph hypothesis testing.
  arXiv  Detail & Related papers  (2025-06-03T12:54:24Z)
• Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries [34.38978643261337]
  We study the online shortest path problem in directed acyclic graphs (DAGs) under bandit feedback against an adaptive adversary.<n>We propose the first computationally efficient algorithm to achieve a near-minimax optimal regret bound of $tilde O(sqrt|E|Tlog |X|)$ with high probability against any adaptive adversary.
  arXiv  Detail & Related papers  (2025-04-01T06:35:42Z)
• Collaborative non-parametric two-sample testing [55.98760097296213]
  The goal is to identify nodes where the null hypothesis $p_v = q_v$ should be rejected. We propose the non-parametric collaborative two-sample testing (CTST) framework that efficiently leverages the graph structure. Our methodology integrates elements from f-divergence estimation, Kernel Methods, and Multitask Learning.
  arXiv  Detail & Related papers  (2024-02-08T14:43:56Z)
• Minimizing Polarization in Noisy Leader-Follower Opinion Dynamics [17.413930396663833]
  We consider a problem of polarization optimization for the leader-follower opinion dynamics in a noisy social network. We adopt the popular leader-follower DeGroot model, where the opinion of every leader is identical and remains unchanged, while the opinion of every follower is subject to white noise. We show that the objective function is monotone and supermodular. We then propose a simple greedy algorithm with an approximation factor $1-1/e$ that approximately solves the problem in $O((n-q)3)$ time.
  arXiv  Detail & Related papers  (2023-08-14T08:52:24Z)
• Fast Online Node Labeling for Very Large Graphs [11.700626862639131]
  Current methods either invert a graph kernel runtime matrix with $mathcalO(n3)$ or $mathcalO(n2)$ space complexity or sample a large volume of random spanning trees. We propose an improvement based on the textitonline relaxation technique introduced by a series of works.
  arXiv  Detail & Related papers  (2023-05-25T17:13:08Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  We show that our algorithm achieves an $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ are the cardinalities of the state and action spaces
  arXiv  Detail & Related papers  (2023-05-15T05:37:32Z)
• Multi-armed Bandit Learning on a Graph [0.0]
  We study an extension of MAB called the graph bandit, where an agent travels over a graph to maximize the reward collected from different nodes. We design a learning algorithm, G-UCB, that balances long-term exploration-exploitation using the principle of optimism. Our proposed algorithm achieves $O(sqrt|S|Tlog(T)+D|S|log T)$ learning regret, where $|S|$ is the number of nodes and $D$ is the diameter of the graph.
  arXiv  Detail & Related papers  (2022-09-20T02:31:42Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  This paper studies the problem of designing an optimal sequence of interventions in a causal graphical model. It is assumed that the graph's structure is known and has $N$ nodes. Two algorithms are proposed for the frequentist (UCB-based) and Bayesian settings.
  arXiv  Detail & Related papers  (2022-08-26T16:21:31Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  We study the problem of estimating the value of a known smooth function $f$ at an unknown point $boldsymbolmu in mathbbRn$, where each component $mu_i$ can be sampled via a noisy oracle. We design an instance-adaptive algorithm that learns to sample according to the importance of each coordinate, and with probability at least $1-delta$ returns an $epsilon$ accurate estimate of $f(boldsymbolmu)$.
  arXiv  Detail & Related papers  (2022-03-18T18:50:52Z)
• A framework for optimal quantum spatial search using alternating phase-walks [0.0]
  We generalise the Childs & Goldstone ($mathcalCG$) algorithm via alternating applications of marked-vertex phase shifts and continuous-time quantum walks. We demonstrate the effectiveness of the algorithm by applying it to obtain $mathcalO(sqrtN)$ search on a variety of graphs.
  arXiv  Detail & Related papers  (2021-09-29T11:16:52Z)
• Maximizing Influence of Leaders in Social Networks [15.05158252504978]
  We consider the edge addition problem for the DeGroot model of opinion dynamics in a social network with $n$ nodes and $m$ edges. We show that our algorithm is efficient and effective, which scales to large networks with more than a million nodes.
  arXiv  Detail & Related papers  (2021-06-11T02:31:46Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
  We study the reward-free reinforcement learning framework, which is particularly suitable for batch reinforcement learning and scenarios where one needs policies for multiple reward functions. We give a new efficient algorithm, textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname), which interacts with the environment at most $Oleft( fracS2Aepsilon2textpolylogleft(fracSAHepsilon2
  arXiv  Detail & Related papers  (2020-10-12T17:51:19Z)
• Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback [15.533908352376853]
  We look for a set of $k$ nodes that maximize the expected number of nodes that are reached by an influence cascade. We show that the adaptivity gap is upper-bounded by $lceil nrceil $, where $n$ is the number of nodes in the graph. We also show that in 0-bounded graphs, i.e. undirected graphs, the adaptivity gap is at most $frac3e3e3-1approx 3.16$.
  arXiv  Detail & Related papers  (2020-06-27T14:43:34Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  We consider the problem of learning the best-fitting single neuron as measured by the expected square loss. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$.
  arXiv  Detail & Related papers  (2020-05-29T07:20:35Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  We study learning in contextual bandits with the help of loss predictors. We show that the optimal regret is $mathcalO(minsqrtT, sqrtmathcalETfrac13)$ when $mathcalE$ is known.
  arXiv  Detail & Related papers  (2020-03-04T07:36:38Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.