Semi-gradient Methods for Value Prediction

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.

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.

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.

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.

Purpose and Setup

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

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.

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.

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

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

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

• Updating before observing the reward and next state.

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

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

• Using the next state as the current state too early.

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

  Fix: Update θ first, then set S to S′.

• Treating the gradient as a single scalar.

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

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

• Confusing the step size with the update direction.

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

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

Practice Trace

Key Takeaways

1. Stochastic gradient descent changes the weight vector immediately after each individual example.
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. Each update addresses one local example error, while repeated updates across suitable examples can reduce an average objective such as MSVE.
4. Semi-gradient TD(0) evaluates a supplied policy by repeatedly improving the weights of a differentiable value-function approximation.
5. For one transition, the reliable order is: choose an action, observe R and S′, update θ, and then set S to S′.