Sequential decisions and value functions

Prerequisites: Conditional expectation and probability.

Learning objectives

• Write a Bellman backup.
• Calculate a short discounted return.
• Distinguish a learned policy from offline evidence.

The state must support prediction of the next step

A Markov decision process specifies states, actions, transition probabilities, rewards, and a discount factor. The Markov assumption says that the distribution of the next state and reward depends on the current state and action, rather than on additional history. A convenient state representation may fail this assumption when it hides important information.

A policy maps states to actions or action probabilities. The value of a state under a policy is the expected discounted sum of future rewards. With discount γ, rewards r₀,r₁,r₂ contribute r₀+γr₁+γ²r₂. The index convention should be stated; textbooks differ in whether the first reward is labeled r₀ or r₁.

Work a Bellman backup

Suppose a state has two actions. Exit gives reward 3 and terminates. Continue gives reward 1 and moves with certainty to a state whose current estimated value is 4. With γ=0.5, the two action values in this backup are 3 and 1+0.5×4=3. They tie. If the successor value were 6, Continue would have estimated value 4 and would be preferred.

For an optimal value function, the Bellman equation takes the maximum over actions of expected immediate reward plus discounted successor value. Value iteration repeatedly applies this backup. In a finite discounted MDP with bounded rewards and 0 ≤ γ < 1, the Bellman optimality operator is a contraction, which gives convergence to the unique optimal value function. That result depends on the stated model and assumptions.

Learning adds an evidence problem

In model-based planning, the transition and reward model is supplied or estimated. In model-free learning, updates can estimate values directly from experience. Both must confront exploration: actions that currently look worse may reveal information needed to improve future decisions.

A high score on logged data does not automatically establish the performance of a different policy. The log may contain little evidence about actions that the new policy would choose. Distribution shift compounds over multiple decisions because the policy affects which states are visited.

Reward is a specification. If a tutoring system rewards only time spent, it may favor confusing material that keeps learners stuck. Define the intended outcome, test for shortcuts, impose constraints where appropriate, and evaluate behavior rather than just the scalar score. In safety-critical settings, simulation and offline evaluation cannot by themselves justify uncontrolled experimentation on people.

Practice problem

A three-step episode gives rewards 2, 0, and 8 with γ=0.5. Compute its return. A second action gives reward 5 immediately and terminates. Which is preferred by this discounted-return objective, and what changes if γ=1?

Worked solution

The first return is 2+0.5×0+0.25×8=4, so the immediate reward of 5 is preferred for γ=0.5. With γ=1 the first return is 10, so it is preferred instead. The discount factor changes the objective, not just the speed of a learning algorithm. With stochastic transitions these comparisons use expectations, and finite observed episodes introduce estimation uncertainty. A preference under this objective is not proof that the reward captures every consequence that matters.

Check your understanding

What does a policy specify?

• A mapping from states to actions or action probabilities.
• Only the transition model.
• Only the discount factor.
• A proof that rewards are ethical.

Explanation

A policy is the decision rule used to choose actions.

Why can a new policy be difficult to evaluate from old logs?

• Discounting makes evaluation impossible.
• Rewards cannot be recorded.
• The old policy may rarely choose the actions the new policy needs.
• Every policy visits identical states.

Explanation

Insufficient action coverage limits evidence about counterfactual decisions.

Primary reading

• Reinforcement Learning: An Introduction: Sutton and Barto

Open the study and save your work →