{'fraction_non_alphanumeric': 0.04807824061386681, 'fraction_numerical': 0.013428336530556317, 'mean_word_length': 4.091123125217998, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Low-Power Status Updates via Sleep-Wake Scheduling

We consider the problem of optimizing the freshness of status updates that are sent from a large number of low-power sources to a common access point. The source nodes utilize carrier sensing to reduce collisions and adopt an asynchronized sleep-wake scheduling strategy to achieve a target network lifetime (e.g., 10 years). We use age of information (AoI) to measure the freshness of status updates, and design sleep-wake parameters for minimizing the weighted-sum peak AoI of the sources, subject to per-source battery lifetime constraints. When the sensing time (i.e., the time duration of carrier sensing) is zero, this sleep-wake design problem can be solved by resorting to a two-layer nested convex optimization procedure; however, for positive sensing times, the problem is non-convex. We devise a low-complexity solution to solve this problem and prove that, for practical sensing times that are short, the solution is within a small gap from the optimum AoI performance. When the mean transmission time of status-update packets is unknown, we devise a reinforcement learning algorithm that adaptively performs the following two tasks in an ``efficient way'': a) it learns the unknown parameter, b) it also generates efficient controls that make channel access decisions. We analyze its performance by quantifying its ``regret'', i.e., the sub-optimality gap between its average performance and the average performance of a controller that knows the mean transmission time. Our numerical and NS-3 simulation results show that our solution can indeed elongate the batteries lifetime of information sources, while providing a competitive AoI performance.


I. INTRODUCTION
In applications such as networked monitoring and control systems, wireless sensor networks, autonomous vehicles, it is crucial for the destination node to receive timely status updates so that it can make accurate decisions. Age of information (AoI) has been used to measure the freshness of status updates. More specifically, AoI [2] is the age of the freshest update at the destination, i.e., it is the time elapsed since the freshest received update was generated. It should be noted that optimizing traditional network performance metrics, such as throughput or delay, do not attain the goal of timely updating.
For instance, it is well known that AoI could become very large when the offered load is high or low [2]. In other words, AoI captures the information lag at the destination, and is hence more apt for achieving the goal of timely updates. Thus, AoI has recently attracted a lot of interests (see [3], [4] and references therein).
In a variety of information update systems, energy consumption is also a critical concern. For example, wireless sensor networks are used for monitoring crucial natural and humanrelated activities, e.g. forest fires, earthquakes, tsunamis, etc.
Since such applications often require the deployment of sensor nodes in remote or hard-to-reach areas, they need to be able to operate unattended for long durations. Likewise, in medical sensor networks, battery replacement/recharging involves a series of medical procedures, leading to disutility to patients. Hence, energy consumption must be constrained in order to support a long battery life of 10-15 years [5] 1 . For networks serving such real-time applications, prolonging battery-life is crucial. Existing works on multi-source networks, e.g., [8]- [11], [11]- [20], focused exclusively on minimizing the AoI and overlooked the need to reduce power consumption. This motivates us to derive scheduling algorithms that achieve a trade-off between the competing tasks of minimizing AoI and reducing the energy consumption in multi-source networks.
Additionally, some status-update systems consist of a large number (e.g., hundreds of thousands) of densely packed wireless nodes, which are serviced by a single access point (AP).
Examples include massive machine-type communications [21]. The dataloads in such "dense networks" [21], [22] are created by applications such as home security and automation, oilfield and pipeline monitoring, smart agriculture, animal and livestock tracking, etc. This introduces high variability in the data packet sizes so that the transmission times of data packets are random. Thus, scheduling algorithms designed for time-slotted systems with a fixed transmission duration, are not applicable to these systems. Besides that, synchronized scheduler for time-slotted systems are feasible when there are relatively few sources and each source has sufficient energy.
However, if there are a huge number of sources, the signaling overhead could be quite high. Since, each source may have limited energy and low traffic rate, the system could be highly inefficient. This motivates us to design asynchronized medium access protocols that coordinate the transmissions of multiple conflicting transmitters connected to a single AP.
Towards that end, we consider a wireless network with M sources that contend for channel access and communicate their update packets to an AP. Each source is equipped with a battery that may get charged by a renewable source of energy, e.g., solar. Moreover, each source employs a sleepwake scheduling scheme [23] under which the source transmits a packet if the channel is idle; and sleeps if either: (i) The channel is busy, (ii) it has completed a packet transmission.
This enables each source to save the precious battery energy by switching off when it is unlikely to gain channel access for packet transmissions. However, since a source cannot transmit during the sleep period, this causes the AoI to increase. We carefully design the sleep-wake parameters to minimize the weighted-sum peak age of the sources, while ensuring that the battery lifetime constraint of each source is satisfied.

A. Related Works
There have been significant recent efforts on analyzing the AoI performance of popular queueing service disciplines, e.g., the First-Come, First-Served (FCFS) [2] Last-Come, First-Served (LCFS) with and without preemption [24], and queueing systems with packet management [25]. In [18], [26]- [29], the age-optimality of Last-Generated, First-Served (LGFS)-type policies in multi-server and multi-hop networks was established, where it was shown that these policies can minimize any non-decreasing functional of the age processes. The design of data sampling and transmission in information update systems was investigated in [30], [31], where sampling policies were derived to minimize nonlinear age functions in single source systems. In [31], it was shown that a variety of information freshness metrics can be represented as monotonic • In our model, sources utilize an asynchronized sleepwake scheduling strategy to achieve an extended battery lifetime. We aim at designing the mean sleeping period of each source, which controls its channel access probability, in order to minimize the total weighted average peak age of the sources while simultaneously meeting per-source battery lifetime constraints. Although, the aforementioned optimization problem is non-convex, we devise a solution.
In the regime for which the sensing time is negligible compared to the packet transmission time, the proposed solution is near-optimal (Theorem 1 and Theorem 3). Our near-optimality results hold for general distributions of the packet transmission times.
• We propose an algorithm that can be easily implemented in many practical control systems. In particular, our solution requires the knowledge of only two variables in its implementation. These two variables are functions of the network parameters. An implementation procedure to compute these two variables is provided.
• As the ratio between the sensing time and the packet transmission time reduces to zero, we show that the age performance of our proposed algorithm is as good as that of the optimal synchronized scheduler (e.g., for timeslotted systems).
• Finally, since our solution is a function of the mean transmission time of data packets, the network operator needs to know this quantity in order to implement the algorithm. The transmission times however depend upon the environmental conditions, which in turn are hard to predict before the system operation begins. To overcome this challenge, we develop a reinforcement learning (RL) [40]- [42] algorithm that maintains an estimate of the (unknown) mean transmission time, and then utilizes this estimate in order to derive a solution that is "seemingly optimal" for the true system. We show that the regret of the proposed RL algorithm scales asÕ( where H is the operating time horizon.

A. Network Model and Sleep-wake Scheduling
Consider a wireless network composed of M source nodes, each observing a time-varying signal. The sources generate update packets of the observed signals and send the packets to an access point (AP) over a shared spectrum band. If multiple 2Õ hides factors that are logarithmic in H. sources transmit packets simultaneously, a packet collision occurs and these packet transmissions fail.
The sources use a sleep-wake scheduling scheme to access the shared spectrum, where each source switches between a sleep mode and a transmission mode over time, according the following rules: Upon waking from the sleep mode, a source first performs carrier sensing to check whether the channel is occupied by another source, as illustrated in Figure 1. The time duration of carrier sensing is denoted as t s , which is sufficiently long to ensure a high sensing accuracy. If the channel is sensed to be busy, the source enters the sleep mode directly; otherwise, the source generates an update packet and sends it over the channel. The source hereafter goes back to the sleep mode.
In the above sleep-wake scheduling scheme, if two sources start transmitting within a time duration of t s , then their sensing periods are overlapping and they may not be able to detect the transmission of each other. In order to obtain a robust system design, we consider that they cannot detect each other's transmission and a collision occurs. Upon completing a packet transmission, sources switch to the reception mode and wait for an acknowledgement (ACK) that indicates the outcome of their transmissions (successful transmission or collision). They then go back to the sleep mode.
A sleep-wake cycle, or simply a cycle, is defined as the time period between the ends of two successive packet transmission or collision events. Each cycle consists of an idle period and a transmission/collision period 3 . As depicted in Figure  1, the packet transmissions in Cycles 1-2 are successful, but a collision occurs in Cycle 3 because Sources 1 and 2 wake up within a short duration t s .
We use T j , j ∈ {1, 2, . . .} to represent the time incurred by the j-th packet transmission or collision event, which includes transmission/collision time and feedback delays. For example, in Figure 1, T 1 is the time duration of the packet transmission event by Source 1, while T 3 is the time duration of the collision event between Source 1 and 2. We assume that the T j 's are i.i.d. for all transmission and collision events, with a general distribution. This assumption does not hold 3 To make the sleep-wake scheduling problem solvable analytically, we make several approximations. For example, in 802.11b frame structure, there exists a Short Inter-frame Space (SIFS) between the packet transmission frame and the ACK frame (i.e., the CTS frame). If another source wakes up during the SIFS, then it may not detect the transmission/ACK frames, leading to unexpected collisions. In our analytical model, such collision events are omitted. In other words, we suppose that each cycle must start with an idle period, where all sources are in the sleep mode, followed by a transmission/collision period. NS-3 simulation results will be provided in Section VI-B to show that these approximations have a negligible impact on the age performance of our solution.  Figure 1: Illustration of the sleep-wake cycles. In Cycles 1-2, we have successful packet transmissions. Let S 1 and S 2 represent the remaining sleeping times of Sources 1 and 2, respectively, after a successful transmission. Then, a collision occurs in Cycle 3 because the difference between wake-up times of Sources 1 and 2 is less than t s , i.e., S 1 − S 2 < t s . As we can observe, each cycle consists of an idle period before a transmission/collision event.
where ∆ l (t) is right-continuous. As shown in Figure 2, the age increases linearly with t, but is reset to a smaller value upon the delivery of a fresher packet. Observe that a small age ∆ l (t) indicates that the AP has a fresh status update packet that was generated at source l recently. Hence, it is desirable to keep ∆ l (t) small for all the sources.
Let us introduce some notations and definitions. Let i l be the index of the i-th delivered packet from source l. We use t l,i and t ′ l,i to denote the generation and delivery times, respectively, of the i-th delivered packet from source l, T i l . 4 Let I l,i = t ′ l,i − t ′ l,i−1 denote the i-th inter-departure time of source l, which satisfies E[I l,i ] = E[I l ] for all i. The i-th peak age of source l, denoted by ∆ peak l,i , is defined as the AoI of source l right before the i-th packet delivery from source l.
As shown in Figure 2, i.e., we have where t ′− l,i is the time instant just before the delivery time t ′ l,i . One can observe from Figure 2 that the peak age is [25] ∆ peak l,i = T (i−1) l + I l,i .
Hence, the average peak age of source l is given by where we omit the subscripts i and i l as I l,i 's and T i l 's are i.i.d. across time. The average peak age metric provides information regarding the worst case age, with the advantage 4 A packet of a particular source is deemed delivered when the source receives the feedback. of having a simpler formulation than the average age metric [25]. Thus, it is suitable for applications that have an upper bound restriction on AoI.
We now derive an expression for E[I l ]. Let α l be the probability of the event that the source l obtains channel access and successfully transmits a packet within a sleep-wake cycle. As shown in [23], one can utilize the memoryless property of exponential distributed sleep periods to get α l = r l e r l ts To keep the paper self-contained, we provide the derivation of (5) in Appendix A. Let N l denote the total number of sleepwake cycles between two subsequent successful transmissions of source l. Because the probability that source l obtains channel access and transmits successfully in a given cycle is α l , N l is geometrically distributed with mean 1 α l . By this and (5), we get An inter-departure time duration of source l is composed of N l consecutive sleep-wake cycles. With a slight abuse of notation, let cycle l,k denote the duration of the k-th sleep-wake cycle after a successful transmission of source l. Hence, Note that cycle l,k 's are i.i.d. across time. Moreover, since the event (N l = n) depends only on the history, N l is a stopping time [43]. Hence, it follows from Wald's identity [44] that Substituting the expressions for E[N l ] and E[cycle] from (6) and (9), respectively, into (8), and (4), we obtain In this paper, we aim to minimize the total weighted average peak age, which is given by where w l > 0 is the weight of source l. These weights enable us to prioritize the sources according to their relative importance [9], [15].

C. Energy Constraint
Each source is equipped with a battery that can possibly be recharged by a renewable energy source, such as solar.
In typical wireless sensor networks, sources have a much smaller power consumption in the sleep mode than in the transmission mode. For example, if the sensor is equipped with the radio unit TR 1000 from RF Monolithic [45], [46], the power consumption in the sleep mode is 15 µW while the power consumption in the transmission mode is 24.75 mW. Motivated by this, we assume that the energy dissipation during the sleep mode is negligible as compared to the power consumption in the transmission mode. Moreover, we assume that the sensing time duration t s is much shorter than the transmission time and hence neglect the energy consumed during channel sensing. In Section VI-B, we show that these assumptions have a negligible effect on the performance of the proposed sleep-wake scheduling algorithm. Under these assumptions, the amount of energy used by a source is equal to the amount of energy consumed in packet transmissions and feedback receptions.
The energy constraint on source l is described by the following parameters: a) Initial battery level B l , which denotes the initial amount of energy stored in the battery, b) Target lifetime D l , which is the minimum time-duration that the source l should be active before its battery is depleted, c) Average energy replenishment rate 5 R l , which is the rate at which the battery of source l receives energy from its energy 5 It is assumed that R l is either known, or it can be estimated accurately.
source. If source l does not have access to an energy source, then we have R l = 0. Define P max,l for source l as where P max,l is the maximum allowable power consumption of source l such that the target lifetime D l is met.
For the sleep-wake scheduling mechanism under consideration, it has been shown in [23] that the fraction of time in which source l is in the transmission mode is given by For the sake of completeness, the derivation of σ l is provided in Appendix B. Let P avg,l denote the average power consumption of source l in the transmission mode. Then the actual power consumption of source l, denoted by P act,l , is given by For source l to achieve its target lifetime D l , we must have P act,l ≤ P max,l , ∀l.
Define b l P max,l /P avg,l as the target power efficiency of source l. By using (13)- (14), the constraints in (15) can be rewritten as Because σ l ≤ 1, if b l ≥ 1, then constraint (16) is always satisfied.

D. Problem Formulation
Our goal is to find the optimal sleep-wake parameters r that minimizes the total weighted average peak age in (11), while simultaneously ensuring the energy constraints (16) for all sources. Dividing the objective function (11) by E[T ], we obtain the following optimization problem: (Problem 1) w l e −r l ts where∆ w-peak opt is the optimal objective value of Problem 1. We will use∆ w-peak (r) to denote the objective value for given sleeping period parameters r. One can notice from (17) that the optimal sleeping period parameters depend on the sensing time t s and the mean transmission time E[T ] only through their ratio t s /E[T ]. This insight plays a crucial role in subsequent analysis of Problem 1.

III. MAIN RESULTS
When t s = 0, although Problem 1 is non-convex, it can be solved by defining an auxiliary variable y = M i=1 r i + 1 and applying a nested optimization algorithm: In the inner layer, we optimize r l for a given y. Then, we write the optimized objective as a function of y. In the outer layer, we optimize y. It happens that the inner and outer layer optimization problems are both convex. The details can be found in Section III-C.
However, this method does not work for positive sensing times t s > 0 and Problem 1 becomes non-convex. Hence, it is challenging to optimize r for positive t s . In this section, we develop a low-complexity closed-form solution which is shown to be near-optimal if the sensing time t s is short as compared with the mean transmission time E[T ]. Our solution is developed by considering the following two regimes sepa- means that the sources have a sufficient amount of total energy to ensure that at least one source is awake at any time, (ii) Energy-scarce regime represented by M i=1 b i < 1, which indicates that the sources have to sleep for some time to meet the sources' energy constraints.

A. Energy-adequate Regime
In the energy-adequate regime where x ⋆ and β ⋆ are expressed in terms of the parameters as follows: and β ⋆ is the unique root of The performance of the above solution r ⋆ is manifested in the following theorem: (20) is near-optimal for solving (17) when t s /E[T ] is sufficiently small, in the following sense: 6 where Proof. See Section IV-A.
From Theorem 1, we can obtain the following corollary: Moreover, the asymptotic optimal objective value of Problem Proof. See Section IV-A.

B. Energy-scarce Regime
Now, we present a solution to Problem 1 in the energyscarce regime M i=1 b i < 1, and show it is near-optimal. The solution r ⋆ of the energy-scarce regime is again given by (18), where x ⋆ and β ⋆ are 6 We use the standard order notation: 7 Observe that, according to (24), the asymptotic optimal average peak age of source l is (1/ min{b l , β ⋆ √ w l } + 1) which decreases with the weight w l . The weighted average peak age is w l (1/ min{b l , β ⋆ √ w l } + 1) which increases with w l . This phenomenon is reasonable and agrees with our expectation. and The near-optimality of the proposed solution (i.e., r ⋆ ) in the energy scarce regime is explained in the following theorem: is sufficiently small, in the following sense: where Proof. See Section IV-B.
We obtain the following corollary from Theorem 3.
Interestingly, the asymptotic optimal objective values of Problem 1 in both regimes, given by (24) and (30), are of an identical expression. However, in the energy-scarce regime, we can observe that β ⋆ , which is defined in (25), always satisfies min{b l , β ⋆ √ w l } = b l for all l.

Remark 1.
We would like to point out that the condition t s /E[T ] ≈ 0 is satisfied in many practical applications. For instance, in a wireless sensor network that is equipped with low-power UHF transceivers [47], the carrier sensing time is t s = 40 µs, while the transmission time is around 5 ms.

C. Discussion
In this subsection, we present a simple implementation of our proposed solution, discuss the nested convex optimization method that can be used to solve Problem 1 when t s = 0, provide some useful insights about our proposed solution at the limit point t s /E[T ] → 0, and provide a comparison with synchronized schedulers performance.
1) Implementation of Sleep-wake Scheduling: We devise a simple algorithm to compute our solution r ⋆ , which is provided in Algorithm 1. Notice that r ⋆ has the same expression (18) in the energy-adequate and energy-scarce regimes. We exploit this fact to simplify the implementation of sleep-wake scheduling. In particular, the sources report w l and b l to the AP, which computes β ⋆ and x ⋆ , and broadcasts them back to the sources. After receiving β ⋆ and x ⋆ , source l computes r ⋆ l based on (18). In practical wireless sensor networks, e.g., smart city networks and industrial control sensor networks [48], [49], the sensors report their measurements via an access point (AP). Hence, it is reasonable to employ the AP in implementing the sleep-wake scheduler.
Algorithm 1: Implementation of sleep-wake scheduler. 1 The AP gathers the parameters The AP computes x ⋆ , β ⋆ from (19) and (20); 4 else 5 The AP computes x ⋆ , β ⋆ from (25) -(27); 6 end 7 The AP broadcasts x ⋆ , β ⋆ to all the M sources; 8 Upon hearing x ⋆ , β ⋆ , source l compute r ⋆ l from (18); In the above implementation procedure, the sources do not need to know if the overall network is in the energy-adequate or energy-scarce regime; only the AP knows about it. Further, the amount of downlink signaling overhead is small, because only two parameters β ⋆ and x ⋆ are broadcasted to the sources. Moreover, when the node density is high, the scalability of the network is a crucial concern and reporting w l and b l for each source is impractical. In this case, the AP can compute β ⋆ and x ⋆ by estimating the distribution of w l and b l , as well as the number of source nodes, which reduces the uplink signaling overhead. Finally, when sources are not in the hearing range of each other, hidden/exposed source problems arise. These problems are challenging to solve analytically. However, this can be solved by designing practical heuristic solutions based on the theoretical solutions. One design method was given in [23].
2) The Nested Convex Optimization Method for t s = 0: If t s = 0, Problem 1 reduces to the following optimization problem: Observe that the optimization problem in (31) is non-convex.
To bypass this difficulty, we use an auxiliary variable y = M i=1 r i + 1. Hence, we obtain the following optimization problem for given y: The objective function in (32) is a convex function. Moreover, the constraints in (33) and (34) are affine. Hence, Problem (32) is convex. Exploiting (32), we solve (31) by using a two-layer nested convex optimization method: In the inner layer, we optimize r for given y. After solving r, we will optimize y in the outer layer. This technique is used in the proof of Lemma 8 in Appendix D, where the reader can find the detailed solution.
3) Asymptotic Behavior of The Optimal Solution: In the energy-adequate regime, the sleeping period parameter r ⋆ l of source l tends to infinity as t s /E[T ] → 0, while the ratio r ⋆ l /r ⋆ i between source l and source i is kept as a constant for all l and i. Hence, the sleeping time of the sources tends to zero. Meanwhile, since t s /E[T ] → 0, the sensing time becomes negligible. The channel access probability of source l in this limit can be computed as Because of (20), Hence, the channel is occupied by the sources at all time, without any time overhead spent on sensing and sleeping.
On the other hand, in the energy-scarce regime, the sleeping period parameter r ⋆ l of source l converges to a constant value when t s /E[T ] → 0, i.e., we have Since the cumulative energy is scarce, the sources necessarily need to stay idle for some time in order to meet their target lifetime. Hence, sleep periods are imposed for achieving the optimal trade-off between minimizing AoI and energy consumption.

4) Comparison with Synchronized Schedulers Performance:
We would like to show that the performance of our proposed algorithm is asymptotically no worse than any synchronized (e.g., centralized) scheduler. Consider a scheduler in which the fraction of time during which source l transmits update packets is equal to a l , where we have a = {a l } M l=1 and M i=1 a i ≤ 1. In this scheduler, only one source is allowed to access the channel at a time, i.e., there is no collision (this can be achieved either by a deterministic scheduler or by assigning a channel access probability a l for each source l after each packet transmission) 8 . We can perform an analysis similar to that of Section II-B, and show that the total weighted average peak age of a synchronized scheduler is given by Hence, the problem of designing an optimal synchronized scheduler that minimizes the total weighted average peak age under energy constraints can be cast as where we have divided the objective function by E[T ]. Next, we show that the performance of our proposed algorithm converges to that of the optimal synchronized scheduler when Proof. The proof is provided in Appendix G which is listed at the end before Appendix H as it requires some results from precedent appendixes.
Synchronized schedulers were recently studied in [15] for the case without energy constraints, i.e., b l ≥ 1 for all l. 8 Note that if M i=1 a i < 1, then it is possible that the scheduler decides not to serve any source after the transmission of some packet. In this case, the scheduler waits for a random time that has the same distribution as the transmission time T before deciding to serve another source.
According to Corollary 5, the channel access probability of the synchronized scheduler in [15] is a special case of our solution (35) where b l ≥ 1 for all l.

IV. PROOFS OF THE MAIN RESULTS
In this section, we provide the proofs of Theorem 1, Corollary 2, Theorem 3, and Corollary 4.

A. The Proofs of Theorem 1 and Corollary 2
We prove Theorem 1 and Corollary 2 in three steps: Step 1: We show that our solution r ⋆ (18) -(20) is feasible for Problem 1.
Hence, by substituting this solution r ⋆ into the objective function of Problem 1 in (17), we get an upper bound on the optimal value∆ w-peak opt , which is expressed in the following lemma: where x ⋆ , β ⋆ are defined in (19), (20).
Proof. In Lemma 6, we showed that our proposed solution r ⋆ (18) - (20) is feasible for Problem 1. Hence, we substitute this solution into Problem 1 to obtain the following upper bound: Next, we replace e − min{bi,β ⋆ √ wi}x ⋆ (ts/E[T ]) by 1 to derive another upper bound with a simple expression, which is given by (42). This completes the proof.
Step 2: We now construct a lower bound on the optimal value of Problem 1. Suppose that r = (r 1 , . . . , r M ) is a feasible solution to Problem 1, such that r l > 0 and Because Hence, the following Problem 2 has a larger feasible set than Problem 1: where∆ w-peak opt,2 is the optimal value of Problem 2. The optimal objective value of Problem 2 is a lower bound of that of Problem 1. We note that the constraint set corresponding to Problem 2 is convex. Thus, this relaxation converts the constraint set of Problem 1 to a convex one, and hence enables us to obtain a lower bound for the optimal value of Problem 1, which is expressed in the following lemma: where β ⋆ is the root of (20).
Proof. See Appendix D.
Step 3: After the upper and lower bounds of∆ w-peak opt were derived in Steps 1-2, we are ready to analysis their gap. By combining (42) and (47), the sub-optimality gap of the solution r ⋆ (18) - (20) is upper bounded by where x ⋆ , β ⋆ are defined in (19), (20). Next, we characterize the right-hand-side (RHS) of (48) by Taylor expansion. For simplicity, let ǫ = ts E[T ] . Using the expression for x ⋆ from (19), we have Moreover, Substituting (49) and (50) in (48), we obtain where the second inequality involves the use of Taylor expansion. This proves Theorem 1.
We can observe that the gap ∆ w-peak (r ⋆ ) −∆ w-peak opt in the energy-adequate regime converges to zero at a speed of O( √ ǫ), as ǫ → 0. Further, both the upper and lower bounds (42), (47) Thus, this value is the asymptotic optimal objective value of Problem 1. This proves Corollary 2.

B. The Proofs of Theorem 3 and Corollary 4
Similar to Section IV-A, we prove Theorem 3 and Corollary 4 also in three steps: Step 1: We show that the proposed solution r ⋆ (18) and Proof. See Appendix E. Now, we construct an upper bound on the optimal value of Problem 1 using our proposed solution as follows: where x ⋆ is defined in (25).
Proof. In Lemma 9, we showed that our proposed solution r ⋆ (18) and (25)  w l e −b l x ⋆ ts Next, we replace e −b l x ⋆ ts E[T ] by 1 to derive another upper bound with a simple expression, which is given by (53). This completes the proof.
Step 2: Similar to the proof in Section IV-A, we use the relaxed problem, Problem 2, to construct a lower bound as follows: Proof. See Appendix F.
Moreover, we observe that the gap ∆ w-peak (r ⋆ ) −∆ w-peak Thus, in this section, we derive learning algorithms that optimize the total weighted average peak age of all sources when the mean transmission time E [T ] is unknown to the scheduler. We begin by reducing our system to an equivalent discrete-time Markov chain.

Contributions and Challenges:
The simplest learning algorithm is called the certainty equivalent rule [50]- [53]. In this, the scheduler maintains an empirical estimate of E [T ], and utilizes sleep parameters that are optimal when the true value of the mean transmission time is equal to this estimate.
The regret of a learning algorithm is the sub-optimality in the performance that results because the algorithm does not know the system parameters. What we are able to show is that by using the CE rule, we are able to get o(H) regret, where H is the time-horizon. This further implies that the long-term timeaverage performance of our CE algorithm is asymptotically optimal.
This result is important since it is well-known by now [54] that in many reinforcement learning problems [40], the CE rule fails to be yield long-term time average performance, because it does not yield a correct estimate of the optimal choices. Thus, more complex learning rules, such as optimism in the face of uncertainty [41], [53] that utilize confidence balls in addition to the empirical estimates and thus have a significantly higher computational complexity, are required in order to ensure optimality. Our main contribution is to show that the vanilla CE rule yields asymptotically the same long-term time average performance as the scheduler that knows the system parameters in advance, i.e. (with a high probability) the "sub-optimality gap" of the CE rule is o(H) where H is the operating time horizon. This means that instead of using more complex learning algorithm such as the UCRL [41] or RBMLE [53], one could use CE thereby saving precious computing power and attaining the optimal average performance (asymptotically). We perform a finite-time performance analysis of the CE rule and explicitly quantify its sub-optimality by deriving an upper-bound on its "regret", i.e., the gap between its average expected performance, and that resulting from the application of optimal sleep parameter. The problem of designing and analyzing learning algorithms for our setup poses several challenges, primarily because the age process evolves in continuous time on a continuous state-space that is not compact. To address this difficulty, we show that for the purpose of optimizing average age, we can equivalently work with a discrete-time process. We then utilize several techniques from the theory of general state-space Markov chains [55] for analyzing the learning regret.
Sampling Continuous Time Process: Consider the multisource system in which the sleep durations are modulated according to the parameter vector r = (r 1 , r 2 , . . . , r M ). Throughout this section, we let n ∈ N be the discrete time of the sampled system. We sample the original continuous-time system at those time instants when one out of the following events occur: • a source l gets channel access and starts transmitting. We say that it wakes up, denoted by m l (n) = 1, • a source l completes packet transmission, and hence goes into sleep mode such that m l (n) = 0.
In what follows, we make this assumption.
As is shown in Lemma 15 (see Appendix H), for the purpose of adaptively choosing sleep parameters, the process s(n) serves as a sufficient-statistics [56] for the optimization problem (17). In other words, s(n) is the state of a Markov decision process. Hence, we will work exclusively with the discretetime system obtained by sampling the original continuoustime system. We use S to denote the state space of a single source, i.e., we have s l (n) ∈ S. Consider the operation over a time horizon of H discrete time-steps, and let K l denote the (random) number of packets delivered to source l until time H. The cumulative cost incurred is given by where ∆ peak l,i denotes the i-th peak age of source l. We let r l (n) ∈ R + denote the sleep period parameter for source l, and denote r(n) := (r 1 (n), r 2 (n), . . . , r M (n)). As is shown in Lemma 15, the expected value of the cumulative value of peak age can be written as follows, where the function g is described in Lemma 15. However, in our setup, the controller that chooses r(n) does not know the density function f of the packet transmission time, and has to adaptively choose the sleeping period paremeter r(n) so as to minimize the operating cost (64).
where∆ w-peak (r ⋆ ) is the optimal performance when the true system parameter is known and hence the scheduler can implement the optimal rate vector. Throughout this section we use θ to denote the mean transmission time E[T ]. Since the optimal rate depends upon the probability density function f (·) only through its mean E [T ], we also denote it by r ⋆ θ . Certainty Equivalence Learning Algorithm: We begin with some notations. Let col(i), i = 1, 2, . . . be a random variable that is equal to 1 if there is no collision at time i, and is 0 otherwise. The empirical estimate of θ at time n is denoted byθ(n), and given aŝ where N (n) : and T (i) ∈ [0, T max ] is the time taken to deliver packet at time i.
The learning rule operates in episodes. We let τ k be the start time of the k-th episode, and let E k := {τ k , τ k + 1, . . . , τ k+1 − 1} be the time-slots that comprise the k-th episode, so that the duration of E k is τ k+1 −τ k time-slots.
We let τ k = 2 k , use k(n) to denote the index of the current episode at time n, and θ(n) to denote the empirical estimate at the beginning of the current episode, defined by θ(n) : =θ(τ k(n) ).
Within each single episode the algorithm implements a single stationary controller that makes decisions only on the basis of the state s(n) and the estimate θ(τ k ) obtained at the beginning of the current ongoing episode k(n). It chooses the sleep period parameter as r(n) = r ⋆ θ(n) , ∀n ∈ E k , i.e., it utilizes the rate vector that is optimal for the system whose mean transmission time is equal to θ(n). Thus, r(n) = r ⋆ θ(τ k ) for τ k ≤ n ≤ τ k+1 − 1.
We summarize our learning rule in Algorithm 2. We will Throughout, for a vector x, we let x denote its Euclidean norm, and x 1 denote its 1-norm.

Assumption 2. With a high probability, say greater than 1−δ,
where δ > 0 is a small constant, the state value s(τ k ) at the beginning of each episode k belongs to a compact set K := x ∈ S M : x 1 ≤ K 1 , where S is the state space of a single source.
The above is not a restrictive assumption, since the scheduler can always ensure that towards the end of each episode, each source receives a sufficient amount of service in order to ensure this condition. We now make a few assumptions regarding the set Θ of "allowable parameters". Assumption 3. Recall that r ⋆ θ is the optimal sleep parameter when the mean transmission time is equal to θ. The following two properties hold for the scheduler that uses r(n) ≡ r ⋆ θ , n ∈ N.
(i) The average cost is finite, i.e. lim sup where ca l (i) is a random variable that is 1 if source l gets channel access at time i, while is 0 otherwise. We denote It is easily verified that (70), (71) hold true whenever the rate vector r is bounded.
The following result quantifies the learning regret of Algorithm 2.
where H is the operating time horizon, γ ≥ 4 is a constant, K 2 , p min are as in Assumption 3, and the parameters δ, L > 0 are as in Lemma 19. Proof. See Appendix H.

VI. NUMERICAL AND SIMULATION RESULTS
We use Matlab and NS-3 to evaluate the performance of our algorithm. We use "age-optimal scheduler" to denote the sleep-wake scheduler with the sleep period paramters r ⋆ l 's as in (18), which was shown to be near-optimal in Theorem 1 and Theorem 3. By "throughput-optimal scheduler", we refer to the sleep-wake algorithm of [23] that is known to achieve the optimal trade-off between the throughput and energy consumption reduction. Moreover, we use "fixed sleeprate scheduler" to denote the sleep-wake scheduler in which i.e., r l = k for all l, where the parameter k has been chosen so as to satisfy the energy constraints of Problem 1. We also let∆ w-peak un (r) denote the unnormalized total weighted average peak age in (11). Finally, we would like to mention that we do not compare the performance of our proposed algorithm with the CSMA algorithms of [36], [37] where the goal was solely to minimize the age. Since they do not incorporate energy constraints, it is not fair to compare the performance of our algorithm with them.  , where the number of sources is M = 10. The age-optimal scheduler is seen to outperform the throughput-optimal and Fixed sleep-rate schedulers. This implies that what minimizes the throughput does not necessarily minimize AoI and vice versa. Moreover, we observe that the total weighted average peak age of all schedulers increases as the sensing time increases. This is expected since an increase in the sensing time leads to an increase in the probability of packet collisions, which in turn deteriorates the age performance of these schedulers.

A. Numerical Evaluations
We then scale the number of sources M , and plot∆ w-peak un (r) in (11) as a function of M in Figure 4. While plotting, we   Fixed sleep-rate scheduler Throughput-optimal scheduler Age-optimal scheduler Figure 6: Total weighted average peak age∆ w-peak un (r) in (11) versus the target lifetime D for a dense network with M = 10 5 sources, where∆ w-peak un (r) has been normalized by M while plotting. Since the throughput-optimal scheduler is infeasible for values of D greater than 18 years, we do not plot its performance for these values.
simulation of the throughput-optimal scheduler for b < 0.01 since the sleeping period parameters that are proposed in [23] are not feasible for Problem 1 in the energy-scarce regime, i.e., We now show the effectiveness of the proposed scheduler when deployed in "dense networks" [21], [22]. Dense networks are characterized by a large number of sources connected to a single AP. We fix M at 10 5 sources, and take the target lifetimes of the sources to be equal, i.e., D l = D for all l. The weights w l 's corresponding to different sources are generated randomly by sampling from the uniform distribution in the range [0, 2]. We let the initial battery level B l = 8 mAh for all l and the output voltage is 5 Volt. We also let the energy consumption in a transmission mode to be 24.75 mW for all sources. We vary the parameter D and plot the resulting performance in Figure 6. While plotting, we normalize the performance by the number of sources M .
We exclude simulations for the throughput-optimal scheduler for values of D for which the scheduler is infeasible, i.e., its cumulative energy consumption exceeds the total allowable energy consumption. The age-optimal scheduler is seen to outperform the others. As observed in Figure 6, under the Age-optimal algorithm (from NS-3) 45 degree slope Figure 7: The average actual lifetime versus the target lifetime D.
age-optimal scheduler, sources can be active for up to 25 years, while simultaneously achieving a decent average peak age of around .2 hour, i.e., 12 minutes. This makes it suitable for dense networks, where it is crucial that the sources are necessarily active for many years.

B. NS-3 Simulation
We use NS-3 [57] to investigate the effect of our model assumptions on the performance of age-optimal scheduler in a more practical situation. We simulate the age-optimal scheduler by using IEEE 802.11b while disabling the RTS-CTS and modifying the back-off times to be exponentially distributed in the MAC layer. Our simulation results are averaged over 5 system realizations. The UDP saturation conditions are satisfied such that the source nodes always have packets to send. Our simulation consists of a WiFi network with 1 AP and 3 associated source nodes in a field of size 50m × 50m. We set the sensing threshold to -100 dBm which covers a range of   of all sources to be equal, i.e., D l = D for all l. The ageoptimal scheduler (theoretical) curve is obtained using (11), while the age-optimal scheduler (from NS-3) curve is obtained using the NS-3 simulator. As we can observe, the difference between the plotted curves does not exceed 2% of the ageoptimal scheduler (theoretical) performance. This emphasizes the negligible impact of our assumptions on the performance of our proposed algorithm.

VII. CONCLUSIONS
We designed an efficient sleep-wake scheduling algorithm for wireless networks that attains the optimal trade-off between minimizing the AoI and energy consumption. Since the associated optimization problem is non-convex, in general we could not hope to solve it for all values of the system parameters. However, in the regime when the carrier sensing time t s is negligible as compared to the average transmission time E[T ], we were able to provide a near-optimal solution.
Moreover, the proposed solution is in a simple form that allowed us to design an easy-to-implement algorithm to obtain the solution. Furthermore, we showed that the performance of our proposed algorithm is asymptotically no worse than that of the optimal synchronized scheduler, as t s /E[T ] → 0. Finally, when the mean transmission time is unknown, we devise a reinforcement learning algorithm that adaptively learns the unknown parameter.

VIII. ACKNOWLEDGEMENTS
The authors appreciate Jiayu Pan and Shaoyi Li for their great efforts in obtaining the ns-3 simulation results.
[66] R. Ayoub, "Euler and the zeta function,"  (5) Define S l as the residual sleeping period of source l after a sleep-wake cycle is over. Due to the memoryless property of exponential distribution, since the sleeping period of source l is exponentially distributed with mean value E[T ]/r l , S l is also exponentially distributed with mean value E[T ]/r l . According to the proposed sleep-wake scheduler, source l gains access to the channel and transmits successfully in a given cycle if S i ≥ S l + t s for all i = l. Hence, we have = r l e r l ts where (a) is due to P[A] = E[P(A|B)], and (b) is due to the fact that S l is independent for different sources.

APPENDIX B DERIVATION OF (13)
Recall the definition of S l at the beginning of Appendix A.
Moreover, define P l as the probability that source l transmits a packet in a given cycle, regardless whether packet collision occurs or not. For the sleep-wake scheduling mechanism the we are utilizing here, source l transmits in a given cycle as long as no other source wakes up before S l − t s , i.e., S i ≥ S l − t s for all i = l. Hence, we have where the first term in the RHS is given by Since S l is exponentially distributed with mean value E[T ]/r l , we can determine the second term in the RHS of (79) as follows: Substituting (84) and (85) back into (79), we get Let α col denote the collision probability in a given cycle. We have α col = 1 − M i=1 α i , because each cycle includes either a successful transmission or a collision. Moreover, let E[Idle] denote the mean of the idle duration in a cycle. By the renewal theory in stochastic processes [58], σ l is given by APPENDIX C

PROOF OF LEMMA 6
First of all, we need to show that (20) has a solution for β ⋆ . In this case, we have the following: Substituting by this into (38), we obtain which is equal to the asymptotic optimal objective value of Problem 1 in energy-scarce regime in (30). This completes the proof.

A. Notation and Background on General State-Space Markov Processes
While analyzing learning algorithm, we will have to work with Markov processes on general state-space [55], [60]. In this section we provide a brief account of such processes.
Notation: For a set of r.v. s X , we let F (X ) denote the smallest sigma-algebra with respect to which each r.v. in X is measurable. For a set X , we let X c denote its complement. For an event X , we let ½(X ) denote its indicator random variable.
For a set X , we let B(X ) denote the sigma-algebra of Borel sets of X .
We begin by showing that s(n) can be taken to be the system state /sufficient statistics [56] in order to describe the sampled process. In what follows, we let S := R + × {0, 1}. Denote by θ := where F t denotes the sigma-algebra generated by all the random variables until the n-th discrete sampling instant. The function K is the kernel [55] associated with the controlled transition probabilities of the process s(n), Thus, K(s, r, A; f ) is the probability with which the state at time n + 1 belongs to the set A, given that the state at time n is equal to s, and the vector comprising of sleep period parameters at time n is equal to r. Note that the kernel is parametrized by the density function of transmission time f .
We begin by stating some definitions associated with Markov Chains on General State-Spaces. Though these can be found in standard textbooks on General State-Space Markov Chains such as [55], [60], we include them here in order to make the paper self-contained.
Let us now fix the controls at r(n) ≡ r, and consider the resulting discrete-time Markov chain s(n) ∈ S M . If A is a Borel set, we let P n (x, A) denote the probability of the event s(n) ∈ A, given that s(0) = x.
for some non-trivial measure ν m (·) and some m ∈ N.

B. Preliminary Results
We now show that in order to minimize the expected value of C(H), it suffices to design controllers that "work directly" with the sampled system. Thus, the quantity s(n) as described in (62) serves as a sufficient statistic for the purpose of optimizing the expectation of cumulative peak age [56]. We also show that this objective can be posed as a constrained Markov decision process [61]. Proof. Consider the cumulative peak-age cost (63) in which the l-th source incurs a penalty of ∆ peak l,i upon delivery of the ith packet. Let this delivery occur at the end of the n-th discrete time-slot (note that this time n is random). Let us denote by a peak l (n) the peak age of source l during the (continuous) time interval (in the non-discretized system) corresponding to the discrete time slots n − 1 and n. We could (instead of charging a penalty of ∆ peak l,i units at the end of n-th slot) charge the quantity E a peak (n)|s(n − 1), r(n − 1) at the discrete time instant n − 1. For sources k = l that are not transmitting between n − 1 and n, and have m k (n − 1) = 0, we let g(s(n − 1)) = 0. It then follows from the law of the iterated expectations [62] that the expected cost of the system under this modified cost function remains the same as that of the original system. This completes the proof.
The set C is small for the process s(n).
2) For the process s(n), each compact set is petite.
3) The process s(n) is strongly aperiodic.
Proof. 1) Consider s(0) ∈ C. It follows that at time n = 0, all the sources are sleeping. Consider the following set denoted C ′ : Sources 1 and 2 wake up within t s time duration of each other, while the other sources wake up much later than these two. Consequently, there is a collision between Source 1 and Source 2, and hence at time n = 1 these two sources enter into sleep mode, so that at time n = 1 all the sources are asleep. Also assume that the cumulative time elapsed for this event to occur is approximately equal to t s + δ, where δ > 0 is a sufficiently small parameter. The probability of the event {s(1) ∈ C ′ } can be lower bounded as follows Since the above lower-bound on the probability of "reaching C ′ " is true for all s(0) ∈ C, it follows from Definition 1 that the set C is small.
2) Consider the process s(n) starting in state s(0), and let the age vector a(0) belong to a compact set, so that s(0) also belongs to a compact set. We will derive a lower bound on the probability of the event {s(N ) ∈ C}, where C is as in (152). This will prove (ii) since we have already shown in (i) that the set C is small. Consider the following sample path: at each time i ∈ [1, M ], we have that source i successfully transmits a packet, and moreover the age of the packet received is approximately equal to 1. We will derive a lower-bound on the probability of this event. In the following discussion we use b > 0 and η ∈ (0, 1 − t s − b), where η denotes the time when Source 1 wakes up. Since the counter of the ith source has a probability density equal to r i e −rix , the probability that during the i-th slot source i gets channel access is lower bounded by (1 − exp(−ηr i ))Π j =i e −rj ; while the probability that the age of its delivered packet is around 1, given that it wakes up at η, is lower bounded by b 0 f (y)dy. Thus, the probability of this sample path is lower bounded by This concludes the proof since along this sample path we have that s(N ) ∈ C.
3) It follows from the discussion on page 121 of [60] that in order to prove the claim it suffices to show that the volume of the set C ∩ C ′ is greater than 0. However, this condition holds true if the parameter δ in (i) above has been chosen so as to satisfy t s + δ < ǫ.
We now show that the process s(n) has a certain "mixing property". For a measure µ and a function f , we define Lemma 17 (Geometric Ergodicity). Consider the controlled Markov process s(n), n = 1, 2, . . . , associated with the network in which the controller utilizes r(n) ≡ r. The process s(n) has an invariant probability measure, which we denote as π(∞, r). Moreover, where R > 0, and ρ < 1.
Proof. Since we have shown in Lemma 16 that s(n) is strongly aperiodic, it follows from Theorem 6.3 of [60] that in order to prove the claim it suffices to show that the following holds true when s(n + 1) 1 is sufficiently large where λ < 1. Note that each source gets to transmit with a probability at least min l α l , and also the ex-

pected value of the inter-sampling time is upper-bounded by max E[T ], E[T ]
M i=1 ri + t s . It then follows that (154) holds true with λ set equal to min l α l , and L equal to where K is the transition kernel as described in Lemma 14, the function g is the one-step cost function as in Lemma (15). Moreover, the function V satisfies the following, where the constant R is as in Lemma 17. Proof. We have shown in Lemma 17 that the process s(n) is geometrically ergodic. Hence, it follows from Theorem 7.5.10 of [63] that there exists a function V (·) that satisfies (155), and moreover it is given as follows, Substituting the geometric bound (153) into the above, we obtain the following where ρ < 1.
where the sub-script r in the expectation E r above refers to the fact that the averaging is performed w.r.t. the measure induced by the policy that uses sleep rates equal to r.
2) The cumulative peak-age is locally Lipschitz continuous function of r. Thus, whenever r ⋆ θ − r is sufficiently small, and where the Lipschitz constant at sleep period parameter r is given by Similarly, the optimal sleep period parameter is a locally Lipschitz function of θ, so that we have, whenever |θ 1 − θ 2 | is sufficiently small.
To prove the statement about Lipschitz continuity, it suffices to show that the average peak age is a Lipschitz continuous function of r, and the optimal rate r ⋆ θ is Lipschitz continuous function of θ. To prove this, it suffices to show that the average peak age is a continuously differentiable function of r, and also r ⋆ θ is a continuously differentiable function of θ (see [64] for more details). The continuously differentiable property is evident from the relations (11), (18)- (20) and (25)- (27). This completes the proof.
Bounds on the Estimation Error: We now derive some concentration results for the estimateθ(n) around the true value θ ⋆ . Let C(n) be the confidence interval associated with the estimateθ(n), i.e., C(n) := θ : |θ −θ(n)| ≤ ξ(n), θ > 0 , where ξ(n) := T max 2 log (n γ ) N (n) , 1 ≤ n ≤ H, γ ≥ 4 is a constant, N (n) is the total number of packet deliveries until n, and T max is the maximum possible transmission time. We begin by showing that with a high probability, our confidence balls are true at all the times. where C(n) is as in (157), and θ ⋆ is the vector consisting of true parameter values. We then have that P (G c 1 (n)) ≤ 1 n γ−1 .
Since the total number of samples n 0 can assume values from the set {0, 1, 2, . . . , n}, the proof then follows by using union bound on n 0 .
Define the event, where N (n) denotes the number of samples that have been obtained until time n for estimating transmission times. We then have that P(G c 2 (n)) ≤ exp (−δ 1 n) .
This completes the proof.
Combining the regret decomposition with the smoothness properties of the optimal average cost that were derived in Lemma 19, we obtain the following key result that allows us to upper-bound R(H). (τ k+1 − τ k ) P(|θ(τ k ) − θ ⋆ | > δ) where the constant δ > 0 is as in Lemma 19. Proof. It follows from the ergodicity properties of the process s(n) that were proved in Lemma 18 and Assumption 2 regarding s(n), that the episodic regret can be bounded as follows (ρ, R are as in Lemma 18 and Assumption 2), The following two events are possible: (i) |θ ⋆ −θ(τ k )| < δ: In this case it follows from Lemma 19 that ∆ w−peak (r ⋆ θ(τ k ) ; θ) −∆ w-peak (r ⋆ ) ≤ L|θ ⋆ −θ(τ k )|.
(ii) |θ ⋆ −θ(τ k )| > δ: It follows from Assumption 3 that the average performance under any sleep parameter cannot exceed K 2 , and hence we can bound ∆ w−peak (r ⋆ θ(τ k ) ; θ) −∆ w-peak (r ⋆ ) by K 2 . The proof then follows by substituting the bounds discussed above for the two cases into (164), and using regret decomposition result.
By combining the result of Lemma 21 with the union bound and using (166) we conclude that G 3 has a probability greater than 1− k>k0 exp(−δ 1 τ k ) = 1−O 1 H . On G 3 , the number of samples N (τ k ) at the beginning of each episode k > k 0 is greater than p min − √ δ 1 τ k . Thus on G 3 , for episodes k > k 0 the radius of C(τ k ) is less than γ log H (pmin− √ δ1)τ k . Let k 1 be the smallest integer that satisfies γ log H (p min − √ δ 1 )τ k1 ≤ δ 2 , i.e. τ k1 ≥ 1 (p min − √ δ 1 )δ 2 γ log H, where the constant δ > 0 is as in Lemma 19. Thus on G 3 , for episodes k ≥ max {k 0 , k 1 }, the radius of confidence intervals is less than δ. Note that on ∩ k G 1 (τ k ) the confidence intervals (157) at the beginning of each episode are true.
Hence, on {∩ k G 1 (τ k )} ∩ G 3 we have |θ(τ k ) − θ ⋆ | < δ for epsiodes k ≥ max {k 0 , k 1 }. Thus, on {∩ k G 1 (τ k )} ∩ G 3 this regret is bounded by K 2 max {τ k0 , τ k1 }. Now consider sample paths for which some of the confidence intervals fail. The probability that C(τ k ) fails is less than 1 τ γ−1 k (Lemma 20); moreover since the episode duration of E k , (τ k+1 − τ k ) is less than τ k , we have that the expected value of the regret during E k in the event of failure of C(τ k ) is less than K 2 1 τ γ−2 k . Since γ ≥ 4, the cumulative expected regret arising from this is bounded by [66]. We summarize our discussion as follows.
Since we have τ k+1 − τ k ≤ τ k , the above can be bounded We are now in a position to prove main result Theorem 12.
Proof. (Theorem 12) The proof follows by substituting the bounds obtained in Lemma 23 and Lemma 24 into the regret decomposition result of Lemma 22.