3.1 MDP, Rewards, and Bellman Equations: The State Must Retain Information Needed to Predict the Future

Reinforcement learning studies sequential decisions: an action affects the immediate reward as well as later states and available actions. Scoring only the current step can leave tomorrow's trouble on someone else's account. An MDP represents this chain through states, transitions, and returns; Bellman backups show how future value propagates.

Learning Objectives

• Use MDPs to clearly define states, actions, transition dynamics, rewards, initial state distribution, and termination conditions;
• Assess whether a state representation satisfies the Markov property;
• Distinguish between policy value, action value, and optimal value;
• Apply Bellman expectation and optimality equations to perform dynamic programming.

1. Complete Elements of an MDP

A finite Markov Decision Process is typically written as:

$$(\mathcal{S},\mathcal{A},P,R,\gamma ,{\rho }_0).$$

• $\mathcal{S}$: the set of states;
• $\mathcal{A}(s)$: the set of valid actions available in state $s$;
• $P(s^{\prime }\mid s,a)$: the transition probability distribution;
• $R$: the reward distribution or expected reward, which may depend on $s$, $a$, and $s^{\prime }$;
• $\gamma$: the discount factor;
• ${\rho }_0$: the initial state distribution.

Specify whether the time limit belongs to the task or to the sampler. A task with a fixed horizon can truly terminate when time expires; remaining time belongs in the state to preserve the Markov property. A sampling cutoff in a continuing task still requires a future-value estimate. See Gymnasium on time limits.

2. The Markov Property Expresses an Assumption

A state $S_t$ satisfies the Markov property if, given the current state and action, the future is independent of earlier history:

$$P(S_{t+1},R_{t+1}\mid S_0,A_0,\dots ,S_t,A_t)=P(S_{t+1},R_{t+1}\mid S_t,A_t).$$

This does not mean the real world has no memory, it means that the current state already contains all the information needed to predict the future.

Using only robot coordinates may not be sufficient: battery level, door state, whether a key was previously obtained, all of these influence future outcomes. If observations cannot fully determine the hidden state, the problem becomes closer to a POMDP; in such cases, the policy might need to use a belief state or a memory/history network.

3. Reward and Return

The immediate reward $R_{t+1}$ is provided by the environment, while the return accumulates future rewards:

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots .$$

For finite episodes, $\gamma =1$ can be used if the return is bounded; for ongoing tasks, $\gamma <1$ or an average-reward formulation is typically preferred.

$\gamma$ is not merely a measure of "patience", it also influences the target value, effective horizon, and numerical stability. It's not accurate to simply say that a higher $\gamma$ value only means slower convergence.

4. Policy, V, and Q

The policy $\pi (a\mid s)$ defines the distribution over actions.

$$V^{\pi }(s)=E_{\pi }[G_t\mid S_t=s],$$$$Q^{\pi }(s,a)=E_{\pi }[G_t\mid S_t=s,A_t=a].$$

The optimal values are:

$$V^{\ast }(s)=\underset{\pi }{max}{V}^{\pi }(s),Q^{\ast }(s,a)=\underset{\pi }{max}{Q}^{\pi }(s,a).$$

Value functions depend on rewards, discount factors, termination conditions, and the environment's transition dynamics. Changing the reward scale or the time horizon makes Q-values incomparable across different settings.

5. Bellman expectation equation

For a fixed policy:

$$V^{\pi }(s)=\sum _a\pi (a\mid s)\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma V^{\pi }(s^{\prime })].$$

It decomposes the long-term return into an immediate reward and the value of the next state. If the model $P,R$ is known, we can iteratively update the value of all states until the changes become sufficiently small, completing iterative policy evaluation.

"Changes become sufficiently small" is a numerical convergence criterion, not equivalent to the absolute error of the true policy value being small; the error bound depends on the contraction property and the chosen threshold.

6. Bellman optimality equation

$$V^{\ast }(s)=\underset{a}{max}\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma V^{\ast }(s^{\prime })].$$

Value iteration repeatedly applies the optimal Bellman backup. This Python 3 fragment (partial) assumes finite states, finite rewards, and 0≤gamma<1. outcomes supplies (probability, successor, reward, terminal) tuples whose probabilities sum to 1 for each state-action pair. States without actions are treated as terminal. Exceeding the sweep budget raises an error instead of reporting an intermediate result as converged.

def value_iteration(states, actions, outcomes, gamma, tolerance, max_sweeps=10000):
    from math import isfinite

    if not 0 <= gamma < 1:
        raise ValueError("this implementation requires 0 <= gamma < 1")
    if not isfinite(tolerance) or tolerance <= 0:
        raise ValueError("tolerance must be positive and finite")
    states = tuple(states)
    value = {s: 0.0 for s in states}

    for _ in range(max_sweeps):
        updated = {}
        max_change = 0.0
        for state in states:
            candidates = []
            for action in actions(state):
                q = sum(
                    probability * (
                        reward + (0.0 if terminal else gamma * value[next_state])
                    )
                    for probability, next_state, reward, terminal
                    in outcomes(state, action)
                )
                candidates.append(q)
            updated[state] = max(candidates) if candidates else 0.0
            max_change = max(max_change, abs(updated[state] - value[state]))
        value = updated
        if max_change < tolerance:
            return value
    raise RuntimeError("value iteration did not reach tolerance")

For example, an action moves deterministically from S to A with reward 0, then from A to a terminal state with reward 2. Let gamma=0.9. Starting from zero, the first sweep gives V(A)=2 and V(S)=0; the second gives V(S)=1.8. This checks that a synchronous sweep does not accidentally read values from the current sweep. Extract a policy by choosing the legal action with the largest expected backup, with an explicit tie rule.

7. Policy iteration

Policy iteration alternates between:

1. Evaluation: compute the current $V^{\pi }$;
2. Improvement: apply one-step greedy with respect to $V^{\pi }$;
3. Stop when the policy stabilizes.

Exact evaluation can be expensive; modified policy iteration performs only a few sweeps. Value iteration can be viewed as tightly interleaving evaluation and improvement.

8. Model-based vs. Model-free

• model-based: Possess or learn the transition model $P$ and reward function $R$, then use them for planning;
• model-free: Learn value functions or policies directly, without explicitly constructing a complete transition model.

"Model-free" does not imply the absence of environmental assumptions, nor does it mean that samples are more efficient. When a model is known, failing to use it may waste valuable information; learning an incorrect model can lead to biased planning. Methods like Dyna combine real interactions with model-generated experience to improve learning.

9. Reward Specification

Rewards are optimization objectives, not wish lists. Review the following:

• Whether long-term side effects have been overlooked;
• Whether the reward can be gamed by an agent through proxy manipulation;
• Whether multi-objective weightings are grounded in measurable units;
• Whether terminal rewards differ from per-step rewards in shaping agent behavior;
• Whether the reward is observable at deployment time;
• Whether different user groups or scenarios bear costs that were not accounted for.

Reward shaping can improve exploration, but arbitrarily adding distance-based rewards may alter the optimal policy. Potential-based shaping can preserve policy invariance under specific conditions, however, the implementation must still be validated.

Common Misconceptions

• State is just the current sensor value: In partially observable environments, past history still influences future outcomes.
• MDPs always have unknown transition dynamics: Known models allow for direct planning and policy optimization.
• Gamma is merely a training trick: It defines a key component of the target value function.
• Denser rewards lead to faster learning and preserve the original goal: Reward shaping can inadvertently introduce new, suboptimal behaviors.

Exercise

1. Define the minimal Markov state for a maze that includes a door, a key, and power supply.
2. Write out the Bellman equations for a three-state MDP and manually perform one backup iteration.
3. Compare the number of sweeps required by value iteration and policy iteration.
4. Construct a reward hacking behavior and revise the objective function and constraints accordingly.

Summary

An MDP turns sequential decision-making into a computable problem. The Bellman equation holds only if the state space is sufficient to predict the future, and if rewards and termination conditions accurately represent the goal; no algorithm can compensate for a missing critical historical state or an incorrect reward signal in the environment model.

The next lesson explores sample-based learning when transition probabilities are unknown: how Monte Carlo and Temporal-Difference methods give rise to Q-learning, and what exploration and convergence conditions are required.