# CS 530 - Lecture 14

## Temporal Difference Learning

Bernhard Firner

2026-03-12

---

## Reading

* Chapter 6 in Sutton and Barto's reinforcement learning book

---

## Review

* Last time we had fun with Monte Carlo policy search
* Key words: on-policy, off-policy, soft-policy, behavior policy, target policy

---

## Off-Policy Motivation

* If we are okay randomly starting in every single state then we can always run our target policy, $\pi$
  * We need to do random starting to guarantee that all states are explored
  * This is called **on-policy** search
* But what if we don't want to randomly start in every possible location?
  * We explore with a different policy, which is **off-policy search**

---

## Off-Policy Problem

* A **soft policy** is like our target policy, $\pi$, but with probability $\epsilon$ it take a random action
* If $\epsilon$ is too large, we'll keep falling into the cliff, so safer paths seem better
* So we want to use one policy to search and learn a different policy

</div>
<div class="col">

<img style="width: 60%" class="r-stretch" src="./figures/RLBook/ch6_cliff_walking_top.png" />
<br/>
<small>Cliff walking example from Sutton and Barto</small>

</div>
</div>

---

## Behavior Policy

* We will search using a behavior policy, $b$, rather than $\pi$
  * Coverage: if $\pi(a|s) > 0$ then $b(a|s) > 0$
  * If that holds, then b's exploration should be sufficient
* But when we finish an episode, should the target policy actually use b's gain values?
  * No, b may be jumping off of a cliff!

---

## Importance Sampling Ratio

$ \rho_{t:T-1} = \prod_{k=t}^{T-1}\frac{\pi(A_k|S_k)}{b(A_k|S_k)}$

* The importance sampling ratio gives a weight to anything discovered by off-policy search
* If $\pi(A_k|S_k)$ is 0, then the target policy would never choose that action, so the importance is 0
  * For example, if $\pi$ would never jump off of the cliff, and $b$ does, then we ignore that sequence

---

## Weighting

* If we weight the observed reward in each state merely the number of times the state has been observed, we could end up with absurd values
  * In fact, if a loop is present then our variance is infinite
* So we bias our gain estimates towards b's rewards instead
  * The statistics are better, even if they are technically incorrect

---

## Weighted Importance Sampling

* $ U(s) \triangleq \frac{\Sigma_{t\in \tau(s)} \rho_{t:T(t)}G_t}{\rho_{t:T(t)}}$
  * If $\rho = 0$ we still treat this as 0
  * Otherwise we normalize by the total importance of the chain from t to T

---

## Off-Policy MC Control

* Here's our learning loop for each episode:
<small>

* $G \leftarrow 0$
  * $W \leftarrow 1$
  * Complete the episode, using $b$
</small>

* Loop from $t=T-1, T-2, ..., 0:$
    * $G \leftarrow \gamma G + R_{t+1}$
    * $C(S_t,A_t) \leftarrow C(S_t,A_t) + W$
    * $Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \frac{W}{C(S_t,A_t)}[G - Q(s_t,A_t)]$
    * $\pi(S_t) \leftarrow \underset{a}{argmax}Q(S_t,a)$
    * If $A_t \neq \pi(S_t) $ then break
    * Else $W \leftarrow \frac{1}{b(A_t|S_t)}$

---

## Great! Sometimes!

* Recall that this worked on some racetracks
  * But didn't work on a more difficult one
* We would need to keep tuning $\epsilon$ to see if random exploration could reach the end
  * And then mess with the initial estimates for the values in Q
  * Reaching the end should see much better than wandering aimlessly

---

## Learning

* This shows the maxQ during MC policy search on racetrack 1
* Obviously there is a high reward at the end, but a high reward path should also exist

</div>
<div class="col">

</div>
</div>

---

## Learning Issue

* We can't learn anything from actions that $\pi$ wouldn't take
  * So we begin by learning about the area near the goal
  * But $\pi$ won't help guide us there until later
* So exploration is inefficient

</div>
<div class="col">

</div>
</div>

---

## More Difficult Map

* Track 2 is more difficult
* Notice how we've explored the entire track?
  * We are basically bumbling along until we hit a "trained" path to the goal
* But $\epsilon$ needs to be high since our policy isn't helping

</div>
<div class="col">

</div>
</div>

---

## Impossible Map

* Monte Carlo policy search takes an unbearably long time on racetrack 4
  * If we gave it more time, or tweaked things, or both, maybe it can be faster
* But can't we come up with a better algorithm?

</div>
<div class="col">

</div>
</div>

---

## Learning While Exploring

* Let's pretend that you were in a maze
* You want food, so every minute you sit around not eating you get a reward of -1
  * What do you do?

---

## Monte Carlo Approach

* If you were a Monte Carlo monster, you would bumble around, feeling a default way about everything until you found your first apple pie
  * But that's crazy!
* If you've wandered around the same room for 10 minutes and haven't found something, you should feel bad about the room!
* We should be able to start learning *immediately*

---

## Temporal Difference Learning

* Let's just update our utility estimates after every step
  * $U(S_t) \leftarrow U(S_t) + \alpha[R + \gamma U(S_{t+1}) - U(S_t)]$
* This is the same moving average estimate as before, but we immediately incorporate the reward
  * The rest is just an estimate, which we'll refine as we go
  * So this is a form of bootstrapping
* But where do we get the initial utility estimates?

---

## Initial Utility Estimates

* These don't really matter
* Think back to that room
  * If you start off positive, and then wander around without finding food, the -1 rewards will quickly make utility estimates negative
  * If you start off negative about everything, then you'll still wander around and become even more negative
* Either way, the unknown areas outside of the room will seem (relatively) more attractive

---

## Initial Estimates

* Only relative utility values matter
* If you are incredibly over-optimistic about everything, then you will explore too much
  * So your initial estimates should be less than your target rewards
    * That means < 0 for our racetrack

---

## Equivalence

* Is this mathematically the same as the Monte Carlo approach?

<p><math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mtable><mtr><mtd columnalign="right" style="text-align: right"><msub><mi>u</mi><mi>π</mi></msub><mrow><mo stretchy="true" form="prefix">(</mo><mi>s</mi><mo stretchy="true" form="postfix">)</mo></mrow></mtd><mtd columnalign="left" style="text-align: left"><mo>≜</mo><msub><mi>𝔼</mi><mi>π</mi></msub><mrow><mo stretchy="true" form="prefix">[</mo><msub><mi>G</mi><mi>t</mi></msub><mo stretchy="false" form="prefix">|</mo><msub><mi>S</mi><mi>t</mi></msub><mo>=</mo><mi>s</mi><mo stretchy="true" form="postfix">]</mo></mrow></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><msub><mi>𝔼</mi><mi>π</mi></msub><mrow><mo stretchy="true" form="prefix">[</mo><msub><mi>R</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>+</mo><mi>γ</mi><msub><mi>G</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo stretchy="false" form="prefix">|</mo><msub><mi>S</mi><mi>t</mi></msub><mo>=</mo><mi>s</mi><mo stretchy="true" form="postfix">]</mo></mrow></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"></mtd><mtd columnalign="left" style="text-align: left"><mo>=</mo><msub><mi>𝔼</mi><mi>π</mi></msub><mrow><mo stretchy="true" form="prefix">[</mo><msub><mi>R</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>+</mo><mi>γ</mi><msub><mi>u</mi><mi>π</mi></msub><mrow><mo stretchy="true" form="prefix">(</mo><msub><mi>S</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo stretchy="true" form="postfix">)</mo></mrow><mo stretchy="false" form="prefix">|</mo><msub><mi>S</mi><mi>t</mi></msub><mo>=</mo><mi>s</mi><mo stretchy="true" form="postfix">]</mo></mrow></mtd></mtr></mtable><annotation encoding="application/x-tex">
\begin{align*}
u_{\pi}(s) &\triangleq \mathbb{E}_{\pi}[G_t | S_t = s] \\
         &= \mathbb{E}_{\pi} [R_{t+1} + \gamma G_{t+1} | S_t = s] \\
         &= \mathbb{E}_{\pi} [R_{t+1} + \gamma u_{\pi}(S_{t+1}) | S_t = s]
\end{align*}
</annotation></semantics></math></p>

* The first line is the Monte Carlo version, with estimates coming from $G_t$ of each episode
* The last is the temporal difference (TD) version
  * So their expectations should converge

---

## TD Error

* The TD estimate obviously has an error
* If our estimate were exactly correct, then
  * $V(S_t) = R_{t+1} + \gamma V(S_{t+1})$
* But our value estimates will be slightly wrong
  * $\delta_t \triangleq R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$
* We learn from that error, and the sum of errors over an entire episode will be equivalent to Monte Carlo's gain

---

## Why TD

* If they are mathematically the same, why would we use TD?
  * Because it can make better estimates with less data
* Consider a world with two states, A and B
* You make 8 observations

<small>
<table>
<tr><td>Episode</td><td>State</td><td>Reward</td><td>State</td><td>Reward</td></tr>
<tr><td>1</td><td>A</td><td>0</td><td>B</td><td>0</td></tr>
<tr><td>2</td><td>B</td><td>1</td><td></td><td></td></tr>
<tr><td>3</td><td>B</td><td>1</td><td></td><td></td></tr>
<tr><td>4</td><td>B</td><td>1</td><td></td><td></td></tr>
<tr><td>5</td><td>B</td><td>1</td><td></td><td></td></tr>
<tr><td>6</td><td>B</td><td>1</td><td></td><td></td></tr>
<tr><td>7</td><td>B</td><td>1</td><td></td><td></td></tr>
<tr><td>8</td><td>B</td><td>0</td><td></td><td></td></tr>
</table>
</small>

---

## Why TD

* What is the expected reward at state A?
  * Monte Carlo would say 0, since there is a single trial with A
  * TD would say $\gamma\frac{3}{4}$, because A lead to B, which has an expected reward of $\frac{3}{4}$

---

## Errors

* Both approaches are justifiable
  * The Monte Carlo approach has minimal error on the observations
  * TD assumes that this is a Markov process, and has minimal error on *future* data if that assumption is true
* **Try to remember that**

---

## Control with TD

* We want to build better racetracks, so how do we learn a policy with TD?
* There are a few TD algorithms
  * SARSA
  * Q-Learning
  * Expected SARSA
  * Double Q-Learning
* They are all very similar, so let's set up the general for of an algorithm first

---

## Initialization

* Begin by initializing some variables:
  * Set a learning step size, $\alpha \in (0, 1]$
  * Value for a soft policy, $\epsilon > 0$
  * $Q(s,a) \leftarrow \mathbb{R}<0$, but $Q(terminal,*)$ for the finish state is 0
  * $\pi(s), b(s) \leftarrow \underset{a}{argmax}Q(s, a)$ (target and behavior policies)

---

## Episodic SARSA Learning

* Choose a starting state, S
  * Choose action, A, from policy

* Loop until finished:
    * Use A, observe R and S'
    * Choose random A' from policy and S'
    * $Q(S,A) \leftarrow Q(S,A) + \alpha[R + \gamma Q(S', A') - Q(S,A)]$
    * $S \leftarrow S'; A \leftarrow A'$

---

## Notes

* The actions taken do not need to be the optimal ones (according to our policy)
  * Thus we can use this for off-policy estimates
  * For example, we could just choose random actions, the Q estimates will still improve

---

## Episodic Q-Learning

* Choose a starting state, S

* Loop until finished:
    * Choose A from policy and S
    * Use A, observe R and S'
    * $Q(S,A) \leftarrow Q(S,A) + \alpha[R + \gamma \underset{a}{max}Q(S',a) - Q(S,A)]$
    * $S \leftarrow S'$

---

## Notes

* Q-Learning is estimating an optimal target policy, $\pi$

  * The key difference is that $\underset{a}{max}Q(S',a)$ could ignore some actions
  * This is no different than in Monte Carlo, but Q will be updated with each step of the loop

---

## Importance Sampling?

* We don't need it!
* Monte Carlo episodes connected the gain at the end to *every* state, action pair
* With SARSA or Q-Learning, if any step has large negative rewards that is immediately learned
  * Positive rewards do propagate back from the adjacent states

---

## SARSA Vs Q Learning

* Remember this cliff?
  * Q-Learning will attempt to follow $\underset{a}{max}Q(S',a)$
  * This looks at the best we could do in the next state, so we will stay near the cliff
* But we are following the b policy for learning, so we fall off sometimes

</div>
<div class="col">

<img style="width: 60%" class="r-stretch" src="./figures/RLBook/ch6_cliff_walking_top.png" />
<br/>
<small>Cliff walking example from Sutton and Barto</small>

</div>
</div>

---

## SARSA Vs Q Learning

* SARSA updates with $Q(S,A)$ with $R + \gamma Q(S', A') - Q(S,A)$, so every time we falling from the cliff makes the agent averse to the state
* The policy learned from Q-learning is superior

<img style="width: 60%" class="r-stretch" src="./figures/RLBook/ch6_cliff_walking_bottom.png" />
<br/>
<small>SARSA looks better during the episodes.</small>

</div>
<div class="col">

<img style="width: 60%" class="r-stretch" src="./figures/RLBook/ch6_cliff_walking_top.png" />
<br/>
<small>Cliff walking example from Sutton and Barto</small>

</div>
</div>

---

## Expected SARSA

* A fix is to take the epected value for the update
* $Q(S,A) \leftarrow Q(S,A) + \alpha[R + \gamma \mathbb{E}_\pi[Q(S', A') | S'] - Q(S,A)]$
  * This becomes $Q(S,A) + \alpha[R + \gamma \underset{a}{\Sigma}\pi(a|S')Q(S',a) - Q(S,A)]$
* Notice that, for our non-stochastic racecar policies, this will be the same as Q-Learning
  * Because there is only one action chosen with p=1
  * Being a superset, this subsumes and replaces Q-learning (but involves more computation)

---

## Maximization Bias

* One last note, and then we can try this all out!
* Should we be worried about bias?
* Consider a state, $s$, with many possible actions, $a$
  * Let's say that mean of the rewards is 0 or negative, but we've gotten a positive estimate from an early experience
  * If the rewards are stochastic, this could slow down learning

---

## Intuitive Example

* You play the lottery, and one day you win
* You want to return to that winning state, so you associate your prior actions with a high reward
  * Buying a ginger ale, picking particular numbers, etc
* Over time, you should recognize that those actions have nothing to do with winning, but you need time to unlearn that signal

---

## Math Example

* Let's say you begin in state A
  * You have two actions, right (don't play the lottery) and left (play)
* Right always has a reward of 0 and ends the episode
* Left leads to second choices: which lottery, which numbers, etc
  * The terminal state has a negative *average* reward, but there are some positive rewards

---

## More Math

* We use $\underset{a}{max}Q(S',a)$ to update Q(S,A) estimates
  * But once we reach S', perhaps not all actions are available
  * Or perhaps every action is available, but we've assigned positive initial probabilities to some lotteries
* We will have to exhaustively try every option that could be positive until we finally admit that not playing was the only way to win

---

## The Problem

* This is a weakness of using our policy to make decisions and to to estimate the value of the next state
  * Once it has decided that something is good, it keeps doing it until proven wrong
* If this is a problem of bias, then perhaps adding multiple decision makers will resolve it
  * This approach is a bit like ensemble regularization in other ML aproaches

---

## Solution: Double Learning

* Store two estimates of the Q function, $Q_1$ and $Q_2$
* Use the other Q to estimate the value of the actions in the next state
  * $Q_1(S,A) \leftarrow Q_1(S,A) + \alpha[R + \gamma Q_2(S', \underset{a}{argmax}Q_1(S',a)) - Q_1(S,A)]$
  * $Q_2(S,A) \leftarrow Q_2(S,A) + \alpha[R + \gamma Q_1(S', \underset{a}{argmax}Q_2(S',a)) - Q_2(S,A)]$
* The action choice still comes from the updating Q, but the reward comes from the other Q estimate
* They will both converge to the same thing, but this remove potential bias, speeding learning

---

## Racing!

* Now we can return to racing

---

## TD Implementation

```python
####################
# Estimate a policy using Q-Learning
####################

import random
import sys

import numpy
import pickle

import policy_map
import racetrack_sim

def softProbs(target_policy, epsilon, state, actions):
    # Get the probability of the soft policy selecting an action in a state
    # b(A_t|S_t)
    # Our behavioral policy will be similar to the target policy
    # Action probabilities sum to 1, with epsilon distributed over all possible actions
    action_probs = [epsilon / len(actions)]*len(actions)
    action_probs[target_policy[state]] += 1 - epsilon
    return action_probs

def softPolicy(target_policy, epsilon, state, actions):
    # Select from one of the possible actions based upon our behavior policy.
    action_probs = softProbs(target_policy, epsilon, state, actions)
    return random.choices(actions, action_probs, k=1)[0]

if __name__ == "__main__":
    if len(sys.argv) < 2:
        print("This program needs a map as its argument!")
        exit(0)

track = []
    with open(sys.argv[1], 'r') as mapfile:
        for line in mapfile:
            track.append(line[:-1])

# Find all of the starting and finish locations
    starts = [(y, x) for y, row in enumerate(track)
                     for x, val in enumerate(row) if val == 'S']
    finishes = [(y, x) for y, row in enumerate(track)
                       for x, val in enumerate(row) if val == 'F']

# Make a list of all possible actions
    actions = []
    for xdelta in [-1, 0, 1]:
        for ydelta in [-1, 0, 1]:
            actions.append((ydelta, xdelta))

MAX_SPEED = 3

# The initial value of the Q function
    DEFAULT_Q = -30

# Enumerate all possible speeds
    # Going to allow speeds from -MAX_SPEED to MAX_SPEED, so allow for 2*MAX_SPEED+1 states.
    # Note: Technically, since the max speed is MAX_SPEED, we don't
    # need this many states because, for example, MAX_SPEED,MAX_SPEED
    # isn't allowed, so simply screen those out
    speeds = []
    for yspeed in range(-MAX_SPEED, MAX_SPEED+1):
        for xspeed in range(-MAX_SPEED, MAX_SPEED+1):
            if abs(yspeed) + abs(xspeed) <= MAX_SPEED:
                speeds.append((yspeed, xspeed))

# Do we need to train, or was a policy provided?
    if len(sys.argv) < 3:
        # Need to train

# Initialize our starting variables
        epsilon = 0.1
        # Alpha is the rate at which we adjust Q(S,A) estimates
        alpha = 0.3
        gamma = 1
        Q1 = {}
        Q2 = {}
        policy = {}
        for y in range(len(track)):
            for x in range(len(track[0])):
                # The full state is the location and the current speed
                for speed in speeds:
                    s = (y, x) + speed
                    # In the book, there are access with Q(s, a), but I'll
                    # store them as an array indexed by s and then a.
                    # This makes it easier to select an action.
                    Q1[s] = []
                    Q2[s] = []
                    for i, action in enumerate(actions):
                        # Make the initial action scores small, Q-learning will update them quickly
                        Q1[s].append(DEFAULT_Q)
                        Q2[s].append(DEFAULT_Q)
                    # Initialize the policy
                    policy[s] = numpy.argmax(Q1[s])
        # For Q-learning we need a special state for being finished
        for speed in speeds:
            s = (-10, -10) + speed
            Q1[s] = [0] * len(actions)
            Q2[s] = [0] * len(actions)
        print(f"There are {len(Q1)} possible states.")
        print("Beginning episodes.")

## Keep track of how long the trials are taking
        episode_durations = []

# Create a policy map visualizer
        vis = policy_map.Visualizer(len(track), len(track[0]), speeds)

for episode in range(5000):
            if episode % 100 == 0:
                if episode != 0:
                    vis.plotMax(Q1, f"double_q_learning_maxQ_{episode}.png")
                # Convert to a video later with a command like: convert -delay 10 -layers Optimize `ls -tr double_q_learning_maxQ_*.png` foo.gif
                print(f"Beginning episode {episode}")
                if episode > 0:
                    print(f"Mean of last 10 episode durations was {numpy.mean(episode_durations[-10:])}")
            # Run the simulation
            finished = False
            # Pick a random starting location
            location = random.choice(starts)
            speed = (0, 0)
            states = []
            past_actions = []
            rewards = [0]
            while not finished:
                # Remember the state
                state = location + speed
                states.append(state)
                # Get the action from the behavior policy
                action = softPolicy(policy, epsilon, state, actions)
                # Remember the action
                past_actions.append(action)
                # Update the speed. Check that it is within bounds
                new_ys = min(MAX_SPEED, max(-MAX_SPEED, speed[0] + action[0]))
                new_xs = min(MAX_SPEED, max(-MAX_SPEED, speed[1] + action[1]))
                # If the total speed is too high, then don't update
                if abs(new_xs) + abs(new_ys) <= MAX_SPEED:
                    speed = (new_ys, new_xs)
                # Update the location, and check each space along the way
                total_speed = abs(speed[0]) + abs(speed[1])
                for step in range(1, total_speed+1):
                    new_y = location[0] + round( (step/total_speed) * speed[0])
                    new_x = location[1] + round( (step/total_speed) * speed[1])
                    # Handle locations and 0 speeds
                    if new_y < 0 or new_y >= len(track) or new_x < 0 or new_x >= len(track[0]) or track[new_y][new_x] == "W":
                        # Hit a wall. Reset.
                        location = random.choice(starts)
                        speed = (0, 0)
                    elif track[new_y][new_x] == "F":
                        # Finished.
                        finished = True
                        rewards.append(0)
                        break
                # Otherwise we move to the next location
                old_location = location
                location = (location[0] + speed[0], location[1] + speed[1])
                if finished:
                    # For Q-learning we need a special state for being finished
                    location = (-10, -10)
                new_state = location + speed
                # Negative reward for every step that still hasn't finished
                if not finished:
                    rewards.append(-1)
                # Q learning will update the Q(S, A) estimate immediately
                a_idx = actions.index(action)
                # Regular Q learning
                #Q1[state][a_idx] = Q1[state][a_idx] + alpha * (rewards[-1] + gamma * float(numpy.max(Q1[new_state])) - Q1[state][a_idx])
                ## Update the policy for the previous state
                #policy[state] = numpy.argmax(Q1[state])
                # Double Q-learning
                if random.random() < 0.5:
                    Q1[state][a_idx] = Q1[state][a_idx] + alpha * (rewards[-1] + gamma * Q2[new_state][numpy.argmax(Q1[new_state])] - Q1[state][a_idx])
                else:
                    Q2[state][a_idx] = Q2[state][a_idx] + alpha * (rewards[-1] + gamma * Q1[new_state][numpy.argmax(Q2[new_state])] - Q2[state][a_idx])
                # Update the policy for the previous state
                policy[state] = numpy.argmax([a + b for a,b, in zip(Q1[state], Q2[state])])

# For illustration
                episode_durations.append(len(states))
            # We remove about 31 lines of code for the old Monte Carlo police estimation

# Save the policy
        with open("policy.pkl", "wb") as outfile:
            pickle.dump((policy, Q1, Q2), outfile)

else:
        with open(sys.argv[2], 'rb') as policyfile:
            policy, Q1, Q2 = pickle.load(policyfile)

num_unexplored = sum([Q1[(y, x) + speed].count(DEFAULT_Q) for speed in speeds for x in range(len(track[0])) for y in range(len(track))])
    print(f"Unexplored tiles are {num_unexplored}/{len(Q1)*len(actions)} ({100*num_unexplored/(len(Q1)*len(actions))}%)")

# debugging/information
    print(f"Actions are {actions}")
    for start in starts:
        print(f"At location {start} Q has action scores {Q1[start + (0, 0)]}")
        print(f"At location {start} policy is {policy[start + (0, 0)]}, which is {actions[policy[start + (0, 0)]]}")

racetrack_sim.simulate(policy, actions, track, starts, MAX_SPEED)
```

-v-

## Curses Library

```python
####################
# Simulator for a racetrack and policy.
####################

import curses
import random
import time

def curses_simulate(stdscr, policy, actions, track, starts, MAX_SPEED):
    # Clear screen and hide the cursor
    curses.curs_set(0)
    stdscr.clear()

# Get screen dimensions, but we're ignoring them for now
    scr_height, scr_width = stdscr.getmaxyx()

# Demonstrate a race
    finished = False
    # Pick a random starting location
    location = random.choice(starts)
    speed = (0, 0)
    while not finished:
        # Print out the track
        for y in range(len(track)):
            for x in range(len(track[0])):
                if (y, x) == location:
                    stdscr.addch(y, x, 'C')
                else:
                    stdscr.addch(y, x, track[y][x])
        # Refresh the screen to show changes
        stdscr.refresh()
        time.sleep(0.5)
        #print(f"\nSpeed: {speed}\n\n")
        # Get the action from the target policy
        a_idx = policy[location+speed]
        action = actions[a_idx]
        # Update the speed. Check that it is within bounds
        new_ys = min(MAX_SPEED, max(-MAX_SPEED, speed[0] + action[0]))
        new_xs = min(MAX_SPEED, max(-MAX_SPEED, speed[1] + action[1]))
        # If the total speed is too high, then don't update
        if abs(new_xs) + abs(new_ys) <= MAX_SPEED:
            speed = (new_ys, new_xs)
        # Update the location, and check each space along the way
        total_speed = abs(speed[0]) + abs(speed[1])
        for step in range(1, total_speed+1):
            new_y = location[0] + round( (step/total_speed) * speed[0])
            new_x = location[1] + round( (step/total_speed) * speed[1])
            # Handle locations and 0 speeds
            if new_y < 0 or new_y >= len(track) or new_x < 0 or new_x >= len(track[0]) or track[new_y][new_x] == "W":
                # Hit a wall. Reset.
                location = random.choice(starts)
                speed = (0, 0)
            elif track[new_y][new_x] == "F":
                # Finished.
                finished = True
        # Otherwise we move to the next location
        location = (location[0] + speed[0], location[1] + speed[1])

def simulate(policy, actions, track, starts, MAX_SPEED):
    curses.wrapper(curses_simulate, policy, actions, track, starts, MAX_SPEED)
```

-v-

## Q value Mapping

```python
####################
# Matplotlib code to visualize policy learning.
####################

import matplotlib.pyplot as plt
from matplotlib.colors import SymLogNorm

import matplotlib
import matplotlib as mpl

import numpy

class Visualizer:
    def __init__(self, height, width, speeds):
        self.height = height
        self.width = width
        self.speeds = speeds
        self.ax = plt.gca()

def plotMax(self, Q, outname):
        self.ax.clear()
        max_values = [[numpy.max([Q[(y, x) + speed] for speed in self.speeds]) for x in range(self.width)] for y in range(self.height)]

im = self.ax.imshow(max_values, norm=SymLogNorm(linthresh=1))
        cbar = self.ax.figure.colorbar(im, ax=self.ax, cmap="YlGn")

self.ax.figure.tight_layout()
        plt.savefig(outname, dpi=2*96)
        cbar.remove()

def plotMean(self, Q, outname):
        self.ax.clear()
        avg_values = [[numpy.mean([Q[(y, x) + speed] for speed in self.speeds]) for x in range(self.width)] for y in range(self.height)]

im = self.ax.imshow(avg_values)
        cbar = self.ax.figure.colorbar(im, ax=self.ax, cmap="YlGn")

self.ax.figure.tight_layout()
        plt.savefig(outname, dpi=2*96)
        cbar.remove()
```

---

## Track 1

* Notice that the both the beginning and the end are rapidly explored
  * The end because that's where the agent goes
  * The beginning because of random starts there

</div>
<div class="col">

</div>
</div>

---

## Track 2

* There is a clear difference between Monte Carlo and Temporal-Difference
* Notice that the finish starts are not fully explored
  * Some are simply nearer to the start
  * Why ever go to the more distance finish locations?
* I had to use a high value for $\epsilon$ with Monte Carlo, so it did extra exploration

</div>
<div class="col">

</div>
</div>

---

## Track 2 Comparison

<img style="width: 60%" class="r-stretch" src="./figures/track2_mcc_learning_maxQ.gif" />
<br/>
<small>Monte Carlo</small>

</div>
<div class="col">

<img style="width: 60%" class="r-stretch" src="./figures/track2_double_q_learning_maxQ.gif" />
<br/>
<small>Q Learning</small>

</div>
</div>

---

## Track 4

* This solves fairly quickly with double Q learning

</div>
<div class="col">

</div>
</div>

---

## Summary

* So we don't need to fully explore a space to begin estimating utility
  * This means that we can learn even in non-episodic contexts
* TD is a one-step, tabular approach
  * And we can unify it with monte carlo approaches by taking multiple steps
* But how do we extend things to continuous spaces?
  * We just need to learn Q with continuous states and/or actions

<!--
With MC policy search

track 1 is 98.17185185185186% unexplored

With double q learning

track 1 is 82.04946474713917% unexplored (state, action pairs)
track 2 is 86.05457227138643% unexplored (state, action pairs)
track 4 is 76.72615535889872% unexplored (state, action pairs)
-->