Learning from Local Walks on Dynamic Graphs with Bandit Feedback

• URL: http://arxiv.org/abs/2607.10571v1
• Date: Sun, 12 Jul 2026 04:56:02 GMT
• Title: Learning from Local Walks on Dynamic Graphs with Bandit Feedback
• Abstract summary: We study multi-armed bandits on dynamic graphs, where arms correspond to the vertices of a network with time-varying edges.<n>We identify a process-agnostic structural condition, based on sliding-window mixing, that ensures the graph's intrinsic walk remains stable for both exploration and navigation.
• Score: 7.465238700168576
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study stochastic multi-armed bandits on dynamic graphs, where arms correspond to the vertices of a network with time-varying edges. In this setting, the learner is restricted to local movement, selecting only its current node or an immediate neighbor at each round. This constraint decouples best-arm identification from exploitation: even after the optimal arm is identified, the learner may remain unable to reach it through the evolving topology. We identify a process-agnostic structural condition, based on sliding-window mixing, that ensures the graph's intrinsic walk remains stable for both exploration and navigation. Under this regime, we analyze a family of local explore-then-commit algorithms and establish sublinear expected regret. Our framework includes a reward-aware strategy, for which we prove a worst-case safety theorem and a separate performance gain theorem.

Related papers

• Anticipatory Reinforcement Learning: From Generative Path-Laws to Distributional Value Functions [0.0]
  This paper introduces Anticipatory Reinforcement Learning (ARL), a novel framework designed to bridge the gap between non-Markovian decision processes and classical reinforcement learning architectures.<n>In environments characterised by jump-diffusions and structural breaks, traditional state-based methods often fail to capture the essential path-dependent geometry required for accurate foresight.
  arXiv  Detail & Related papers  (2026-04-06T13:15:44Z)
• On Multi-Step Theorem Prediction via Non-Parametric Structural Priors [50.16583672681106]
  In this work, we explore training-free theorem prediction through the lens of in-context learning (ICL)<n>We propose Theorem Precedence Graphs, which encode temporal dependencies from historical solution traces as directed graphs, and impose explicit topological constraints that effectively prune the search space during inference.<n>Experiments on the FormalGeo7k benchmark show that our method achieves 89.29% accuracy, substantially outperforming ICL baselines and matching state-of-the-art supervised models.
  arXiv  Detail & Related papers  (2026-03-05T06:08:50Z)
• Learning to Explore: Policy-Guided Outlier Synthesis for Graph Out-of-Distribution Detection [51.93878677594561]
  In unsupervised graph-level OOD detection, models are typically trained using only in-distribution (ID) data.<n>We propose a Policy-Guided Outlier Synthesis framework that replaces statics with a learned exploration strategy.
  arXiv  Detail & Related papers  (2026-02-28T11:40:18Z)
• Flickering Multi-Armed Bandits [7.465238700168576]
  We introduce Flickering Multi-Armed Bandits (FMAB), a new MAB framework where the set of available arms (or actions) can change at each round.<n>We model this constrained, evolving availability using random graph processes, where arms are nodes and the agent's movement is restricted to its local neighborhood.<n>We show that our algorithm is near-optimal by establishing a matching information-theoretic lower bound for this problem class.
  arXiv  Detail & Related papers  (2026-02-19T12:24:01Z)
• Adaptive Initial Residual Connections for GNNs with Theoretical Guarantees [7.831509538890674]
  We investigate an adaptive residual scheme in which different nodes have varying residual strengths.<n>We prove that this approach prevents oversmoothing; particularly, we show that the Dirichlet energy of the embeddings remains bounded away from zero.<n>This is the first theoretical guarantee not only for the adaptive setting, but also for static residual connections with activation functions.
  arXiv  Detail & Related papers  (2025-11-10T01:08:37Z)
• Learning by Steering the Neural Dynamics: A Statistical Mechanics Perspective [0.0]
  We study how neural dynamics can support fully local, distributed learning.<n>We propose a biologically plausible algorithm for supervised learning with any binary recurrent network.
  arXiv  Detail & Related papers  (2025-10-13T22:28:34Z)
• On the Effective Usage of Priors in RSS-based Localization [56.68864078417909]
  We propose a Received Signal Strength (RSS) fingerprint and convolutional neural network-based algorithm, LocUNet. In this paper, we study the localization problem in dense urban settings. We first recognize LocUNet's ability to learn the underlying prior distribution of the Rx position or Rx and transmitter (Tx) association preferences from the training data, and attribute its high performance to these.
  arXiv  Detail & Related papers  (2022-11-28T00:31:02Z)
• Modelling Neighbor Relation in Joint Space-Time Graph for Video Correspondence Learning [53.74240452117145]
  This paper presents a self-supervised method for learning reliable visual correspondence from unlabeled videos. We formulate the correspondence as finding paths in a joint space-time graph, where nodes are grid patches sampled from frames, and are linked by two types of edges. Our learned representation outperforms the state-of-the-art self-supervised methods on a variety of visual tasks.
  arXiv  Detail & Related papers  (2021-09-28T05:40:01Z)
• Spatial-spectral Hyperspectral Image Classification via Multiple Random Anchor Graphs Ensemble Learning [88.60285937702304]
  This paper proposes a novel spatial-spectral HSI classification method via multiple random anchor graphs ensemble learning (RAGE) Firstly, the local binary pattern is adopted to extract the more descriptive features on each selected band, which preserves local structures and subtle changes of a region. Secondly, the adaptive neighbors assignment is introduced in the construction of anchor graph, to reduce the computational complexity.
  arXiv  Detail & Related papers  (2021-03-25T09:31:41Z)
• Latent Bandits Revisited [55.88616813182679]
  A latent bandit problem is one in which the learning agent knows the arm reward distributions conditioned on an unknown discrete latent state. We propose general algorithms for this setting, based on both upper confidence bounds (UCBs) and Thompson sampling. We provide a unified theoretical analysis of our algorithms, which have lower regret than classic bandit policies when the number of latent states is smaller than actions.
  arXiv  Detail & Related papers  (2020-06-15T19:24:02Z)
• Learning Representations using Spectral-Biased Random Walks on Graphs [18.369974607582584]
  We study how much a probabilistic bias in this process affects the quality of the nodes picked by the process. We succinctly capture this neighborhood as a probability measure based on the spectrum of the node's neighborhood subgraph represented as a normalized laplacian matrix. We empirically evaluate our approach against several state-of-the-art node embedding techniques on a wide variety of real-world datasets.
  arXiv  Detail & Related papers  (2020-05-19T20:42:43Z)

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.