# Markov Decision Process (MDP)
Reinforcement learning problems are usually representend with the MDP framework, meaning those:
- Set of State
- Set of actions
- Set of rewards
- Discount Factor ( Gamma )
- State-transition probabilites ( because not all the environements are deterministic )


One way of solving it is by using 
## Dynamic Programming :
2 Iteratives functions way :
1. Policy Evaluation :
Bellman's Equation allow us to define the value function ( for a state ) recursively :
\begin{align}
V_\pi (s) = \sum_a \pi (a|s) \sum_s' \sum_r p(s', r|s, a){r+ \gamma V_\pi (s') }
\end{align}
and because it is a linear equation, we can develop it and obtain a **policy evaluation**
2. Policy Improvement ( take the argmax over Q(s, a))

### Value Iteration
- Instead of waiting for the policy evaluation to converge, just do 1 iteration
- It will still converge
- We don't need to do Policy Improvement step at all
- Since it's argmax, then taking the max in the policy evaluation step is equivalent
\begin{align}
    V_k+1 (s) = max_a \sum_s' \sum_r p(s', r|s, a){r + \gamma V_k (s')}
\end{align}

But Dynamic Programming requires us to know all of the transitions probabilites which is impossible in real life problems.
Also we need to loop through all states on every iteration which is not practible on large domain of S.

## Monte Carlo (MC) :
MC is all about learning from experience, where expected values can be approximated by sample means
Play a bunch of episodes, gather returns, average them 
\begin{align}
        V(s) = E[G(t)|S(t)=s] \approx \frac{1}{N} \sum_{i=1}^{N} G_{i,s}
\end{align}

It gives us only Value function for the states that we met.
And the problem is that :
- it won't always work.
- requires many episodes.
- don't work on not episodic task.
- the episode might never end if it bumps into a wall.
- agent won't do it again, since policy choose argmax.
- it can leave many states unexplored ( one possible solution is the "random start" or the "epsilon-greedy" method)

## Temporal Difference Learning (TD) :
- Unique to RL
- MC: Sample returns based on an episode
- TD : Estimate returns based on current value function estimate
- We looked at TD(0).
- Instead of using G (which is the sampled return ), we use $ r + \gamma V(s') $ which estimates the return from the next state and onward r.
- Its like calculating the mean ( which is space consuming because we need to store all of the samples episodes ) but in a more optimized way : we can calculate current sample mean from last sample mean.
\begin{align}
V_t (s) = V_{t-1} (s) + frac{1}{t} [G_t - V_{t-1} (s)] = \frac{1}{t} \sum_{t'=1}^{t} G_{t'}
\end{align}

Which can be generalized like that (looking like Gradient Descent) :
\begin{align}
V(s) = V(s) + \alpha [G - V(s)]
\end{align}

**TD(0)**
- Instead of using G, we us current reward r and the next state value V(s)
- We only need to wait t+1 to update value for state at time t while MC need to wait the until the end of entire episode.

**TD Control**
\begin{align}
Q(s, a) \leftarrow Q(s, a) + \alpha [r + \gamma max_{a'} Q(s',a') - Q(s,a)]
\end{align}

But those methos do now work on larger problems with billions of states and actions ( because here we use a dictionary of state/action ), that's why we will need approximation methods

- Knowing that supervised-learning is used a function approximator
- We want to estimate V(s) or Q(s, a) :
\begin{align}
Input : x = \phi (s), Target : G
\end{align}

- Since reward is a real number, so is G, therefore we do regression, and the appropriate loss is a squared error 
\begin{align}
E = \sum_{n=1}^{N} (G_n - V ( \phi ( S_n); 0))^2
\end{align}

- we need a differentiable model so we can use gradient descent 
\begin{align}
V ( \phi ( S_n);\theta) = \theta^T \phi (S_n)
\end{align}

- $\theta$ is the model parameter, so that's what we need to update
\begin{align}
\theta = \theta - \alpha ( \frac{\delta E}{\delta \theta} ) = \theta + \alpha (G - V) \phi(S)
\end{align}


```python

```

4986ce38e86d9d506074db83f2a7ebe96b243962
ipynb
Jupyter Notebook
Advanced AI : Deep Reinforcement Learning UDEMY/Introduction.ipynb
raysr/Deep-Reinforcement-Learning-Notebooks
a7e988205bb21a2bf6972cf51bbd46d624ecf9ef
MIT
2019-02-08T14:39:17.000Z
2019-03-22T01:03:25.000Z
Advanced AI : Deep Reinforcement Learning UDEMY/Introduction.ipynb
raysr/Gym-Deep-Q-Agents
a7e988205bb21a2bf6972cf51bbd46d624ecf9ef
MIT
Advanced AI : Deep Reinforcement Learning UDEMY/Introduction.ipynb
raysr/Gym-Deep-Q-Agents
a7e988205bb21a2bf6972cf51bbd46d624ecf9ef
MIT
2021-03-04T14:48:55.000Z
2021-03-04T14:48:55.000Z
Qwen/Qwen-72B
1. YES
2. YES