CS Paper Radar

Worse Routes, Fresher Information: Preemption Redefines Which Route is Best

Adem Utku Atasayar, Aimin Li, Elif Uysal

cs.IT ·submitted 2026-09-12 00:23 UTC · v2
published

Abstract

This paper studies joint sampling, route activation, and preemption control over $N$ heterogeneous transmission routes under a long-run objective combining Age of Information (AoI) with sampling and transmission costs. We formulate the problem as an average-cost impulse-control model, derive a vector-form integral average-cost optimality equation over a hybrid state space, and establish structural reductions on the state. We consider a two-route case and compute optimized policies using discretized policy iteration. Surprisingly, the results show that preemption can reverse routing preferences: the optimized policy may exclusively use a route with both a larger mean delay and a larger delay variance while avoiding the seemingly superior route. Relative to baselines that do not allow preemption, the proposed policy reduces average AoI by up to $96\%$.

Comment
6 pages, 3 figures. Accepted at the Beyond AoI Workshop, ACM MobiHoc 2026. Version 2 adds acknowledgments and publication information
DOI
10.1145/3842721.3850127

Closest papers

Nearest neighbours by meaning across the whole index.

Fundamental Tradeoffs in Sampling, Transmission and Information Freshness: Instantaneous Feedback

cs.IT cs.NIeess.SY ·2026-11-16 ·Subhankar Banerjee, Sennur Ulukus
theory similarity 0.62
Abstract

We study a time-slotted generate-at-will status-update system over an erasure channel with transmission success probability $q$, subject to average sampling- and transmission-rate constraints $f_s$ and $f_r$, respectively. The sampler-transmitter pair jointly decides whether to idle, retransmit a stale packet, or replace it with a fresh sample. We derive a universal lower bound on the optimal average age of information, analyze a class of stationary randomized policies, and obtain an optimal policy within this class that provides a $4$-approximation guarantee. The joint problem reduces to the sampling-constrained problem when $f_s\leq qf_r$ and the transmission-constrained problem when $f_s\geq f_r$. For $qf_r<f_s<f_r$, we formulate a constrained Markov decision process (CMDP) and introduce the class $\barΠ$ of $(W,R)$ policies, where $W$ specifies a waiting threshold for transmission and $R$ specifies a packet-replacement threshold. We prove that, for every choice of Lagrange multipliers, the corresponding Lagrangian-relaxed Markov decision process admits an optimal policy in $\barΠ$. We then formulate a linear program (LP) over distributions of $(W,R)$ policies and prove that choosing a policy according to an optimal LP solution yields an optimal CMDP policy. Moreover, there exists an optimal LP solution assigning positive probability to at most three $(W,R)$ policies. Since $\barΠ$ is countably infinite, for every $ε>0$ we construct a finite subset $\barΠ_ε\subset\barΠ$ and show that the LP restricted to this set yields an $ε$-optimal policy. Finally, we derive a stronger pair of lower bounds by considering systems with only the sampling-rate or transmission-rate constraint. Using these bounds, we construct a policy randomizing among four $(W,R)$ policies with a $2$-approximation guarantee for $qf_r<f_s<f_r$.

0.12

From Learned-Mode AV-Traffic Pairing to Planner Decisions: A Marginal-Preserving Study on Argoverse 2

cs.RO ·2026-09-14 ·Jingyu Wang
similarity 0.58
Abstract · 8 pages, 4 figures. Accepted to the 16th Workshop on Planning, Perception and Navigation for Intelligent Vehicles (PPNIV), held in conjuncti…

Joint motion forecasts pair each autonomous-vehicle (AV) future with surrounding traffic, but actor-level metrics do not show whether that structure matters to a planner. We study this question with a marginal-preserving product control that removes AV-traffic pairing among the learned modes while retaining the fixed constant-velocity pair and holding trajectories, actor-level marginals before planner conditioning, candidates, the cost terms and weights, and fallback fixed. The intervention also changes candidate-conditioned concentration. Across twelve runs on 1,400 held-out Argoverse 2 scenarios, the intervention changes 3.0% of route-level offline selections at $τ=4$ m. Control-minus-joint recorded-trajectory regret is $-0.026$ and $-0.118$ at the two training sizes; crossed and seed-$t$ intervals span zero. At $τ=1$ m, relative costs change in 87.9% of route evaluations and route-level offline selections in 8.1%. Before concentration matching, descriptive outcome estimates favor the control. Most of this gap disappears along an approximate concentration-matching path; the remaining contrasts are $+0.112$ and $-0.047$, and both crossed intervals span zero. Actor-level forecast metrics remain identical. Pairing-strength and temperature sweeps show that the decision contrast grows with pairing removal and sharper conditioning. The intervention changes planner decisions even though actor-level metrics remain unchanged. The matching analysis, however, cannot separate any recorded-outcome effect of learned-mode AV-traffic pairing from the accompanying change in conditioned concentration.

0.31

Decision Aware Origin-Destination Demand Estimation with Structurally Constrained Data

cs.LG ·2026-11-09 ·Xianzhe Wang, Yueyue Fan, Johannes Royset
position similarity 0.57
Abstract

Origin-destination (OD) demand plays an important role in transportation system design and management applications. Conventional OD estimation methods typically judge estimation quality based on how estimated demand aligns with observed traffic data and historical demand patterns. We argue that data alignment alone is insufficient; how errors in OD estimates influence downstream decision quality should also be considered. This paper develops a decision aware OD demand estimation framework that leverages structurally constrained traffic data to characterize an admissible demand region, within which we identify OD estimates that would lead to least regret in the downstream decision. Therefore, our OD estimates are both data-consistent and decision-relevant. Methodologically, we approximate the admissible demand region induced by physical network constraints through a geometric representation, which regularizes the search over feasible OD estimates. Within this regularized region, we use a convex surrogate of downstream regret to obtain a tractable decision aware optimization problem. Numerical experiments show that the proposed framework consistently reduces decision regret relative to conventional estimation benchmarks, demonstrating the value of aligning OD demand estimation with downstream decision quality.

0.27

Semantic Freshness Optimal Sampling and Transmission for Gossiping Receivers

cs.IT cs.NIeess.SP ·2026-08-31 ·Irtiza Hasan, Ahmed Arafa
publishedtheory similarity 0.57
Abstract · To appear in IEEE ITW 2026

We study the optimal joint sampling and transmission policy for a transmitter communicating with two gossiping receivers that share information with each other, with the objective of tracking a source under the Version Age of Information (VAoI) metric. The transmitter can observe source-version changes, but it has to pay a sampling cost to get the current source information content. Similarly, it can communicate with a receiver by paying a transmission cost. Gossiping enables local information exchange and is able to reduce costly direct transmissions. With imperfect communication links, we formulate an infinite-horizon average-cost Markov Decision Process (MDP) to jointly minimize receiver VAoI, sampling cost, and transmission cost. Using Relative Value Iteration (RVI), we evaluate the optimal policy and establish several properties of its structure. We prove that sampling has a threshold structure in the transmitter VAoI. Among direct transmissions, it is optimal to serve the older receiver. We further characterize the transmit or idle decision through the receiver VAoI difference. Our analysis shows that link reliability and receiver VAoI imbalance have a significant effect on the optimal policy structure. Numerical results verify the structural properties and demonstrate the performance gains of the optimal policy over multiple baselines.

0.47

Learning Adaptive SED for heterogeneous load balancing

cs.LG math.PR ·2026-09-07 ·Sanne van Kempen, Jaron Sanders, Fiona Sloothaak, Maarten G. Wolf
theory similarity 0.57
Abstract · 34 pages

We study a two-server load balancing system with heterogeneous service rates that are a priori unknown to the dispatcher. The goal is to route customers according to the Shortest--Expected--Delay (SED) policy, but this requires knowledge of the service rates. Empirical policies that route based on estimates perform poorly: due to estimation error, the empirical policy disagrees with the oracle on an infinite region of the state space. We propose an online learning algorithm that converges to SED while learning the service rates. The algorithm carefully balances empirical SED routing with forced exploration phases that guarantee sufficient sampling of both servers. We prove that our algorithm achieves finite regret; this differs from classical Multi-Armed Bandit settings where regret typically grows logarithmically in time. Finally, numerical experiments demonstrate the performance of our algorithm and highlight the regimes in which forced exploration is especially beneficial.

0.30

When Fresh Information Is Not Enough: Age-of-Actuation-Optimal Scheduling for Energy-Harvesting Actuators

cs.IT ·2026-10-15 ·Ali Nikkhah, Anthony Ephremides, Nikolaos Pappas
similarity 0.57
Abstract

We study transmission scheduling in an energy-harvesting actuation system where an actuation requires both a received update and available energy. While age of information (AoI) measures information freshness, age of actuation (AoA) measures the time elapsed since the latest completed actuation. The transmitter observes the receiver's AoA and battery state and decides whether to transmit a fresh update in each slot. We formulate average-AoA minimization as a Markov decision process and establish an AoA-threshold property for an optimal policy. We also derive the average AoA in closed form under the AoI-optimal policy, which is always-transmit. Numerical results show that AoA-aware scheduling can improve actuation freshness while reducing the number of transmissions, although information freshness may deteriorate. The two policies coincide for some pairs of channel success and energy-arrival probabilities. For a one-unit battery, the transmission rate under the AoA-optimal policy can vary nonmonotonically with the energy-arrival probability.

0.20

A Performative Control Approach to Day-to-Day Traffic Signal Retiming

eess.SY ·2026-10-13 ·Shuchang Jiang, Xinwu Qian, Santiago Segarra, Zhongyuan Zhao
similarity 0.56
Abstract · 8 pages, 6 figures, 2 tables

Conventional fixed-time traffic signal optimization and recent day-to-day signal retiming generally model route adaptation under prescribed route-choice behavior and origin-destination (OD) demand, while neglecting the fact that travelers' behavior can be performative to the signal control policy. A signal timing policy learned from historical traffic observations must therefore account for how its own deployment changes the distribution on which it will be evaluated in the future. We formulate this problem as performative signal control under observed traveler responses and characterize performative stability of the coupled policy-demand system. We propose incremental day-to-day retiming using the local policy gradient at the current operating point, estimated offline through simulation-based zeroth-order optimization without an explicit day-to-day demand-response model. This gradual approach provides a feasible path for policy and demand to co-evolve toward stability. Experiments on a downtown Denver network show that our approach improves congestion, throughput, and stability, generalizes across different demand levels, and remains effective when the offline simulator contains mismatched travel demand and routing behaviors.

0.21

Timing Sensitivity in Actuated Traffic Signal Control: A simulation study on one urban network

eess.SY ·2026-09-29 ·Nitai Aharoni
code/data similarity 0.56
Abstract · 13 pages, 1 figure, 12 tables. Code, network and experiment configurations at https://github.com/nitaiaharoni1/traffic-simulator

A comparison between adaptive and fixed-time traffic signals can change when only their timing settings change. We examine this sensitivity in 240 simulation runs on one OpenStreetMap-derived urban network, using eight configurations, three arrival rates and ten paired demand seeds. The experiment varies the maximum green of presence-based actuation, retimes the fixed baseline, and includes a discharge-based phase-termination rule. The endpoint is finite-window time spent per offered trip, including entry waiting and penalties for removed or abandoned trips. At the highest tested load, actuation with a maximum green of twice the planned split has a mean endpoint 57.4 per cent above the original fixed plan. Reducing that multiplier to 1.25 puts it 70.7 per cent below the same plan. Against the best of three tested fixed plans, discharge-based termination reduces the mean endpoint by 14.8, 15.8 and 18.3 per cent across the three loads. Both timing sweeps favour their shortest tested setting, so neither identifies an optimum. This exploratory study uses synthetic demand, negligible start-up lost time and physical removal of persistently stationary vehicles. The results support testing timing sensitivity before attributing performance to a controller family; they do not establish a setting for real-world deployment.

0.41