# Solving Task Scheduling Problems in Dew Computing via Deep Reinforcement Learning
## 4 Reinforcement Learning (RL)  
RL agents learn optimal behaviors by interacting with an environment [9], where optimal behavior is defined with respect to a reward signal that the agent seeks to maximize. Formally, the environment is modeled as a _Markov decision process (MDP)_. An MDP is a tuple \(\mathcal{M}=S,A,r,p,\gamma,\mu\), where \(S\) is a finite set of _states_, \(A\) is a finite set of _actions_, \(r:S\times A\times S\rightarrow\mathbb{R}\) is the _reward function_, \(p(s_{t+1}|s_{t},a_{t})\) is the _transition probability distribution_, \(\gamma\in(0,1]\) is the _discount factor_, and \(\mu\) is the _initial state distribution_, where \(\mu(s_{0})\) is the probability that the agent starts in state \(s_{0}\in S\). A subset of the states might also be labeled as _terminal states_. At the beginning of an _episode_, the environment is set to an initial state \(s_{0}\), which is sampled from \(\mu\). Then, at time step \(t\), the agent observes the current state \(s_{t}\in S\) and executes an action \(a_{t}\in A\). In response, the environment returns the next state \(s_{t+1}\sim p(\cdot|s_{t},a_{t})\) and the immediate reward \(r_{t+1}=r(s_{t},a_{t},s_{t+1})\). The process is then repeated from \(s_{t+1}\) until potentially reaching a terminal state, when a new episode will begin. The agent's goal is to collect as much reward from the environment as possible. To do so, the agent learns a _policy_\(\pi(a|s)\), which is a probability distribution over the actions \(a\in A\) given a state \(s\in S\). Every policy induces a probability distribution over the future states and rewards that the agent will encounter if it selects actions according to such a policy. Therefore, we can rank different policies by how much reward they are expected to receive. Ideally, the agent will be able to improve its policy until finding an _optimal policy_, denoted by \(\pi^{*}\), which is a policy that maximizes the expected reward received by the agent. Formally, optimal policies are defined as follows:  
\[\pi^{*}=\text{argmax}_{\pi}\sum_{s\in S}\mu(s)\mathbb{E}_{\pi}\left[\sum_{t=0 }^{\infty}\gamma^{t}r_{t}\middle|s_{0}=s\right] \tag{1}\]  
Different methods have been proposed to learn optimal policies. Some classical examples include Q-learning [17] and SARSA [18]. Those approaches are known as tabular methods, since they use a large table to approximate \(\pi^{*}\). Such a table includes one entry per state \(s\in S\) and then, for each action \(a\in A\), approximates the expected reward from executing action \(a\) in state \(s\). Note that the size of the table is equal to \(S\times A\) and, thus, tabular methods are impractical when solving problems with really large state spaces--as is the case in Dew environments. To solve problems with large (and potentially infinite) state spaces, deep RL methods use _deep neural networks_ with parameters \(\theta\) to model the policy \(\pi_{\theta}(a|s)\). Neural networks are state-approximation techniques that, given a large enough network, can model any function [52]. In this case, the neural network \(\pi_{\theta}\) receives as input a vector of real numbers (i.e., features) that represents the current state of the environment and outputs a probability distribution over the possible actions \(a\in A\). We note that the output of the network depends on the parameters \(\theta\), which are initially set to a random value. As a result, the initial policy \(\pi_{\theta}(a|s)\) will tend to select all actions with equal probability. Then, the learning goal is to find \(\theta^{*}\) such that \(\pi_{\theta^{*}}\approx\pi^{*}\). The key difference between deep RL methods lies in how they search for \(\theta^{*}\). The first deep RL algorithm was _Deep Q-Network (DQN)_[53], which is a value-based method. After DQN, an actor-critic method, called, _Asynchronous Advantage Actor-Critic (A3C)_[22], was proposed. A3C learns much faster than DQN if we consider training time (although A3C is less sample efficient than DQN). Then, _Proximal Policy Optimization (PPO)_[19]was proposed.