### Terminology and notation

#### Inputs
- $ s_t $ - state 
- $ o_t $ - observation
- $ a_t $ - action

#### Outputs
- $ \pi_\theta(a_t|o_t) $ - policy
- $ \pi_\theta(a_t|s_t) $ - policy (fully observed)

### Mappings
- $ r(s, a) $: reward function

### Markov Decision Processes

#### Markov chain
- $ M = \{S, T\} $
- $ S - $ state space, states $ s \in S $ (discrete or continuous)
- $ T - $ transition operator, transition probability, dynamics function, $ p(s_{t+1}|s_t) $
    - let $ \mu_{t, i} = p(s_t = i) $ $ \vec{\mu_t} $ is a vector of probabilities
    - let $ T_{i, j} = p(s_{t+1}=i \lvert s_t = j) $, then $ \vec{\mu_{t+1}} = T\vec{\mu_t}$
    - T is a linear operator applied on the current vector of state probabilities to produce the next vector of state\                 probabilities. (2d matrix)

#### Markov property
- Given $ s_t $, $ s_{t+1} $ is independent of $ s_{t-1} $

- Markov chain by itself does not allow us to specify a decision making problem because there is no notion of actions.\
    (pioneered in 1950s.)
    
    
#### Markov Decision Process
- $ M = \{S, A, T, r\} $
- $ S - $ state space, states $ s \in S $ (discrete or continuous)
- $ A - $ action space, actions $ a \in A $ (discrete or continuous)
- $ T - $ transition operator, transition probability, dynamics function, $ p(s_{t+1}|s_t, a_t) $ (now a tensor, 3d matrix)
- $ r - $ reward function, $ r: S x A \rightarrow \mathbb{R} $
    


#### Parially observed Markov Decision Process
- $ M = \{S, \mathcal{A}, \mathcal{O}, T, \mathcal{E}, r\} $
- $ S - $ state space, states $ s \in S $ (discrete or continuous)
- $ \mathcal{A} - $ action space, actions $ a \in \mathcal{A} $ (discrete or continuous)
- $ \mathcal{O} - $ observation space, observations $ o \in \mathcal{O} $ (discrete or continuous)
- $ T - $ transition operator, transition probability, dynamics function, $ p(s_{t+1}|s_t, a_t) $ (now a tensor, 3d matrix)
- $ \mathcal{E} - $ emission probability $ p(o_t|s_t)$
- $ r - $ reward function, $ r: S x \mathcal{A} \rightarrow \mathbb{R} $
    
- We will be making decisions based on observations without access to the true states.



### The goal of reinforcement learning

#### To learn a policy
- $ \pi_{\theta}(a|s): s \rightarrow a $

#### Simulate environment dynamics to produce the next state
- $ p(s^{'}| s, a): s, a \rightarrow s^{'} $

#### Joint  probability distribution over states and actions (trajectory distribution) for a finite time horizon
- $ p_\theta(s_1, a_1, \dots, s_T, a_T )$ = $ p(s_1) \prod\limits_{t=1}^T \pi_\theta(a_t|s_t)p(s_{t+1}|s_t, a_t)$

#### Optimal policy
- $ \theta^{\star} = arg \max\limits_{\theta} E_{T \sim p_{\theta}(\tau) }[\sum\limits_t r(s_t, a_t)] $
- $ \tau $ stands for the trajectory. trajectories are sequences of states and actions.
- $ \theta $ represents the parameter of a neural network.
- expectation accounts for the stochasticity of the policy, transition probabilities, and the initial state distribution.
- expected value under the trajectory distribution of the sum of rewards.

#### Finite horizon case: state-action marginal using augmented  markov state
\begin{align}
\theta^{\star} = arg \max\limits_{\theta} E_{T \sim p_{\theta}(\tau) }\left[ \sum\limits_t r(s_t, a_t) \right]
\end{align}

\begin{eqnarray*}
\theta^{\star} = arg \max\limits_{\theta} \sum\limits_t E_{(s_t, a_t) \sim p_{\theta}(s_t, a_t) }\left[ r(s_t, a_t) \right]
\end{eqnarray*}

#### Infinite horizon case: stationary distribution
\begin{eqnarray*}
\theta^{\star} = arg \max\limits_{\theta} \sum\limits_{t=1}^T E_{(s_t, a_t) \sim p_{\theta}(s_t, a_t) }\left[ r(s_t, a_t) \right]
\end{eqnarray*}

- Assumptions
    - ergodicity
    - $\mu = T\mu, (T-I)\mu = 0$
    - $\mu$ is eigenvector of T with eigenvalue 1!

### Expectations and stochastic systems
- In reinforcement learning, we almost always care about increasing expected values (expectations).
- Why reinforcement learning algorithms can optimize non-smooth reward functions?
    - mainly because the expected values of non-smooth reward functions are smooth in $ \theta $. (How?)

### Reinforcement Learning Algorithms

#### The anatomy of a reinforcement learning algorithm
- Always contain three basic parts
    1. Generate samples (i.e. run the policy) - trial stage.\
        (sample trajectories from the trajectory distribution, typically the one induced by our policy) 
    2. Fit a model/ estimate the return. (either model-based (dynamics) or implicit model (value-function))
    3. Improve the policy. (Change the policy to make it better.)
- Examples - Different incarnations of the second and third stage 
    1. (Policy gradient)
        - Run policy $ \rightarrow $ Evaluate policy $ \rightarrow $ Improve policy
        - generate trajectories $ \rightarrow $ sum up the rewards $ \rightarrow $ try to make good trajectories be more likely.\
        calculate and apply gradients.
    2. RL by backprop (Model-based)
    


### Types of algorithms
1. Policy gradients: directly differentiate the above objective
2. Value-based: estimate value function or Q-function of the optimal policy (no explicit policy)
3. Actor-critic: estimate value function or Q-function of the current policy, use it to improve policy.
4. Model-based RL: estimate the transition model, and then
    - use it for planning (no explicit policy)
        - Trajectory optimization/optimal control (primarily in continuous spaces) - essentially backpropagation to optimize\
            actions
        - Discrete planning in discrete action spaces - e.g., Monte Carlo tree search
    - use it to improve a policy (backpropogate gradients)
        - Requires some tricks to make it work
    - use the model to learn a value function
        - Dynamic Programming
        - Generate simulated experience for model free learner.
    - something else

#### Rollout, sample the policy i.e. run the policy one step at a time.

### Tradeoffs between algorithms
(Why can't we just learn one RL algorithm that works for all tasks)\
- Different tradeoffs
    - Sample efficiency: How many samples do we need from orange box
    - Stability and ease of use: Multiple hyperparameters to select
- Different assumptions
    - Stochastic or deterministic?
    - Continuous or discrete?
    - Episodic or infinite horizon?
- Different things are easy or hard in different settings
    - Easier to represent the policy?
    - Easier to represent the model?
    
#### Sample Efficiency
- How many samples do we need to get a good policy?
- Most important question: Is the algorithm off policy?
    - Off policy: able to improve the policy without generating new samples from that policy
    - On policy: each time the policy is changed, even a little bit, we need to generate new samples
    

##### Why would we use a less efficient algorithm?
Wall clock time is not the same as efficiency!

#### Stability and ease of use
- Does it converge?
- And if it converges, to what?
- And does it converge every time?

Why is any of this even a question???
- Supervised learning: almost always gradient descent
- Reinforcement learning: often not gradient descent

#### Comparison: assumptions
- common assumption #1: full observability
    - generally assumed by value function fitting methods
    - can be mitigated by adding recurrence
- common assumption #2: episodic learning
    - Often assumed by pure policy gradient methods
    - assumed by some model-based RL methods
- common assumption #3: continuity or smoothness
    - Assumed by some continuous value function learning methods
    - Often assumed by some model-based RL methods

### Examples of algorithms
1. Value-based: estimate value function or Q-function of the optimal policy (no explicit policy)
    - Q-learning, DQN
    - Temporal difference learning
    - Fitted value iteration
2. Policy gradients: directly differentiate the above objective
    - REINFORCE
    - Natural policy gradient
    - Trust region policy optimization (TRPO)
    - Proximal Policy Optimization (PPO)
3. Actor-critic: estimate value function or Q-function of the current policy, use it to improve policy.
    - Asynchronous advantage actor-critic (A3C)
    - Soft actor-critic (SAC)
    - DDPg
4. Model-based RL: estimate the transition model, and the then
    - Dyna
    - Guided policy search


```python

```

ipynb
14892fe90dbe6b53b83dee67c32306607b50d0f0
Jupyter Notebook
97c648f119debf98f951a69aac6c0d626007c2b6
MIT
mohankumarSriram/bob-the-robot
notebooks/rl_basics.ipynb
97c648f119debf98f951a69aac6c0d626007c2b6
MIT
mohankumarSriram/bob-the-robot
notebooks/rl_basics.ipynb
97c648f119debf98f951a69aac6c0d626007c2b6
MIT
mohankumarSriram/bob-the-robot
notebooks/rl_basics.ipynb