# Solving Task Scheduling Problems in Dew Computing via Deep Reinforcement Learning
## 5 Reinforcement Learning for Dew Computing
### Environment Definition: States, Actions, and Rewards  
The first step to apply RL in Dew computing is to properly define the environment that the agent is going to interact with: that is, to define the states \(S\) of the environment, the actions \(A\) that the agent can perform, and the reward signal \(r(s,a,s^{\prime})\) that the agent will  
Figure 2: Overview of a scheduling problem in a Dew environment. Jobs arrive over time to the scheduler. Once a job arrives, the scheduler must assign that job to a device connected to the local network. In order to make such a decision, the scheduler has access to information about the job and the state of each device connected to the network. More details can be found in Section 5.3.  
optimize for. We might also have to define the transition probabilities \(p(s^{\prime}|s,a)\) if the agent does not interact with a real system (or with a predefined simulator). Whether the agent succeeds or fails at distributing jobs in a Dew environment partially depends on how we define those four elements: \(S\), \(A\), \(r\), and \(p\). To define a Dew environment in terms of \(S\), \(A\), \(r\), and \(p\), our starting point was a state-of-the-art simulator called EdgeDewSim [7, 21]. EdgeDewSim simulates real Dew environments with high accuracy. Among its many features, EdgeDewSim simulates the energy consumption of each device, the job executions, user behaviors, and basic network congestion. Thus, the transition probabilities \(p\) in the environment are modeled by EdgeDewSim. To define the state space \(S\), we considered two key features of RL. First, most RL agents do not have memory. They learn a policy \(\pi(a_{t}|s_{t})\) that makes decisions purely based on the information available in the current state \(s_{t}\in S\). Thus, \(s_{t}\) must include all the relevant information that the agent needs in order to assign a job to the correct device. Second, we note that any information that is identical for all the states \(s\in S\) is useless for the agent. The reason is that the agent has to discriminate whether action \(a\) is a good action in state \(s\). If a subset of information \(x\subset s\) is identical for all states, then \(x\) provides no discriminatory information to the agent. We then define the state space as follows: \(S=D\times J\times C\), where \((d,j,c)\in S\). Specifically, \(d\in D\) contains information on the current state of each device. This information includes, for each device, its CPU usage percentage, its remaining battery, and its current job queue. Then, \(j\in J\) provides information about the job that the scheduler must assign next. This information includes the job's ops, input size, and output size. Finally, \(c\in C\) contains general statistics about the previously completed jobs. These statistics include the number of jobs that have arrived, the number of jobs that have been completed, the sum of the jobs' ops that have been completed, and the elapsed time since the beginning of the simulation (i.e., \(t-t_{0}\)). We note that \(s\in S\) comprises all the necessary information to properly assign job \(j\) to a device in a fixed Dew environment. If the environment is not fixed, then we might want to add some additional features, such as the number of instructions per second a device can execute, or how big its battery is. We discuss this further in Section 7. Our definition of the action space \(A\) is as expected. We define one possible action per device in the Dew environment. Then, whenever the agent executes action \(a_{i}\in A\) given the current state \((d,j,c)\in S\), the job \(j\) is assigned to the device associated with action \(a_{i}\). Finally, the reward function is equal to the GIPS executed in the Dew environment, as defined in Equation (2). Formally,  
\[r(s,a,s^{\prime})= \begin{cases}\frac{\sum_{i\in c_{t}}j\text{ops}}{1-t_{0}}& \text{if $s^{\prime}$ is terminal}\\ 0&\text{otherwise}\end{cases}  \tag{3}\]  
Note that this reward function only rewards the agent in terminal states.