# CS 462 - Lecture 24

## Rehearse Lawyer

## Reincarnate Leeward

## Reinforced Leaded

## Reinforcement Learn

## Reinforcement Learning

Bernhard Firner

2026-04-22

---

## Review

* Reinforcement learning generally operates in two phases:
  * An exploration phase, where we don't know anything about the optimal policy
  * An exploitation phase, where we use what we've learned to make an optimal (or good) policy
* Most approaches smoothly transition from exploration to exploitation, but that isn't necessary

---

## Book

* If you want a text book with a bit more foundational theory than what is in UDL, try [Reinforcement Learning: An Introduction](http://incompleteideas.net/book/the-book-2nd.html) by Sutton and Barto
* For our quick deep dive, we are going through chapter 19 of the UDL book
* And using the [RL gym](https://gymnasium.farama.org/introduction/basic_usage/)

---

## Vocabulary

* We introduced some ideas last time
  * Reward: $R_t$ is the reward we receive for an action at time $t$.
  * Gain: $G_t$ is the cumulative reward at time $t$.
  * Value/Utility: This is a measure of expected gain from our current position.

---

## What Are We Learning?

* There are two options
* Action utility function, $Q$
  * $Q(s, a)$ is the expected utility of action $a$ while in state $s$
* Policy, $\pi$
  * $\pi(a|s)$ is the probability of taking action $a$ in state $s$
* Policy learning is a bit more tricky, so let's stick with Q for now

---

## Optimal Policy

* An optimal policy takes the best action at each state
  * Best as determined by the expected gain
* $\pi(s) \leftarrow \underset{a}{argmax} Q(s, a)~ \forall s \in S$
* It should be obvious that if the values in Q are wrong then our policy will also be non-optimal

---

## Stochastic Policies

* Quick note on stochastic policies
* Sometimes our policies *must* be stochastic
  * For example, in a multiplayer game, if we always choose the *best* action then those actions are too predictable
  * Think poker; without any bluffing, our agent won't be very good
* Other times, we are actually uncertain about the actual state
  * Taking the same action every time may lead to a loop, so sometimes we need to try a different action

---

## Modelling

* Learning Q implicitly assumes that we are in a Markov process world
  * Meaning that there are multiple states
  * And actions cause state transitions with some knowable probabilities
* If those assumptions aren't true things become difficult

---

## How Do We Explore?

* A $\epsilon$-greedy policy is a method of adding randomness to a policy
  * Simple: with probability $\epsilon$ we take a random action
* Every action will be taken with probability at least $\frac{\epsilon}{|A(s)|}$
  * Where $|A(s)|$ is the total number of actions at state $s$
* The "best" action is taken greedily with probability $1 - \epsilon + \frac{\epsilon}{|A(s)|}$

---

## What are we Learning?

* We want $Q(s_t,a_t) = \mathcal{E}\left[G_t|s_t,a_t\right]$
  * Recall $G_t \leftarrow R_{t+1} + \gamma G_{t+1}$
  * So $G_t = \sum\limits_{k=0}^T\gamma^kr_{t+k+1}$
* But the gain is going to depend upon what actions we take
* What we are actually estimating is $Q(s_t,a_t|\pi) = \mathbb{E}\left[G_t|s_t,a_t,\pi\right]$
  * Which means that Q estimates will improve along with the policy, which improves Q estimates, etc

---

## When Do We Learn?

* Choosing when to learn has some importance
* Monte Carlo methods explore until an episode ends, at which point the final gain is used to update estimated rewards at each state encountered
* We may use a large amount of randomness in our actions to ensure we are exploring well

---

## Gain Assignment

* But wait! What if random exploration jumps off of a cliff?
  * If the policy wouldn't do that, should it change Q?
  * $Q(s_t,a_t|\pi) = \mathbb{E}\left[G_t|s_t,a_t,\pi\right]$
* No, but that means that we begin learning only near the goal of the episode
  * Earlier states will be stuck with initial values for a while

<div class="col">
<img style="width: 70%" class="r-stretch" src="./figures/cliff-walking-dqn-5episodes.gif" />
<br/>
<small>Exploration after 5 episodes.</small>
</div>

---

## Gain Assignment

* We should only update expectations when we see actions that the policy would have chosen
  * This is called *importance sampling*
* But with random exploration, we may not update very often
  * So this can make learning quite slow
* Is there a different way?

---

## TD Learning

* Temporal difference (TD) learning updates differently
* At every step, we simply learn by the difference between our current estimate and the estimate of the future
* Sitting around in the same spot for a while, we begin to suspect that it is not good
  * So we begin to learn immediately

<div class="col">
<img style="width: 70%" class="r-stretch" src="./figures/cliff-walking-dqn-25episodes.gif" />
<br/>
<small>A Q-Learning agent explores after 25 episodes.</small>
</div>

---

## TD Learning

* This update is equivalent to the Monte Carlo approach
  * Line 1 is Monte Carlo, line 3 is TD learning

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

* Of course we are estimating $u_{\pi}(s)$ with Q, so it is biased (meaning incorrect) at first
  * But converges to the correct value over time

---

## TD Variations

* There are a few variations
* Critically, how should we estimate $u(S_{t+1})$?
  * Should it be $\mathbb{E}\left[Q(s_{t+1},A)\right]$, an estimate over all $a \in A$?
  * Or should it be $\mathbb{E}\left[\underset{a}{max}Q(s_{t+1},a_{t+1})\right]$, an estimate over the best action?

---

## SARSA

* SARSA is named after the variables used
  * $Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha[R + \gamma Q(s_{t+1}, A) - Q(s_t,a_t)]$
* Any result will affect the Q estimate, even jumping off of the cliff
* This approach will cause our RL agent to avoid the edge of the cliff
  * Even though it is the fastest route

---

## Q-Learning

* $Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha[R + \gamma \underset{a}{max}Q(s_{t+1},a) - Q(s_t,a_t)]$
* If we jump off the cliff but that wasn't the best action, that won't affect other estimates
  * SARSA, on the other hand, would always avoid the cliff edge
* But Q-Learning can be biased a few bad estimates, leading to surprisingly noisy results
* So let's look for solutions

---

## Expected SARSA

* A fix is to SARSA is to take the expected value for the update
* $Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha\left[R + \gamma \mathbb{E_\pi}[Q(s_{t+1}, a_{t+1}) | s_{t+1}] - Q(s_t,a_t)\right]$
  * This becomes $Q(s_t,a_t) + \alpha\left[R + \gamma \underset{a}{\Sigma}\pi(a|s_{t+1})Q(s_{t+1},a) - Q(s_t,a_t)\right]$
* For deterministic (non-stochastic) policies, this is the same as Q-Learning
  * Because there is only one action chosen with p=1
  * Being a superset, we could always replace Q-learning with this

---

## Bias

* Q-Learning makes biased estimates
* Consider walking into a store and buying a lottery ticket
  * There are near limitless numbers to pick, so if you assigned each of them a random value some of them will have huge rewards
    * According to your initial estimates, at least
* It will take you a near limitless amount of time to actually learn that none of them guarantee a win

---

## The Solution?

* Go to the store with a friend
* One of your chooses the numbers, the other decides on the expected reward of those numbers
  * Since you don't share the same lucky numbers, your expected reward doesn't seem good anymore
* Over time, both learners will converge to the same estimates, but large initial biases are avoided

---

## 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

<p style="font-size: 70%"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mtable><mtr><mtd columnalign="right" style="text-align: right"><msub><mi>Q</mi><mn>1</mn></msub><mrow><mo stretchy="true" form="prefix">(</mo><msub><mi>s</mi><mi>t</mi></msub><mo>,</mo><msub><mi>a</mi><mi>t</mi></msub><mo stretchy="true" form="postfix">)</mo></mrow></mtd><mtd columnalign="left" style="text-align: left"><mo>←</mo><msub><mi>Q</mi><mn>1</mn></msub><mrow><mo stretchy="true" form="prefix">(</mo><msub><mi>s</mi><mi>t</mi></msub><mo>,</mo><msub><mi>a</mi><mi>t</mi></msub><mo stretchy="true" form="postfix">)</mo></mrow><mo>+</mo><mi>α</mi><mrow><mo stretchy="true" form="prefix">[</mo><mi>R</mi><mo>+</mo><mi>γ</mi><msub><mi>Q</mi><mn>2</mn></msub><mrow><mo stretchy="true" form="prefix">(</mo><msub><mi>s</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>,</mo><munder><mrow><mi>a</mi><mi>r</mi><mi>g</mi><mi>m</mi><mi>a</mi><mi>x</mi></mrow><mi>a</mi></munder><msub><mi>Q</mi><mn>1</mn></msub><mrow><mo stretchy="true" form="prefix">(</mo><msub><mi>s</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>,</mo><mi>a</mi><mo stretchy="true" form="postfix">)</mo></mrow><mo stretchy="true" form="postfix">)</mo></mrow><mo>−</mo><msub><mi>Q</mi><mn>1</mn></msub><mrow><mo stretchy="true" form="prefix">(</mo><msub><mi>s</mi><mi>t</mi></msub><mo>,</mo><msub><mi>a</mi><mi>t</mi></msub><mo stretchy="true" form="postfix">)</mo></mrow><mo stretchy="true" form="postfix">]</mo></mrow></mtd></mtr><mtr><mtd columnalign="right" style="text-align: right"><msub><mi>Q</mi><mn>2</mn></msub><mrow><mo stretchy="true" form="prefix">(</mo><msub><mi>s</mi><mi>t</mi></msub><mo>,</mo><msub><mi>a</mi><mi>t</mi></msub><mo stretchy="true" form="postfix">)</mo></mrow></mtd><mtd columnalign="left" style="text-align: left"><mo>←</mo><msub><mi>Q</mi><mn>2</mn></msub><mrow><mo stretchy="true" form="prefix">(</mo><msub><mi>s</mi><mi>t</mi></msub><mo>,</mo><msub><mi>a</mi><mi>t</mi></msub><mo stretchy="true" form="postfix">)</mo></mrow><mo>+</mo><mi>α</mi><mrow><mo stretchy="true" form="prefix">[</mo><mi>R</mi><mo>+</mo><mi>γ</mi><msub><mi>Q</mi><mn>1</mn></msub><mrow><mo stretchy="true" form="prefix">(</mo><msub><mi>s</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>,</mo><munder><mrow><mi>a</mi><mi>r</mi><mi>g</mi><mi>m</mi><mi>a</mi><mi>x</mi></mrow><mi>a</mi></munder><msub><mi>Q</mi><mn>2</mn></msub><mrow><mo stretchy="true" form="prefix">(</mo><msub><mi>s</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>,</mo><mi>a</mi><mo stretchy="true" form="postfix">)</mo></mrow><mo stretchy="true" form="postfix">)</mo></mrow><mo>−</mo><msub><mi>Q</mi><mn>2</mn></msub><mrow><mo stretchy="true" form="prefix">(</mo><msub><mi>s</mi><mi>t</mi></msub><mo>,</mo><msub><mi>a</mi><mi>t</mi></msub><mo stretchy="true" form="postfix">)</mo></mrow><mo stretchy="true" form="postfix">]</mo></mrow></mtd></mtr></mtable><annotation encoding="application/x-tex">\begin{align*}
Q_1(s_t,a_t) & \leftarrow Q_1(s_t,a_t) + \alpha\left[R + \gamma Q_2(s_{t+1}, \underset{a}{argmax}Q_1(s_{t+1},a)) - Q_1(s_t,a_t)\right] \\
Q_2(s_t,a_t) & \leftarrow Q_2(s_t,a_t) + \alpha\left[R + \gamma Q_1(s_{t+1}, \underset{a}{argmax}Q_2(s_{t+1},a)) - Q_2(s_t,a_t)\right]
\end{align*}</annotation></semantics></math></p>

* When choosing an action, each estimator consults the other for the action to use in the Q estimate
* Convergence occurs over time, but this removes potential bias, speeding learning

---

## Code Example

* For discrete environments, we simply use a linear model

```python
class QModel(torch.nn.Module):
    """A linear neural network for state-action value estimation."""

def __init__(self, states, actions):
        super(QModel, self).__init__()
        # This model takes in the current state and a one-hot vector of actions
        self.net = torch.nn.Sequential(
            torch.nn.Linear(in_features=states+actions, out_features=128),
            torch.nn.ReLU(),
            torch.nn.Linear(in_features=128, out_features=32),
            torch.nn.Linear(in_features=32, out_features=1),
            )
        self.states = states

torch.nn.init.normal_(self.net[0].weight.data)
        torch.nn.init.normal_(self.net[2].weight.data)
        torch.nn.init.normal_(self.net[3].weight.data)

def forward(self, x):
        """Forward through the network."""
        return self.net(x)
```

---

## Learning

* Learning is straightforward
* Collect a dataset of state action pairs and learn at the end of episodes and every $n$ steps

```
dataset = torch.utils.data.TensorDataset(self.past_state_actions, self.past_rewards)
loader = torch.utils.data.DataLoader(dataset, batch_size = self.batch_size, shuffle=True)
for state_actions, rewards in loader:
    # Zero gradients before gradient calculation
    self.optimizer.zero_grad()
    # Forward again to make a gradient
    # Update with the error
    y_hat = self.model.forward(state_actions.float())
    y = rewards
    loss = self.criterion(y_hat, y)

# Gradient calculation
    loss.backward()
    # Update weights
    self.optimizer.step()
```

---

## History

* We also need to keep some history
* To prevent us from learning from old and irrelevant data, we can discard old samples with probability $1-p$

```python
mask = torch.rand(self.past_state_actions.size(0)) < self.history_p
self.past_state_actions = self.past_state_actions[mask]
self.past_rewards = self.past_rewards[mask]
```

---

## Cartpole

```python
import argparse
import gymnasium as gym
import numpy
import pickle
import random
import torch

import rl_learners

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument(
        "--algorithm",
        required=False,
        type=str,
        default='dnn',
        choices=['dnn', 'sarsadnn'],
        help="Policy search algorithm.")
    parser.add_argument(
        "--policy",
        required=False,
        type=str,
        default=None,
        help="Pickle file with an existing policy")
    parser.add_argument(
        "--episodes",
        required=False,
        type=int,
        default=1250,
        help="The number of episodes to run")
    parser.add_argument(
        "--record",
        required=False,
        default=False,
        action='store_true',
        help="Record the end result as a video.")

args = parser.parse_args()

# Do we need to train, or was a policy provided?
    if args.policy is None:

env = gym.make('CartPole-v1')

# The action space is discrete, with values 0 or 1
        print(f"Action space: {env.action_space}")
        # The observation space is a tuple of cart position, cart velocity, pole angle, and pole angular velocity
        print(f"Observation space: {env.observation_space}")

epsilon = 0.1

if args.algorithm == 'dnn':
            qmodel = rl_learners.NNQ(actions=(False, 2), states=(True, 4), alpha=0.0001, gamma=0.99, history_p=0.5)
        elif args.algorithm == 'sarsadnn':
            qmodel = rl_learners.SarsaDNN(actions=(False, 2), states=(True, 4), alpha=0.001, gamma=1.0, history_p=0.5)

# Save a new model whenever we get a new best
        best = 0

for episode in range(args.episodes):
            state, info = env.reset()

# Run the simulation
            finished = False

sim_steps = 0
            while not(finished):
                # Epsilon greedy policy
                if random.random() < epsilon:
                    action = random.choice([0,1])
                else:
                    action = qmodel.bestAction(state)

next_state, reward, terminated, truncated, info = env.step(action)

if terminated:
                    next_state = None

qmodel.updateQ(state, next_state, action, reward)

# Update the state
                state = next_state

sim_steps += 1
                finished = terminated
                # Don't let this run forever
                if sim_steps > 1000:
                    finished = True
            print(f"{episode} {sim_steps}")
            if sim_steps > best:
                # Save the policy
                with open("policy_best.pkl", "wb") as outfile:
                    pickle.dump(qmodel, outfile)
        env.close()

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

else:
        with open(args.policy, 'rb') as policyfile:
            qmodel = pickle.load(policyfile)

# Play with policy
    if args.record:
        env = gym.make('CartPole-v1', render_mode="rgb_array")
        env = gym.wrappers.RecordVideo(
            env,
            #episode_trigger=lambda num: num % 2 == 0,
            video_folder="./",
            name_prefix="cartpole",
        )
    else:
        env = gym.make('CartPole-v1', render_mode="human")
    state, info = env.reset()
    # Run the simulation
    finished = False

# Set the model to evaluation
    if args.algorithm == 'actorcritic':
        qmodel.model.eval()

sim_steps = 0
    while not(finished):
        action = qmodel.bestAction(state)

# Take the action
        next_state, reward, terminated, truncated, info = env.step(action)

# Update the state
        state = next_state

finished = terminated
        sim_steps += 1
        # Don't let this run forever
        if sim_steps > 2000:
            finished = True
    env.close()
```

---

## Results

<div class="col">
<img style="width: 60%" class="r-stretch" src="./figures/cartpole-q-learning.gif" />
<br/>
<small>Cartpole with Q-Learning using a NN to predict Q. A few hundred episodes.</small>
</div>

---

## Results

* It takes around 1200 episodes to learn cartpole (with some hyperparemeters)

<div class="col">
<img style="width: 60%" class="r-stretch" src="./figures/cartpole-q-learning12ksteps.gif" />
<br/>
<small>Cartpole after 1200 episodes.</small>
</div>

---

## Statistics and RL

* It is important to mention that RL is terrible for sample statistics
* If the agent is too good at a task, and all of those states are stored as samples, they will all look the same
  * So the DNN could forget older things
  * Or the DNN will learn that doing *anything* will lead to enormous reward
* Managing your training samples can be the trickiest part of training

---

## Batch Statistics

* Let's say you allow cartpole to run until failure
  * The model achieves a run of 30k steps
  * What do your training batches look like?
* They are all the same, which violates the goals of stochastic gradient descent

---

## Batch Poisoning

* In effect, your batches lack any meaningful statistics
* They poison the model, leading to a sudden collapse in performance

---

## Data Limiting

* Retaining only a subset of data and limiting episode durations helps
* For a simple problem like cartpole, the best method is to simply stop early
  * With our $\epsilon$ policy random actions are included in the episodes

---

## Learning in Simulation

* If a task is deterministic, or at least well-understood, it can be simulated
* This is useful for training
* And it is also useful when actually doing a task
  * Why? Because we are likely to get into a state that we did not encounter during training
  * For example, Go has around $10^{170}$ states
  * Any continuous environment has an unbounded number of possible states

---

## Rollout During Episodes

* So what is the best policy when we encounter a rare or unseen state?
* Assuming that we can simulate some steps ahead, the Rollout algorithm is quite effective
* Algorithm
  * Choose random actions, or every action if there aren't many
  * Simulate the rest of the game using the policy, $\pi$
  * Select the action with the greatest final reward

---

## Policy Improvement

* Why would that be better than simply using our policy?
* Suppose original policy, $\pi$, results in some utility for the current state: $u_\pi(s)$
* Now rollout results in $\pi'(s) = a \neq \pi(s)$, but $q_\pi(s, a) \geq u_\pi(s)$
  * That means it we find an action better than the current policy at just a single step, we have a better policy
* This is useful both during learning and during games (or in real life)

---

## Discovered Policy

* The policy could actually be random and rollout would result in an improvement
* But improving upon a decent policy will result in better outcomes than improving upon a bad policy
* We may still have good reasons to use a random policy
  * For example in games with a great deal of randomness and a large number of states
  * Or if our "good" policy is computationaly expensive, a basic one may allow more simulations

---

## Parallel Advantages

* One important advantage of this approach is that we can run multiple simulations in parallel
* If we always followed the current Q estimates, our simulations may all end up redundant
  * But with some randomness from rollout, we could cover a large varietey of states in a large space
  * That also gives us a variety of data to put into a batch
* With rollout, we are free to run as many parallel simulations as we can from any point in time

---

## Simulated Results

* So if we are playing a game and use rollout, what do we do with the simulated results?
  * We throw them out
* If this task has a large state space, we are unlikely to visit state $s$ again
* Because of the randomness in rollout, only a small subset of the exploration will follow the trajectory that actually occurs
* An alternative that remembers discoveries is Monte Carlo Tree Search

---

## MCTS

* Monte Carlo Tree Search is rollout, but with an improved focus during search
* If the states being explored better match the actual states to follow, this also allows us to retain information
  * The accumulated states and value estimates are more likely to be revisited
* Exploration is focused on (state,action) trajectories that look promising, based upon current simulated returns

---

## MCTS Algorithm

* **Selection**: Select a leaf node in a tree of current value estimates. This is the *tree policy*, which could be $\epsilon\text-greedy$ rather than rollout
* **Expansion**: Add child nodes to the leaf node using the policy. This step can be skipped to avoid growing the tree.
* **Simulation**: Simulate to the end from the selected node or one of the new child nodes using rollout.
* **Backup**: Use the final gain to update the leaf node. Don't update the rest of the tree to avoid mixing random rollout and $\pi$.

---

<img style="width: 75%" class="r-stretch" src="./figures/RLBook/ch8_figure10_MCTS.png" />
<br/>
<small>Monte Carlo Tree Search in chapter 8 of Sutton and Barto</small>

</div>

---

## Advantages

* MCTS allows us to distinguish between a route that has both good and bad moves vs a route that is just mediocre
* Actions are less random than in rollout because explored steps actually use our policy
  * We are more likely to reach those states again
* We can also retain part of the tree structure as we continue, so this will be more computationally efficient
* On tasks that have many possible actions and require long sequences of steps, this can succeed where rollout fails

---

## Human-Level Play

* A deep Q network combined with rollout or MCTS is sufficient to reach human level play
  * On Go
  * On many Atari games
  * Games like Pong
* It is surprisingly insufficient for a game like [Pitfall](https://ale.farama.org/environments/pitfall/)
* Notice that jumping changes out state
  * So we had better try jumping in every position to see if it is good

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

<img style="width: 55%" class="r-stretch" src="./figures/pitfall.gif" />
<br/>
<small>The Atari game, Pitfall.</small>

</div>
</div>

---

## More RL

* There are two major topics left
* Gradient policy learning
  * The DNN is used to output a policy directly
  * Generally modelled as a categorical or normal probability distribution
* Learning in latent spaces
  * Learning on a continuous space with continuous actions is somewhat intractible
  * Operating on a compressed latent representation is more feasible

---

## Priming Concepts

* Content-wise, we are cramming a lot into a lecture
* And policy learning requires some hands-on experience to appreciate
  * It is quite finicky, and the methods to make it work require tuning
* The basic update equation starts with this:
  * $\theta \leftarrow \theta + \alpha \cdot \frac{\delta log \left[ \pi(a|s_t, \theta) \right]}{\delta \theta}G_t$

---

## Policy Update

* $\theta \leftarrow \theta + \alpha \cdot \frac{\delta log \left[ \pi(a|s_t, \theta) \right]}{\delta \theta}G_t$
* This says that we update parameters by the reward multiplied by the log likelihood of doing the action
  * High positive rewards should be likely
  * High negative rewards should be unlikely
* Sounds fine, but won't work without some help

---

## Next Time

* We'll try to get through some more fundamentals of policy learning
* But it is also time to wrap things
* So lecture 25 will be half RL and half wrap-up
* Lecture 26 will be review