Markov decision processes formally describe an environment for Reinforcement Learning when the environment is fully observable. |
Resources
Prediction
These methods estimate the value function of an unknown MDP.
Monte Carlo
- Learns directly from complete episodes of experience. Caveat: all episodes must terminate
- Uses the concept 'value = empirical mean return'
- Goal is to learn
from episodes of experience under policy 
- Challenges:
- Make sure we visit all states over our episodes enough times sufficient for a mean to be approaching a limit
Method
- Gather a set of episodes and run over each of them
- Each time a state is visited:
- Increment a counter
- Increment the total return for the state
- Value is estimated by the mean return
- By the law of large numbers
as 
The increments can be done on first visits only, or on every visit and the limiting results will still hold. Why one or the other?
Typically the value function is estimated and updated on the fly with incremental mean calculations:
V(S_t) \leftarrow V(S_t) + \frac{1}{N(S_t)} ( G_t - V(S_t)) |
or over a moving window (slowly forget old episode contributions):
V(S_t) \leftarrow V(S_t) + \alpha ( G_t - V(S_t)) |
Temporal Difference Learning
Fundamentally different from Monte Carlo in that incomplete episodes are permissable. For the remainder of the return, a guess is provided to bootstrap the calculations.
\begin{align}
V(S_t) &\leftarrow V(S_t) + \alpha ( G_t - V(S_t)) \\
&\leftarrow V(S_t) + \alpha ( R_{t+1} + \gamma V(S_{t+1}) - V(S_t)) \\
\end{align} |
- TD Target - is the estimated return
, this is considered a biased estimate as opposed to the Monte Carlo method- There are specific cases where the bias causes misbehaviour
- True TD Target - is the estimated return
, this is considered an unbiased estimate - Exploits the Markov Properties of the system (i.e. uses some knowledge about the system to provide a biased estimate.
- Lends to an increased efficiency.
- TD(lambda) - allows you to choose how far ahead to use returns before using a biased estimate (moving between shallow and deep backups).
Comparisons
| Property | Dynamic Programming | Monte Carlo | TD |
|---|
| Episodes | No | Yes, terminating | Yes, may be incomplete |
| Bootstrapping | Yes | No | Yes |
| Sampling | No | Yes | Yes |
| Initial Value | Not sensitive | Not sensitive | Sensitive |
| Bias | No Bias | No Bias | Bias estimate |
| Nosie/Variance | None | Lots (many R's in the measured G_t) | Low (one R before the bias estimate) |
| Batching | - | Converges to a best fit for the observations | Converges to a max likelihood given all the data |
|
| More effective in non-Markov environments | More efficient in Markov environments |
Control
How can we find the optimal value function and subsequently policy? The algorithms are mostly concerned with On/Off Policy Monte Carlo and Temporal-Difference learning.
- On Policy - 'learning while on the job'
- Learn about policy from experience sampled from
- Off Policy - 'look over someone else's shoulder', e.g. robot looking at a human
- Learn about policy from experience sampled from
On-Policy Monte-Carlo Iteration
Basic premise is to apply the same process that dynamic programming uses to greedily improve the policy.
But this has two problems:
- Value Function: extracting the policy from the value function requires knowledge of the transition dynamics,
- Solution: use Q instead of V since it doesn't need to know the transitions
\pi'(s) = argmax_{a \in A} \mathcal{R}^a_{s} + \mathcal{P}^a_{ss'}V(s') \hspace{1cm} \rightarrow \hspace{1cm} \pi'(s) = argmax_{a \in \mathcal{A}} Q(s,a) |
- Policies: no guarantee that the greedy policy improvements generate policies that can sufficiently explore the space
- Solution: introduce some randomness to the greedy update (note m is the number of actions to be tried) ... epsilon-greedy!
- This satisfies the policy improvement theorem, i.e. everything gets better
- Hard to do better than this naive method
\pi(a|s) = \begin{cases}
\epsilon/m + 1 - \epsilon & \mathrm{if} \; a^* = argmax_{a \in A} Q(s,a) \\
\epsilon/m & \mathrm{otherwise} \\
\end{cases}
|
- Improvements
- Update the policy after every episode, speedup!
- Greedy in the Limit with Infinite Exploration (GLIE)
- All state-action pairs are explored infinitely many times
- The policy converges ona greedy policy
- Guarantee GLIE
- Evaluation: Something to do with sampling and counting?
- Improvement: Make sure epsilon goes to zero as the update count goes up
On-Policy TD (Sarsa)
- Convergence - guaranteed if policies are GLIE and step sizes satisfy the Robbins-Munro properties for a sequence
- Robbins-Munro -
, 
- Can consider n-step returns as we did for TD prediction, what is the best n to use? Sarsa(lambda)! Also can utilise eligibility traces
The lambda approach can help you update more quickly over one episode. See below.
Off-Policy Learning
Goal
- Evaluate target policy
to compute 
or 
while following behaviour policy 
Why?
- Learn from watching humans
- Re-use experience generated from old policies - cache/batch old episodes
- Learn about optimal policy while following exploratory policy - make sure we explore the state space sufficiently
- Learn about multiple policies while following one policy
- Importance Sampling - has high variance (noise) for Monte-Carlo, but can be made to work for TD.
- Target Policy - is the policy we are trying to optimise
- Behaviour Policy - is the policy we are trying to improve
Off-Policy Q-Learning
Take the next step from the observed policy, but then consider bootstrapping the rest from the optimal policy
- Next action:
- Alternative successor action:
- Update towards value of the alternative action:
Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha(R_{t+1} + \gamma Q(S_{t+1}, A') - Q(S_t, A_t)) |
- Is the reward the reward gained from
?
