Learning When to Sample: Long-Horizon Budget Control for Graph Adaptive Filters

Many monitoring networks, including power grids, weather stations and sensor meshes, cannot read every node at every instant. An estimator tracks the full network state from a few measured nodes. Graph signal processing has good tools for choosing which nodes to read at a given moment. It has almost nothing for deciding how many to read now versus later. Under a fixed average budget, spending little during quiet periods and a lot during bursts can matter far more than squeezing the last bit of efficiency out of the choice of nodes. The best existing method for this timing problem looks only two steps ahead and requires an exactly known model of how the signal evolves.

We propose to split the problem into two parts. A fast greedy rule picks the nodes at each step, which is the part where greedy is already provably near-optimal. A small reinforcement-learning policy decides how much of a banked budget to spend at each step. It is trained with a dense reward built from the adaptive filter's own uncertainty, so that it learns long-horizon spending habits without being given the signal's dynamics. The two-sentence version is this: let greedy choose where to sample and let a learned controller choose when and how much. Train that controller with a reward equal to the step-by-step drop in the filter's estimated error, which leaves the best policy unchanged but gives a learning signal at every step.

Core Claim

Three terms first. A graph adaptive filter, such as graph least-mean-squares (LMS) or recursive least-squares (RLS), is an online estimator. It updates its estimate of a signal living on the graph's nodes each time a few nodes are measured (Adaptive Graph Signal Processing: Algorithms and Optimal Sampling Strategies). Informative node selection asks which subset of nodes to measure. Reward shaping adds an auxiliary reward to a sparse objective so that a learning agent gets feedback sooner.

Our claim is that a budget-allocation policy, trained with potential-based shaping on the filter's covariance trace, beats two kinds of methods when the signal's dynamics are unknown or switch abruptly. It beats myopic greedy samplers that spend a fixed amount per step. It also beats truncated two-stage dynamic programming. We further claim that the decomposition is what makes learning workable. A reinforcement-learning agent that chooses node subsets directly faces a combinatorial action space and would be both harder to train and no better at the within-step choice. Theory already says greedy is near-optimal for that choice in noisy regimes (Greedy Sampling of Graph Signals).

The shaping term is concrete. Let $P_t$ be the filter's error covariance over its $K$ spectral coefficients. When the filter's errors at sampled nodes exceed what $P_t$ predicts, $P_t$ is inflated. The potential is $\Phi_t = -\operatorname{tr}(P_t)$. The agent's reward at step $t$ is

$$r_t = -\|\mathbf{x}_t - \hat{\mathbf{x}}_t\|^2 + \gamma\,\Phi_{t+1} - \Phi_t,$$

where $\mathbf{x}_t$ is the true signal, $\hat{\mathbf{x}}_t$ the filter's estimate, and $\gamma$ the discount factor. The first term is the true tracking objective, available in simulation or on held-out nodes in real data. The second is a telescoping potential difference. Dynamic potential-based shaping provably leaves the optimal policy unchanged even when the potential depends on time (Dynamic potential-based reward shaping), and residual-driven inflation makes our potential time-dependent in exactly this way. One caveat matters. The guarantee assumes the agent's state is Markov. Here the state is the filter state plus the budget bank, which is only approximately Markov when dynamics are unknown, so we treat invariance as something to check empirically rather than assume.

Relation to Prior Work

The closest work is Sampling Policy Design for Tracking Time-varying Graph Signals with Adaptive Budget Allocation. It casts Kalman-filter tracking as a sequential decision problem with a long-run average budget, truncates the look-ahead to two stages, and proves that truncated problem convex. It motivates our work, because it shows that budget timing pays off: accumulated error 22.412 versus 460.124 for a myopic information-gain rule on a 100-node heat benchmark. It also constrains our work, because its gains are the bar to clear. We differ in two ways. Our horizon is set by a learned value function rather than a two-stage truncation. We also need no known transition matrix, only the filter's own covariance and residuals.

The static and probabilistic samplers supply the inner node picker but not the timing:

From A-Optimal Sampling and Robust Reconstruction for Graph Signals via Truncated Neumann Series we reuse the truncated Neumann and Chebyshev approximations. These let the inner greedy rule run without a full eigendecomposition of the graph.

On the reinforcement-learning side, two papers supply the method:

INSPIRE-GNN uses reinforcement learning for one-time static sensor placement. It is adjacent work, but it involves no online filter and no budget timing.

Research Program

The system. We would build the following loop. A graph RLS filter, plus a graph LMS variant, tracks a signal assumed approximately bandlimited to $K$ spectral components. Each step, the controller sees a compact state:

  • the covariance trace and its recent change,
  • the norm of the filter errors at sampled nodes and a short history of that norm,
  • the remaining budget bank, which refills by the average budget $\bar M$ per step,
  • a coarse summary of where residuals are concentrated on the graph, pooled over graph clusters.

The controller outputs a spend $m_t \le$ bank. Neumann-approximated greedy A-optimality, which minimizes the trace of the reconstruction error covariance, then picks $m_t$ nodes, with node scores weighted by the inflated $P_t$. The bank enforces the average budget exactly, so no penalty tuning is needed. The controller is a small actor-critic network trained in simulation.

Analyses. Besides the main comparisons, we would run two analyses. First, we would check whether shaping really preserves the learned policy, by comparing converged policies under shaped and unshaped rewards given long training. Second, we would characterize what the controller has learned. We expect it to bank budget during quiet periods, spend before predictable bursts, and spend in response to error spikes. A result where the controller behaves like a simple threshold rule would itself be informative.

Baselines

Naive reference. The do-nothing point is uniform random sampling of exactly $\bar M$ nodes per step, feeding the same RLS filter. Anything that does not clearly beat it is uninformative.

Fixed-budget greedy. This is Neumann-approximated greedy A-optimality (A-Optimal Sampling and Robust Reconstruction for Graph Signals via Truncated Neumann Series), run at every step with $m_t = \bar M$ and with the same residual-inflated covariance. It is the strongest myopic competitor and is identical to our system except for the controller. This makes it the cleanest ablation of the learned timing. Beating it means lower accumulated error at equal average budget on non-stationary signals.

Strongest existing method. This is the two-stage truncated dynamic program of Sampling Policy Design for Tracking Time-varying Graph Signals with Adaptive Budget Allocation. On its 100-vertex heat-diffusion benchmark it reports accumulated tracking error 22.412, against 26.582 for its myopic signal-aware baseline. On its 7-cluster opinion-dynamics graph it reports long-term NMSE 0.7186, against 0.7385 for the best baseline.

We would reimplement both benchmarks and report our reproduced numbers next to the published ones. The dynamic program would be run in two arms. In the oracle arm it receives the true transition model; there we expect at best to match it. In the realistic arm it receives a transition model estimated online by least squares from the same data our controller sees. Beating it means lower error than the estimated-model arm under switching or nonlinear dynamics, and staying within a few percent of the oracle arm when dynamics are linear and known.

Event-triggered rule. We would also include a hand-designed two-parameter rule that spends more when the error norm exceeds a threshold. It is tuned by grid search with the same number of simulator episodes the controller uses for training.

Reward ablations. These isolate the shaping ingredient. The controller is trained three ways: with the sparse terminal objective only, with the naive per-step error reduction (which is not potential-based and is prone to hacking), and with our potential. Each gets identical training budgets and seeds.

End-to-end reinforcement learning. Finally, an agent that chooses node subsets directly tests whether the decomposition matters.

All methods share the filter, the graph, the noise realizations and the average budget. Learned and tuned methods get matched simulator-episode budgets.

Why not just…?

Why not just use the event-triggered threshold rule? This is the real threat. If budget timing only needs to react to error spikes, a two-parameter rule may capture nearly all the gain. Our bet is that learning helps where spending must anticipate events: periodic loads on the power grid, diurnal temperature swings, a heat source on a predictable trajectory. Reacting after the error appears is already too late there. The tuned threshold rule is a full baseline. If it comes within noise of the controller on all benchmarks, we will report that the learned controller is unnecessary and that the contribution reduces to residual-inflated greedy plus event triggering.

Why not just run greedy at every step, since it is near-optimal? Greedy Sampling of Graph Signals proves near-optimality for the within-step subset choice, and it is sharpest at low signal-to-noise ratio. That is exactly why we keep greedy as the inner picker. The theory says nothing about spending across time. The 460.124 versus 22.412 gap in Sampling Policy Design for Tracking Time-varying Graph Signals with Adaptive Budget Allocation shows that timing can dominate. Our fixed-budget greedy ablation measures this directly on our own benchmarks.

Why not just extend the dynamic program, or fit a model and plan? Planning beyond two stages over subsets grows exponentially, and the convexity result relies on a known linear transition model. The estimated-model arm of the dynamic-program baseline is the fair version of "fit a model and plan." When dynamics really are linear and stationary, this baseline may win. We will report that regime honestly rather than avoid it.

Why not just do convex relaxation offline? Design of Sampling Set for Bandlimited Graph Signal Estimation produces fixed sampling proportions that need repeated measurements to realize. It does not respond to the signal at all, so it falls into the same static class as the probabilistic design of Adaptive Graph Signal Processing, which we include as a secondary baseline.

Proposed Experiments

Benchmarks. We would use four benchmarks:

  • The 100-vertex heat-diffusion benchmark, in two variants: the original random-walk source, and a switched source whose speed and diffusion rate change abruptly at unannounced times.
  • The 7-cluster Krause–Hegselmann opinion-dynamics graph. Its nonlinear dynamics already stress any planner that assumes linearity.
  • The IEEE 118-bus power network and the 109-station U.S. hourly temperature data used in Adaptive Graph Signal Processing. For these, no reported numerical result was found on Lacuna, and they are evaluated with held-out stations as ground truth.
  • A 1000-node Watts–Strogatz graph (mean degree 8, rewiring probability 0.1, $K = 50$) following A-Optimal Sampling and Robust Reconstruction for Graph Signals via Truncated Neumann Series, to test scale.

Metrics. These are accumulated tracking error, long-term NMSE, worst-window error during bursts, and wall-clock time per decision.

Decisive check 1: timing under unknown dynamics. On switched heat diffusion and opinion dynamics, the controller should beat fixed-budget greedy, the estimated-model dynamic program and the tuned threshold rule at equal average budget, across at least ten seeds. Failing against the threshold rule falsifies the need for learning.

Decisive check 2: the shaping ingredient. Under matched training budgets, the potential-shaped controller should reach a given error level in fewer episodes than both the sparse-reward and the naive-reward versions. The naive version should show measurable hacking, such as hoarding budget to keep the covariance artificially low. Converged shaped and unshaped policies should agree.

Decisive check 3: where the gain lives. We would sweep signal-to-noise ratio and the degree of non-stationarity. Following the supermodularity result, we predict essentially no gain over fixed-budget greedy on stationary low-SNR signals, and a gain that grows with how predictable the bursts are. Gains on stationary low-SNR signals would suggest the controller is exploiting something other than timing, and we would examine it. A complete absence of gains on burst-driven signals would mean the decomposition does not pay off.

Decisive check 4: model-known regime. With the oracle linear model on the original heat benchmark, we report how close the controller comes to the dynamic program's oracle arm, set against its published 22.412. This bounds the price paid for learning without a model.