RL @ ECE-UofT - Lecture 05: Deep Bootstraping and epsilon-Greedy Improvement

Overview

Ali Bereyhi develops n-step temporal-difference learning as a bridge between one-step TD and Monte Carlo, then introduces TD(λ), which geometrically combines returns of different depths to balance estimation bias and variance. He derives eligibility traces as an online, backward-time implementation of TD(λ), then shifts from policy evaluation to control, explaining why greedy improvement can prevent exploration and how ε-greedy action selection addresses that problem.

Key takeaways

N-step TD interpolates between TD(0) and Monte Carlo: a larger horizon uses more observed rewards and less bootstrapping, but the best horizon depends on the environment and policy.
TD(λ) combines available n-step returns with weights that sum to one: λ=0 yields TD(0), λ=1 yields Monte Carlo for episodic returns, and intermediate values trade off bias and variance.
Eligibility traces implement TD(λ) online by updating each state in proportion to its trace, eₜ(S), using the current TD error; the backward and forward views agree after a trajectory when initialized identically.
Greedy control can stop sampling alternatives: a first $150 reward from Company B may make a learner repeatedly choose B without ever finding out whether Company A pays more.
Under uniform exploration across m actions, ε-greedy assigns ε/m probability to each action from exploration, giving the greedy action total probability 1−ε+ε/m.
The lecture positions SARSA as on-policy TD control and Q-learning as off-policy control, distinguishing whether the learned action values correspond to the behavior policy or a different target policy.

Chapters

0:00 Model-Free Reinforcement Learning: Policy Evaluation and Improvement

The setting assumes an MDP exists but its transition and reward model are unavailable.
Generalized policy iteration alternates between evaluating a policy from samples and improving it, traditionally by choosing the highest-value action.

5:07 Monte Carlo and TD(0): Complete Returns Versus One-Step Targets

Monte Carlo estimates a state value by averaging complete sampled returns after trajectories reach termination.
TD(0) updates after one transition using the immediate reward plus the estimated value of the next state.

6:54 N-Step TD Extends the Bootstrap Horizon

An n-step target sums the next n rewards, discounting each by its position, then adds a bootstrapped value for the state after those rewards.
For n=1, the method uses a one-step TD target; increasing n incorporates more observed trajectory rewards before bootstrapping.

13:00 Why Deeper Bootstrapping Can Improve State-Value Estimates

If a one-step target bootstraps from an unseen state initialized to zero, its estimate can be badly misleading.
A deeper target can reach a better-estimated state—for example, replacing an unreliable value for S₂ with a more reliable estimate for S₃.

20:01 N-Step Returns and the Standard Value-Update Rule

Bereyhi defines an n-step sample target as discounted rewards through the n-step horizon plus the estimated value beyond it.
The update remains value ← value + α(target − value); Monte Carlo, TD(0), and n-step TD differ mainly in how they construct the target.

25:20 Applying N-Step TD Along a Sampled Trajectory

For each state on a trajectory, the update uses the rewards available over the selected n-step window and the value at its endpoint.
The trajectory must extend far enough to supply the n rewards and bootstrap state, so updates near its end have a shorter available horizon.

29:32 N-Step TD Connects TD(0) to Monte Carlo

Setting n=0 recovers the shallow TD(0) target; letting n reach the end of an episodic trajectory removes bootstrapping and yields a Monte Carlo return.
Intermediate n values trade off reliance on estimated future values against use of rewards actually observed in the trajectory.

35:32 Choosing N: The Bias–Variance Trade-Off

In a 16-by-16 grid-world illustration, estimation error first improves and then worsens as the step size α changes.
Increasing n can reduce TD(0)'s bias while increasing variance; even with α tuned for each n, an intermediate horizon can outperform both extremes.

40:40 Why One Fixed N Is Hard to Tune

The best n depends on the environment, policy, and trajectory length, making a single fixed horizon inconvenient across sampled episodes.
A trajectory provides targets at multiple depths, motivating an estimator that combines them rather than discarding all but one.

45:21 TD(λ) Geometrically Weights Returns of Different Depths

The λ-return combines TD(0), TD(1), and deeper n-step returns using weights that decay geometrically with depth.
For a maximum depth L, the weights are 1−λ, (1−λ)λ, through (1−λ)λ^(L−1), followed by λ^L; they sum to one.

52:03 λ-Returns Reuse Each Trajectory at Multiple Horizons

Each state can receive a weighted average of all n-step estimates available from the same trajectory, increasing the amount of information used per sample.
The final weight λ^L absorbs the deepest return, so the weighting remains normalized even when trajectory lengths differ.

56:01 TD(λ) Updates Values Using the λ-Return

TD(λ) uses the same incremental update structure as TD(0) and n-step TD, substituting the λ-return for the target.
At each trajectory position, the available returns have different depths; their geometrically weighted combination supplies the value estimate.

58:27 λ=0 and λ=1 Recover TD(0) and Monte Carlo

With λ=0, all weight falls on the one-step target, recovering TD(0); with λ=1, only the full return remains in an episodic setting, recovering Monte Carlo.
Intermediate λ values combine shallow and deep targets, and the choice must be tuned because it changes the bias–variance balance.

1:06:47 Forward-View TD(λ) Discounts Deeper Predictions

The forward view assigns the immediate TD estimate weight 1−λ and progressively smaller weights to estimates that look farther into the future.
A deep estimate may be less reliable because it depends on more future transitions and accumulated prediction uncertainty.

1:13:02 Credit Assignment: Weighing the Reliability of Future Outcomes

As a trajectory extends, the number of possible state sequences grows, so one observed path represents a smaller fraction of possible futures.
Geometric λ weights provide an intuitive way to reduce credit assigned to distant estimates, though Bereyhi notes that these weights are not proven optimal.

1:21:00 Why TD(λ) Needs a Backward, Online View

In the forward view, an update to an earlier state can affect later estimates when those later states are visited.
Eligibility tracing reverses the bookkeeping: a newly observed TD error can update earlier states immediately instead of waiting for the trajectory to finish.

1:25:00 Eligibility Traces Track Recently Visited States

The backward-view motivation is to revise earlier value estimates when later observations improve the estimates on which they depended.
An eligibility table assigns a trace to each state, decaying older traces by γλ and increasing the trace for the currently visited state.

1:31:41 Initializing and Updating the Eligibility Table

At the start of a trajectory, each state's eligibility is zero; at each time step, existing traces are multiplied by the discount factor γ and λ.
The currently observed state receives an additional one, marking its recent visit while retaining decayed traces for previous states.

1:33:42 Repeated Visits Accumulate State Eligibility

A state's trace shrinks while it is not revisited and increases by one when it appears again.
With γλ=0.1, a state visited two steps earlier retains a small trace, while a repeated visit can raise its eligibility slightly above one.

1:41:23 Use TD Errors to Update Every Eligible State

At time t, the TD(0) error is δₜ = rₜ₊₁ + γV(Sₜ₊₁) − V(Sₜ).
Instead of updating only Sₜ, the backward view updates each state S by αδₜeₜ(S), scaling its change by its current eligibility.

1:48:48 Eligibility Traces Make TD(λ) Updates Online

A never-visited state has zero eligibility and receives no update; recently or repeatedly visited states receive larger trace-scaled updates.
At the beginning of a new episode, traces are reset; in continuing tasks, traces can be maintained as observations arrive.

1:54:33 Forward and Backward TD(λ) Views Agree at Episode End

Starting from the same value estimates, the forward λ-return updates and backward eligibility-trace updates produce the same final estimates after a trajectory.
The backward view differs in timing: it applies TD errors online as they occur rather than waiting to process the completed trajectory.

1:58:44 Eligibility-Trace Limits Recover TD and Monte Carlo

When λ=0, only the currently visited state has a nonzero trace, so the update reduces to TD(0).
When λ=1 and γ=1, prior visits retain full eligibility, corresponding to the Monte Carlo-style accumulation described in the lecture.

2:04:30 Prediction Algorithms Versus Online Control

Prediction evaluates a supplied policy by estimating its state or action values; control also changes the policy to improve behavior.
Batch-style generalized policy iteration gathers trajectories to evaluate a policy before improving it, whereas online control updates from each new observation.

2:09:05 Control Updates Values and Policy During Interaction

Online control aims to learn while interacting, updating action values and improving the policy rather than discarding experience after a policy change.
Eligibility traces can propagate a new TD error to many previously visited states, allowing more of each observation to influence learning.

2:16:20 Monte Carlo Control Improves After Each Episode

In the Monte Carlo example, a complete trajectory updates the action values for the state–action pairs encountered.
After that episode, the policy is improved and the next trajectory is sampled under the revised policy.

2:18:22 Greedy Improvement Can Lock a Learner Into a Bad Action

A purely greedy policy always selects the action with the highest current estimated value, even when those estimates are based on very few samples.
Once the policy stops selecting alternatives, their values cannot be learned from new experience, so the learner may remain suboptimal.

2:25:06 Company A and Company B Show the Exploration Problem

If the first sampled job is Company B and pays $150, a greedy learner may keep returning to B without ever measuring Company A.
Later B rewards, such as $250, can strengthen that preference while leaving the alternative unevaluated; the same lock-in can start with A.

2:29:34 ε-Greedy Improvement Balances Exploration and Exploitation

With probability 1−ε, ε-greedy selects the action with the highest estimated value; with probability ε, it explores by choosing an action randomly.
Exploration collects evidence about actions that current estimates may undervalue, while greedy choices exploit the best estimate so far.

2:32:47 Action Probabilities Under ε-Greedy Selection

For m available actions and uniform random exploration, each action receives ε/m probability from exploration.
The currently greedy action therefore has total probability 1−ε+ε/m, while each other action has probability ε/m.

2:37:04 The ε-Greedy Improvement Guarantee

Bereyhi outlines the ε-greedy improvement theorem: using action values for the current policy to form a new ε-greedy policy improves policy value under the stated setup.
A larger ε encourages exploration early; reducing ε as estimates become more reliable shifts behavior toward exploitation.

2:39:57 Next Steps: SARSA, Q-Learning, and On- versus Off-Policy Learning

SARSA will replace Monte Carlo returns with TD updates while learning the value of the policy that is actually being followed, making it on-policy.
Q-learning will use off-policy learning, with importance sampling introduced as one route to evaluating a different target policy from sampled behavior.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Ali Bereyhi.