## 2 Reinforcement Learning: Background
### Reinforcement Learning  
The idea behind the MDP is the [PERSON] assumption: \"The future is independent of the past history, given the present\" [3]. It is reasonable to deduce that as long as the current state captures all relevant information about past events, the past history may no longer be informative. An environment here is modeled as a set of states. The goal is to maximize its performance while choosing actions that can have an effect on these states [20]. The MDP shown in Figure 1 can be described formally with four components: _states_, _actions_, a _transition function_, and a _reward function_. A finite MDP is a tuple \(\langle S,A,T,R,\gamma\rangle\), where \(S\) is a finite set of _states_; \(A\) is a finite set of _actions_; \(T:S\times A\times S^{\prime}\rightarrow[0,1]\) is a _transition function_, which specifies for each state an action and a subsequent state and the probability of the next state being brought about; \(R:S\times A\times S^{\prime}\rightarrow\Re\) is a _reward function_ specifying for each state, action, and subsequent state the sum of expected immediate and discounted rewards; and \(\gamma\) is a _discount factor_ specifying the relative importance of immediate rewards. Figure 1: [PERSON] decision process from the reinforcement learning perspective: each node represents state \(S\), \(A_{t+1}\) denotes action \(A\), and \(R_{t+1}\) denotes reward \(R\). States \(S\) play a role in an outcome in addition to providing whatever information is necessary for choosing an action. Actions \(A\) can be used to control the state. The transition function \(T\) determines how the system will move to the next state. By performing an action in a state, the agent makes the transition from the current state to a new state based on a probability distribution over the set of possible transitions. Reward functions \(\Re\) specify rewards for being in a state or performing some action in a state. They implicitly specify the goal of the agent [20] (Figure 2). A solution to the MDP is characterized by the Bellman optimality equation [3]:  
\[Q^{*}(s,a)=E_{(s,a,s^{\prime})}\Big{[}R+\gamma\max_{a^{\prime}} Q^{*}(s^{\prime},a^{\prime})\Big{]} \tag{1}\] \[=\sum_{s^{\prime}}P(s,a,s^{\prime})\Big{(}R+\gamma\max_{a^{\prime }}Q^{*}(s^{\prime},a^{\prime})\Big{)},\]  
where the tuple \(\langle s,a,s^{\prime}\rangle\) refers to the current state \(s\), an action \(a\), and the state in the next time step \(s^{\prime}\), and \(Q(s,a)\) refers to the state-action value. \(P(s,a,s^{\prime})\) and \(R\) refer to the state-action-state transition probability and an immediate reward, respectively. The Bellman optimality equation specifies that the value estimate for states and actions in each state (seen in Equation (2)) is given by the expectation over a state-space distribution of the future reward, which consists of an immediate reward amount plus the value estimate of the possible next state (often dubbed as the \"TD target\"). For example, an MF RL approximates this process under the assumption that the state transition is stationary, so the expectation over the state-space transitions can be empirically estimated by sampling actions for the environment. \[V^{*}(s)=\max_{a}Q^{*}(s,a). \tag{2}\]  
\[\pi^{*}(s)=argmax_{a}Q^{*}(s,a). \tag{3}\]  
Solving the MDP means computing an optimal policy \(\pi^{*}\) (Equation (3)) by estimating the expected amount of reward for each state or action \(Q^{*}(s,a)\) (Equation (1)), and then developing a policy that favors more valuable actions, leading to the maximization of the amount of future outcomes \(V^{\pi}\) (Equation (2)). As a means to solve the equation, classical RL employed various iterative methods such as dynamic programming (DP) [21] and model-free algorithms such as Monte Carlo (MC) methods [22; 23] or the temporal difference approach (TD) [18].