Andrea Fox

Francesco De Pellegrini

Eitan Altman

Learning Optimal Edge Processing with Offloading and Energy Harvesting

Keywords: AoI, Energy-Harvesting, Offloading, MDP, Reinforcement Learning

Modern portable devices can execute increasingly sophisticated AI models on sensed data. The complexity of such processing tasks is data-dependent and has relevant energy cost. This work develops an Age of Information markovian model for a system where multiple battery-operated devices perform data processing and energy harvesting in parallel. Part of their computational burden is offloaded to an edge server which polls devices at given rate. The structural properties of an optimal policy for a single device-server system are derived. They permit to define a new model-free reinforcement learning method specialized for monotone policies, namely Ordered Q-Learning, providing a fast procedure to learn the optimal policy. The method is oblivious to the devices' battery capacities, the cost and the value of data batch processing and to the dynamics of the energy harvesting process. Finally, the polling strategy of the server is optimized by combining this policy improvement technique with stochastic approximation methods. Extensive numerical results provide insight into the system properties and demonstrate that the proposed learning algorithms outperform existing baselines.

INTRODUCTION

New generations of mobile access networks promise low delay and high-speed throughput data connections paired with in-network processing capabilities [START_REF] Hu | Mobile edge computing: a key technology towards 5G[END_REF]. They will support mobile computing services able to integrate AI-intensive processing tasks in their workloads such as, e.g., smart city services or virtual and augmented reality applications. In the next future, the vast majority of enterprise IoT projects are expected to have an AI component, up from less than 10% in 2018 [START_REF] Lovelock | Forecast: The business value of artificial intelligence, worldwide, 2017-2025[END_REF]. To support these applications, edge networks must evolve to solve the key challenges of such scenario [START_REF] Wang | Adaptive federated learning in resource constrained edge computing systems[END_REF]. In fact, the energy consumption of AI applications is critical for battery operated devices. On the other hand, they may require periodic updates based on fresh data, settling specific requirements on the rate at which data are fetched and processed. The standard metric to this respect is the Age of Information (AoI), denoting the freshness of information when received at the destination [START_REF] Kaul | Real-time status: How often should one update?[END_REF]. In the literature, AoI performance has been studied for several queuing disciplines determining the average system time of data reads. The standard objective is to maximize some long term reward for the AoI of retrieved information [START_REF] Yates | Age of information: An introduction and survey[END_REF][START_REF] Kadota | Minimizing the age of information in wireless networks with stochastic arrivals[END_REF]. In the context of this paper, it is the long term reward for processing data, also called age of processing [START_REF] Li | Age of processing: Age-driven status sampling and processing offloading for edge-computing-enabled real-time IoT applications[END_REF].

Energy harvesting from renewable sources, such as solar cells or piezoelectric generators, has becoming available on devices used, e.g., for Internet of things (IoT) applications. In the literature, optimal policies for AoI minimization under energy harvesting have been studied using Markov decision theory both in continuous and in discrete time [START_REF] Wang | Minimizing aoi for real-time monitoring in resource-constrained industrial IoT networks[END_REF][START_REF] Elif Tugce Ceran | Learning to minimize age of information over an unreliable channel with energy harvesting[END_REF][START_REF] Yang | Optimal online sensing scheduling for energy harvesting sensors with infinite and finite batteries[END_REF][START_REF] Abd-Elmagid | Aoi-optimal joint sampling and updating for wireless powered communication systems[END_REF][START_REF] Stamatakis | Control of status updates for energy harvesting devices that monitor processes with alarms[END_REF]. Most such studies focused on optimal policies to optimize AoI subject to energy causality constraints. The problem is to reserve the battery charge for moments when it is most needed, e.g., for alarm generation events [START_REF] Stamatakis | Control of status updates for energy harvesting devices that monitor processes with alarms[END_REF].

The scenario studied in this paper considers the uncertainty of battery consumption and the uncertainty about the amount of energy harvested over time. In fact, the energy cost of AI tasks depends inherently on the statistical distribution of input data and on the preference for lightweight or heavyweight models. Thus, when such a computing task is launched on a batch of data, the energy required to finish processing may exceed the available battery charge. In this event, a further delay for data processing is needed in order to harvest enough energy to complete the ongoing task.

Finally, in edge computing, task offloading to edge-servers mitigates the problem of energy consumption to run AI tasks on mobile devices [START_REF] Li | Age of processing: Age-driven status sampling and processing offloading for edge-computing-enabled real-time IoT applications[END_REF][START_REF] Chen | Joint offloading and resource allocation for computation and communication in mobile cloud with computing access point[END_REF][START_REF] Chen | Efficient multi-user computation offloading for mobile-edge cloud computing[END_REF][START_REF] Yan | Offloading and resource allocation with general task graph in mobile edge computing: A deep reinforcement learning approach[END_REF][START_REF] Chen | Performance optimization in mobile-edge computing via deep reinforcement learning[END_REF][START_REF] Arafa | Timely cloud computing: Preemption and waiting[END_REF][START_REF] Song | Age based task scheduling and computation offloading in mobile-edge computing systems[END_REF][START_REF] Huang | AoI-aware energy control and computation offloading for industrial IoT[END_REF]. Thus, a device can delegate computing tasks to edge servers. However, in a realistic scenario, offloading is constrained by the availability of the edge-server, which may be supporting multiple devices. Moreover, not always task offloading proves convenient, depending also on the delays it introduces.

Main contribution. This work develops a markovian modeling framework where multiple battery-operated devices process data in parallel and perform energy harvesting. Furthermore, an intermittent edge-server supports task offloading. Events of battery depletion may occur due to the unknown complexity of data processing and to the randomness of the harvesting process. Hence, an optimal stationary policy prescribes whether or not a device should process a new data batch based on AoI and battery status. By proving that such policy is monotone it is possible to design a lightweight reinforcement learning (RL) algorithm, namely Ordered Q-learning. It applies to the wide class of problems with monotone structure of the optimal value function w.r.t. the state-action partial order. In this setting, it outperforms standard baselines, including policy gradient methods. Finally, the polling probability vector of the server is optimized by stochastic learning. To the best of the authors' knowledge, this is the first work to study the problem of AoI minimization in a system where multiple battery operated devices perform energy harvesting and rely on an edge-server for task offloading, incurring possibly in battery depletion depending on data and battery status. The paper is organized as follows. Sec. 2 describes the state of the art. In Sec. 3 the basic server-device Markov decision model is introduced. The monotone structure of an optimal policy is analyzed in Sec. 4. Sec. 5 describes RL algorithms converging the optimal solution. Sec. 6 extends analysis and algorithmic solutions to the case of multiple devices. Numerical results are provided in Sec. 7 and a concluding section ends the paper.

RELATED WORKS

The term AoI was first used in [START_REF] Kaul | Real-time status: How often should one update?[END_REF] to denote freshness of data received at the destination. Several later works on AoI focused on the minimization of such metric [START_REF] Yates | Age of information: An introduction and survey[END_REF]. The AoI minimization has been studied in combination with energy harvesting to charge IoT devices [START_REF] Wang | Minimizing aoi for real-time monitoring in resource-constrained industrial IoT networks[END_REF][START_REF] Elif Tugce Ceran | Learning to minimize age of information over an unreliable channel with energy harvesting[END_REF][START_REF] Yang | Optimal online sensing scheduling for energy harvesting sensors with infinite and finite batteries[END_REF][START_REF] Abd-Elmagid | Aoi-optimal joint sampling and updating for wireless powered communication systems[END_REF][START_REF] Stamatakis | Control of status updates for energy harvesting devices that monitor processes with alarms[END_REF]. The energy-aware scheduling policies of the type studied in this paper have been introduced to vary the sensing rate based on the instantaneous battery charge [START_REF] Yang | Optimal online sensing scheduling for energy harvesting sensors with infinite and finite batteries[END_REF]. Conversely, the effect of error prone channels of the type studied in [START_REF] Wang | Minimizing aoi for real-time monitoring in resource-constrained industrial IoT networks[END_REF] and [START_REF] Elif Tugce Ceran | Learning to minimize age of information over an unreliable channel with energy harvesting[END_REF] is left for future works. In the proposed model, as in [START_REF] Yang | Optimal online sensing scheduling for energy harvesting sensors with infinite and finite batteries[END_REF][START_REF] Abd-Elmagid | Aoi-optimal joint sampling and updating for wireless powered communication systems[END_REF], measurements are possible only when the battery level is sufficiently high. As in [START_REF] Stamatakis | Control of status updates for energy harvesting devices that monitor processes with alarms[END_REF], the proposed model accounts for data-dependent energy consumption. Moreover, it considers in detail the effect of battery depletion events.

Several works combine AoI minimization and task offloading to external devices. Authors of [START_REF] Li | Age of processing: Age-driven status sampling and processing offloading for edge-computing-enabled real-time IoT applications[END_REF], [START_REF] Arafa | Timely cloud computing: Preemption and waiting[END_REF] and [START_REF] Song | Age based task scheduling and computation offloading in mobile-edge computing systems[END_REF] studied the performance of a device-server system where a local processor device is supported by a remote server. As the present work, [START_REF] Chen | Joint offloading and resource allocation for computation and communication in mobile cloud with computing access point[END_REF] and [START_REF] Chen | Efficient multi-user computation offloading for mobile-edge cloud computing[END_REF] study the trade-off between energy consumption and execution delays to offload applications to an edge server. In [START_REF] Yan | Offloading and resource allocation with general task graph in mobile edge computing: A deep reinforcement learning approach[END_REF] and [START_REF] Chen | Performance optimization in mobile-edge computing via deep reinforcement learning[END_REF] deep reinforcement learning (DRL) is used to compute optimal offloading policies. As showed later, knowing the properties of the optimal value function permits much less expensive solutions. With very few exceptions, e.g., [START_REF] Huang | AoI-aware energy control and computation offloading for industrial IoT[END_REF] and [START_REF] Kadota | Minimizing the age of information in wireless networks with stochastic arrivals[END_REF], AoI in multi-device systems of the type studied in this paper are not addressed in the literature. In [START_REF] Huang | AoI-aware energy control and computation offloading for industrial IoT[END_REF] the average AoI is minimized by choosing whether to use the local processor or an edge server according to the network status. [START_REF] Kadota | Minimizing the age of information in wireless networks with stochastic arrivals[END_REF] provides lower bounds on the average AoI performance achievable for several queuing disciplines on a single-hop network as the one studied in this work. Note that the metric addressed in this work is not the average AoI but rather the peak AoI [START_REF] Barakat | How to measure the average and peak aoi in real networks?[END_REF].

The first Markovian model for the control of AoI appeared in [START_REF] Altman | Poster: aging control for smartphones in hybrid networks[END_REF]. MDP models were later used in [START_REF] Stamatakis | Control of status updates for energy harvesting devices that monitor processes with alarms[END_REF][START_REF] Chen | Performance optimization in mobile-edge computing via deep reinforcement learning[END_REF][START_REF] Huang | AoI-aware energy control and computation offloading for industrial IoT[END_REF][START_REF] Champati | On the minimum achievable age of information for general service-time distributions[END_REF]. Works [START_REF] Li | Age of processing: Age-driven status sampling and processing offloading for edge-computing-enabled real-time IoT applications[END_REF][START_REF] Wang | Minimizing aoi for real-time monitoring in resource-constrained industrial IoT networks[END_REF] use constrained MDPs, while [START_REF] Abd-Elmagid | Aoi-optimal joint sampling and updating for wireless powered communication systems[END_REF][START_REF] Yao | Age-optimal low-power status update over time-correlated fading channel[END_REF] use partially observable MDPs. Including constraints and partial observations are interesting extensions but out of the scope of the present work. Threshold policies for the control of the AoI have been obtained before [START_REF] Li | Age of processing: Age-driven status sampling and processing offloading for edge-computing-enabled real-time IoT applications[END_REF][START_REF] Elif Tugce Ceran | Learning to minimize age of information over an unreliable channel with energy harvesting[END_REF][START_REF] Abd-Elmagid | Aoi-optimal joint sampling and updating for wireless powered communication systems[END_REF]. In [START_REF] Elif Tugce Ceran | Learning to minimize age of information over an unreliable channel with energy harvesting[END_REF] the threshold is one-dimensional while the policy structure described in [START_REF] Li | Age of processing: Age-driven status sampling and processing offloading for edge-computing-enabled real-time IoT applications[END_REF] is only characterized numerically. In [START_REF] Abd-Elmagid | Aoi-optimal joint sampling and updating for wireless powered communication systems[END_REF] the threshold regards two incorrelated control variables: in the proposed model, state transitions for AoI and energy both depend on the chosen action.

SYSTEM MODEL

The device-server scheme is represented in Fig. 1: the device can read data batches and process them, while the edge server can poll the device to offload the computation. Thus, data batches are either read and processed locally on the device or read and offloaded. Time steps are discrete with index 𝑡 = 1, 2, . . .. Processing data at time 𝑡 on the device requires 𝐶 𝑡 energy units, which form a sequence of i.i.d. random variables {𝐶 𝑡 } with probability distribution 𝑝 𝐶 (𝑐) = P{𝐶 = 𝑐}. When the device is polled by the edge server, the data processing task is offloaded and it has zero energy cost for the device. However, sending and retrieving processed data from the server incurs in a constant delay of 𝛿 ≥ 0 time units. The device has a battery of capacity 𝐵 > 0 energy units and it can harvest a number of energy units 𝐻 𝑡 per timestep 𝑡. The energy fetched per timestep, namely the harvesting rate, forms a sequence of i.i.d. random variables {𝐻 𝑡 } whose corresponding probability distribution is 𝑝 𝐻 (ℎ) = P{𝐻 = ℎ}.

Let introduce the Semi Markov Decision Process (SMDP) which models the system. The state of the device at time 𝑡 is denoted as 𝑠 𝑡 = (𝑥 𝑡 , 𝑒 𝑡 , 𝑧 𝑡 ), where 𝑥 𝑡 represents the AoI, 𝑒 𝑡 is the device battery level and 𝑧 𝑡 is the server state. Binary variable 𝑧 𝑡 indicates whether the server has polled the device for offloading, 𝑧 𝑡 = 1, or not, 𝑧 𝑡 = 0. The corresponding per slot transition probability is 𝑝 𝑍 (𝑧 ′ |𝑧), e.g., 𝑝 𝑍 (1|0) is the probability for the server to poll the device at 𝑡 + 1 given that it did not at 𝑡. Note that 𝑥 𝑡 is the AoI of the last data batch processed by a tagged device and the AoI is measured at the end of each time slot. It holds 𝑥 𝑡 = 1 when the device has just processed fresh data. Afterwards, the AoI increases of one timestep at every time slot 𝑡 until either the device fetches a new data batch and performs the computation or the server polls the device and offloading occurs. In both cases, at the end of the data processing the AoI is reset to 1.

Freshness function 𝑢 (𝑥) is the utility for processing a data batch 𝑥 time units after the last one was processed; 𝑢 (•) is bounded and nonincreasing. It is assumed that there exists 𝑀 > 0 such that 𝑢 (𝑀 +𝑘) = 𝑢 (𝑀) for all 𝑘 > 0, so that the AoI takes values in {1, . . . , 𝑀 }. The state space is denoted S = {1, . . . , 𝑀 } × {0, . . . , 𝐵} × {0, 1}.

Finally, it is possible that the battery available at timeslot 𝑡 is not sufficient to terminate the computation immediately, namely, 𝜙 𝑡 := 𝑐 𝑡 -(ℎ 𝑡 + 𝑒 𝑡 ) > 0. In this case, a delay is incurred in order to harvest a sufficient amount of energy and complete the processing of the current batch. The corresponding timeslot has a random duration, due to the stochastic nature of energy harvesting.

The action set is A = {0, 1}, where 0 means wait and 1 process. The action taken at time 𝑡 is denoted 𝑎 𝑡 . If 𝑎 𝑡 = 1, the device fetches a new data batch, which is processed at energy cost 𝑐 𝑡 > 0. For every state 𝑠 𝑡 where 𝑧 𝑡 = 0 the action set available at each device is A (𝑠 𝑡 ) = {0, 1}, i.e. it can process or not the information. On the other hand, when 𝑧 𝑡 = 1 the action set is A (𝑠 𝑡 ) = {1}: thus if the device is polled by the server, by default the data unit is processed. Furthermore, the energy to transmit data to the server is assumed to be negligible compared to local data processing. Finally, the dynamics of the AoI for data batches is

𝑥 𝑡 +1 = 1 if 𝑎 𝑡 = 1 [𝑥 𝑡 + 1] 𝑀 if 𝑎 𝑡 = 0
where [𝑦] 𝐴 := max{0, min{𝑦, 𝐴}}. The AoI at the renewal instants is also called peak AoI [START_REF] Barakat | How to measure the average and peak aoi in real networks?[END_REF] in the literature: it corresponds to the processing rate. It now possible to characterize the transition probabilities for a given action 𝑎 ∈ A (𝑠). Hereafter 𝐻 is considered to be deterministic with 𝐻 ≡ 1 and the time index is omitted for notation's sake. The general case for stochastic harvesting rate is derived in [START_REF] Champati | On the minimum achievable age of information for general service-time distributions[END_REF] and [START_REF] Yao | Age-optimal low-power status update over time-correlated fading channel[END_REF].

Let 𝑠 = (𝑥, 𝑒, 𝑧) be the current state of the device and 𝑠 ′ = (𝑥 ′ , 𝑒 ′ , 𝑧 ′ ) the following state under action 𝑎.

The transition probability from 𝑠 to 𝑠 ′ is written, for 𝑎 = 0, as

𝑝 (𝑠 ′ |𝑠, 0) =          𝑝 𝑍 (𝑧 ′ | 0) 𝑠 = (𝑥, 𝑒, 0), 𝑠 ′ = ( [𝑥 + 1] 𝑀 , [𝑒 + 1] 𝐵 , 𝑧 ′ ), 0 otherwise (1)
Instead, when 𝑎 = 1, the transition probability from 𝑠 to 𝑠 ′ is

𝑝 (𝑠 ′ | 𝑠, 1) =                                                        𝑝 𝑍 (𝑧 ′ | 0)𝑝 𝐶 (𝑒 + 1 -𝑒 ′ ) 𝑠 =(𝑥, 𝑒, 0), 𝑠 ′ =(1, 𝑒 ′ , 𝑧 ′ ), 0 < 𝑒 ′ < 𝐵 𝑝 𝑍 (𝑧 | 0) ∞ 𝑐=𝑒+1 𝑝 𝐶 (𝑐 ) 𝑠 = (𝑥, 𝑒, 0), 𝑠 ′ = (1, 0, 𝑧 ′ ) 𝑝 𝑍 (𝑧 | 0) 𝑒+1-𝐵 𝑐=1 𝑝 𝐶 (𝑐 ) 𝑠 = (𝑥, 𝑒, 0), 𝑠 ′ = (1, 𝐵, 𝑧 ′ ) 𝑝 𝑍 (𝑧 ′ | 1) 𝑠 = (𝑥, 𝑒 , 1)
,

𝑠 ′ = (1, [𝑒 + 1] 𝐵 , 𝑧 ′ ), 𝑒 + ℎ < 𝐵 0 otherwise (2)
The sojourn times 𝜏 (𝑠, 𝑠 ′ ) of the SMDP are associated to the transition from an origin state 𝑠 = (𝑥, 𝑒, 𝑧) to a destination 𝑠 ′ = (𝑥 ′ , 𝑒 ′ , 𝑧 ′ ). They are unitary except possibly those corresponding to the transition to a renewal state, i.e., where 𝑥 ′ = 1. For that transition, if 𝑧 = 1 the sojourn time is 𝜏 (𝑠, 𝑠 ′ ) = 1 + 𝛿, due to the round-trip delay for the edge-server offloading. If 𝑧 = 0 it is 𝜏 (𝑠, 𝑠 ′ ) = 1 when 𝜙 = 𝐶 -𝑒 -𝐻 ≤ 0. Otherwise, when 𝐶 -𝑒 -𝐻 > 0 it writes

𝜏 (𝑠, 𝑠 ′ ) = min 𝑘 | 𝑘 ∑ 𝑟 =1 𝐻 𝑟 > 𝐶 -𝑒 -𝐻 (3)
that is the number of recharges required in order to complete the computation. Note that during such sojourn time, the device cannot be interrupted until the end of processing. In the case of deterministic energy harvesting with 𝐻 ≡ 1, it holds 𝜏 (𝑠,

𝑠 ′ ) = (1 -𝑧) max{1, 𝐶 - 𝑒 -𝐻 } + 𝑧 (1 + 𝛿).
In order to simplify the analysis, let consider the equivalent MDP obtained by sampling the decision process at the time when actions are taken. Its reward under the state action pair (𝑠 𝑡 , 𝑎 𝑡 ) at time 𝑡 is proportional to the freshness of information at the end of process, as well as on the initial level of energy and the server availability:

𝑟 𝑡 +1 (𝑠 𝑡 , 𝑎 𝑡 ) = 𝑢 (𝑥 𝑡 ) -𝑑 (𝑐 𝑡 -𝑒 𝑡 -ℎ 𝑡 ) • 𝑎 𝑡 if 𝑧 𝑡 = 0 𝑢 ([𝑥 𝑡 + 𝛿] 𝑀 ) if 𝑧 𝑡 = 1 (4)
Function 𝑑 : R → R + is a penalty that depends on the amount of energy units required to complete the local processing if 𝑎 = 1 is selected. It is further assumed that 𝑑 (𝑥) = 0 when 𝑥 ≤ 0 and that 𝑑 is a bounded non-decreasing function.

Discounted Model

The processing policy 𝜋 for a tagged device is a probability distribution over the state-action space. The value function for policy 𝜋 is 𝑣 𝜋 (𝑠) := E 𝜋 [𝐺 𝑡 |𝑠 𝑡 = 𝑠] where 𝐺 𝑡 := ∞ 𝑡 =0 𝛾 𝑘 𝑟 𝑡 +1+𝑘 (𝑠 𝑡 , 𝜋 (𝑠 𝑡 )); the 𝑄-function 𝑞 𝜋 (𝑠, 𝑎) := E 𝜋 [𝐺 𝑡 |𝑠 𝑡 = 𝑠, 𝑎 𝑡 = 𝑎] is used later in Section 5.2. In the discounted model presented next, the objective is to maximize 𝑣 𝜋 (𝑠) in the set of stationary policies, where 𝜋 = 𝜋 (𝑠) is the probability that the device performs action 𝑎 = 1 in state 𝑠. As showed in Sec. 4.2, the corresponding ergodic state occupancy probability permits to calculate the sampling rate based on the average peak AoI. The optimal value function 𝑣 * (𝑠) solves the the Bellman optimality equation associated to the discounted reward problem

𝑣 * (𝑥, 𝑒, 0) = max 𝑢 (𝑥) - ∞ ∑ 𝑐=1 𝑝 𝐶 (𝑐) ∞ ∑ ℎ=1 𝑝 𝐻 (ℎ)𝑑 (𝑒 + ℎ -𝑐)+ + 𝛾 ∞ ∑ 𝑐=1 𝑝 𝐶 (𝑐) ∞ ∑ ℎ=1 𝑝 𝐻 (ℎ)E 𝑍 [𝑣 * (1, [𝑒 + ℎ -𝑐] 𝐵 , 𝑧)] , 𝑢 (𝑥) + 𝛾 ∞ ∑ ℎ=1 𝑝 𝐻 (ℎ)E 𝑍 [𝑣 * ([𝑥 + 1] 𝑀 , [𝑒 + ℎ] 𝐵 , 𝑧)]
in the case 𝑧 = 0. When 𝑧 = 1 the action set is a singleton, then

𝑣 * (𝑥, 𝑒, 1) = 𝑢 ([𝑥 + 𝛿] 𝑀 ) + ∞ ∑ ℎ=1 𝑝 𝐻 (ℎ)E 𝑍 [𝑣 * (1, [𝑒 + ℎ] 𝐵 , 𝑧)] (5)
Structural properties. The optimal policy and the corresponding value functions have several properties that are exploited in the next section. First, from (4) it is immediate that, if the harvesting process {𝐻 ′ 𝑡 } is stochastically larger than {𝐻 𝑡 }, also 𝑣 ′ (𝑠) ≥ 𝑣 (𝑠) for all 𝑠 ∈ S; similar observations hold w.r.t. process {𝐶 𝑡 }.

Before proving the next result, a few definitions are introduced. First, a policy is monotone if the action is either increasing or decreasing in the state, given an assigned partial order on the state space S and on the action space 𝐴. In particular, the following partial order is defined on the state space

(𝑥, 𝑒 + 1, 𝑧) ⪰ (𝑥, 𝑒, 𝑧 ′ ) (𝑥 -1, 𝑒, 𝑧) ⪰ (𝑥, 𝑒, 𝑧 ′ ) (6)
whereas the obvious order is imposed on the action space 𝐴 = {0, 1}. PROOF. The proof is made by verifying that the system model adheres to the following three assumptions [START_REF] Puterman | Markov Decision Processes[END_REF]. i. Non decreasing rewards. Let consider 𝑠 + = (𝑥, 𝑒, 𝑧), 𝑠 -= (𝑥 + 1, 𝑒, 𝑧) and a fixed value of 𝑐. For 𝑎 = 1, 𝑟 (𝑠 + , 1) = 𝑢 (𝑥)-𝑑 (𝑐-𝑒-ℎ) ≥ 𝑢 (𝑥 + 1) -𝑑 (𝑐 -𝑒ℎ) = 𝑟 (𝑠 -, 1), as 𝑢 is nonincreasing. For 𝑎 = 0 the same property holds since 𝑟 (𝑠 + , 0) = 𝑢 (𝑥) ≥ 𝑢 (𝑥 + 1) = 𝑟 (𝑠 -, 0). Now assume 𝑠 + = (𝑥, 𝑒 +1, 𝑧) and 𝑠 -= (𝑥, 𝑒, 𝑧). For 𝑎 = 0 the reward is equal for both states. For 𝑎 = 1, 𝑟 (𝑠 + , 1) = 𝑢 (𝑥) -𝑑 (𝑐 -𝑒 -1 -ℎ) ≥ 𝑢 (𝑥) -𝑑 (𝑐 -𝑒 -ℎ) = 𝑟 (𝑠 -, 1) since 𝑑 is by assumption nondecreasing. ii. Supermodular rewards. This property can be easily verified for both cases considered before; iii. Increasing tail transition probability. First, let consider the case 𝑠 + = (𝑥, 𝑒, 𝑧) and 𝑠 -= (𝑥 + 1, 𝑒, 𝑧). When 𝑎 = 1,

𝑤 (𝑠 ′ |𝑠 + , 1) = ∑ 𝜁 ⪰𝑠 ′ 𝑝 (𝜁 |𝑠 + , 1) = ∑ 𝜁 ⪰𝑠 ′ 𝑝 (𝜁 |𝑠 -, 1) = 𝑤 (𝑠 ′ |𝑠 -, 1)
as the final value of the AoI is always 1 after action 𝑎 = 1, while the final energy level only depends on the initial energy 𝑒. If 𝑎 = 0, then

𝑤 (𝑠 ′ |𝑠 + , 0) = 1{(𝑥 + 1, 𝑒 + ℎ, 𝑧) ≥ 𝑠 ′ } ≥ 1{(𝑥 + 2, 𝑒 + ℎ, 𝑧) ≥ 𝑠 ′ } = 𝑤 (𝑠 ′ |𝑠 -, 0).
The inequality is induced by the partial order of states. Now, consider 𝑠 + = (𝑥, 𝑒 + 1, 𝑧) and 𝑠 -= (𝑥, 𝑒, 𝑧). When 𝑎 = 1, the inequality is verified because the final energy obtained with a transition that starts in 𝑠 + is larger or equal than the one obtained when starting in 𝑠 -w.p.1. Conversely, when

𝑎 = 0, 𝑤 (𝑠 ′ | 𝑠 + , 0) = 1{(𝑥 + 1, 𝑒 +ℎ + 1, 𝑧) ⪰ 𝑠 ′ } ≥ 1{(𝑥 + 1, 𝑒 +ℎ, 𝑧) ⪰ 𝑠 ′ } = 𝑤 (𝑠 ′ | 𝑠 -, 0)
and the inequality follows from [START_REF] Kadota | Minimizing the age of information in wireless networks with stochastic arrivals[END_REF]. □

From Lemma 1 it follows easily a property of the optimal 𝑄function 𝑞 * (𝑠, 𝑎) which will prove useful in order to develop suitable learning algorithms.

COROLLARY 1. Fixed 𝑎 ∈ {0, 1}, then for 𝑠 = (𝑥, 𝑒, 𝑧) ∈ S i. 𝑞 * ((𝑥, 𝑒, 𝑧), 𝑎) ≤ 𝑞 * ((𝑥, [𝑒 + 1] 𝐵 , 𝑧), 𝑎) ii. 𝑞 * (( [𝑥 + 1] 𝑀 , 𝑒, 𝑧), 𝑎) ≤ 𝑞 * ((𝑥, 𝑒, 𝑧), 𝑎)
In all numerical tests, function 𝑄 appears indeed superadditive in S × A, a property that would be sufficient to prove the monotonicity of the optimal policy. Unfortunately, the classic assumption on the supermodularity of the tail transition probability (see Prop. 4.7.3 in [START_REF] Puterman | Markov Decision Processes[END_REF]) which grants the existence of a monotone policy can be easily disproved.

THEOREM 1 (OPTIMAL POLICY STRUCTURE).

A stationary deterministic policy 𝜋 is optimal if and only if it is monotone. In particular, there exist thresholds 𝑇 (𝑒), 0 ≤ 𝑇 (𝑒) ≤ 𝑀 such that :

i. 𝜋 (𝑒, 𝑥, 0) = 1 if and only if 𝑥 ≥ 𝑇 (𝑒); ii. 𝑇 (𝑒) ≥ 𝑇 (𝑒 + 1) + 1; iii. if 𝛾 = 0, then 𝑇 (𝑒) ≥ 𝑇 (𝑒 + 1)
PROOF. i. At first it is showed the existence of a threshold 𝑇 (𝑒) for every level of energy 𝑒. Consider the function Δ𝑞 * (𝑥, 𝑒, 𝑧) = 𝑞 * ((𝑥, 𝑒, 𝑧), 1) -𝑞 * ((𝑥, 𝑒, 𝑧), 0): it holds

Δ𝑞 * (𝑥, 𝑒, 0) =-E 𝐶 [𝑑 (𝑒 + ℎ -𝑐)] +𝛾 ∞ ∑ 𝑐=1 𝑝 𝐶 (𝑐)E 𝑍 [𝑣 * (1, [𝑒 + ℎ -𝑐] 𝐵 , 𝑧)] -E 𝑍 [𝑣 * ([𝑥 + 1] 𝑀 , [𝑒 + ℎ] 𝐵 , 𝑧)] (7)
The increment w.r.t. 𝑥 is nonnegative, due to Lemma 1:

Δ𝑞 * (𝑥 + 1, 𝑒, 0) -Δ𝑞 * (𝑥, 𝑒, 0) =-𝛾 E 𝑍 [𝑣 * ( [𝑥 + 2] 𝑀 , [𝑒 + ℎ] 𝐵 , 𝑧] - -E 𝑍 [𝑣 * ( [𝑥 + 1] 𝑀 , [𝑒 + ℎ] 𝐵 , 𝑧)] ii.
Observe that all states ([𝑇 (𝑒) + 𝑘] 𝑀 , [𝑒 + 1] 𝐵 , 𝑧) are transient for any integer 𝑘 > 1. Hence, one could replace the policy for those states with no change in the state occupancy probability. iii. Follows from the structure of the instantaneous reward. □

From Thm. 1 it follows that an optimal policy is monotone with a threshold structure.

OPTIMAL POLICY PERFORMANCE

An optimal policy 𝜋 * can be obtained using standard dynamic programming methods, under the assumption of having full information on the transition probabilities; in the following 𝑝 𝜋 * is the stationary distribution given by 𝜋 * . Efficient variants of value iteration or policy iteration algorithms for monotone policies do exist. Alternatively, the optimal solution can be found solving a suitable linear program [START_REF] Puterman | Markov Decision Processes[END_REF]. This section describes first how to evaluate the average peak AoI of the optimal policy, which renders the actual sampling rate of a device. It further introduces some properties of the discounted reward for a given distribution over the initial state for a policy 𝜋.

Average Peak AoI

Once determined an optimal policy, the corresponding average peak AoI can be computed by considering the renewal process {𝑁 (𝑡), 𝑡 ≥ 0} defined by the instants of visit to a state with AoI 𝑥 = 1 for the corresponding Markov reward process. Let 𝑌 𝑟 , 𝑟 = 1, 2, . . . be the random variable describing the length of the 𝑟 -th renewal and the corresponding renewal process [START_REF] Brémaud | Markov chains: Gibbs fields, Monte Carlo simulation, and queues[END_REF]. Denote as Δ𝑁 = E [𝑁 (𝑡 + 1)] -E [𝑁 (𝑡)] the average number of renewal events, i.e., of processing events, per time unit. From Blackwell theorem [START_REF] Ross | Stochastic processes[END_REF],

Δ𝑁 𝑡 → 1 E[𝑌 ]
. Let denote 𝐿 the number of transitions during renewal period 𝑌 : it is the mean return time to a state with 𝑥 = 1, i.e., the inverse of the stationary probability of being in a state 𝑠 where 𝜋 * (𝑠) = 1:

𝐿 = 1 𝑠:𝜋 * (𝑠 )=1 𝑝 𝜋 * (𝑠) (8)
By recalling the form of the sojourn times 𝜏 (𝑠, 𝑠 ′ ) of the SMDP, the expected value of the length of the renewal cycle 𝑌 is computed as

E [𝑌 ] = ∑ {𝑠 ′ :𝑥 ′ =1} E 𝑠∼𝑝 𝜋 * 𝜋 * (𝑠 )=1 𝜏 (𝑠, 𝑠 ′ ) 𝑝 𝜋 * (𝑠 ′ ) + 1 𝐿 -1
obtained using a partition of the possible renewal states. For notation's sake, let

𝜒 (𝑒 ′ ) := E 𝑠∼𝑝 𝜋 * : 𝜋 * (𝑠 )=1 ,𝑧 ′ 𝜏 (𝑠, (1, 𝑒 ′ , 𝑧 ′ )
) the expected sojourn time when the transition ends in a state 𝑠 ′ = (1, 𝑒, ′ , 𝑧 ′ ). Computing 𝜒 (𝑒 ′ ) accounts for the possible sample paths to renew to an energy state 𝑒 ′ . Two possible cases are to be considered. If 𝑧 = 1, then 𝑒 +ℎ = 𝑒 ′ with 𝑝 𝐻 (Δ𝑒) where Δ𝑒 = 𝑒 ′ -𝑒. Else, if 𝑧 = 0, the possibility that 𝜙 > 0 requires to account for the recharges needed to get to the final level of energy 𝑒 ′ , which depends on the distribution of both 𝐻 and 𝐶.

𝜒 (𝑒 ′ ) =𝑝 𝑍 (1) (1+𝛿 ) 𝐵 ∑ 𝑒=0 𝑝 𝐸 (𝑒 )𝑝 𝐻 (Δ𝑒 )+ (9)
+𝑝 𝑍 (0)

𝐵 ∑ 𝑒=0 𝑝 𝐸 (𝑒 ) ∞ ∑ 𝑟 =1 Γ 1,𝑟 𝑝 𝐶 (ℎ 1 -Δ𝑒 ) + ∞ ∑ 𝑘=2 𝑘 𝐵 ∑ 𝑒=0 𝑝 𝐸 (𝑒 ) ∞ ∑ 𝑟 =1 Γ 𝑘 -1,𝑟 ∞ ∑ 𝑐=𝑒+ 𝑘 -1 𝑗 =1 ℎ 𝑗 +1 𝑝 𝐶 (𝑐 )𝑝 𝐻 Δ𝑒 + 𝑐 - 𝑘 -1 ∑ 𝑗 =1 𝐻 𝑗
where 𝑝 𝐸 (𝑒) indicates the probability that action 𝑎 = 1 is done when the energy level is equal to 𝑒 (can be obtained from the stationary distribution under a given policy) and Γ 𝑘,𝑟 is the probability to harvest 𝑟 energy units in 𝑘 steps, namely Γ 𝑘,𝑟 = P 𝑘 𝑗=1 𝐻 𝑗 = 𝑟 . Note how it has been assumed that ∀𝑧 1 , 𝑧 2 P(𝑧

1 | 𝑧 2 ) = 𝑝 𝑍 (𝑧 1 | 𝑧 2 ) = 𝑝 𝑍 (𝑧 1 ).
For the sake of notation, 𝑝 𝑍 (0) = 1 -𝑝 𝑍 and 𝑝 𝑍 (1) = 𝑝 𝑍 , with 𝑝 𝑍 ∈ [0, 1]. The same will be assumed throughout the remainder of the work. Without loss of generality, let 𝑘 ≤ 𝐵: Γ 𝑘,𝑟 is defined by the following iteration

Γ 𝑘,𝑟 = 𝐵 𝑗=1 Γ 𝑘 -1,𝑟 -𝑗 𝑝 𝐻 ( 𝑗) 𝑘 ≤ 𝑟 ≤ 𝐵 0 otherwise ( 10
)
where Γ 1,𝑟 = 𝑝 𝐻 (𝑟 )1{1 ≤ 𝑟 ≤ 𝐵}. Finally, the expected value of 𝑋 is

E [𝑋 ] = 1 ∑ 𝑧 ′ =0 𝐵 ∑ 𝑒 ′ =0 𝑝 𝜋 * (1, 𝑒 ′ , 𝑧 ′ ) 𝐵 𝑗=0 𝑝 𝜋 * (1, 𝑗, 𝑧 ′ ) 𝜒 (𝑒 ′ ) + 1 𝐿 -1
In Section 7 numerical results will explore extensively how the model parameters influence the peak AoI.

Reward of a policy

The learning procedure for the multi-device model presented later in Sec.6 pivots on the dependence of the discounted reward 𝑅 𝛾,𝜋 of a tagged policy 𝜋 on the server polling probability 𝑝 𝑍 . The performance measure for a policy used by a device is the discounted reward given a certain initial state distribution. In particular, sample paths initiate on renewal states with AoI 𝑥 = 1, energy 𝑒 chosen uniformly at random and expected server availability 𝑝 𝑍 . Fixed 𝜋, let 𝑃 𝜋 be the transition matrix of the corresponding Markov Chain and let vector 𝑟 𝜋 be the instantaneous reward attained at each state by following the action indicated by the policy. Let further define vector 𝑑 0 describing the initial distribution of states. The discounted reward of a device can be computed as

𝑅 𝛾,𝜋 = 𝑑 0 𝐼 + 𝛾𝑃 𝜋 + 𝛾 2 𝑃 2 𝜋 + . . . 𝑟 𝜋 (11)
Basic facts of MDP theory imply that the geometric series generated by 𝛾𝑃 𝜋 is always converging so that

𝑅 𝛾,𝜋 = 𝑑 0 (𝐼 -𝛾𝑃 𝜋 ) -1 𝑟 𝜋 (12)
To analyze this quantity it is useful to explicitly express the parametric dependence 𝑑 0 = 𝑑 0 (𝑝 𝑍 ) and 𝑃 𝜋 = 𝑃 𝜋 (𝑝 𝑍 ). In particular,

𝑑 0 (𝑝 𝑍 ) =          1 𝐵+1 𝑝 𝑍 𝑥 = 1, 𝑧 = 0 1 𝐵+1 (1 -𝑝 𝑍 ) 𝑥 = 1, 𝑧 = 1 0 otherwise
The bijective function 𝑓 : {1, . . . , 𝑀 }×{0, . . . , 𝐵} → {1, . . . , 𝑀 (𝐵+ 1)} maps each couple (𝑥, 𝑒) to an integer value and two matrixes 𝑃 0 , 𝑃 1 ∈ M (𝐵+1)𝑀 × (𝐵+1)𝑀 such that

𝑃 0 𝑖 𝑗 = P 𝑓 (𝑥 ′ , 𝑒 ′ ) = 𝑗 | 𝑓 (𝑥, 𝑒) = 𝑖, 𝑧 = 0, 𝑎 = 𝜋 (𝑥, 𝑒, 0)
and

𝑃 1 𝑖 𝑗 = P 𝑓 (𝑥 ′ , 𝑒 ′ ) = 𝑗 | 𝑓 (𝑥, 𝑒) = 𝑖, 𝑧 = 1, 𝑎 = 1
Both matrix will depend on the distribution of the random variables 𝐶 and 𝐻 , as well as on the fixed policy 𝜋. The explicit dependence of the transition matrix 𝑃 𝜋 on the server's polling probability writes

𝑃 𝜋 (𝑝 𝑍 ) = (1 -𝑝 𝑍 )𝑃 0 𝑝 𝑍 𝑃 0 (1 -𝑝 𝑍 )𝑃 1 𝑝 𝑍 𝑃 1
which provides an explicit form to

𝑅 𝛾,𝜋 (𝑝 𝑍 ) = 𝑑 0 (𝑝 𝑍 ) 𝐼 -𝛾𝑃 𝜋 (𝑝 𝑍 ) -1

𝑟 𝜋

Remark. For 𝛿 > 0 the function 𝑅 𝛾,𝜋 (𝑝 𝑍 ) appears concave on the interval [0, 1] for all tested stationary policies and parameters of the Markov decision process. The proof of the convergence of the algorithm introduced in Section 6 assumes this fact to be true. A formal proof is provided for a specific choice of parameters (𝑀 = 2, 𝐵 = 1) and a particular policy in Section C. Additionally, 𝑅 𝛾,𝜋 (𝑝 𝑍 ) is indeed continuous and differentiable since each term of the matrix appearing in its explicit form has such property, as showed in C.

Finally, evaluating the optimal reward as a function of 𝑝 𝑍 requires to consider different optimal policies and to determine

𝑅 𝛾 (𝑝 𝑍 ) = max 𝜋 𝑅 𝛾,𝜋 (𝑝 𝑍 ) ( 13
)
As it is a point-wise maximum, the continuity of 𝑅 𝛾 (•) is true. However, even if the conjecture about the concavity of 𝑅 𝛾,𝜋 is verified, 𝑅 𝛾 (𝑝 𝑍 ) is not necessarily concave as it is the maximum of a set of concave functions.

LEARNING THE OPTIMAL POLICY

In a realistic setting, transition probabilities ( 1) and ( 2) may not be available. Furthermore, rewards (4) depend on the model used for the data-batch computation and also on data properties which may be only learned at runtime. A new model-free algorithm, namely [START_REF] John | Learning from Delayed Rewards[END_REF] adapted for MDPs with monotone value functions under a given partial order imposed on the state space. As showed in Section 7, OQL outperforms other reinforcement learning algorithms such as policy gradient methods and yet retains the convergence guarantees of QL. Two variants of OQL based on the structure of the optimal policy are introduced next; they leverage two different partial orders on the states to find the optimal policy.

Ordered Q-learning (OQL) is introduced next. It is a version of Q- learning (QL)

Ordered Q-learning

In the OQL the vector of the estimates of the 𝑄-function are forced to comply to the monotonicity properties of the optimal 𝑄-function.

The update rule [START_REF] Chen | Efficient multi-user computation offloading for mobile-edge cloud computing[END_REF] for each state-action pair (𝑠, 𝑎) ∈ S × 𝐴 hence writes

         𝑄 𝑡 +1 (𝑠, 𝑎) = (1 -𝛼 𝑡 )𝑄 𝑡 (𝑠, 𝑎) + 𝛼 𝑡 𝑟 𝑡 +1 (𝑠, 𝑎) + 𝛾 max 𝑏 𝑄 𝑡 (𝑠 ′ , 𝑏) 𝑄 𝑡 +1 (𝑠 ′ , 𝑎) = Π 𝑠 𝑄 𝑡 +1 (𝑠 ′ , 𝑎) ∀𝑠 ′ ∈ S (14)
where projection Π 𝑠 (•) at state 𝑠 is a projection adapted to specific partial order imposed on the state space. Let 𝑓 :

S → R: if 𝑠 ′ > 𝑠, then Π 𝑠 (𝑓 (𝑠 ′ )) = max{𝑓 (𝑠 ′ ), 𝑓 (𝑠)} and if 𝑠 ′ ≤ 𝑠, then Π 𝑠 (𝑓 (𝑠 ′ )) = min{𝑓 (𝑠 ′ ), 𝑓 (𝑠)}.
Thus, the basic Q-learning iteration is followed by a state-dependent projection on the set of allowed estimates. Alg. 1 reports on the complete algorithm for the version of the algorithm with a constant stepsize 𝛼 𝑡 = 𝛼. The convergence of the OQL can be ensured under the assumption that 𝛼 𝑡 = 𝛼 𝑡 (𝑠, 𝑎) appearing in ( 14 end for 12: end for THEOREM 2. Consider the Ordered Q-learning algorithm described by the update rule in [START_REF] Chen | Efficient multi-user computation offloading for mobile-edge cloud computing[END_REF]. Let 𝛾 < 1. Let 𝑞 * be monotone, i.e., if 𝑠 1 ≤ 𝑠 2 according to some order on the states, then 𝑞 * (𝑠 1 , 𝑎) ≤ 𝑞 * (𝑠 2 , 𝑎). Then 𝑄 𝑡 (𝑠, 𝑎) converges to 𝑞 * (𝑠, 𝑎) w.p.1. for every state 𝑠 ∈ S and for every action 𝑎 ∈ A (𝑠).

PROOF. A sketch of the proof of Theorem 5 is based on the Policy Improvement theorem's [START_REF] Sutton | Reinforcement learning: An introduction[END_REF]. Let consider a generic step of the OQL algorithm. Let 𝜋 be the current policy and 𝜋 ′ be the policy obtained at the iteration of OQL. Let assume that 𝜋 ′ improves the current policy, i.e., 𝑞 𝜋 (𝑠, 𝜋 ′ (𝑠)) ≥ 𝑣 𝜋 (𝑠) for all 𝑠 ∈ S. As showed in [START_REF] Sutton | Reinforcement learning: An introduction[END_REF], this implies that 𝑣 ′ 𝜋 (𝑠) ≥ 𝑣 𝜋 (𝑠) ∀𝑠 ∈ S. Now let consider any state 𝑠 + ⪰ 𝑠. After applying the projection, it holds 𝑞 𝜋 (𝑠 + , 𝜋 ′ (𝑠)) ≥ 𝑞 𝜋 (𝑠, 𝜋 ′ (𝑠)). Finally, since both 𝜋 ′ (𝑠) and 𝜋 ′ (𝑠 + ) ∈ A (𝑠 + ), it is possible to write

𝑣 𝜋 ′ (𝑠 + ) = 𝑞 𝜋 ′ (𝑠 + , 𝜋 ′ (𝑠 + )) = max{𝑞 𝜋 ′ (𝑠 + , 𝜋 ′ (𝑠)), 𝑞 𝜋 ′ (𝑠 + , 𝜋 (𝑠 + ))} ≥ 𝑞 𝜋 ′ (𝑠 + , 𝜋 ′ (𝑠)) ≥ 𝑞 𝜋 ′ (𝑠, 𝜋 ′ (𝑠)) = 𝑣 𝜋 ′ (𝑠)
which concludes the proof. □

The above proof sketch is based on the simplifying assumption that the true values of the 𝑄-function are available at each iteration; this assumption permits to use dynamic programming arguments. The complete proof of Theorem 5 is rooted in the original argument of convergence for Q-learning, developed by Tsitsiklis in [START_REF] Tsitsiklis | Asynchronous stochastic approximation and q-learning[END_REF], which is based on stochastic approximations. It is presented in Section D. For OQL, the technical difficulty is to account for the use of statedependent projection Π 𝑠 .

It is further possible to define the 𝑛-step version of OQL, where the first equation in [START_REF] Chen | Efficient multi-user computation offloading for mobile-edge cloud computing[END_REF] is replaced by the one of 𝑛-step QL [START_REF] Sutton | Reinforcement learning: An introduction[END_REF].

Stairway Q-Learning

Stairway Q-learning (SQL) is defined imposing on the state space the natural partial order considered in Cor. 1 so that the assumptions of Thm. 5 automatically hold for the system at hand. For every pair of states 𝑠 1 = (𝑥 1 , 𝑒 1 , 𝑧) and 𝑠 2 = (𝑥 2 , 𝑒 2 , 𝑧) and for every vector 𝑣 ∈ R | S | , the explicit form of the projection operator on the set of vectors that suit the partial order considered is

Π 𝑠 1 (𝑣 (𝑠 2 )) =                        max (𝑣 (𝑠 1 ), 𝑣 (𝑠 2 )) if 𝑥 1 < 𝑥 2 and 𝑒 1 ≥ 𝑒 2 or 𝑥 1 ≤ 𝑥 2 and 𝑒 1 > 𝑒 2 𝑣 (𝑠 1 ) if 𝑥 1 = 𝑥 2 and 𝑒 1 = 𝑒 2 min (𝑣 (𝑠 1 ), 𝑣 (𝑠 2 )) if 𝑥 1 > 𝑥 2 and 𝑒 1 ≤ 𝑒 2 or 𝑥 1 ≥ 𝑥 2 and 𝑒 1 < 𝑒 2 𝑣 (𝑠 2 ) otherwise
In Section 7 it will be showed that the performance of SQL improves significantly compared to the standard QL, both in the 1-step version here introduced and in the 𝑛-step version.

Threshold Q-learning

Threshold Q-learning (TQL) considers a simplified partial order of the type (𝑥, 𝑒, 𝑧) ⪰ (𝑥 + 1, 𝑒, 𝑧 ′ ) for 𝑥 = 1, . . . , 𝑀 -1: it imposes the partial order only w.r.t. energy. The monotonicity condition writes

𝑞 * ((𝑥, 𝑒, 𝑧), 𝑎) ≤ 𝑞 * (([𝑥 + 1] 𝑀 , 𝑒, 𝑧), 𝑎) ∀𝑥, 𝑒, 𝑧, 𝑎 (15)
The convergence follows from Theorem 5. The projection function w.r.t. a certain state 𝑠, Π 𝑠 : R → R, can be written as

Π 𝑠 1 (𝑣 (𝑠 2 )) =              max (𝑣 (𝑠 1 ), 𝑣 (𝑠 2 )) if 𝑥 1 < 𝑥 2 𝑣 (𝑠 1 ) if 𝑥 1 = 𝑥 2 min (𝑣 (𝑠 1 ), 𝑣 (𝑠 2 )) if 𝑥 1 > 𝑥 2 𝑣 (𝑠 2 ) otherwise (16)
for every pair of states 𝑠 1 = (𝑥 1 , 𝑒, 𝑧) and 𝑠 2 = (𝑥 2 , 𝑒, 𝑧). Note that in this case only states with same energy and server availability are compared: this significantly reduces the number of projection operations compared to SQL, especially when 𝐵 is large. Despite its reduced complexity, in many cases this algorithm has showed similar convergence speed as SQL. Note how for both SQL and TQL it is not possible to guarantee the corresponding policy to have the threshold structure at each timestep. However, the numerical results show that policy displays the threshold structure after a rather small number of iterations.

Reinforce

One of the baselines algorithms used for comparison is Reinforce (RF) [START_REF] Sutton | Policy gradient methods for reinforcement learning with function approximation[END_REF]. RF performs a basic policy-gradient iteration in the form

𝜃 t+1 = 𝜃 𝑡 + 𝛼 𝑡 𝐺 𝑡 ∇ 𝜃 𝜋 (𝑎 𝑡 |𝑠 𝑡 , 𝜃 t ) 𝜋 (𝑎 𝑡 |𝑠 𝑡 , 𝜃 t ) (17)
where 0 < 𝛼 𝑡 < 1 is a stepsize and 𝐺 𝑡 is the policy reward estimation.

The gradient is operated on the following policy parametrization based on the threshold structure of the optimal policy

𝜋 (𝑥, 𝑒, 𝑧) =          0 𝑥 < ⌊𝜃 𝑒 ⌋ 1 1+exp{𝑘 (𝜃 𝑒 -𝑥 -0.5) } 𝑥 = ⌊𝜃 𝑒 ⌋ 1 𝑥 > ⌈𝜃 𝑒 ⌉ (18)
where 𝑘 > 0 is a suitable hyperparameter.

MULTI-DEVICE MODEL

The model is now extended to the case of 𝑁 devices connected to the edge server. server polls device 𝑘 with probability 𝑝 𝑍,𝑘 , where 𝑝 𝑍 ∈ 𝑃 𝑍 = {𝑝 𝑍 ∈ [0, 1] 𝑁 : 𝑁 𝑘=0 𝑝 𝑍,𝑘 = 1} and 𝑘 = 0 denotes the null device, i.e., no polling. All the devices are assumed to be independent of each other: by doing so, the optimal policy of each device is not influenced by the state of the other devices at a given timestep; the interesting case of correlated harvesting or data samples is left as part of future works. Moreover, the polling decision of the server is feedforward, i.e., the state of a device is only known once the device is polled, so that the polling action is independent of the state of devices.

The server seeks the optimal random polling probability 𝑝 𝑍,𝑘 that maximizes the sum of the rewards of the devices, i. 𝑝 𝑍,𝑘 ≥ 0 𝑘 = 0, . . . , 𝑁 In order to solve problem (MD), since the discounted reward (13) cannot be computed (unless all the transition probabilities are known), stochastic approximation might be used to find a solution. Furthermore, as already observed in Section 4.2, 𝑅 𝛾 (•) cannot be assumed differentiable or concave, ruling out stochastic approximation methods requiring differentiable objective functions, such as SPSA [START_REF] Fu | Optimization of discrete event systems via simultaneous perturbation stochastic approximation[END_REF]. Other direct methods with less strict requirements, such as Enhanced Localized Random Search do exist [START_REF] Spall | Introduction to stochastic search and optimization: estimation, simulation, and control[END_REF]. The proposed algorithm, namely the Alternating Polling and Policy Improvement (APPI) algorithm, is summarized in Alg. 2. It alternates two steps: 1) a policy learning step (line 4) for a given polling probability vector 𝑝 𝑍 , and 2) a polling optimization step (line 5) optimizing 𝑝 𝑍 for a given policy using stochastic approximation methods. For the policy learning step it is sufficient to use one of the learning methods proposed in Sec. 5, e.g., Stairway Q-learning for the efficiency's sake. Conversely, as observed before, if the policy for each device is fixed, the objective function is 𝑘 𝑅 𝛾 𝑘 ,𝜋 𝑘 (𝑝 𝑍,𝑘 ) with 𝜋 𝑘 = 𝜋 * 𝑘 (𝑝 𝑍,𝑘,𝑜𝑙𝑑 ), i.e., the optimal policy according to the previous value of the polling probability vector. As showed in Section 7.3, this algorithm is both faster and more accurate than general methods for the problem studied. In order to discuss the polling optimization step, recall that the objective function is concave in 𝑝 𝑍 (and so a.e. continuously differentiable) suggesting the use of stochastic gradient ascent methods of the Kiefer-Wolfowitz family [START_REF] Kushner | Stochastic Approximation Methods for Constrained and Unconstrained Systems[END_REF]. The iteration scheme is

𝑝 𝑛+1 𝑍 = Π Θ 𝑝 𝑛 𝑍 -𝛼 𝑛 ĝ𝑛 (20)
where 𝑝 𝑛 𝑍 is the 𝑛th iterate of the parameter, ĝ𝑛 represents an estimate of the gradient of the objective function, {𝛼 𝑛 } 𝑛 is a sequence converging to 0 and Π Θ is a projection on the 𝑁 + 1-dimensional simplex Θ = {𝑝 𝑍 ≥ 0| 𝑝 𝑍,𝑘 = 1}, i.e., the space of possible polling probability vectors, including the null action when polling is not active. The projection activates when 𝑝 𝑍 ± 𝑐 𝑛 Δ 𝑛 lies outside the constraint set and reverts to the nearest point in Θ.

The specific technique to determine ĝ𝑛 in ( 20) is based on simultaneous random increments (SPSA) [START_REF] Fu | Optimization of discrete event systems via simultaneous perturbation stochastic approximation[END_REF]. This technique estimates two increments, one in the positive and one in the negative direction. Due to the independence between different devices, each component of the gradient depends only on the parameter 𝑝 𝑍,𝑘 of the device considered. Let R𝛾 𝑘 ,𝜋 𝑘 denote the approximated reward for device 𝑘. The corresponding component of the gradient estimate writes

( ĝ𝑛 ) 𝑘 = R𝛾 𝑘 ,𝜋 𝑘 𝑝 𝑍,𝑘 + 𝑐 𝑛 (Δ 𝑛 ) 𝑘 -R𝛾 𝑘 ,𝜋 𝑘 𝑝 𝑍,𝑘 -𝑐 𝑛 (Δ 𝑛 ) 𝑘 2𝑐 𝑛 (Δ 𝑛 ) 𝑘 (21)
where {𝑐 𝑛 } is a sequence converging to 0 and {Δ 𝑛 } is an i.i.d. vector sequence of perturbations of i.i.d. components {(Δ 𝑛 ) 𝑖 , 𝑖 = 1, . . . , 𝑁 } with zero mean and where E |(Δ 𝑛 ) -2 𝑖 | is uniformly bounded. The following proposition estabilishes the conditions on the objective function, on the step-size sequence {𝛼 𝑛 } and on the gradient estimates ĝ𝑛 for which the SPSA iteration converges to the global maximum of the corresponding total discounted reward when a policy is fixed for each device. PROPOSITION 1. Let {𝛼 𝑛 } and {𝑐 𝑛 } be such that 𝑛 𝛼 𝑛 = ∞, 𝑛 𝛼 𝑛 𝑐 𝑛 2 < ∞. Moreover, assume that E |(Δ 𝑛 ) 𝑖 | -2 is uniformly bounded on 𝑃 𝑍 and that 𝑅 𝛾 𝑘 ,𝜋 𝑘 (𝑝 𝑍,𝑘 ) is concave. Then the iteration (20) converges to the optimal parameter 𝑝 * 𝑍 w.p.1. PROOF. The desired result is obtained by verifying the assumptions of Proposition 1 in [START_REF] Ecuyer | Stochastic optimization by simulation: Convergence proofs for the GI/G/1 queue in steady-state[END_REF], whose proof is a consequence of Theorem 5.3.1 in [START_REF] Kushner | Stochastic Approximation Methods for Constrained and Unconstrained Systems[END_REF]. i. the objective function is differentiable and either concave or unimodal: its differentiability is proved in Section C, while the other condition is assumed to be verified; ii. 𝑏 𝑛 = E [ ĝ𝑛 |𝑝 𝑍 , 𝑠 𝑛 ] -∇𝐽 (𝑝 𝑍 ) → 0 w.p.1: it holds from Lemma 2 in [START_REF] Fu | Optimization of discrete event systems via simultaneous perturbation stochastic approximation[END_REF] [START_REF] Fu | Optimization of discrete event systems via simultaneous perturbation stochastic approximation[END_REF] and by the fact that 𝑅((𝑝 𝑍 ) 𝑘 , 𝜔), representing the reward of sample path 𝜔 has second moment uniformly bounded in 𝑝 𝑍 : we can notice that it is independent of 𝑝 𝑍 . Indeed, given a path, since 𝑥 ≤ 𝑀 and 𝑝 𝑍 ∈ [0, 1], the reward is upper bounded by a constant, therefore its second moment is uniformly bounded, which concludes the proof. □ Hence, fixed the policy for each device, the corresponding optimal polling probability vector is attained. Thanks to the convergence properties of the learning methods (see Section 5) for a fixed vector 𝑝 𝑍 , and since the number of policies is finite, this proves that APPI converges w.p. Unfortunately, this does not imply the convergence to the globally optimal polling probability vector, as the function to optimize is not concave, but rather just the pointwise maximum of a set of concave functions. Due to its particular structure, only convergence to the local optimum of the objective function can be ensured.

NUMERICAL RESULTS

The numerical experiments are divided into 3 parts. The first one describes the performance of the single device-server system tested on a range of system parameters. The second one compares the Ordered Q-learning methods introduced in Sec. 5 with baseline RL algorithms. Finally, the performance of the APPI algorithm introduced in Sec. 6 is assessed against alternative general methods. The devices and server parameters, namely 𝑀, 𝐵, 𝛾, 𝛿, 𝑝 𝑍 , 𝑟 (•), 𝑑 (•), 𝑝 𝐻 and 𝑝 𝐶 , constitute the environment. For the data processing cost 𝐶 three possible probability distributions will be considered: the uniform one in {1, . . . , 𝐵 + 1}, the binary one where 𝑝 𝐶 (1) = 𝑝 𝐶 (𝐵 + 1) = 1/2 and finally the symmetric one obtained as 𝑝 𝐶 (𝑐) = 𝐴•exp{-1 2 ((𝑐-𝜇)/𝜎) 2 } for 𝑐 ∈ {1, . . . , 𝐵 + 1}: 𝜇 and 𝜎 shape the distribution, whereas 𝐴 is an appropriate normalization constant. In Table 2 the first column represents the environment used in Subsec. 7.1. The second column reports the sets from which the system parameters are drawn uniformly at random in the experiments of Subsec. 7.2 and Subsec. 7.3.

Device-server performance evaluation

Fig. 3a describes the impact of the server availability 𝑝 𝑍 onto the average (peak) AoI in a single device system. Excluding the case 𝜇 = 1, i.e., for lower values of the average batch processing cost, the average AoI is maximal for 𝑝 𝑍 = 0 and attains its minimum close to 𝑝 𝑍 = 1 (the optimal 𝑝 𝑍 is highlighted with dots in Fig. 3a). In fact, for higher processing cost, a larger server polling probability permits to select action 𝑎 = 1 more often, as the possible battery discharge due to data processing is compensated by frequent task offloading events. For lower cost figures, instead, it is the roundtrip delay 𝛿 that renders the offloading less convenient: when 𝛿 = 0, actually, the corresponding curve (not reported for the space's sake) becomes strictly decreasing. the optimal value of 𝑝 𝑍 decreases as 𝛿 increases, irrespective of the distribution of the processing cost. Fig. 3b shows that offloading can be detrimental for larger values of 𝛿: indeed, for lower batch processing costs (𝜇 = 1 and 𝜇 = 3) the value that minimizes the average peak AoI is 𝑝 𝑍 = 0. In these cases the risk of emptying the battery is sufficiently low to choose action 𝑎 = 1 very frequently. In turn, the presence of the server, and the additional delay required by task offloading, becomes a penalty. Finally, Fig. 3c depicts the average AoI for increasing average harvesting rates, i.e., for increasing values of 𝜆 (note that here 𝜆 = 0 indicates the deterministic case 𝐻 ≡ 1). Irrespective of the processing cost distribution 𝑝 𝐶 , the average peak AoI is monotone decreasing, as expected and approaches 1 + 𝛿 𝑝 𝑍 for large recharging rates.

Learning the optimal policy

The RL algorithms introduced in Section 5 are compared with two baselines, namely QL and RF. Each test is repeated over 50 different environments where the system's parameters are drawn uniformly at random, as reported in Table 2. Each experiment consists in a sequence of 3000 episodes. At the end of each episode, the discounted reward is calculated using a policy evaluation step. The evaluation is truncated when the weight discount falls below 0.001. The estimation of the optimal reward ( 12) is collected starting from a state 𝑠 0 = (1, 𝑒, 𝑧), with 𝑒 and 𝑧 drawn uniformly at random. In order to compare results of different runs, the rewards have been normalized against the baseline stationary policy which chooses action 𝑎 = 1 if the state is such that either 𝑧 = 1 or 𝑠 = (𝑀, 𝐵, 0).

Finally, for each tested algorithm several sets of hyperparameters have been probed to determine the configuration ensuring the highest discounted reward; in fact, such parameters are observed to influence heavily the performance of the different algorithms. For the Q-learning type of algorithms (QL, TQL and SQL), these consist of 𝑛, determining the adopted 𝑛-steps variant, and 𝜙 and 𝛽, which determine the learning rate 𝛼 𝑡 (𝑠 𝑡 ) = 𝜙 • (#visits in state 𝑠 𝑡 ) -𝛽 . For Reinforce the hyperparameter are 𝑘, appearing in [START_REF] Song | Age based task scheduling and computation offloading in mobile-edge computing systems[END_REF], as well as 𝑛 and 𝑚 defining stepsize 𝛼 𝑡 = 𝑛/(𝑡 + 1) 𝑚 .

The results of the experiments are summarized in policy. In order to avoid this, in policy gradient RL it is possible to introduce multiple simultaneous state-action perturbations, e.g., trust-region techniques [START_REF] Schulman | Trust region policy optimization[END_REF], at the price of increased complexity. Finally, SQL outperforms the other methods attaining a gain of 10%.

Multi-device system

The two last experiments evaluate the performance of the APPI learning procedure introduced in Sec. 6. To this aim, three alternative algorithms to be compared to APPI have been implemented. They replace the polling probability improvement step with Naive Random Search (NRS), Enhanced Random Search (ENRS) and SPSA, respectively. Details on those procedures are found in [START_REF] Spall | Introduction to stochastic search and optimization: estimation, simulation, and control[END_REF].

The first test covers a scenario with 𝑁 = 3 devices. For each run of the experiment, a set of parameters is generated at random for each device (i.e., 𝑀, 𝐵, 𝛾, 𝑝 𝑍 , 𝛿 𝑟 (•), 𝑑 (•), 𝑝 𝐶 and 𝑝 𝐻 ) and an initial polling probability distribution is imposed on the edge server. The device parameters are drawn uniformly at random from the sets described in Table 2, second column. For each algorithm it is recorded 1) the total discounted reward and 2) number of policy learning iterations performed. The results are averaged over 50 runs, by considering each time different initial polling distributions and different environments. Also, all the reward values are normalized to fall into an interval [𝑅 min , 𝑅 max ]. 𝑅 max is the reward obtained by an ideal APPI implementation which finds the optimal policy using value iteration, while 𝑅 min is the reward obtained averaging 10 runs under a random polling probability and the corresponding device's optimal policies. The numerical results are collected in steps as well. The last experiment tests the scalability of APPI by increasing the number of devices 𝑁 . The outcomes are reported in Table 5. Those are the average of 50 simulations per value of 𝑁 . As before, in each simulation the environment is drawn at random using the distributions indicated in Table 2. The normalized reward attained by APPI appears marginally affected by the number of devices, whereas the number of policy improvement steps is in the order of a few units and increases linearly.

CONCLUSIONS

This work has provided a theoretical framework to model edge devices running AI applications whose energy footprint depends on the data being processed. It factors in energy harvesting and edge-server task offloading. The optimal processing policy on edge devices is hence derived and its key structural features are proved. This is the basis for a model-based, specialized reinforcement learning method, namely Ordered Q-learning. The learning procedure is hence applied to the multidevice setting where the server's offloading rate vector is optimized by alternating stochastic gradient ascent and policy learning. Numerical tests performed against the ground-truth, i.e., an actual optimal policy, show that existing baselines are systematically outperformed both in accuracy and convergence speed. This confirms that by rooting RL techniques into the structural properties of the optimal solution, important performance margins against generic RL solutions are attained. Several extension of the proposed models are indeed possible in the multi-device setting. In particular, one could include capacity constraints. This in turn requires to study optimal randomized stationary policies for constrained MDPs. Also, to improve the learning procedure of the polling probability, one could use the history on the device state retrieved at polling instants.

∑ 𝑟 =𝑘 -1 Γ 𝑘 -1,𝑟 ∞ ∑ 𝑡 =𝑒+𝑟 +1 𝑝 𝐶 (𝑐)𝑝 𝐻 (𝑒 ′ + 𝑐 -𝑟 -𝑒) 𝑠 = (𝑥, 𝑒, 0), 𝑠 ′ = (1, 𝑒 ′ , 𝑧 ′ ), 0 ≤ 𝑒 ′ < 𝐵 𝑝 𝑍 (𝑧 | 0) ∞ 𝑐=1 𝑝 𝐶 (𝑐) ∞ ℎ=𝐵-𝑒+𝑐 𝑝 𝐻 (ℎ) 𝑠 = (𝑥, 𝑒, 0), 𝑠 ′ = (1, 𝐵, 𝑧 ′ ) 𝑝 𝑍 (𝑧 ′ | 1)𝑝 𝐻 (ℎ) 𝑠 = (𝑥, 𝑒 , 1)
,

𝑠 ′ = (1, 𝑒 + ℎ, 𝑧 ′ ), 𝑒 ′ < 𝐵 𝑝 𝑍 (𝑧 ′ | 1) ∞ ℎ=𝐵-𝑒 𝑝 𝐻 (ℎ) 𝑠 = (𝑥, 𝑒 , 1)
,

𝑠 ′ = (1, 𝐵, 𝑧 ′ ) 0 otherwise (23)
where Γ 𝑘,𝑟 has been defined in [START_REF] Yang | Optimal online sensing scheduling for energy harvesting sensors with infinite and finite batteries[END_REF]. For what concerns the instantaneous reward, it depends on the difference a 𝐻 𝑡 -𝐶 𝑡 , that is

𝑟 𝑡 +1 (𝑠 𝑡 , 𝑎 𝑡 ) =          𝑢 (𝑥 𝑡 ) - +∞ ∑ ℎ 𝑡 =1 +∞ ∑ 𝑐 𝑡 =1 𝑑 (𝑒 𝑡 + ℎ 𝑡 -𝑐 𝑡 ) • 𝑎 𝑡 if 𝑧 𝑡 = 0 𝑢 ([𝑥 𝑡 + 𝛿] 𝑀 ) if 𝑧 𝑡 = 1 (24)

B DERIVATION OF THE AVERAGE SOJOURN TIME

This section shows how to derive the expression (9) for 𝜒 (𝑒 ′ ), i.e., the expected sojourn time when the transition leads to a state 𝑠 ′ = (1, 𝑒, ′ , 𝑧 ′ ).

In particular from the law of total probability it follows

𝜒 (𝑒 ′ ) = (1 + 𝛿)𝑝 𝑍 (1)P 𝑒 + ℎ 1 = 𝑒 ′ + 𝑝 𝑍 (0) P 𝑒 + ℎ 1 -𝑐 = 𝑒 ′ + 2P(𝑒 + ℎ 1 -𝑐 < 0) P 𝑒 + ℎ 1 + ℎ 2 -𝑐 = 𝑒 ′ + . . . = (1 + 𝛿)𝑝 𝑍 (1)P 𝑒 + ℎ 1 = 𝑒 ′ + 𝑝 𝑍 (0) P 𝑒 + ℎ -𝑐 = 𝑒 ′ + ∞ ∑ 𝑘=2 𝑘P 𝑒 + 𝑘 -1 ∑ 𝑗=2 ℎ 𝑗 -𝑐 < 0 P ℎ 𝑘 = 𝑒 ′ + 𝑐 - 𝑘 -1 ∑ 𝑗=2 ℎ 𝑗 -𝑒 = (1 + 𝛿)𝑝 𝑍 (1) 𝐵 ∑ 𝑒=0 𝑝 𝐸 (𝑒)𝑝 𝐻 (𝑒 ′ -𝑒) + 𝑝 𝑍 (0) 𝐵 ∑ 𝑒=0 𝑝 𝐸 (𝑒) ∞ ∑ ℎ 1 =1 𝑝 𝐻 (ℎ 1 )𝑝 𝐶 (𝑒 + ℎ 1 -𝑒 ′ )+ + ∞ ∑ 𝑘=2 𝑘 𝐵 ∑ 𝑒=0 𝑝 𝐸 (𝑒) ∞ ∑ ℎ 1 =1 𝑝 𝐻 (ℎ 1 ) • • • • • ∞ ∑ ℎ 𝑘 -1 =0 𝑝 𝐻 (ℎ 𝑘 ) ∞ ∑ 𝑐=𝑒+ 𝑘 -1 𝑗 =1 ℎ 𝑗 +1 𝑝 𝐶 (𝑐)𝑝 𝐻 (𝑒 ′ + 𝑐 - 𝑘 -1 ∑ 𝑗=1 ℎ 𝑗 -𝑒) = (1 + 𝛿)𝑝 𝑍 (1) 𝐵 ∑ 𝑒=0 𝑝 𝐸 (𝑒)𝑝 𝐻 (𝑒 ′ -𝑒) + 𝑝 𝑍 (0) 𝐵 ∑ 𝑒=0 𝑝 𝐸 (𝑒) ∞ ∑ 𝑟 =1 Γ 1,𝑟 𝑝 𝐶 (𝑒 + ℎ 1 -𝑒 ′ )+ + ∞ ∑ 𝑘=2 𝑘 𝐵 ∑ 𝑒=0 𝑝 𝐸 (𝑒) ∞ ∑ 𝑟 =1 Γ 𝑘 -1,𝑟 ∞ ∑ 𝑐=𝑒+ 𝑘 -1 𝑗 =1 ℎ 𝑗 +1 𝑝 𝐶 (𝑐)𝑝 𝐻 (𝑒 ′ + 𝑐 - 𝑘 -1 ∑ 𝑗=1 ℎ 𝑗 -𝑒)
As seen in [START_REF] Stamatakis | Control of status updates for energy harvesting devices that monitor processes with alarms[END_REF], in order to compute the discounted reward it has to be defined the inverse of the matrix 𝐼 -𝛾𝑃 𝜋 , which will not be reported here, but can be computed by standard means. The product between the initial distribution 𝑑 0 (𝑝 𝑍 ) and the latter matrix gives

𝑑 0 (𝑝 𝑍 ) 𝐼 -𝛾𝑃 𝜋 -1 = 1-𝑝 𝑍 2 0 1-𝑝 𝑍 2 0 𝑝 𝑍 2 0 𝑝 𝑍 2 0 𝐼 -𝛾𝑃 𝜋 -1 (30) = 1 4𝛾 2 -4𝛾 2 𝑝 𝑍 + 4𝛾𝑝 𝑍 -4 -𝛾 2 + 3𝛾 2 𝑝 3 𝑍 -7𝛾 2 𝑝 2 𝑍 -2𝛾𝑝 2 𝑍 + 5𝛾 2 𝑝 𝑍 + 2𝛾𝑝 𝑍 + 2𝑝 𝑍 -2 0 𝛾 2 -3𝛾 2 𝑝 3 𝑍 + 7𝛾 2 𝑝 2 𝑍 + 2𝛾𝑝 2 𝑍 -5𝛾 2 𝑝 𝑍 -2𝛾𝑝 𝑍 + 2𝑝 𝑍 -2 4(-𝛾 -𝛾𝑝 2 𝑍 + 2𝛾𝑝 𝑍 -3𝛾 2 𝑝 3 𝑍 + 4𝛾 2 𝑝 2 𝑍 + 2𝛾𝑝 2 𝑍 -𝛾 2 𝑝 𝑍 -2𝑝 𝑍 ) 0 3𝛾 2 𝑝 3 𝑍 -4𝛾 2 𝑝 2 𝑍 -2𝛾𝑝 2 𝑍 + 𝛾 2 𝑝 𝑍 -2𝑝 𝑍 4(𝛾𝑝 2
𝑍 -𝛾𝑝 𝑍 ) 𝑇

For the system at hand, the instantaneous reward can be written as 𝑟 ((𝑥, 𝑒, 𝑧), 𝑎) = 𝑢 (𝑥). Finally, direct computation show that

𝑅 𝛾,𝜋 (𝑝 𝑍 ) = 𝑥 (𝑢 (1) + 𝛾𝑢 (2) -𝑢 (2)) -(𝑢 (1) + 𝛾𝑢 (2)) (𝛾 -𝛾 2 )𝑥 + 𝛾 2 -1 (31)
This function is concave for 𝛾 ∈ (0, 1) as its second derivative can be explicitly computed and it is always non positive for 𝑢 (1) ≥ 𝑢 (2):

𝑑 2 𝑑𝑝 2 𝑍 𝑅 𝛾,𝜋 (𝑝 𝑍 ) = 2(𝛾 -𝛾 2 ) (𝛾 -𝛾 2 )(-𝑢 (1) -𝛾𝑢 (2)) -(𝑢 (1) + 𝛾𝑢 (2) -𝑢 (2))(𝛾 2 -1) (𝛾 2 -𝛾 2 𝑝 𝑍 + 𝛾𝑝 𝑍 -1) 3 = 2(𝛾 -𝛾 2 ) (𝑢 (1)(1 -𝛾) -𝑢 (2)(1 -𝛾)) (𝛾 2 -𝛾 2 𝑝 𝑍 + 𝛾𝑝 𝑍 -1) 3 = 2(𝛾 -𝛾 2 )(1 -𝛾)(𝑢 (1) -𝑢 (2)) (𝛾 2 -𝛾 2 𝑝 𝑍 + 𝛾𝑝 𝑍 -1) 3
For 𝛾 ∈ [0, 1), 𝑢 (1) ≥ 𝑢 (2) and 𝑝 𝑍 ∈ [0, 1] the numerator is clearly nonnegative, while the denominator is always negative, thus implying that the second derivative of 𝑅 𝛾,𝜋 (𝑝 𝑍 ) is nonThen-positive and the function itself is concave in the case studied. Note how this example also proves that 𝛿 > 0 is a necessary condition to have the concavity of the discounted reward 𝑅 𝛾,𝜋 . Indeed, if 𝛿 = 0 it can be showed that

𝑅 𝛾,𝜋 (𝑝 𝑍 ) = 𝛾𝑢 (2)𝑝 𝑍 -(𝑢 (1) + 𝛾𝑢 (2))
(𝛾 -𝛾 2 )𝑝 𝑍 + 𝛾 2 -1 which is not concave for 𝑝 𝑍 ∈ (0, 1).

D CONVERGENCE OF ORDERED Q-LEARNING

The proof of the convergence of the Ordered Q-learning algorithm introduced in Section 5.1 follows the same path as the one for Q-learning introduced in [START_REF] Tsitsiklis | Asynchronous stochastic approximation and q-learning[END_REF], of which this is a mere adaptation to the particular structure of the functions involved in the case studied. This section is divided into two parts: in the first one, it will be proved a results for generic sequences, while in the latter it will be showed how Ordered Q-learning's convergence is a consequence of the first result. The general algorithm consists in an alternation of noisy updates of one single component of a vector 𝑥 ∈ R 𝑛 and an update of other elements of the vector, with the goal of maintaining a certain (possibly partial) order on the values of all the components of 𝑥. Let 𝑥 (𝑡) be the vector at time 𝑡 and denote as 𝑥 𝑖 (𝑡) its 𝑖-th component. The update equation is

𝑥 𝑖 (𝑡 + 1) = 𝑥 𝑖 (𝑡) + 𝛼 𝑖 (𝑡) (𝐹 𝑖 (𝑥 (𝑡)) -𝑥 𝑖 (𝑡) + 𝑤 𝑖 (𝑡)) 𝑥 𝑗 (𝑡) = Π 𝑖 (𝑥 𝑖 (𝑡)) ∀𝑗 ∈ S (32)
with the function Π 𝑖 (•) indicating the projection on the space of ordered vectors. Before stating the convergence result for [START_REF] Spall | Introduction to stochastic search and optimization: estimation, simulation, and control[END_REF], some assumption required in its proof will be described. The first one refers to the statistics of the random variable 𝑤 𝑖 involved in the algorithm. ASSUMPTION 1.

(i): 𝑥 (0) is F (0)-measurable (ii): for every 𝑖 and 𝑡, 𝑤 𝑖 (𝑡) is F (𝑡)-measurable (iii): for every 𝑖 and 𝑡, 𝛼 𝑖 (𝑡) is F (𝑡)-measurable (iv): for every 𝑖 and 𝑡, E [𝑤 𝑖 (𝑡)|F (𝑡)] = 0 (v): there exist deterministic constants 𝐴 and 𝐵 such that Finally, some assumptions on the structure of the iteration mapping 𝐹 are required.

ASSUMPTION 3.

(i): 𝐹 is monotone (ii): the mapping 𝐹 is continuous (iii): the mapping 𝐹 has an unique fixed point 𝑥 * (iv): if 𝑒 ∈ R 𝑛 is the vector with all components equal to 1 and 𝑟 is positive and scalar, then 𝐹 (𝑥) -𝑟𝑒 ≤ 𝐹 (𝑥 -𝑟𝑒) ≤ 𝐹 (𝑥 + 𝑟𝑒) ≤ 𝐹 (𝑥) + 𝑟𝑒 (v): for every value of 𝑖 ∈ S and for every vector

𝑣 ∈ R 𝑛 𝐹 (Π 𝑖 (𝑣)) = Π 𝑖 (𝐹 (Π 𝑖 (𝑣)) (33)
The last assumption requires that the mapping 𝐹 maintains the order on the values when applied to an already ordered vector 𝑣 = Π 𝑖 (𝑣). We can now state and prove the general result that will be later used to find the convergence of Ordered Q-learning. THEOREM 4. Assume that Assumptions 1, 2 and 3 hold, and suppose that 𝑥 (𝑡) is bounded with probability 1. Then 𝑥 (𝑡) computed according to [START_REF] Spall | Introduction to stochastic search and optimization: estimation, simulation, and control[END_REF] converges to 𝑥 ★ with probability 1.

The proof of Theorem 4 requires the use of additional lemmas that will be stated when needed. LEMMA 2. Let {F (𝑡)} be an increasing sequence of 𝜎-fields. For each 𝑡, let 𝛼 (𝑡), 𝑤 (𝑡) and 𝐵(𝑡) be F (𝑡)-measurable scalar random variables. Let 𝐶 be a deterministic constant. Suppose that the following hold with probability 1:

(1) The proof is found in [START_REF] Tsitsiklis | Asynchronous stochastic approximation and q-learning[END_REF].

E [𝑤 (𝑡) | F (𝑡)] = 0 (2) E 𝑤 2 (𝑡) | F (𝑡) ≤ 𝐵(𝑡) (3) 𝛼 (𝑡) ∈ [0, 1] (4)
It is then proved that the sequence 𝑥 (𝑡) is bounded: PROPOSITION 2. The sequence 𝑥 (𝑡) given by (32) is bounded with probability 1.

PROOF. This can proved by induction. First of all, observe that to have 𝑥 (0) bounded, it is sufficient to choose a bounded initial vector and thus it is trivially proved. Then, assume 𝑥 (𝑡) bounded. To prove the boundedness of 𝑥 (𝑡 + 1) it is sufficient to observe that 𝑥 (𝑡 + 1) is bounded, as the update rule is the same as in Q-learning (and it is known, for Theorem 1 in [START_REF] Tsitsiklis | Asynchronous stochastic approximation and q-learning[END_REF] that Q-learning gives a bounded sequence). The desired result is then a consequence of the definition of the projection Π 𝑖 for a certain 𝑖. □

From the bounded sequence {𝑥 (𝑡)} one can further define two additional sequences, {𝑈 𝑘 } and {𝐿 𝑘 }. Let 𝑟 be a scalar such that 𝑥 ★ -𝑟𝑒 ≤ 𝑥 (𝑡)𝑥 ★ + 𝑟𝑒 for every 𝑡, with 𝑒 being the vector with unitary value in each component. The first term of each sequence is defined, respectively, as 𝑈 0 = 𝑥 ★ + 𝑟𝑒 and 𝐿 0 = 𝑥 ★ -𝑟𝑒, while the other terms are defined in a recursive way:

𝑈 𝑘+1 = 𝑈 𝑘 + 𝐹 (𝑈 𝑘 ) 2 𝑘 ≥ 0 and 𝐿 𝑘+1 = 𝐿 𝑘 + 𝐹 (𝐿 𝑘 ) 2 𝑘 ≥ 0
Note how, due to [START_REF] Kushner | Stochastic Approximation Methods for Constrained and Unconstrained Systems[END_REF] and the vectors 𝑈 0 and 𝐿 0 being ordered, for every 𝑘 ≥ 0 and for every 𝑖, the following equalities are verified:

Π 𝑖 (𝑈 𝑘 ) = 𝑈 𝑘 , Π 𝑖 (𝐿 𝑘 ) = 𝐿 𝑘
Lemma 3, Lemma 4 and Lemma 6 will be simply stated. Their proof can be found in [START_REF] Tsitsiklis | Asynchronous stochastic approximation and q-learning[END_REF].

LEMMA 3. For every 𝑘 ≥ 0, the inequalities 𝐹 (𝑈 𝑘 ) ≤ 𝑈 𝑘+1 ≤ 𝑈 𝑘 and 𝐹 (𝐿 𝑘 ) ≥ 𝐿 𝑘+1 ≥ 𝐿 𝑘 are verified.

LEMMA 4. The sequences of ordered elements {𝑈 𝑘 } and {𝐿 𝑘 } converge to 𝑥 ★ .

To conclude the proof of theorem 4, it will be sufficient to show that for every 𝑘 there exists some 𝑡 𝑘 such that

𝐿 𝑘 ≤ 𝑥 (𝑡) ≤ 𝑈 𝑘 ∀𝑡 ≥ 𝑡 𝑘 (34)
Once again, a proof by means of induction will be build.

For 𝑘 = 0, equation ( 34) is always verified with 𝑡 0 = 0. Now, fix a certain 𝑘 for which [START_REF] Ecuyer | Stochastic optimization by simulation: Convergence proofs for the GI/G/1 queue in steady-state[END_REF] for all 𝑖 and 𝑡 ≥ 𝑡 ′′ 𝑘 . The proof of this lemma is the same as the one of Lemma 7 in [START_REF] Tsitsiklis | Asynchronous stochastic approximation and q-learning[END_REF], considering 𝑥 𝑖 (𝑡) instead of 𝑥 𝑖 (𝑡). Finally, thanks to the knowledge on the structure of the solution, it can further be proved the following lemma. 𝑥

𝑗 (𝑡) =              max 𝑥 𝑗 (𝑡), 𝑥 𝑖 (𝑡) 𝑗 > 𝑖 𝑥 𝑖 (𝑡) 𝑖 = 𝑗 min 𝑥 𝑗 (𝑡), 𝑥 𝑖 (𝑡) 𝑗 < 𝑖 𝑥 𝑗 (𝑡) otherwise (35)
Now, to prove the desired result each of the cases described in [START_REF] Schulman | Trust region policy optimization[END_REF] has to be studied: clearly when 𝑖 = 𝑗 the result is immediately proved.

When 𝑗 > 𝑖, if 𝑥 𝑗 (𝑡) < 𝑥 𝑖 (𝑡) ≤ 𝑈 𝑘+1 𝑖 ≤ 𝑈 𝑘+1 𝑖 then 𝑥 𝑗 (𝑡) = 𝑥 𝑖 (𝑡) ≤ 𝑈 𝑘+1 𝑗 .
Clearly the result is also proved when 𝑥 𝑗 (𝑡) = 𝑥 𝑗 (𝑡). On the other hand, when 𝑗 < 𝑖, if 𝑥 𝑗 (𝑡) > 𝑥 𝑖 (𝑡) then one gets 𝑥 𝑗 (𝑡) = 𝑥 𝑖 (𝑡) < 𝑥 𝑗 (𝑡) ≤ 𝑈 𝑘+1 𝑗 which proves the desired result. To conclude the prove it is sufficient to observe that the result is clearly still valid when 𝑥 𝑗 (𝑡) = 𝑥 𝑗 (𝑡).

□

By symmetrical argument one can also establish that 𝑥 𝑖 (𝑡) ≥ 𝐿 𝑘+1 𝑖 for all values of 𝑡 ≥ 𝑡 ′′′ 𝑘 for a certain 𝑡 ′′′ 𝑘 . This proves equation [START_REF] Ecuyer | Stochastic optimization by simulation: Convergence proofs for the GI/G/1 queue in steady-state[END_REF] for 𝑘 + 1, thus completing the proof of the theorem.

Note how in the case studied for every pair of states 𝑠 + , 𝑠 -such that 𝑠 + ≥ 𝑠 -, one has:

(1) non decreasing reward function: 𝑟 (𝑠 + , 𝑎) ≥ 𝑟 (𝑠 -, 𝑎) ∀𝑎 (2) superaddittive reward function: 𝑟 (𝑠 + , 𝑎 + ) + 𝑟 (𝑠 -, 𝑎 -) ≥ 𝑟 (𝑠 + , 𝑎 -) + 𝑟 (𝑠 -, 𝑎 + ) (3) increasing tail trandition probability:

𝑤 (𝑠 ′ |𝑠 + , 𝑎) = 𝜁 ⪰𝑠 ′ 𝑝 (𝜁 |𝑠 + , 𝑎) ≥ 𝜁 ⪰𝑠 ′ 𝑝 (𝜁 |𝑠 -, 𝑎) = 𝑤 (𝑠 ′ |𝑠 -, 𝑎)
Using the result in Theorem 4, it is now possible to prove the convergence of Ordered Q-learning: THEOREM 5. Consider the Ordered Q-learning algorithm described by the update rule in [START_REF] Chen | Efficient multi-user computation offloading for mobile-edge cloud computing[END_REF]. Let 𝛾 < 1. Assume that, for every pair of states 𝑠 + , 𝑠 -such that 𝑠 + ≥ 𝑠 -, one has:

(1) non decreasing reward function: 𝑟 (𝑠 + , 𝑎) ≥ 𝑟 (𝑠 -, 𝑎) ∀𝑎 (2) superaddittive reward function: 𝑟 (𝑠 + , 𝑎 + ) + 𝑟 (𝑠 -, 𝑎 -) ≥ 𝑟 (𝑠 + , 𝑎 -) + 𝑟 (𝑠 -, 𝑎 + ) (3) increasing tail trandition probability: 𝑤 (𝑠 ′ |𝑠 + , 𝑎) = 𝜁 ⪰𝑠 ′ 𝑝 (𝜁 |𝑠 + , 𝑎) ≥ 𝜁 ⪰𝑠 ′ 𝑝 (𝜁 |𝑠 -, 𝑎) = 𝑤 (𝑠 ′ |𝑠 -, 𝑎)

Then 𝑞 * is a monotone function, i.e., if 𝑠 1 ≤ 𝑠 2 according to some order on the states, then 𝑞 * (𝑠 1 , 𝑎) ≤ 𝑞 * (𝑠 2 , 𝑎). Moreover, 𝑄 𝑡 (𝑠, 𝑎) converges to 𝑞 * (𝑠, 𝑎) w.p.1. for every state 𝑠 ∈ S and for every action 𝑎 ∈ A (𝑠).

PROOF. As already observed in the proof of Lemma 1, the conditions on the reward and on the transition probabilities imply the monotonicity of the optimal value function 𝑣 * . Moreover, applying Lemma 4.7.2 in [START_REF] Puterman | Markov Decision Processes[END_REF] (with the sequence 𝑥 𝑗 given by the tail transition probabilities and the non decreasing optimal value function) yields the following condition on the transition probability for every action 𝑎:

E 𝑠 ′ ∼𝑝 𝑠 + • (𝑎) 𝑣 (𝑠 ′ ) ≥ E 𝑠 ′ ∼𝑝 𝑠 -• (𝑎) 𝑣 (𝑠 ′ ) (36)
with 𝑣 denoting any non decreasing function, such as the optimal value function 𝑣 * . This easily implies that even the optimal Q-function 𝑞 * is non decreasing for every action 𝑎.

To prove the convergence of the Ordered Q-learning algorithm it is then sufficient to show that all the assumptions of Theorem 4 are verified.

Consider a problem described by a Markov Decision process defined on a finite space state S. For every states 𝑠 ∈ S there is a finite set A (𝑠) of possible actions and a set of transition probabilities 𝑝 𝑖 𝑗 (𝑎) ∈ [0, 1], 𝑖, 𝑗 ∈ S, 𝑎 ∈ A (𝑖) such that 𝑗 ∈ S 𝑝 𝑖 𝑗 (𝑠) = 1 for all 𝑎 ∈ A (𝑖) and ∀𝑖 ∈ S.

For every state 𝑠 ∈ S and every action 𝑎 ∈ A (𝑠) can be defined a random variable 𝑟 𝑠𝑎 which represents the reward obtained when applying action 𝑎 at state 𝑠. It can further be assumed that the variance of 𝑟 𝑠𝑎 is finite for every state 𝑠 and action 𝑎 ∈ A (𝑠).

Recall that the goal is to evaluate the optimal function 𝑣 * = max 𝜋 𝑣 𝜋 , defined for each state 𝑠 ∈ S as In order to prove the convergence of the method it is sufficient to show that equation [START_REF] Chen | Efficient multi-user computation offloading for mobile-edge cloud computing[END_REF] has the form of [START_REF] Spall | Introduction to stochastic search and optimization: estimation, simulation, and control[END_REF]

where the expected value is expressed in terms of the state 𝑠 ′ reached from the initial state 𝑠 with a probability equal to 𝑝 𝑠,𝑠 ′ . Note how, differently to the case studied in [START_REF] Tsitsiklis | Asynchronous stochastic approximation and q-learning[END_REF], this time the reward is deterministic given state and action.

Clearly if 𝑄 is a fixed point of 𝐹 , then the vector with components 𝑉 𝑠 = max 𝑎∈ A (𝑠 ) 𝑄 𝑠𝑎 is also a fixed point of 𝑇 . The definition of the mapping 𝐹 allows to rewrite equation [START_REF] Chen | Efficient multi-user computation offloading for mobile-edge cloud computing[END_REF] as where ★ is a consequence of (36). Further note how the components different to 𝑠, 𝑎 remain unchanged and are not reported for space's sake. This concludes the proof. □

𝑄

Figure 1 :

 1 Figure 1: Device performing local processing of data batches with energy harvesting and intermittent edge-server offloading.

Figure 2 :

 2 Figure 2: A sample path of the process 𝒔 𝒕 = (𝒙 𝒕 , 𝒆 𝒕 , 0) for 𝑯 ≡ 1: in red the vacation periods where the battery is empty. The duration of timeslot starting at time 𝒕 = 6 is 4 timesteps.

1 : 5 : 8 : 9 :

 1589 ) is a standard stepsize i.e., +∞ 𝑡 =1 𝛼 𝑡 (𝑠, 𝑎) = +∞ w.p.1. and +∞ 𝑡 =1 𝛼 𝑡 (𝑠, 𝑎) 2 < +∞ w.p.1. It holds the following result: Algorithm 1 Ordered Q-learning Require: step size 𝛼 ∈ (0, 1], discount factor 𝛾 ∈ [0, 1) 𝑄 (𝑠, 𝑎) ∈ R, ∀𝑠 ∈ S 2: 𝑄 (𝑠 ′ , 𝑎) ← 0 for 𝑠 ′ terminal state 3: for each episode 4: initialize 𝑠 ∈ S for each step of the episode 6:choose 𝑎 ∈ A (𝑠) given by 𝑄 (e.g., 𝜖-greedy) 7: take action 𝑎 and observe reward 𝑅 and 𝑠 ′ 𝑄 (𝑠, 𝑎)← (1 -𝛼) 𝑄 (𝑠, 𝑎) + 𝛼 [𝑅 + 𝛾 max 𝑎 𝑄 (𝑠 ′ , 𝑎)] 𝑄 ( s, 𝑎)← Π 𝑠 (𝑄 ( s, 𝑎)), ∀s ∈ S 10: 𝑠 ← 𝑠 ′ 11:

  e., 𝑅(𝑝 𝑍 ) := 𝑁 𝑘=1 𝑅 𝛾 𝑘 (𝑝 𝑍,𝑘 ), where 𝑅 𝛾 𝑘 (𝑝 𝑍,𝑘 ) obeys to (13), subject to the polling capacity constraint, i.e., maximize: 𝑅(𝑝 𝑍 ) = 𝑁 ∑ 𝑘=1 𝑅 𝛾 𝑘 (𝑝 𝑍,𝑘 )

Figure 3 :

 3 Fig.3adescribes the impact of the server availability 𝑝 𝑍 onto the average (peak) AoI in a single device system. Excluding the case 𝜇 = 1, i.e., for lower values of the average batch processing cost, the average AoI is maximal for 𝑝 𝑍 = 0 and attains its minimum close to 𝑝 𝑍 = 1 (the optimal 𝑝 𝑍 is highlighted with dots in Fig.3a). In fact, for higher processing cost, a larger server polling probability permits to select action 𝑎 = 1 more often, as the possible battery discharge due to data processing is compensated by frequent task offloading events. For lower cost figures, instead, it is the roundtrip delay 𝛿 that renders the offloading less convenient: when 𝛿 = 0, actually, the corresponding curve (not reported for the space's sake) becomes strictly decreasing.Fig.3bplots the value of the optimal polling probability 𝑝 𝑍 for increasing values of 𝛿. These are obtained by means of an appropriate stochastic optimization. The results show, as expected, that

E 𝑤 2 1 ( 2

 212 𝑖 (𝑡)|F (𝑡) ≤ 𝐴 + 𝐵 max 𝑗 max 𝜏 ≤𝑡 𝑥 𝑗 (𝜏) ∀𝑖, 𝑡 It follows an assumption on the values of the sequence of learning rates {𝛼 𝑖 } 𝑖 : ASSUMPTION 2. (i): for every 𝑖, ∞ ∑ 𝑡 =0𝛼 𝑖 (𝑡) = ∞ 𝑤 .𝑝.ii): there exists some deterministic constant C such that for every 𝑖, 𝑖 (𝑡) ≤ 𝐶 𝑤 .𝑝.1

  ∞ 𝑡 =0 𝛼 (𝑡) = ∞ (5) ∞ 𝑡 =0 𝛼 2 (𝑡) ≤ 𝐶 Suppose that the sequence {𝐵(𝑡)} is bounded with probability 1. Let 𝑊 (𝑡) satisfy the recursion 𝑊 (𝑡 + 1) = (1 -𝛼 (𝑡))𝑊 (𝑡) + 𝛼 (𝑡)𝑤 (𝑡) Then lim 𝑡 →∞ 𝑊 (𝑡) = 0 with probability 1.

LEMMA 7 .

 7 𝑥 𝑖 (𝑡) ≤ 𝑈 𝑘+1 𝑖 for all 𝑖 and 𝑡 ≥ 𝑡 ′′ 𝑘 . PROOF. Lemma 6 gives that 𝑥 𝑖 (𝑡) ≤ 𝑈 𝑘+1 𝑖 ∀𝑡 ≥ 𝑡 ′′ 𝑘 Now consider 𝑥 (𝑡) = Π 𝑖 (𝑥 (𝑡)), where 𝑖 represents the state visited at time 𝑡 for which the updated estimate has been computed in the first equation.

E

  𝑣 * (𝑠) = max 𝜋 𝑣 𝜋 (𝑠) = max 𝜋 max 𝑎∈ A (𝑠 ) E 𝑠 ′ ∼𝜋 𝑟 𝑠𝑎 + 𝛾𝑣 𝜋 (𝑠 ′ ) 𝑠 ′ ∼𝑝 𝑠 • (𝑎) 𝑟 𝑠𝑎 + 𝛾 max 𝑏 ∈ A (𝑠 ′ ) 𝑞 𝜋 (𝑠 ′ , 𝑏)Recall that the positive constant value 𝛾 ∈ R is assumed to be strictly smaller than 1. Now define the dynamic programming operator 𝑇 : R | S | → R | S | with components 𝑇 𝑖 by letting 𝑇 𝑖 (𝑉 ) = max 𝑎∈ A (𝑖 ) It is well known that if 𝛾 < 1 the operator 𝑇 is a contraction with respect to the norm ∥•∥ ∞ and 𝑣 * is its unique fixed point. The Ordered Q-learning algorithm previously described is a method for computing 𝑣 * based on a reformulation of the Bellman equation 𝑣 * = 𝑇 (𝑣 * ).

  and it satisfies all the assumptions of Theorem 4. Let 𝐹 : R | S | | A | → R | S | | A | be the mapping whose components 𝐹 𝑠𝑎 is defined as𝐹 𝑠𝑎 (𝑄) = 𝑟 𝑠𝑎 + 𝛾E max 𝑏 ∈ A (𝑠 ′ )𝑄 (𝑠 ′ , 𝑏)

=

  Finally, it remains to prove that Assumption 3 is verified. Proving (3.i) and (3.ii) is trivial, as both are a natural consequence of the definition of the mapping 𝐹 . If 𝛾 < 1 it can also be observed how|𝐹 𝑠𝑎 (𝑄 1 ) -𝐹 𝑠𝑎 (𝑄 2 )| ≤ 𝛾 max 𝑠 ′ ∈ S,𝑏 ∈ A (𝑠 ′ ) |𝑄 1 (𝑠 ′ , 𝑏) -𝑄 2 (𝑠 ′ , 𝑏)| ∀𝑄 1 , 𝑄 2 ∈ R | S |which yields that the mapping 𝐹 is a contraction and verifies (3.iii). The validity of (3.iv) is a consequence of the linearity of 𝐹 and of the expected value, while to prove (3.v) it can be directly showed that ∀𝑣 ∈ R 𝑛 one has 𝑣 = Π 𝑗 (𝑣) ⇒ Π 𝑗 (𝐹 (Π 𝑗 (𝑣))) = 𝐹 (Π 𝑗 (𝑣))Π 𝑗𝑎 (𝐹 (𝑣)) = Π 𝑗𝑎 𝑟 𝑠𝑎 + 𝛾E 𝑠 ′ ∼𝑝 𝑠 • (𝑎) max 𝑏 𝑣 (𝑠 ′ , 𝑏) 𝑟 𝑠𝑎 + E 𝑠 ′ ∼𝑝 𝑠 • (𝑎) [max 𝑏 𝑣 (𝑠 ′ , 𝑏)] , 𝑟 𝑗𝑎 + 𝛾E 𝑠 ′ ∼𝑝 𝑗 • (𝑎) [max 𝑏 𝑣 (𝑠 ′ , 𝑏)] s > j 𝑟 𝑠𝑎 + 𝛾E 𝑠 ′ ∼𝑝 𝑠 • (𝑎) [max 𝑏 𝑣 (𝑠 ′ , 𝑏)] s = j min 𝑟 𝑠𝑎 + 𝛾E 𝑠 ′ ∼𝑝 𝑠 • (𝑎) [max 𝑏 𝑣 (𝑠 ′ , 𝑏)] , 𝑟 𝑗𝑎 + 𝛾E 𝑠 ′ ∼𝑝𝑗 • (𝑎) [max 𝑏 𝑣 (𝑠 ′ , 𝑏)] 𝑟 𝑠𝑎 + 𝛾E 𝑠 ′ ∼𝑝 𝑠 • (𝑎) max 𝑏 𝑣 (𝑠 ′ , 𝑏) 𝑠𝑎 = 𝐹 (𝑣)

Table 1 :

 1 List of symbols used in the paper. 𝑥 𝑡 ∈ {1, . . . , 𝑀 } 𝑒 𝑡 buffer energy level 𝑒 𝑡 ∈ {0, 1, . . . , 𝐵 } 𝑧 𝑡 server availability 𝑧 𝑡 ∈ {0, 1} 𝑠 𝑡 = (𝑥 𝑡 , 𝑒 𝑡 , 𝑧 𝑡 )

	Symbol	Meaning
	𝑡	time step 𝑡 = 1, 2, . . .
	𝑥 𝑡	age of information (AoI) device state
	𝛾	discount factor
	S	state space
	A = {0, 1}	action set, action set of state 𝑠, A (𝑠 ) ⊂ A
	𝑎 𝑡 = {0, 1}	action taken at time 𝑡
	𝐵	battery capacity
	𝑀	saturation bound on AoI
	𝐶 𝑡	batch processing cost at time 𝑡
	𝐻 𝑡	harvested energy at time 𝑡
	𝛿	offloading roundtrip time

  Let 𝑠 + be larger than 𝑠 -if 𝑠 + ⪰ 𝑠 -. The real function 𝜓 : S×A → R is supermodular if 𝜓 (𝑥 + , 𝑦 + ) + 𝜓 (𝑥 -, 𝑦 -) ≥ 𝜓 (𝑥 + , 𝑦 -) + 𝜓 (𝑥 -, 𝑦 + ), also equivalent to say that 𝜓 (𝑥 + , 𝑦) -𝜓 (𝑥 -, 𝑦) is decreasing in 𝑦.

	The tail transition probability 𝑤 (𝑠 ′ |𝑠, 𝑎) := 𝜁 ⪰𝑠 ′ 𝑝 (𝜁 |𝑠, 𝑎) defines
	the probability of making a transition to states larger than 𝑠 taking
	action 𝑎.
	LEMMA 1. i. 𝑣 * (𝑥, 𝑒, 𝑧) is non increasing in 𝑥
	ii. 𝑣 * (𝑥, 𝑒, 𝑧) is non decreasing in 𝑒.

  Pseudocode of APPI Require: 𝜖 > 0 1: initial polling probability 𝑝 𝑍,new 2: while 𝑝 𝑍,old -𝑝 𝑍,new > 𝜖 3: 𝑝 𝑍,old ← 𝑝 𝑍,new 4: Optimal policy learning: find optimal policy 𝜋 * 𝑘 (𝑝 𝑍,old ) for ∀𝑘 5: Polling optimization: find 𝑝 𝑍,new ≥ 0 such that 𝑝 𝑍,new = arg max 𝑝 𝑍 𝑘 𝑅 𝛾 𝑘 ,𝜋 * 𝑘 (𝑝 𝑍 ,𝑘,old ) (𝑝 𝑍 ) 𝑘 𝑝 𝑍,new = 1 6: end while 7: return 𝑝 𝑍,new

Each device 𝑘 ∈ {1, . . . , 𝑁 } follows the single device-server model described in Section 3. At each timeslot the Algorithm 2

  1.

	Parameter	Subsec. 7.1	Subsec. 7.2 and 7.3
	M	15	{10, . . . , 25}
	B	15	{10, . . . , 25}
	𝛾	0.95	{0.9, . . . , 0.99}
	𝑝 𝑍	0.05	{0.01, . . . , 0.1}
	𝛿	1	1
	Reward	𝑟 (𝑥 ) = 𝑀 -𝑥	𝑟 (𝑥 ) = 𝑀 -𝑥
	Discharge Penalty 𝑑 (𝑒 ) = 𝑒 4 • 1{𝑒 ≥ 0} 𝑑 (𝑒 ) = 1 𝑒<0 (-𝑒 ) 𝑘 ,
			with 𝑘 ∈ {1, 2, 3, 4}
	Harvesting	Poisson (𝜆 = 1)	Poisson (𝜆 = 1)
	Processing Cost	uniform, binary and	symmetric with
		symmetric for 𝜇 ∈	𝜇 ∈ {1, . . . , 𝐵/2}
		{1, 4, 8.5}	𝜎 ∈ {1, 2, 3, 4}

Table 2 :

 2 The system parameters used in the numerical experiments.

Table 3 .

 3 In particular, RF appears to converge quickly, but to a suboptimal

		250 episodes 1000 episodes 3000 episodes
	QL	0.723 ± 0.254	0.796 ± 0.220	0.810 ± 0.208
	TQL	0.752 ± 0.255	0.857 ± 0.181	0.880 ± 0.117

SQL 0.850 ± 0.209 0.943 ± 0.051 0.964 ± 0.060 Reinforce 0.893 ± 0.225 0.893 ± 0.227 0.893 ± 0.224

Table 3 :

 3 RL tests: discounted reward for increasing number of episodes; best performance results are marked bold.

Table 4 :

 4 APPI consistently outperforms the other algorithms by attaining higher discounted reward and requiring much fewer policy improvement

	Algorithm Discounted reward Policy learning steps
	NRS	0.423 ± 0.237	4.98 ± 1.378
	ENRS	0.678 ± 0.184	10.06 ± 3.331
	SPSA	0.449 ± 0.276	5.54 ± 1.846
	APPI	0.747 ± 0.143	2.98 ± 1.086

Table 4 :

 4 Comparison of different polling improvement algorithms for 𝑵 = 3.

	N Discounted reward Policy learning steps
	1	0.794 ± 0.222	2.18 ± 0.77
	3	0.747 ± 0.143	2.98 ± 1.086
	5	0.699 ± 0.192	3.78 ± 1.221
	7	0.724 ± 0.222	4.08 ± 1.074
	10	0.714 ± 0.237	5.06 ± 1.302

Table 5 :

 5 Performance of APPI for increasing number of devices connected to the edge server.

  is true. Let 𝑊 𝑖 (0) = 0 and 𝑊 𝑖 (𝑡 + 1) = (1 -𝛼 𝑖 (𝑡))𝑊 𝑖 (𝑡) + 𝛼 𝑖 (𝑡)𝑤 𝑖 (𝑡) Due to Lemma 2, lim 𝑡 →∞ 𝑊 𝑖 (𝑡) = 0. Moreover, for every time 𝑡 0 , can be further defined 𝑊 𝑖 (𝑡 0 ; 𝑡 0 ) = 0 and𝑊 𝑖 (𝑡 + 1; 𝑡 0 ) = (1 -𝛼 𝑖 (𝑡))𝑊 𝑖 (𝑡; 𝑡 0 ) + 𝛼 𝑖 (𝑡)𝑤 𝑖 (𝑡) 𝑡 ≥ 𝑡 0Following the same argument as above, it is proved that lim 𝑡 →∞ 𝑊 𝑖 (𝑡; 𝑡 0 ) = 0. Then, one can design a sequence 𝑋 𝑖 (𝑡), 𝑡 ≥ 𝑡 ′ 𝑘 , by letting 𝑋 𝑖 (𝑡 ′ This lemma is analogous to Lemma 6 in[START_REF] Tsitsiklis | Asynchronous stochastic approximation and q-learning[END_REF], where the inequality was proved for 𝑥 𝑖 (𝑡) with the corresponding definition. It can be equally proved in our case following the same proof, with the care of considering 𝑥 𝑖 (𝑡) at each step in spite of 𝑥 (𝑡). □ Now, let 𝛿 𝑘 be equal to the minimum of 𝑈 𝑘 𝑖 -𝐹 𝑖 (𝑈 𝑘 ) /4, where the minimum is taken over all 𝑖 for which 𝑈 𝑘 𝑖 -𝐹 𝑖 (𝑈 𝑘 ) is positive. Clearly 𝛿 𝑘 is well-defined and positive, unless 𝑈 𝑘 = 𝐹 (𝑈 𝑘 ), but this would imply that convergence has been reached. 𝛿 𝑘 for all 𝑡 ≥ 𝑡 ′′ 𝑘 . Such value of 𝑡 ′′ 𝑘 exists due to the first assumption on the sequence of 𝛼s and the convergence of 𝑊 𝑖 (𝑡; 𝑡 ′ 𝑘 ) to 0.

	Let 𝑡 ′′ 𝑘 ≥ 𝑡 ′ 𝑘 be such that
	𝑡 ′′ 𝑘 -1 𝜏=𝑡 ′	(1 -𝛼 𝑖 (𝜏)) ≤	1 4
	𝑘
	and
	𝑊 𝑖 (𝑡; 𝑡 ′ 𝑘 ) ≤

𝑘 ) = 𝑈 𝑘 𝑖 and

𝑋 𝑖 (𝑡 + 1) = (1 -𝛼 𝑖 (𝑡))𝑋 𝑖 (𝑡) + 𝛼 𝑖 (𝑡)𝐹 𝑖 (𝑈 𝑘 ) 𝑡 ≥ 𝑡 ′

𝑘

With these definitions, the following lemma can be proved. LEMMA 5. 𝑥 𝑖 (𝑡) ≤ 𝑋 𝑖 (𝑡) + 𝑊 𝑖 (𝑡; 𝑡 ′ 𝑘 ) 𝑡 ≥ 𝑡 ′ 𝑘 PROOF. LEMMA 6. 𝑥 𝑖 (𝑡) ≤ 𝑈 𝑘+1 𝑖

  𝑡 +1 (𝑠, 𝑎) = 𝑄 𝑡 (𝑠, 𝑎) + 𝛼 𝑡 (𝑠, 𝑎) (𝐹 𝑠𝑎 (𝑄 𝑡 ) -𝑄 𝑡 (𝑠, 𝑎)+ 𝑤 𝑡 (𝑠, 𝑎)) 𝑄 𝑡 +1 (𝑠, 𝑎) = Π 𝑠 (𝑄 𝑡 +1 (𝑠 ′ , 𝑎)) ∀𝑠 ′ 𝑄 𝑡 (𝑠 ′ , 𝑏) -E max 𝑏 ∈ A (𝑠 ′ ) 𝑄 𝑡 (𝑠 ′ , 𝑏) | F (𝑡)(39)with the expected value expressed in terms of the reached state 𝑠 ′ . It remains to show that the Assumptions 1, 2 and 3 previously described are verified in the framework considered.Let the filtration F (𝑡) represent the history of the algorithm up to time 𝑡. This implies that (1.i), (1.ii) and (1.iii) are naturally verified. Moreover, (1.iv) is a natural consequence of the definition of the random variable 𝑤 𝑖 in (39). Finally, assumption (1.v) is verified as the conditional variance of 𝑤 𝑖 can always be bounded by max 𝑠 ′ ∈ S max 𝑎∈ A (𝑠 ) 𝑄 2 𝑡 (𝑠, 𝑎), which is itself a bounded quantity. Assumption 2 can be imposed by choosing an appropriate definition of the random variable 𝛼 describing the stepsizes in the Ordered Q-learning algorithm.

	(38)
	where
	𝑤 𝑡 (𝑠, 𝑎) = 𝛾 max 𝑏 ∈ A (𝑠 ′ )

This work has been partially supported by the French National Research Agency (ANR) within the framework of the PARFAIT project (ANR-21-CE25-0013), see http://parfait.univ-avignon.fr.

A TRANSITION PROBABILITIES: STOCHASTIC HARVESTING RATE

This section derives the transition probabilities [START_REF] Hu | Mobile edge computing: a key technology towards 5G[END_REF] to the case of a stochastic harvesting sequence of i.i.d. random variables {𝐻 𝑡 }. Here, both both 𝐻 𝑡 and 𝐶 𝑡 may have unbounded support [0, +∞). When the action is 𝑎 = 0 they write

The generalization of (2), for the case when 𝑎 = 1, writes:

C PROPERTIES OF THE DISCOUNTED REWARD

The APPI learning procedure is based on the assumptions that function 𝑅 𝛾,𝜋 (𝑝 𝑍 ) which describes the discounted reward for a fixed policy 𝝅 is smooth and concave.

Continuity and differentiability

As recalled in Section 4.2, the function 𝑅 𝛾,𝜋 (𝑝 𝑍 ) which describes the discounted reward for a fixed policy 𝝅 and a given initial state distribution is continuous in [0, 1] and differentiable in (0, 1). The following theorem formally proves the result.

THEOREM 3. 𝑅 𝛾,𝜋 (𝑝 𝑍 ) is continuous in [0, 1] and differentiable in (0, 1) w.r.t. 𝑝 𝑍 for every fixed policy 𝜋.

PROOF. To show the continuity of 𝑅 𝛾,𝜋 (𝑝 𝑍 ) we consider the equivalent formulation [START_REF] Abd-Elmagid | Aoi-optimal joint sampling and updating for wireless powered communication systems[END_REF]. First of all notice that 𝑑 0 (𝑝 𝑍 ) and 𝑃 𝜋 (𝑝 𝑍 ) are componentwise continuous and differentiable in 𝑝 𝑍 . By recalling the expression for the average reward

and recalling that 𝑟 𝜋 is a vector in R | S | and whose terms are independent on 𝑝 𝑍 , the statement follows. □

Concavity

Extensive numerical experiments have showed that 𝑅 𝛾,𝜋 (𝑝 𝑍 ) is concave for a fixed the discount factor 𝛾 and and the policy 𝜋 when 𝛿 > 0. The case with 𝛾 = 0 gives that 𝑅 0,𝜋 (𝑝 𝑍 ) = ⟨𝑑 0 (𝑝 𝑍 ), 𝑟 𝜋 ⟩, which is a linear combination of concave functions and will therefore not be considered in the following. The result is demonstrated for a specific example. Backed by the variety of experiments tested, it is likely that a similar conclusion can be reached also in general.

The example is represented by a system with 𝐵 = 1 and 𝑀 = 2. This corresponds to the case when battery of the device is either full or empty while the information can just be new, i.e., 𝑥 = 1, or old, i.e., 𝑥 = 2. Moreover, assume a deterministic harvesting rate 𝐻 ≡ 1 and cost distribution

Finally, consider 𝛿 = 1 and 𝛾 ∈ (0, 1). The policy studied is the trivial one, 𝜋, such that

Consider now an By assuming an initial distribution where 𝑧 = 0, the transition towards a state 𝑠 ′ = (𝑥, 𝑒, 𝑧) having AoI 𝑥, energy 𝑒 and any value if 𝑧 is described by

where states are indexed using index function index