Adaptive Requesting in Decentralized Edge Networks via Non-Stationary Bandits
Yi Zhuang 1, Kun Yang 2, Xingran Chen 3 · 2026
Read Adaptive Requesting in Decentralized Edge Networks via Non-Stationary Bandits by Yi Zhuang 1, Kun Yang 2, Xingran Chen 3 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-08760.txt.
Introduction
Yi Zhuang, Kun Yang, and Xingran Chen study how edge net users should ask for fresh data. In an edge net, users ask through gate nodes that link to far hosts. A user can not see the load on a gate, nor what peer users do. Yet old data is of no use, so each user wants the freshest copy it can get.
The team frames each ask choice as a bet with odds that shift in time. Past odds do not stay fixed, since load and peer acts change. Their method lets each user learn on its own, with no central boss. A reader who runs edge nets gets a self taught ask rule. It aims to keep data fresh while the net shifts round the user.
Catalog record
| CREATOR | Yi Zhuang 1, Kun Yang 2, Xingran Chen 3 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 121 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-08760
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Adaptive Requesting in Decentralized Edge Networks via Non-Stationary Bandits Yi Zhuang 1, Kun Yang 2, Xingran Chen 3 Abstract We study a decentralized collaborative requesting problem that aims to optimize the information freshness of time-sensitive clients in edge networks consisting of multiple clients, access nodes (ANs), and servers. Clients request content through ANs acting as gateways, without observing AN states or the actions of other clients. We define the reward as the age of information reduction resulting from a client’s selection of an AN, and formulate the problem as a non-stationary multi-armed bandit. In this decentralized and partially observable setting, the resulting reward process is history-dependent and coupled across clients, and exhibits both abrupt and gradual changes in expected rewards, rendering classical bandits ineffective. To address these challenges, we propose the Aging Bandit with Adaptive Reset algorithm, which combines adaptive windowing with periodic monitoring to track evolving reward distributions. We establish theoretical performance guarantees showing that the proposed algorithm achieves near-optimal performance, and we validate the theoretical results through simulations. I Introduction The proliferation of latency-sensitive applications, such as real-time sensing [ 21 ] , interactive services [ 35 ] , and distributed control [ 40 ] , poses a significant challenge to maintaining the freshness of information in modern computer networks, as the utility of such applications critically depends on the timely delivery of updates. Traditional cloud-centric networks rely on centralized processing, in which data generated at the network edge must be transmitted to remote cloud servers for computation and decision making [ 22 ] . This centralized workflow introduces long communication paths and concentrates traffic on backhaul links, which, in turn, leads to increased transmission delays and network congestion. As a result, cloud-centric networks often struggle to meet the stringent latency requirements imposed by latency-sensitive applications, significantly degrading information freshness [ 9 , 7 ] . To overcome these limitations, modern network designs are increasingly shifting toward decentralized edge networks [ 29 ] that distribute computation, storage, and control across the network [ 9 ] . Such networks typically consist of end users, access nodes (ANs), and servers, where ANs are deployed closer to end users and serve as intermediate network entities. Within this framework, ANs function as gateways that perform localized caching and forwarding of information, enabling data to be processed and delivered without always traversing the entire network to the cloud. By shortening communication paths and alleviating backhaul congestion, this decentralized network effectively reduces end-to-end latency and allows time-critical updates to be delivered to clients in a more timely manner [ 9 ] . This paper addresses the issue of timely content requests for latency-sensitive end users, referred to as clients, in a decentralized edge network (see Fig. 1 ). In this setting, multiple servers, ANs, and clients interact within the edge network, where clients cannot directly communicate with servers. Instead, ANs act as gateways, either fetching cached content or sending commands to servers for content retrieval [ 16 , 9 ] . To ensure timely information delivery, we adopt the Age of Information (AoI) [ 21 , 40 ] as the performance metric and aim to minimize the time-average AoI of clients, where AoI quantifies the time elapsed since the generation of the most recently received update. Optimizing AoI in a decentralized edge network therefore has broad implications for real-time applications—including smart cities, autonomous vehicles, industrial automation, and health monitoring systems [ 7 , 8 , 20 ] —where low-latency and fresh information are essential for safety and operational efficiency. Fig. 1 : An example of decentralized an edge network. This problem presents several key challenges. Some related challenges have been partially discussed in prior work [ 9 ] , but they are systematically addressed here. (i) Decentralization among clients : each client makes decisions based solely on local information, hindering global coordination across the network. (ii) Intra-client decision coupling : since each client can send at most one request per server per time slot, its decisions across different servers are inherently coupled. This coupling significantly complicates the analysis and renders existing tools—such as the age-of-version metric introduced in prior work [ 5 ] —inapplicable. (iii) Inter-client coupling via shared ANs : a client’s request affects the state of shared ANs, which in turn alters the observations available to other clients. This creates a dynamically coupled environment, making real-time decision-making analytically intractable. (iv) Topological complexity : the decentralized edge network exhibits a two-hop network with multiple receivers per hop and limited communication resources. This structural complexity further complicates policy optimization, as coordination must be achieved under stringent resource constraints. Given the challenges above, traditional theoretical analysis becomes infeasible, motivating the use of reinforcement learning techniques, which have demonstrated strong performance in real-time decision-making tasks [ 41 ] . In decentralized edge networks, it is essential to develop decentralized learning that allows individual nodes—each with access only to local observations—to collaboratively optimize global objectives without centralized coordination [ 13 ] . Among such approaches, Multi-Armed Bandit (MAB) methods [ 34 ] are particularly promising due to their simplicity, scalability, and favorable analytical properties, making them well-suited for distributed online decision-making under uncertainty. According to the definition of AoI [ 40 ] , the age increases when no packet is delivered and drops upon the reception of a fresh packet. As a result, the state of each arm—typically including the age—evolves over time even when it is not selected. This “restless” evolution induces highly non-stationary, history-dependent reward dynamics and naturally characterizes the problem as a restless bandit [ 26 ] (referred to as an Aging Bandit problem [ 3 ] ). Although non-stationary MAB variants (e.g., SW-UCB and D-UCB) have been developed [ 14 ] , they remain insufficient for our setting for three reasons: (i) they often require prior knowledge of the change frequency; (ii) they typically assume independent rewards across agents, which is violated by our shared-update mechanism; and (iii) they are usually tailored to either abrupt or gradual changes, but not both simultaneously. A well-known approach for restless bandits is Whittle’s index policy, which has been widely applied in Aging Bandit settings [ 17 , 28 , 36 , 27 , 24 , 19 , 18 ] . However, Whittle-type approaches are ill-suited for decentralized decision-making because they generally require global state information [ 19 ] . Moreover, verifying Whittle indexability is often challenging in complex decentralized environments; prior work [ 19 ] only extends the framework to a limited and simplified decentralized case that does not cover our setting. Decentralized Aging Bandit formulations have also been studied in [ 3 , 12 , 15 ] , primarily for dynamic channel selection in single-hop wireless networks to improve information freshness. These works focus on estimating channel erasure probabilities with rewards constrained to [0,1] , and their modeling assumptions and objectives differ substantially from ours, limiting their applicability to the decentralized edge-network setting considered here. I-A Contributions In this work, we study the problem of optimizing information freshness for time-critical clients in decentralized edge networks. Each client independently selects an AN based solely on its local observations, without access to the states of ANs or the actions of other clients. By defining the reward as