Aging Bandits: Regret Analysis and Order-Optimal Learning Algorithm for Wireless Networks with Stochastic Arrivals

Age-of-Information (AoI) is a performance metric that captures the freshness of the information from the perspective of the destination. AoI measures the time that elapsed since the generation of the packet that was most recently delivered to the destination. This performance metric has been receiving attention in the literature [1, 2, 3] for its application in communication systems that carry time-sensitive data. In this paper, we consider a network with $M$ sources transmitting time-sensitive information to the destination over $N$ unreliable wireless channels, as illustrated in Fig. 1. Packets from each source are generated according to an i.i.d. stochastic process with known statistics and the state of each wireless channel (ON/OFF) varies according to an i.i.d. stochastic process with unknown statistics. At every time slot, the learning algorithm schedules a single pair (source, channel) and the selected source attempts to transmit its packet via the selected wireless channel. When a packet with fresh information is successfully transmitted to the destination, the AoI associated with the selected source is reduced. The goal of the scheduler is to keep the information associated with every source in the network as fresh as possible, i.e. to minimize the AoI in the network. To decide which pair to select in a time slot, the scheduler takes into account: i) the packet generation processes at the $M$ sources; ii) the current values of AoI at the destination; and iii) the estimated reliability of the $N$ wireless channels.

In this sequential decision problem, the outcomes of previous transmission attempts are used to estimate the reliability of the wireless channels. This statistical learning problem is closely related to the stochastic multi-armed bandit (MAB) problem in which the wireless channels are the bandits that give i.i.d. rewards and the scheduler is the player that attempts to learn the statistics of the bandits in order to maximize the reward accumulated over time. The main challenge in the stochastic MAB problem is to strike a balance between exploiting the bandit that gave the highest rewards in the past and exploring other bandits that may give high rewards in the future. To evaluate the performance of different learning algorithms, we define regret. Regret is the difference between the expected cumulative reward of a genie algorithm (that knows the statistics of the bandits a priori) and the expected cumulative reward of the learning algorithm under consideration. The regret captures the penalty incurred by having to learn the statistics of the bandits over time. Some well-known order-optimal learning algorithms in terms of regret are: $\epsilon$-Greedy, Upper Confidence Bound (UCB), and Thompson Sampling (TS). The regret of these policies was shown to increase no more than logarithmically in time [4, 5, 6], $O(\log T)$, and this bound was shown to be tight [7].

We refer to our problem as the Aging Bandit problem. An important distinction between the stochastic MAB problem and the Aging Bandit problem is the reward structure. In the stochastic MAB problem, the player selects a bandit in each time slot and receives a reward that is i.i.d. over time and depends only on the probability distribution associated with the selected bandit. In the Aging Bandit problem, the scheduler selects a pair (source, channel) and the reward is the AoI reduction that results from a packet transmission to the destination. This reward depends on the state of the selected channel (which is i.i.d. over time), since a failed transmission gives zero reward, and it also depends on the history of previous packet deliveries and packet generations. In particular, if the selected source has recently delivered a fresh information update to the destination, then the reduction in AoI may be small. In contrast, if the selected source has not updated the destination for a long period, then the AoI reduction may be large. The reward structure of Aging Bandits is closely related to the AoI evolution (formally defined in Sec. II) which is history-dependent. This intricate reward structure has significant impact on the analysis of regret and on the development of learning algorithms when compared to the analysis of the traditional stochastic MAB.

The literature on MAB problems is vast, dating more than eight decades [8]. For surveys on different types of MAB problems, we refer the readers to [9, 10, 11, 12]. Most relevant to this work are [13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]. The authors in [13, 14, 15] considered the problem of minimizing the expected queue-length in a system with a single queue and multiple servers with unknown service rates. In [13], the authors introduced the concept of queue-length regret, developed a learning algorithm inspired by Thompson Sampling, and analyzed its regret. In [14, 15], the authors used information particular to the queue evolution to develop a learning algorithm with $O(1)$ queue-length regret.

The authors in [16, 17, 18, 19, 20, 21, 22, 23, 24] considered the problem of minimizing the average AoI in a single-hop wireless network with unreliable channels. In [16, 17, 18, 19, 20, 21], the authors posed the AoI minimization problem in a network with multiple sources and known channel statistics as a restless MAB problem, developed the associated Whittle’s Index scheduling policy, and evaluated its performance in terms of the average AoI. In [22], the authors considered the AoI minimization problem in a network with a single source-destination pair and unknown channel statistics, introduced the concept of AoI regret, and showed that the AoI regret of UCB and TS scale as $O(\log T)$. In [23], the authors obtained similar results as in [22] for the more challenging case of correlated wireless channels. In [24], the authors considered the AoI minimization problem in a network with multiple sources that generate and transmit fresh packets at every time slot through (possibly) different channels with unknown statistics. The authors in [24] showed that the AoI regret of a UCB-based distributed learning algorithm scales as $O(\log^{2}T)$. An important modelling assumption common to [22, 23, 24] is that sources generate and transmit fresh packets at every time slot. The more realistic assumptions of random packet generation and scheduled transmissions have significant impact on the AoI evolution, on the analysis of AoI regret, and on the development of learning algorithms. For example, in Sec. IV, we leverage the random packet generation to develop a learning algorithm with $O(1)$ AoI regret.

In this paper, we study learning algorithms that attempt to minimize AoI in a network with multiple sources generating packets according to stochastic processes and transmitting these packets to the destination over wireless channels with initially unknown statistics. At every time slot, the learning algorithm schedules a single pair (source, channel) and the selected source attempts to transmit a packet through the selected channel. Note that the source policy, which selects a source at each time slot, and the channel policy, which selects the channel to be used in each time slot, can be naturally decoupled, as the optimal channel is independent of the source selected. In this paper, we focus on the exploration-exploitation dilemma faced by the channel policy. In particular, we consider learning algorithms employing the optimal source policy and different channel policies. Our main contributions include:

• •

  we analyze the performance of channel policies based on traditional MAB algorithms including $\epsilon$-Greedy, UCB, and TS, and show that their AoI regret scales as $\Theta(\log T)$. These results generalize the analysis in [22] to networks with multiple sources generating packets randomly. The analysis of the AoI regret is more challenging in this network setting since the AoI evolution depends on both the source policy and the stochastic packet generation process. These challenges are discussed in Sec. III;

• •

  we develop a novel learning algorithm and establish that it has $O(1)$ AoI regret. The key insight is that when packets are generated randomly, the learning algorithm can utilize times when the network has no packets to transmit, in order to learn the statistics of the channel. To the best of our knowledge, this is the first learning algorithm with bounded AoI regret.

The remainder of this paper is outlined as follows. In Sec. II, the network model and performance metrics are formally presented. In Sec. III, we analyze the AoI regret of traditional learning algorithms. In Sec. IV, we develop an order-optimal learning algorithm and analyze its AoI regret. In Sec. V, we compare the AoI regret of different learning algorithms using simulations. The paper is concluded in Sec. VI. Some of the technical proofs have been omitted due to the space constraint, and will be made available in a technical report.

Consider a single-hop wireless network with $M$ sources, $N$ channels and a single destination, as illustrated in Fig. 1. Each source generates packets containing time-sensitive information and these packets are to be transmitted to the destination through one of the wireless channels. Let the time be slotted, with slot index $t\in\{1,2,\cdots,T\}$, where $T$ is the time horizon of this discrete-time system. The slot duration allows for a single packet transmission. We normalize the slot duration to unity.

At the beginning of every slot $t$, each source generates a packet with probability $\lambda\in(0,1)$. Let $a_{m}(t)\in\{0,1\}$ be the indicator function that is equal to $1$ when source $m\in\{1,2,\cdots,M\}$ generates a packet in slot $t$, and $a_{m}(t)=0$ otherwise. This Bernoulli process with parameter $\lambda$ is i.i.d. over time and independent across different sources, with $\mathrm{P}\left(a_{m}(t)=1\right)=\lambda,\forall m,t$. A packet that is generated in slot $t$ can be transmitted during the same slot $t$. We denote the vector of packet generations in slot $t$ by $\vec{a}(t)=\left[a_{1}(t)\ \cdots\ a_{M}(t)\right]^{\mathsf{T}}$.

Each source has a transmission queue to store its packets. Sources keep only the most recently generated packet, i.e. the freshest packet, in their queue. When source $m$ generates a new packet at the beginning of slot $t$, older packets (if any) are discarded from its queue. Notice that delivering the most recently generated packet provides the freshest information to the destination. This queueing discipline is known to optimize the AoI in a variety of contexts [25, 26, 27]. After a packet delivery from source $m$, the queue remains empty until the next packet generation from the same source. However, while the queue is empty, a dummy packet can be transmitted for the purpose of probing the channels.

The networked system is empty during slot $t$ if there are no data packets available for transmission, i.e. if the $M$ queues are empty. Let $E(t)\in\{0,1\}$ be the indicator function that is equal to $1$ if the system is empty during slot $t$, and $E(t)=0$ otherwise. Notice that if there is a packet generation at the beginning of slot $t$, then the system is nonempty during slot $t$ and $E(t)=0$. Recall that when the system is empty, sources can still transmit dummy packets.

In a slot, the learning algorithm selects a single pair $(m,n)$, where $m\in\{1,2,\cdots,M\}$ is the index of the source and $n\in\{1,2,\cdots,N\}$ is the index of the wireless channel. Then, during this slot, source $m$ transmits a packet to the destination through channel $n$. If channel $n$ is ON, then the packet is successfully transmitted to the destination, and if channel $n$ is OFF, then the transmission fails. The learning algorithm does not know the channel states while making scheduling decisions, and the outcome of a transmission attempt during slot $t$ is known at the beginning of slot $t+1$. Let $b_{n}(t)\in\{0,1\}$ be the indicator function that represents the state of channel $n$ during slot $t$. The channel is ON, $b_{n}(t)=1$, with probability $\mu_{n}\in(0,1]$, and the channel is OFF, $b_{n}(t)=0$, with probability $1-\mu_{n}$. The channel state process is i.i.d. over time and independent across different channels.

The reliability of channel $n$ is represented by the probability of this channel being ON, $\mu_{n}$. Let $\vec{\mu}=\left[\mu_{1}\ \cdots\ \mu_{N}\right]^{\mathsf{T}}$ be the vector of channel reliabilities. Let $\mu^{*}$ be the maximum channel reliability and let $n^{*}$ be the index of the corresponding channel, i.e.  $\mu^{*}=\max_{n}\mu_{n}=\mu_{n^{*}}$. For simplicity, we assume that the optimal channel $n^{*}$ is unique. Naturally, if the channel reliabilities were known by the learning algorithm in advance, then the algorithm would select channel $n^{*}$ in every slot $t$. However, since the channel reliabilities $\vec{\mu}$ are initially unknown, the learning algorithm has to estimate $\mu_{n}$ using observations from previous transmission attempts, while at the same time attempting to minimize the AoI in the network. Next, we formulate the AoI minimization problem.

The problem of learning channel reliabilities over time is closely related to the stochastic MAB problem. A natural class of channel policies to consider are traditional MAB algorithms such as $\epsilon$-Greedy, UCB, and TS. In this section, we derive bounds on the AoI regret of learning algorithms that employ queue-independent channel policies. Notice that the class of queue-independent channel policies $\Pi_{B}$ includes traditional MAB algorithms. We describe a learning algorithm employing TS as its channel policy in Algorithm 1.

Scheduling decisions of a learning algorithm $\pi$ might differ from those of $\pi^{*}$ both in the source and in the channel, which makes the analysis of the AoI regret $\sum_{t=1}^{T}\sum_{m=1}^{M}\mathrm{E}[h_{m}^{\pi}(t)-h_{m}^{*}(t)]$ challenging. To alleviate this challenge, we use stochastic coupling to create equivalent coupled channel state processes that are simpler to analyze. Similar coupling arguments were employed in [13, 22].

By construction, the coupled channel states are no longer independent. In particular, if a channel is ON during slot $t$, then all channels with higher reliability $\mu_{n}$ are also ON during that slot. Notice that, in each slot $t$, each coupled channel $n$ has the same probability distribution as the associated original channel $n$, namely $\mathrm{P}\left(b_{n}(t)=1\right)=\mu_{n},\forall n,t$. Hence, given the scheduling decision $(m(t),n(t))$ of $\pi$ during any slot $t$, the probability of a successful transmission attempt from source $m(t)$ through channel $n(t)$ is the same for both the coupled and original channel states. It follows that the probability distribution of $h_{m}^{\pi}(t)$ also remains the same for all slots $t$ and for all sources $m$ and, thus, the AoI regret $R^{\pi}(T)$ in (3) also remains the same for both the coupled and original channel state processes. For simplicity of analysis, henceforth in this paper, we assume that the channel state processes are coupled as described in Remark 1.

In Proposition 2, Proposition 3, and Corollary 4, we derive bounds on the AoI regret of a learning algorithm $\pi$ with respect to its expected number of suboptimal channel choices, namely

where $\mathbbm{1}\left\{n^{\pi}(t)\neq n^{*}\right\}=1$ if $n^{\pi}(t)\neq n^{*}$, and $\mathbbm{1}\left\{n^{\pi}(t)\neq n^{*}\right\}=0$ otherwise. We consider two classes of admissible learning algorithms

Both classes employ queue-independent channel policies. The difference is that $\Pi$ employs any admissible source policy $\pi_{a}\in\Pi_{A}$, while $\Pi^{*}$ employs the optimal source policy $\pi_{a}^{*}$. Naturally, we have $\Pi^{*}\subset\Pi$.

Corollary 4 follows directly from Propositions 2 and  3. Notice that the bounds in Proposition 3 and Corollary 4 are not valid for the broader class of learning algorithms $\Pi$ which includes suboptimal source policies. This is because suboptimal source choices may add to the AoI regret, possibly making it grow faster than $\mathrm{E}\left[K^{\pi}(T)\right]$.

Prior to analyzing the AoI regret of learning algorithms that employ $\epsilon$-Greedy, UCB, and TS as their channel policy, we define $\alpha$-consistent learning algorithms [12, 13] and discuss a few of their properties. Let $\mathrm{E}[T^{\pi}_{n}(T)]$ be the expected number of times channel $n$ is selected by $\pi\in\Pi$ in the first $T$ slots, namely

Intuitively, a learning algorithm $\pi\in\Pi$ is $\alpha$-consistent if its channel policy has good performance in every network configuration. Consider a learning algorithm with a trivial channel policy that selects $n(t)=1$ in every slot $t$. In network configurations with $n^{*}=1$, this channel policy never selects suboptimal channels, i.e. $\mathrm{E}\left[T^{\pi}_{n}(T)\right]=O(T^{\alpha}),\forall n\neq n^{*}$. However, in network settings with $n^{*}\neq 1$, this channel policy is such that $\mathrm{E}\left[T^{\pi}_{1}(T)\right]=T$, which violates the definition of $\alpha$-consistency. In the remainder of this section, we focus on channel policies that have good performance in every network configuration. In particular, we analyze the AoI regret of $\alpha$-consistent learning algorithms with queue-independent channel policies.

Notice that the lower bound in Remark 6 applies to $\alpha$-consistent learning algorithms with queue-independent channel policies that do not know the statistics of the channels in advance.

Learning algorithms that employ $\epsilon$-Greedy, UCB, and TS as their channel policy are known to have suboptimal channel choices scaling as $\mathrm{E}[K^{\pi}(T)]=O(\log T)$ for any network configuration $(\lambda,\vec{\mu})$ [4, 30], which implies that they are $\alpha$-consistent. Hence, it follows from the upper bound in Proposition 3 and from (12) that the AoI regret of these learning algorithms scale as

In [22], the authors derived lower and upper bounds on the AoI regret of learning algorithms employing queue-independent channel policies, including UCB and TS, in networks with a single source generating and transmitting fresh packets in every slot $t$. Propositions 2 and 3 generalize the results in [22] to networks with multiple sources generating packets according to stochastic processes. The analysis of the AoI regret is more challenging in this network setting for the following reasons: i) the optimal source policy $\pi^{*}_{a}$ is unknown and there is no closed-form expression for the expected total AoI (1) of the optimal algorithm $\pi^{*}=(\pi_{a}^{*},\pi_{b}^{*})$; and ii) the learning algorithm under consideration $\pi=(\pi_{a},\pi_{b})$ can make suboptimal choices both in terms of sources $m(t)$ and channels $n(t)$, and these two types of suboptimal choices affect the AoI regret $R^{\pi}(T)$ differently. Next, we develop a learning algorithm that leverages information about the status of the transmission queues in making scheduling decisions $n(t)$, and show that this new learning algorithm has $O(1)$ AoI regret.

In this section, we develop a learning algorithm $\bar{\eta}\in\bar{\Pi}$ with a queue-dependent channel policy that selects $n(t)$ using information about the outcome of previous transmission attempts, namely $H_{B}(t)=\{n(1),b(1),\cdots,n(t-1),b(t-1)\}$, and about the current status of the transmission queues, $E(t)$. Then, we derive an upper bound on its AoI regret. In particular, we show that the AoI regret of $\bar{\eta}$ is such that $R^{\bar{\eta}}(T)=O(1)$. Notice that the only difference between the learning algorithms $\pi\in\Pi$ in Sec. III and the order-optimal learning algorithm $\bar{\eta}$ is the knowledge of $E(t)$. This seemingly modest addition led to the reduction of the AoI regret from $R^{\pi}(T)=\Omega(\log T)$ to $R^{\bar{\eta}}(T)=O(1)$. To the best of our knowledge, this is the first learning algorithm with bounded AoI regret.

The key insight is that when packets are generated randomly, the learning algorithm $\bar{\eta}$ can utilize times when the network has no data packets to transmit, i.e. when $E(t)=1$, to transmit dummy packets and learn the statistics of the channels without incurring an opportunity cost. The order-optimal learning algorithm $\bar{\eta}=(\eta_{a},\bar{\eta}_{b})$ has optimal source policy $\eta_{a}=\pi^{*}_{a}$ and a channel policy $\bar{\eta}_{b}\in\bar{\Pi}_{B}$ that operates as follows: when the system is empty, $E(t)=1$, the policy chooses a channel uniformly at random and uses the outcome of the transmission attempt to update its estimates of the channel reliabilities and, when the system is nonempty, $E(t)=0$, the policy chooses the channel with the current highest estimated reliability. Notice that the channel policy only updates its estimates of the channel reliabilities when the system is empty. A similar channel policy was used in [14, 15] to develop a learning algorithm with bounded queue-length regret. The order-optimal learning algorithm $\bar{\eta}$ is described in Algorithm 2. The upper bound on the AoI regret is established in the theorem that follows.

In the particular case of a network with sources generating fresh packets at every slot $t$, i.e. $\lambda=1$, the algorithm $\bar{\eta}$ cannot utilize slots in which the system is empty to learn the channel reliabilities without incurring a cost in terms of AoI regret, which results in a $R^{\bar{\eta}}(T)$ that grows over time. The upper bound in Theorem 7 is only valid for the network models described in Sec. II, in which $\lambda\in(0,1)$. Next, we evaluate the AoI regret of the different learning algorithms discussed in this paper using MATLAB simulations and we propose a heuristic algorithm that leverages the fast learning rates of TS and the bounded regret of the order-optimal algorithm.

In this section, we evaluate the performance of learning algorithms in terms of the AoI regret in (3). We compare learning algorithms employing the Age-Based Max-Weight source policy [29, Sec. 5] and different channel policies, namely: i) $\epsilon$-Greedy; ii) UCB; iii) TS; iv) Optimal; and v) Hybrid. The Age-Based Max-Weight source policy selects, in each slot $t$, the source $m$ associated with the packet that gives the largest AoI reduction, $\tau_{m}(t+1)-\tau_{m}(t)$, if the transmission in slot $t$ is successful. Intuitively, this policy is selecting the source with highest potential reward in terms of AoI. In [29], the authors evaluate the performance of the Age-Based Max-Weight source policy both analytically and using simulations, and show that it achieves near optimal AoI. The first three channel policies, namely $\epsilon$-Greedy, UCB, and TS, were discussed in Sec. III. The Optimal policy is the order-optimal channel policy $\bar{\eta}_{b}$ developed in Sec. IV. The Hybrid policy employs TS for a fixed period in the beginning of the simulation and then employs the Optimal policy in the remaining slots.

We simulate a network with a time horizon of $T=10^{5}$ slots, $M=3$ sources, each generating packets according to a Bernoulli process with rate $\lambda$, and $N=5$ channels with reliabilities $\vec{\mu}=[0.4\ 0.45\ 0.5\ 0.55\ 0.6]^{\mathsf{T}}$. Figures 3 and 4 show simulation results of the evolution of the AoI regret over time for $\lambda=0.1$ and $\lambda=0.75$, respectively. Figure 5 shows simulation results of the evolution of the reliability estimates associated with the channels with $\mu_{4}=0.55$ and $\mu_{5}=0.6$ over time for $\lambda=0.75$. Each data point in Figs. 3, 4, and 5 is an average over the results of $10^{3}$ simulations.

The results in Figs. 3 and 4 suggest that, as expected, the AoI regret associated with Optimal and Hybrid is bounded, while the AoI regrets associated with $\epsilon$-Greedy, UCB and TS grow over time. By comparing the AoI regret of Optimal and TS in Figs. 3 and 4, it is clear that the AoI regret of the Optimal channel policy varies significantly with $\lambda$. In particular, for $T=10^{5}$, when $\lambda$ increases from $0.1$ to $0.75$, the AoI regret of TS increases by a factor of $1.5$ (from $1,318$ to $1,963$), while the AoI regret of Optimal increases by a factor of $491.0$ (from $1,068$ to $481,700$). A main reason for this performance degradation is that when $\lambda$ increases, empty systems with $E(t)=1$ occur less often and, as a result, the Optimal channel policy takes longer to learn the reliability of the channels, as can be seen in Fig. 5. To improve the performance of the Optimal policy for networks with large $\lambda$, we propose a heuristic policy called Hybrid channel policy, which employs TS in the first $10^{4}$ slots to quickly learn the reliability of the channels, and then shifts to the Optimal policy which has bounded AoI regret in the long term. Figure 5 illustrates the difference in the learning rates between Optimal and Hybrid. Notice in Fig. 5 that there are extended periods of time in which the Optimal channel policy assigns a larger estimated reliability to a suboptimal channel, which leads to the large AoI regret shown in Fig. 4. However, as established in Theorem 7, for a long enough time-horizon $T$, the Optimal policy will eventually converge to the true reliabilities, at which point the AoI regret will stop increasing.

This paper considers a single-hop wireless network with $M$ sources transmitting time-sensitive information to the destination over $N$ unreliable channels. Packets from each source are generated according to a Bernoulli process with known rate $\lambda$ and the state of channel $n$ (ON/OFF) varies according to a Bernoulli process with unknown rate $\mu_{n}$. The reliabilities $\vec{\mu}$ of the wireless channels is to be learned through observation. At every slot $t$, the learning algorithm selects a single pair $(m(t),n(t))$ and the selected source $m(t)$ attempts to transmit its packet via the selected channel $n(t)$. The goal of the learning algorithm is to minimize the expected total AoI $\bar{h}(T)$. To analyze the performance of the learning algorithm, we derive bounds on the AoI regret $R^{\pi}(T)$ associated with different learning algorithms. Our main contributions include: i) analyzing the performance of learning algorithms that employ channel policies based on traditional MAB algorithms ($\epsilon$-Greedy, UCB, and TS) and showing that their AoI regret scales as $\Theta(\log T)$; and ii) developing a novel learning algorithm and establishing that it has $O(1)$ AoI regret. To the best of our knowledge, this is the first learning algorithm with bounded AoI regret. Interesting extensions of this work include consideration of sources with unknown packet generation rates and channels with time-varying statistics.