Temporal-Difference (TD) Learning

here only TD(0)

Temporal-Difference Learning

• TD methods learn directly from episodes of experiments
• TD is model-free: no knowledge of MDP transitions / rewards
• TD learns from incomplete episodes, by bootstrapping
• TD updates a guess towards a guess

TD-Predition

from [SuBa] 6.1 TD Prediction

General Rule: We move the estimate towards the target:

$$ \text{newEstimate} \leftarrow \text{oldEstimate} + \alpha (\text{Target} - \text{oldEstimate} ) $$

Constant $\alpha$ MC-Update (every visit):

We write $s_t$ as an abbreviation for $S_t = s$ and $s'_{t+1}$ for $S_{t+1}=s'$.

$$ v(s_t) \leftarrow v(s_t) + \alpha (\mathcal R_{t} - V(s_t)) $$

with

• $\mathcal R_t$: actual return following time $t$
• $v(s_t)$: Value function of the state at time $t$

TD-Update for $v$:

Update value $v(s_t)$ towards estimated return $R_{t+1} + \gamma V(s_{t+1})$:

$$ v(s) \leftarrow v(s) + \alpha \left(R_{t+1} + \gamma V(s'_{t+1}) - V(s_t)\right) $$

with

• $R_{t+1}$: reward after

• $v(s_t)$: Value function of the state at time $t$

• $R_{t+1} + \gamma V(s_{t+1})$ is called the TD target

• $\delta_t = R_{t+1} + \gamma V(s_{t+1}) - V(s_t)$ is called the TD error

Bootstrapping: update is based partially on an existing estimate.

TD methods combine the sampling of Monte Carlo with the bootstrapping of DP.

import numpy as np

import matplotlib.pyplot as plt
%matplotlib inline

import gym
env = gym.make('FrozenLake-v0')
env.action_space

[2016-11-25 10:59:55,816] Making new env: FrozenLake-v0

Discrete(4)

env.observation_space

Discrete(16)

env.reset()

0

env.step(0)

(0, 0.0, False, {'prob': 0.3333333333333333})

env.step(1)

(1, 0.0, False, {'prob': 0.3333333333333333})

# generate a random 
pi = np.random.dirichlet(np.ones(4), size=16)
pi.shape

(16, 4)

nb_episodes = 500000
alpha = 0.05
gamma = 0.9

v = np.zeros(16)
for i in range(nb_episodes):
    done = False
    observation = env.reset()
    while not done:
        # sample an action from the prob distribution of the observation 
        action = np.random.choice(4, 1, p=pi[observation])
        new_observation, reward, done, info = env.step(action[0])
        v[observation] = v[observation] + alpha * (reward + gamma * v[new_observation] - v[observation])
        observation = new_observation

v

array([ 0.00252811,  0.00301464,  0.00904892,  0.00196215,  0.00304672,
        0.        ,  0.01552929,  0.        ,  0.01167169,  0.04485331,
        0.08182545,  0.        ,  0.        ,  0.14350985,  0.39562114,  0.        ])

Read:

• 6.2 Advantages of TD Prediction Methods
• 6.3 Optimality of TD(0)

Sarsa - On Policy TD Control

SARSA: State-Action Reward State-Action

Read:

• 6.4 Sarsa: On-Policy TD Control

TD-Update for $q$:

$$ q(s_t, a_t) \leftarrow q(s_t, a_t) + \alpha \left(R_{t+1} + \gamma q\left(s'_{t+1}, \pi(s')\right) - q(s_t, a_t) \right) $$

with

• $R_{t+1}$
• $q(s_t, a_t)$: Value function of the state at time $t$

Bootstrapping: update is based partially on an existing estimate.

TD methods combine the sampling of Monte Carlo with the bootstrapping of DP.

def action_epsilon_greedy(q, s, epsilon=0.05):
    if np.random.rand() > epsilon:
        return np.argmax(q[s])
    return np.random.randint(4)

def get_action_epsilon_greedy(epsilon):
    return lambda q,s: action_epsilon_greedy(q, s, epsilon=epsilon)

FrozenLake-v0 defines "solving" as getting average reward of 0.78 over 100 consecutive trials.

def average_performance(policy_fct, q):
    acc_returns = 0.
    n = 500
    for i in range(n):
        done = False
        s = env.reset()
        while not done:
            a = policy_fct(q, s)
            s, reward, done, info = env.step(a)
            acc_returns += reward
    return acc_returns/n

nb_episodes = 200000

STEPS = 2000

# SARSA: On-policy TD control algorithm
def sarsa(alpha = 0.02, 
              gamma = 1., 
              epsilon = 0.05,
              q = None, 
              progress = None, 
              env=env):
    
    if q is None:
        q = np.ones((16,4)) 
    
    for i in range(nb_episodes):
        done = False
        s = env.reset()
        a = action_epsilon_greedy(q, s, epsilon=epsilon)
        while not done:
            new_s, reward, done, info = env.step(a)
            new_a = action_epsilon_greedy(q, new_s, epsilon=epsilon)
            q[s, a] = q[s, a] + alpha * (reward + gamma * q[new_s, new_a] - q[s, a])
            s = new_s
            a = new_a
        
        # only for plotting the performance, not part of the algorithm 
        if progress is not None and i%STEPS == 0:
            progress[i//STEPS] = average_performance(get_action_epsilon_greedy(epsilon), q=q)
    return q, progress

param_performance = dict()
for param in np.arange(0.01, 0.11, 0.02):
    progress = np.zeros((nb_episodes//STEPS))
    _, param_performance[str(param)] = sarsa(epsilon=param, progress=progress)
    print ("done:", param)

done: 0.01
done: 0.03
done: 0.05
done: 0.07
done: 0.09

def plot_performance(performance):
    nb_plots = len(performance)
    plt.figure(figsize=(10,20))
    plt.suptitle("Learning progress depending on epsilon")
    for i, perf in enumerate(sorted(performance)):
        plt.subplot(nb_plots, 1, i+1)
        plt.plot(STEPS * np.arange(nb_episodes//STEPS), performance[perf], label=perf)
        plt.xlabel("epochs")
        plt.ylim(-0.01,0.7)
        plt.ylabel("average reward of an epoch")
        plt.legend()

plot_performance(param_performance)

As you can see the larger $\epsilon$ the faster is the learning. But the larger the $\epsilon$ the lower is the average reward per episode.

A hack could be to use at the end the greedy policy. But keep in mind, that we have not estimated the q-values of the greedy policy. So this can be problematic in more elaborate environments.

sarsa_performance = np.ndarray(nb_episodes//STEPS)
q, sarsa_performance = sarsa(progress=sarsa_performance)

plt.plot(STEPS*np.arange(nb_episodes//STEPS), sarsa_performance)
plt.xlabel("epochs")
plt.title("Learning progress for SARSA")
plt.ylabel("average reward of an epoch")

<matplotlib.text.Text at 0x10b015a90>

def greedy_policy(q, s):
    return np.argmax(q[s])
print(average_performance(greedy_policy, q=q)) 

0.838

Q-Learning - Off Policy Control

Read [SuBa] 6.5 Q-Learning: Off-Policy TD Control

Update rule:

$$ q(s_t, a_t) \leftarrow q(s_t, a_t) + \alpha \left(R_t + \gamma \cdot \text{arg}\max_{a'} \left(q\left(s'_{t+1}, a'\right)\right) - q(s_t, a_t) \right) $$

Here:

• estimation policy is greedy
• behaviour policy is $\epsilon$-greedy

q = np.ones((16, 4)) # optimism
#q = - np.ones((16, 4)) # pessimism 
#q = np.random.rand(16, 4) * 2. - 1. # random
#q = np.zeros((16, 4)) 

nb_episodes = 500000
STEPS=5000
alpha = 0.001
gamma = 1.
epsion = 0.05

q_performance = np.ndarray(nb_episodes//STEPS) 

# Q-Learning: Off-policy TD control algorithm
for i in range(nb_episodes):
    done = False
    s = env.reset()
    while not done:
        a = action_epsilon_greedy(q, s) # behaviour policy 
        new_s, reward, done, info = env.step(a)
        a_max = np.argmax(q[new_s]) # estimation policy 
        q[s, a] = q[s, a] + alpha * (reward + gamma * q[new_s, a_max] - q[s, a])
        s = new_s
        
        
    # for plotting the performance    
    if i%STEPS == 0:
        q_performance[i//STEPS] = average_performance(greedy_policy, q)

plt.plot(STEPS * np.arange(nb_episodes//STEPS), q_performance)
plt.xlabel("epochs")
plt.ylabel("average reward of an epoch")
plt.title("Learning progress for Q-Learning")

<matplotlib.text.Text at 0x10b0384e0>

average_performance(greedy_policy, q)

0.828

Exercises:

• Study the dependence in the FrozenLake-environment for q-learning and Sarsa on
  • the hyperparameters $\alpha$ and $\gamma$
  • the start values of $q$ (Optimism, Zeros, Random, Pessimism)
  • the number of epochs
• Compare Q-Learning, SARSA and Monte Carlo Control for the FrozenLake-environment

Bias/Variance Trade-Off

• return $G_t = R_{t+1}+ \gamma R_{t+2} + \dots + \gamma^{T-1}R_T$ is unbiased estimate of $v_\pi(S_t)$
• true TD target $R_{t+1} + \gamma v_\pi (S_{t+1})$ is unbiased estimate of $v_\pi(S_t)$
• TD target $R_{t+1} + \gamma V_\pi (S_{t+1})$ is biased estimate of $v_\pi(S_t)$
• TD target is much lower variance than the return:
  • return depends on many random actions, transitions, rewards
  • TD target depends on one random action, transition, reward

Advantages and Disadvantages of MC vs. TD

• TD can learn before knowing the final outcome
  • TD can learn online after every step
  • MC must wait until end of episode before return is known
• TD can learn without the final outcome
  • TD can learn from incomplete sequences
  • MC can only learn from complete sequences
  • TD works in continuing (non-termiating) environments
  • MC only works for episodic (terminating) environments

Bias/Variance Trade-Off

• return $G_t = R_{t+1}+ \gamma R_{t+2} + \dots + \gamma^{T-1}R_T$ is unbiased estimate of $v_\pi(S_t)$
• true TD target $R_{t+1} + \gamma v_\pi (S_{t+1})$ is unbiased estimate of $v_\pi(S_t)$
• TD target $R_{t+1} + \gamma V_\pi (S_{t+1})$ is biased estimate of $v_\pi(S_t)$
• TD target is much lower variance than the return:
  • return depends on many random actions, transitions, rewards
  • TD target depends on one random action, transition, reward

Advantages and Disadvantages of MC vs. TD (2)

• MC has high variance, zero bias
  • good convergence properties
  • (even with function approximation)
  • not very sensitive to initial value
  • very simple to understand and use
• TD has low variance, some bias
  • usually more efficent than MC
  • TD(0) converges to $V_\pi(s)$
  • (but not always with function approximation)
  • more sensitive to initial values

Certainty Equivalence

• MC converges to solution with minimum mean-squared error
  • best fit to the observed returns $$ \sum_{k=1}^K \sum_{t=1}^{T_k} \left(g_t^k - V(s_t^k)\right)$$
• TD(0) converges to solution of max likelihood Markov model
  • solution to the MDP $\left< \mathcal S, \mathcal A, \mathcal{\hat P}, \mathcal{\hat R}, \gamma \right>$ that best fits the data $$ \mathcal{\hat P^a_{s,s'}} = \frac{1}{N(s,a)}\sum_{k=1}^{K}\sum_{t=1}^{T_k}\mathbb 1(s_t^k, a_t^k,s_{t+1}^k=s,a,s') $$ $$ \mathcal{\hat R^a_{s,s'}} = \frac{1}{N(s,a)}\sum_{k=1}^{K}\sum_{t=1}^{T_k}\mathbb 1(s_t^k, a_t^k=s,a)r_t^k $$

Advantages and Disadvantages of MC vs. TD (3)

• TD exploits Markov property
  • usually more efficient in Markov environments
• MC does not exploid Markov peoperty
  • usually more effective in non-Markov environments

Bootstapping and Sampling

• Bootstrapping: update involves an estimate
  • MC does bootstrap
  • DP bootstraps
  • TD bootstraps
• Sampling:
  • MC samples
  • DP does not sample
  • TD samples

Literature:

• [SuBa] Sutton, Richard S., and Andrew G. Barto. Introduction to reinforcement learning. Vol. 135. Cambridge: MIT Press, 1998.
• Szepesvári, Csaba. "Algorithms for reinforcement learning." Synthesis lectures on artificial intelligence and machine learning 4.1 (2010): 1-103.
• D. Silver. UCL Course on RL