Temporal Difference (TD) learning is a fundamental reinforcement learning technique that combines ideas from Monte Carlo methods and dynamic programming. It allows agents to learn from experience without requiring a model of the environment, making it particularly valuable for real-world applications.

Understanding Policy Evaluation

Mathematical Foundation

Policy evaluation refers to the process of determining the value function $J_π$ for a given policy $π$. The value function represents the expected cumulative reward when following policy $π$ from a given state.

$$ \underbrace{J_π \in \mathbb{R}^S}_{\substack{\text{Value function} \\ \text{for policy } π}} $$

Where:

  • $S = |S|$ represents the total number of states in the state space
  • $J_π$ maps each state to its expected value under policy $π$

Process

The process for policy evaluation follows these steps:

  1. Policy Definition: Let $μ: S → Δ(A)$ be the policy mapping states to probability distributions over actions
  2. Initialization: Start at some state $s_0 \in S$
  3. Action Selection: Take action $a_0 \sim μ(s_0)$ according to the policy
  4. Transition: Observe next state $s_1 \sim P(\cdot|s_0,a_0)$ based on environment dynamics
  5. Reward: Receive reward $r(s_0,a_0)$
  6. Continue: Repeat the process to generate a trajectory

The resulting sequence is:

$$ s_0, a_0, r(s_0,a_0), s_1, a_1, r(s_1,a_1), s_2, \ldots $$

Value Function Estimation

The quality or value of state $s_0$ under policy $μ$ is defined as:

$$ \underbrace{J_μ(s_0)}_{\substack{\text{Value of} \\ \text{state } s_0}} = \underbrace{\mathbb{E}\left[\sum_{t=0}^{\infty} \gamma^t r(s_t,a_t)\right]}_{\substack{\text{Expected discounted} \\ \text{sum of rewards}}} $$

Where:

  • $\gamma \in (0,1)$ is the discount factor that determines the present value of future rewards
  • The expectation is taken over all possible trajectories when following policy $μ$ from state $s_0$

The Bellman Equation: The Foundation of TD Learning

The value function $J_μ$ satisfies the Bellman equation, which provides a recursive relationship between the value of a state and the values of its possible successor states:

$$ \underbrace{J_μ(s)}_{\substack{\text{Value of} \\ \text{state } s}} = \underbrace{\mathbb{E}_{a \sim μ(s), s' \sim P(\cdot|s,a)}[r(s,a) + \gamma J_μ(s')]}_{\substack{\text{Expected immediate reward} \\ \text{plus discounted future value}}} $$

This can be expanded to show the explicit summations:

$$ \underbrace{J_μ(s)}_{\substack{\text{Value of} \\ \text{state } s}} = \sum_{a \in A} \underbrace{μ(a|s)}_{\substack{\text{Probability of} \\ \text{selecting action } a}} \sum_{s' \in S} \underbrace{P(s'|s,a)}_{\substack{\text{Transition} \\ \text{probability}}} \underbrace{[r(s,a) + \gamma J_μ(s')]}_{\substack{\text{Reward plus} \\ \text{discounted future value}}} $$

The Bellman equation forms the theoretical foundation for TD learning algorithms, as it establishes the relationship between current and future values that these algorithms exploit. With this foundation in place, we can now explore different approaches to policy evaluation.

Approaches to Policy Evaluation

Policy evaluation is the process of determining the value function $J_μ$ for a given policy $μ$. There are two main approaches to policy evaluation: model-based and model-free methods, each with distinct advantages in different scenarios.

Model-Based Policy Evaluation: When We Know the Environment

When we have complete knowledge of the environment dynamics (transition probabilities $P$ and reward function $r$), we can directly solve for the value function using the Bellman equation.

Direct Solution Method

The Bellman equation can be written as a system of linear equations:

$$ \underbrace{J_μ(s)}_{\substack{\text{Value of} \\ \text{state } s}} = \sum_{a \in A} \underbrace{μ(a|s)}_{\substack{\text{Policy} \\ \text{probability}}} \sum_{s' \in S} \underbrace{P(s'|s,a)}_{\substack{\text{Transition} \\ \text{probability}}} \underbrace{[r(s,a) + \gamma J_μ(s')]}_{\substack{\text{Reward plus} \\ \text{discounted future value}}} $$

For a finite state space with $|S|$ states, this forms a system of $|S|$ linear equations with $|S|$ unknowns (the values $J_μ(s)$ for each state $s$). This system can be solved directly:

  1. Express the Bellman equations in matrix form: $J_μ = R_μ + \gamma P_μ J_μ$
  2. Solve for $J_μ$: $J_μ = (I - \gamma P_μ)^{-1} R_μ$

Where:

  • $J_μ$ is the vector of state values
  • $R_μ$ is the vector of expected immediate rewards under policy $μ$
  • $P_μ$ is the state transition probability matrix under policy $μ$
  • $I$ is the identity matrix

This approach provides an exact solution but requires:

  • Complete knowledge of the model ($P$ and $r$)
  • Computational resources to solve the linear system (which can be prohibitive for large state spaces)

Iterative Solution Methods

For larger state spaces, iterative methods are often more practical:

Value Iteration for Policy Evaluation

  1. Initialize $J_μ^0(s) = 0$ for all states $s \in S$
  2. For $k = 0, 1, 2, …$, update:
$$ \underbrace{J_μ^{k+1}(s)}_{\substack{\text{Updated} \\ \text{value estimate}}} = \sum_{a \in A} \underbrace{μ(a|s)}_{\substack{\text{Policy} \\ \text{probability}}} \sum_{s' \in S} \underbrace{P(s'|s,a)}_{\substack{\text{Transition} \\ \text{probability}}} \underbrace{[r(s,a) + \gamma J_μ^k(s')]}_{\substack{\text{Reward plus} \\ \text{discounted future value}}} $$
  1. Continue until convergence: $\max_{s \in S} |J_μ^{k+1}(s) - J_μ^k(s)| < \epsilon$ for some small $\epsilon > 0$

While model-based methods are powerful when the environment is known, most real-world problems require learning without complete knowledge of the environment. This leads us to model-free approaches.

Model-Free Policy Evaluation: Learning from Experience

In many real-world scenarios, we don’t have access to the environment model ($P$ and $r$). Instead, we must learn the value function by interacting with the environment and observing outcomes.

Monte Carlo Methods: Learning from Complete Episodes

Monte Carlo methods estimate the value function by averaging returns from complete episodes:

$$ \underbrace{J_\mu(s)}_{\substack{\text{Value of} \\ \text{state } s}} = \mathbb{E}_\mu \left[ \underbrace{\sum_{t=0}^{T} \gamma^t r(s_t, a_t)}_{\substack{\text{Total discounted} \\ \text{return}}} \bigg| s_0 = s \right] $$

The process works as follows:

  1. Initialize value estimates $V(s) = 0$ for all states $s \in S$
  2. Initialize counters $N(s) = 0$ for all states $s \in S$
  3. For each episode:
    • Follow policy $\mu$ to generate a trajectory: $(s_0, a_0, r_0, s_1, a_1, r_1, …, s_T)$
    • Calculate the return for each state visited: $G_t = \sum_{k=t}^{T} \gamma^{k-t} r_k$
    • For each state $s_t$ visited in the episode:
      • Increment counter: $N(s_t) = N(s_t) + 1$
      • Update value estimate: $V(s_t) = V(s_t) + \frac{1}{N(s_t)}(G_t - V(s_t))$

Monte Carlo methods require complete episodes but provide unbiased estimates of the value function. However, they can be slow to converge and may require a large number of episodes to obtain accurate estimates. This limitation leads us to temporal difference methods, which offer a more efficient learning approach.

Temporal Difference Methods: Learning from Partial Episodes

Temporal difference (TD) methods learn the value function by bootstrapping from partial episodes:

TD(0) Learning: The Simplest TD Method

TD(0) is the simplest temporal difference method that updates value estimates based on the immediate reward and the estimated value of the next state:

$$ \underbrace{V(s_t) \leftarrow V(s_t) + \alpha_t \left[ \underbrace{r_t}_{\substack{\text{Immediate} \\ \text{reward}}} + \underbrace{\gamma V(s_{t+1})}_{\substack{\text{Discounted value} \\ \text{of next state}}} - \underbrace{V(s_t)}_{\substack{\text{Current state} \\ \text{value}}} \right]}_{\substack{\text{TD(0) update rule}}} $$

Where:

  • $V(s_t)$ is the estimated value of state $s_t$
  • $\alpha_t \in (0,1]$ is the learning rate at time $t$
  • $r_t$ is the reward received after taking action $a_t$ in state $s_t$
  • $\gamma \in [0,1)$ is the discount factor
  • $s_{t+1}$ is the next state
  • The term $r_t + \gamma V(s_{t+1}) - V(s_t)$ is called the TD error This update rule is more intuitive and directly represents how TD(0) works: we adjust our estimate of the current state’s value based on the observed reward and our estimate of the next state’s value.

TD(0) offers significant advantages over Monte Carlo methods:

  1. Real-time learning: TD methods update value estimates after each step rather than waiting for episode completion, making them more suitable for continuous environments and providing faster feedback.

  2. Online updates: The algorithm can learn during an episode, allowing for immediate policy improvements without waiting for complete trajectories.

  3. Lower variance: By bootstrapping from existing value estimates, TD methods typically have lower variance than Monte Carlo methods, though they introduce some bias.

  4. Works in non-terminating environments: Unlike Monte Carlo methods which require episodes to end, TD learning can be applied in continuing tasks where there is no natural endpoint.

With this understanding of TD(0), we can now explore more advanced TD methods that offer even greater flexibility and performance in complex environments.