## 3 Overview of Reinforcement Learning (RL)
### Markov Decision Framework  
Reinforcement learning formulates the desired issue as a Markov decision process (MDP) [22; 23]. Definitions related to reinforcement learning are presented below:  
**Definition 1**.: _MDP consists of a tuple \((S,A,P,R,\gamma)\):_  
* _S: A limited state space_
* _A: A limited action space_
* _R: A reward function, like_ \(R=\mathbb{E}[R_{t+1}|S_{t}=s,A_{t}=a]\)_._
* _P: A state transition probability, like_ \(P=\mathbb{P}[S_{t+1}=s^{\prime}|S_{t}=s,A_{t}=a]\)_._
* \(\gamma\)_: Discount factor so that_ \(\gamma\in[0,1]\)_._ _When resolving such a problem, the subsequent state is obtained from the former state. This means that it is not dependent on past states._ \[\mathbb{P}[S_{t+1}-S_{t}]=\mathbb{P}[S_{t+1}-S_{1},...,S_{t}]\] (1) _The action and state sets and environment dynamics define a finite MDP. Equation (_2_) defines the probability of each state-reward pair:_ \[p\big{(}s^{\prime},r|s,a\big{)}\doteq\Pr\{S_{t+1}=s,R_{t+1}=r|S_{t}=s,A_{t}=a\}\] (2) _where_ \((s,a)\) _and_ \((s^{\prime},r)\) _indicate the former state-action and latter state-reward pairs, respectively._ _The sum of the collected rewards (i.e.,_ \(G_{t}=R_{t+1}+R_{t+2}+\cdots+R_{T}\) _so that_ \(T\) _is the final time step) must be maximized by the agent. This function can be used when the task is episodic. This means that it has a final state. However, if the task is continuous, then there is no final state, i.e.,_ \(T=\infty\)_._  
**Definition 2**.: \(G_{t}\) _(obtained from Equation (3)) is the total long-term returns after considering the discount factor._  
\[G_{t}=\sum_{k=0}^{\infty}\gamma^{k}R_{t+k+1} \tag{3}\]  
_so that \(\gamma^{k}\) (i.e., discount factor) is between \([0,1]\). \(R_{t+k+1}\) also reflects the reward at time \(t+k+1\)  
**Definition 3**.: _A probability distribution called the policy \(\pi\) is defined with regard to the actions taken for the existing states. In fact, once the agent reaches a state, it chooses the subsequent action with regard to the policy._  
\[\pi(a|s)\doteq\mathbb{P}[A_{t}=a|S_{t}=s] \tag{4}\]  
_so that a is the action selected for the state \(s\)._  
**Definition 4**.: _Assuming the agent in state \(s\) and listening the policy \(\pi\), State-Value function \(v_{\pi}(s)\) is defined according to Equation (5):_  
\[v_{\pi}\doteq\mathbb{E}_{\pi}[G_{t}|S_{t}=s]=\mathbb{E}_{\pi}\Bigg{[}\sum_{k= 0}^{\infty}\gamma^{k}R_{t+k+1}|S_{t}=s\Bigg{]} \tag{5}\]  
**Definition 5**.: _Assuming the agent in state \(s\), taking the action \(a\), and listening the policy \(\pi\), Action-Value function \(q_{\pi}(s,a)\) is defined according to (6):_  
\[q_{\pi}(s,a)\doteq\mathbb{E}_{\pi}[G_{t}|S_{t}=s,A_{t}=a]=\mathbb{E}_{\pi} \Bigg{[}\sum_{k=0}^{\infty}\gamma^{k}R_{t+k+1}|S_{t}=s,A_{t}=a\Bigg{]} \tag{6}\]  
_The Bellman equation is met by both value functions (i.e., \(v_{\pi}(s)\) and \(q_{\pi}(s,a)\)):_  
\[v_{\pi}(s)=\sum_{a}\pi(a|s)\sum_{s^{\prime},r}p\big{(}s^{\prime},r|s,a\big{)} \big{[}r+\gamma v_{\pi}(s^{\prime})\big{]},\ \ \forall\ \ s\in S \tag{7}\]  
_When a RL algorithm discovers the best policy \(\pi^{*}\), it is converged. In this case, two optimal state-value and action-value functions are calculated in accordance with the optimal policy \(\pi^{*}\)._  
**Definition 6**.: _Optimal state-value function \(v_{*}(s)\) represents the best value of \(v_{\pi}(s)\) at all policies._  
\[v_{*}(s)=\max_{\pi}v_{\pi}(s),\ \ \forall\ \ s\in S \tag{8}\]  
**Definition 7**.: _Optimal action-value function \(q_{*}(s,a)\) represents the best value of \(q_{\pi}(s,a)\) at all policies._  
\[q_{*}(s,a)=\max_{\pi}q_{\pi}(s,a),\ \ \forall\ \ s\in S \tag{9}\]  
_See [10; 22] for more details about RL techniques._