Reinforcement Learning Lecture 5: Model-Free Control

David Silver introduces model-free control: learning a policy from experience when the transition and reward model is unknown or too costly to use.

He distinguishes on-policy learning, which evaluates the behavior being followed, from off-policy learning, which can learn about a different target policy.

Many practical environments are too complex to model or integrate over exactly. Interaction gives samples of transitions and rewards without requiring a complete model.

He gives examples of learning from one’s own actions and from another agent or human demonstration. The behavior producing data need not always be the policy being evaluated.

Generalized policy iteration alternates policy evaluation with policy improvement. The two processes can be interleaved rather than completed as separate exhaustive phases.

The lecture begins with Monte Carlo control: sample complete episodes, estimate returns, and improve a policy using the estimates.

A naive approach has two difficulties: choosing actions from state values requires knowledge of transitions, and a greedy policy may stop exploring actions it has not tried.

Action values Q(s,a) address the first issue: they estimate the return after taking an action in a state, so actions can be compared without a one-step model.

Given action values, greedy improvement chooses an action with maximum Q. Monte Carlo estimates can be updated from observed returns for state–action pairs.

The exploration problem remains: an action that initially looks best may be chosen forever, leaving a potentially better action untested.

An ε-greedy policy usually selects a greedy action and, with probability ε, selects randomly among actions. This keeps some exploration while using current estimates.

Silver discusses why ε-greedy improvement can improve an ε-soft policy under the stated policy-improvement argument. The guarantee concerns the defined policy class and assumptions.

The proof compares the expected action value under the new policy with that under the old policy; the greedy part cannot be worse than the corresponding weighted average.

Monte Carlo control can alternate evaluation and ε-greedy improvement. Fully evaluating a policy each time can be wasteful, motivating more frequent updates.

Instead of waiting for an exact evaluation, one can sample an episode, update estimates and improve the policy, then repeat. This is an instance of generalized policy iteration.

GLIE means greedy in the limit with infinite exploration: actions continue to be explored sufficiently, while the policy approaches greediness in the limit.

One illustrative schedule decreases ε over time, but decreasing it alone is not enough: the required state–action pairs must still be visited infinitely often for the theoretical result.

An incremental mean updates each Q estimate using the observed return and the number of visits. Under the lecture’s tabular assumptions and GLIE conditions, Monte Carlo control converges to optimal action values.

Silver answers a question about initialization: the asymptotic result can tolerate different starting values under its assumptions, but initial values can strongly affect practical learning speed.

With constant step sizes or finite data, initialization and update choices can have lasting practical effects; the asymptotic theorem is not a guarantee for every implementation.

A blackjack example illustrates using sampled episodes to improve action values and a policy. The resulting policy is specific to the game and rules being modeled.

The lecture then moves to temporal-difference control. TD updates can occur before an episode ends and can use an estimate of future value, called bootstrapping.

An online update can improve efficiency but trades a sampled complete return for a target partly based on an existing estimate, introducing a different bias–variance tradeoff.

SARSA uses the sequence state, action, reward, next state and next action. Its one-step target is reward plus discounted Q for the action actually selected by the current policy.

The update moves Q(s,a) toward r + γQ(s′,a′) with a step size. After observing the next state and choosing the next action, the process repeats.

An ε-greedy policy can be derived from the current action values at each step, so policy improvement and TD evaluation proceed together.

SARSA is on-policy because its target uses the next action selected by the behavior policy. Exploration is therefore reflected in the values being learned.

Convergence claims require assumptions about exploration and step sizes in the tabular setting. Practical systems may relax these conditions, with different behavior as a result.

He illustrates SARSA with a windy gridworld: an agent must find a route to a goal under environmental disturbances and improve through repeated interaction.

The learning curve and path are results for a particular example; exploration, rewards and environment conditions affect learned behavior.

One-step SARSA uses the next reward and next action value. One can instead include more observed rewards before bootstrapping from a later value estimate.

An n-step return combines the first n discounted rewards with an estimate beyond step n. Larger n includes more observed trajectory but requires waiting longer.

The λ-return combines multiple n-step returns with weights that generally decrease for more distant steps. λ controls the mixture of time scales.

In the limits discussed, λ = 0 corresponds to one-step TD, while λ approaching 1 moves toward a Monte Carlo form using complete returns.

The forward view defines a target through returns of different future lengths. For online computation, the backward view uses eligibility traces to distribute new TD error to recent state–action pairs.

SARSA(λ) maintains an eligibility trace for each state–action pair. A visit increases the trace, which then decays over time, typically giving recent experience more weight.

The one-step TD error compares observed reward and next value with the previous estimate. The algorithm uses that error multiplied by eligibility traces to update relevant action values.

A grid path illustrates credit assignment: an unexpected reward can adjust recently visited state–action pairs more strongly than older experience.

λ affects how far updates propagate backward and the bias–variance tradeoff. Longer trajectories include more random outcomes but rely less on bootstrapped estimates.

Eligibility traces can propagate new information to earlier steps before an episode ends, potentially helping with sparse rewards without automatically solving exploration.

A question clarifies that the various n-step targets all estimate cumulative future return; they differ in where they use an existing value estimate.

Forward and backward views express related credit-assignment ideas under appropriate conditions; online implementation and parameter-update details affect strict equivalence.

The final section introduces off-policy learning: use data generated by a behavior policy to evaluate or improve another target policy.

Motivations include learning from human or other-agent demonstrations and reusing past experience rather than resampling under the target policy every time.

Off-policy methods can study multiple hypothetical policies from one stream, but the data must cover behavior required by the target policy; weighting cannot repair missing support.

Importance sampling adjusts samples by ratios of target-policy and behavior-policy probabilities to correct distribution differences. Small probabilities or large policy differences can create high variance.

Multiplying probability ratios over long trajectories can produce especially high variance. TD methods bootstrap over shorter updates, changing the tradeoff without eliminating risk.

Q-learning is an off-policy TD control method: the behavior policy can explore while the update target uses the largest currently estimated action value in the next state.

Its one-step target is r + γ maxₐ Q(s′,a), and a step size moves the current Q(s,a) toward it. This differs from SARSA’s target using the actual next action.

The exploratory behavior and greedy target policies can differ. Theoretical convergence still depends on sufficient visitation, suitable step sizes and tabular assumptions, and does not guarantee convergence of every deep-learning implementation.

Silver connects the Q-learning update to the Bellman optimality equation: environment samples replace the full expectation used in dynamic programming, and the target uses the current best next-action estimate.

The lecture closes by connecting Monte Carlo, TD and dynamic programming. The next lecture will address function approximation and larger state spaces.