Concepts / Semi-gradient Methods for Value Prediction

Semi-gradient Methods for Value Prediction

Semi-gradient methods are easier to understand if you first focus on the timing of an update.

  • Programming

Immediate Weight Adjustments

Semi-gradient methods are easier to understand if you first focus on the timing of an update. A value-prediction system receives examples one after another. Stochastic gradient descent does not wait until every example has been processed before changing its parameters. Instead, it makes a small adjustment to the weight vector immediately after each example. Semi-gradient TD(0) uses this repeated-update idea while estimating the value function of a supplied policy.

Key point

The word stochastic refers here to using one example for each update. The update is local because it responds to the example currently being considered, but many such updates can support improvement of an average objective such as mean squared value error, or MSVE.

Gradient Direction and Step Size

Gradient descent minimizes a function by moving in the direction of the negative gradient. The gradient is a vector, not a single number: it has one partial derivative for each component of the weight vector. Each component indicates how the error changes when the corresponding weight changes. Taken together, the gradient points toward the direction of greatest error increase. Subtracting the gradient therefore points toward the direction of most rapid decrease.

The step-size parameter controls the scale of the movement. A positive step size multiplies the descent direction, so it determines how large the adjustment is while the negative gradient determines its direction. The current weight vector is the starting point, and the updated weight vector is the result after taking that scaled step.

Current weightsθtUpdated weightsθt+1Gradienterror increase directionStep sizepositive scalestarting pointnegative directionsets movement scale
How does the gradient indicate the direction of steepest error increase, and how does the step-size parameter control movement in the opposite direction?
Update approachWhen weights changeWhat supplies the immediate direction
Ordinary gradient descentAfter considering the full objectiveThe gradient of the objective being minimized
Stochastic gradient descentAfter each individual exampleThe example currently being considered

The key distinction is when the weight vector is changed and whether the immediate update is based on one example or the full objective.

From Local Error to MSVE

A single stochastic update does not directly examine every example at once. It focuses on the error associated with the one example just considered. This local focus can still improve broader performance because the process repeats across many examples. When those examples follow the same distribution as the states used for the MSVE objective, small corrections on observed examples can have the overall effect of reducing an average measure such as mean squared value error.

In the real world

Generated example: Imagine a value-prediction system receiving a stream of state examples. After the first example, it makes one small correction. After the next example, it makes another correction based on that new local error. No single correction represents the entire average objective, but the repeated sequence can move performance toward a lower average error when the examples have the relevant distribution.

Key point

Keep the two interpretations separate: locally, an update tries to reduce one example's error; broadly, repeated updates across suitable examples work toward reducing an average performance measure. The local step and the overall objective are related, but they are not identical.

Value Estimates from Weights

Semi-gradient TD(0) represents a value function with a differentiable function v̂ that depends on a state and a weight vector θ. The weights are the adjustable parameters. For a current state, the function uses the state together with the current weights to produce an estimated value. After a transition is observed, the algorithm changes θ; using the changed weights can therefore change the estimated value produced for a state.

StateSEstimated valuev̂(S, θ)Weight updatenew θEstimated valueusing updated θWeight vectorθinputparameterscurrent estimate participateschanges parameters
How do the weight vector and a state produce an estimated value, and how can an update change that estimate?

Purpose and Setup

Definition

Semi-gradient TD(0) is used for policy evaluation and value-function estimation. It estimates the value function of a supplied policy π while repeatedly improving the weights of a differentiable value-function approximation.

  • The policy π being evaluated
  • A differentiable value function v̂ that depends on a state and weight vector θ
  • A current weight vector θ
  • Episodes generated by the supplied policy
  • A current state S from which the next action is selected

One Transition in Order

For one TD(0) transition, preserve the algorithm's order exactly. Begin with the current state S. Choose an action from the policy π(·|S). Then observe the reward R and next state S′. Only after both have been observed can the weight update use the current-state estimate, the next-state estimate, the observed reward, the gradient, and the step size. After the update, assign S to S′ so that the next iteration starts from the observed next state.

Worked example

Tracing a Single Transition

A trace begins at state S with weight vector θ. The policy selects an action. The environment then supplies reward R and next state S′. Identify the correct role of each item in the update sequence.

  1. 1
    Start

    Use the current state S and current weight vector θ. The value function supplies the current-state estimate.

  2. 2
    Select

    Choose an action from the supplied policy π(·|S).

  3. 3
    Observe

    Receive the reward R and observe the next state S′. These are required before the update can be traced.

  4. 4
    Update

    Use R, the next-state estimate, the current-state estimate, the gradient, and the positive step-size parameter to adjust θ.

  5. 5
    Advance

    After the weight update, replace S with S′. The next transition begins from that new current state.

Result

The reliable one-step order is choose an action, observe R and S′, update θ, and then set S to S′.

Policy πselect actionEnvironmentreturn R and S′Weight vector θapply updateCurrent state Sset S to S′Terminal statestop episodeactionR and S′after updatecontinue if nonterminalif S′ is terminal
What happens first, next, and last as TD(0) selects an action, observes the next state and reward, updates the weights, and continues until the episode ends?

Episode-Level Tracing

At the episode level, the one-step sequence repeats. The policy chooses an action from the current state, the transition produces R and S′, the algorithm updates θ once for that observed transition, and then the current state is replaced by S′. The episode stops when S′ is terminal. The order matters because the current state used for the update must still be the state from which the action was selected.

Key point

The update uses information from both sides of the transition: the current-state estimate describes the state being updated, while the reward and next-state estimate provide the observed transition information used to adjust the weights. The gradient connects that error-related adjustment to the components of θ, and the step size controls the scale.

Tracing Unexpected Results

When a traced result looks unexpected, do not begin by changing the final weight value. Find the first point at which the trace no longer matches the algorithm. Check the action, observations, update inputs, and state assignment in that order.

  • Common mistake

    Using an action that did not come from the supplied policy.

    What it looks like

    The trace shows an action selected without applying π(·|S).

    Why it fails

    Semi-gradient TD(0) evaluates the supplied policy, so the action-selection step must come from that policy.

    Do this instead

    Verify the action-selection step before checking the numerical update.

  • Common mistake

    Updating before observing the reward and next state.

    What it looks like

    The trace changes θ immediately after choosing an action.

    Why it fails

    The reward R and next state S′ appear in the update information and must be observed first.

    Do this instead

    Place the observation of R and S′ before the weight update.

  • Common mistake

    Using the next state as the current state too early.

    What it looks like

    The trace assigns S to S′ before calculating the update.

    Why it fails

    The update must use the current S from which the action was selected and the observed S′ as the next state.

    Do this instead

    Update θ first, then set S to S′.

  • Common mistake

    Treating the gradient as a single scalar.

    What it looks like

    The trace uses one undifferentiated number for all weight components.

    Why it fails

    The gradient is a derivative vector with one partial derivative for each component of the weight vector.

    Do this instead

    Track the gradient as a vector whose components describe how the error changes with the corresponding weights.

  • Common mistake

    Confusing the step size with the update direction.

    What it looks like

    The trace treats α as deciding whether the update should move toward increasing or decreasing error.

    Why it fails

    The negative gradient supplies the descent direction; the positive step size controls the movement's scale.

    Do this instead

    Separate direction, supplied by the negative gradient, from scale, supplied by the step size.

Check policy actionπ(·|S)Check observationsR and S′Check estimatescurrent and next stateCheck weight updategradient and step sizeCheck stateassignmentS becomes S′ after updateFirst mismatchtrace diverges hereif incorrectif correctif missing or wrongif correctif inconsistentif correctif incorrectif correctif incorrect
At which state, estimate, reward, gradient, or update step could an unexpected value first arise when tracing one transition?

Practice Trace

EASY

A trace follows this order: choose an action from π, observe S′ and R, replace S with S′, and then update θ. Identify the first ordering problem and rewrite the one-step order correctly.

Hints
  • The reward and next state must be available before the update.
  • The update must still use the original current state.
  • The state assignment occurs after the weight update.

What do you think happens?

What may happen if a trace assigns S to S′ before applying the update?

  • The trace remains in the required order.

  • The update may no longer use the intended current state.

  • The step size corrects the ordering automatically.

  • The episode must terminate immediately.

Reveal answer
Answer:

The update may no longer use the intended current state.

The required order is to observe R and S′, update θ using the current S and observed S′, and only then assign S to S′.

Key Takeaways

  1. 1
    Stochastic gradient descent changes the weight vector immediately after each individual example.
  2. 2
    The gradient points toward greatest error increase, so the negative gradient supplies the direction of decreasing error; the positive step size controls the movement's scale.
  3. 3
    Each update addresses one local example error, while repeated updates across suitable examples can reduce an average objective such as MSVE.
  4. 4
    Semi-gradient TD(0) evaluates a supplied policy by repeatedly improving the weights of a differentiable value-function approximation.
  5. 5
    For one transition, the reliable order is: choose an action, observe R and S′, update θ, and then set S to S′.

At a glance

  • SGD makes a small weight adjustment after each individual example rather than waiting for all examples.
  • The negative gradient gives the direction of decreasing error, while the step size determines the adjustment's scale.
  • Many local example-based updates can support reduction of an average objective such as MSVE.
  • Semi-gradient TD(0) is used to evaluate a policy and estimate its value function with differentiable value-function approximation.
  • A correct TD(0) trace observes the reward and next state before updating and assigns the next state only after the update.

Related Topics

Related concepts

More concepts starting with S