Markov decision processes formally describe an environment for Reinforcement Learning when the environment is not observable.

---

Resources

• David Silver's Course Slides: '15
  
  • 01 - Introduction (slides, video)
  • 02 - Markov Decision Processes (slides, video)
  • 03 - Dynamic Programming (slides, video)
  • 04 - Model Free Prediction (slides, video)
  • 05 - Model Free Control (slides, video)

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 
  • Often faster to implement with incremental means
• 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:

or  over a moving window (slowly forget old episode contributions):

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.

• 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

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

• 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

• 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:

• Is the reward the reward gained from ?
• Use an epsilon-greedy policy for the behavioural policy (exploration) and greedy policy for target policy (optimal)