Q-Learning: Off-Policy TD Control

While SARSA learns the value of the policy the agent is currently following (including its exploration steps), Q-Learning takes a different, often more direct, route. Developed by Chris Watkins in 1989, Q-Learning is a foundational off-policy Temporal Difference (TD) control algorithm.

What does "off-policy" mean in this context? It means the policy being learned about (the target policy) is different from the policy used to generate the behavior (the behavior policy). Q-Learning aims directly for the optimal action-value function, $Q^*(S, A)$, regardless of the policy the agent is actually using to explore the environment. The target policy in Q-Learning is the greedy policy with respect to the current action-value estimates, while the behavior policy can be something more exploratory, like epsilon-greedy.

The Q-Learning Update Rule

The core of Q-Learning lies in its update rule. After taking action $A_t$ in state $S_t$ and observing the reward $R_{t+1}$ and the next state $S_{t+1}$, Q-Learning updates its estimate $Q(S_t, A_t)$ using the following rule:

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a) - Q(S_t, A_t) \right]$$

Let's break this down:

1. $Q(S_t, A_t)$: The current estimate of the action-value for the state-action pair experienced.
2. $\alpha$: The learning rate, determining how much the new estimate affects the old one.
3. $R_{t+1}$: The immediate reward received after taking action $A_t$.
4. $\gamma$: The discount factor, valuing immediate rewards more than future ones.
5. $\max_{a} Q(S_{t+1}, a)$: This is the defining part of Q-Learning. Instead of using the Q-value of the actual next action taken ($A_{t+1}$, like in SARSA), Q-Learning uses the maximum possible Q-value for any action $a$ available in the next state $S_{t+1}$. It estimates the return assuming the agent follows the optimal (greedy) policy from state $S_{t+1}$ onwards.
6. $R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a)$: This is the TD target, representing an updated estimate of the expected return starting from state $S_t$ and taking action $A_t$.
7. $[ R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a) - Q(S_t, A_t) ]$: This is the TD error, the difference between the new estimated return (the TD target) and the old estimate $Q(S_t, A_t)$.

The use of the maximum over next actions allows Q-Learning to learn about the greedy policy (which would always choose the action a maximizing $Q(S_{t+1}, a)$) even if the agent is behaving differently (e.g., occasionally taking random actions for exploration via an epsilon-greedy policy).

Comparison of information used in the TD target calculation for SARSA and Q-Learning. SARSA uses the Q-value of the actual next state-action pair ($S_{t+1}, A_{t+1}$), while Q-Learning uses the maximum Q-value over all possible actions $a$ in the next state $S_{t+1}$.

The Q-Learning Algorithm

Here's the pseudocode for the Q-Learning algorithm:

Initialize Q(s, a) arbitrarily for all s in S, a in A(s)
(e.g., Q(s, a) = 0)
Initialize Q(terminal_state, .) = 0

Loop for each episode:
    Initialize S (starting state for the episode)
    Loop for each step of the episode:
        Choose A from S using policy derived from Q (e.g., epsilon-greedy)
        Take action A, observe R, S'
        
        # Core Q-Learning Update
        Q(S, A) <- Q(S, A) + alpha * [R + gamma * max_a Q(S', a) - Q(S, A)]
        
        S <- S'  # Move to the next state
        
        If S is terminal, break inner loop (end episode)
End Loop (episodes)

Algorithm Steps:

1. Initialization: Initialize the Q-table with arbitrary values (often zero). The Q-values for terminal states must be zero. Set learning parameters $\alpha$ (learning rate) and $\gamma$ (discount factor), and parameters for the exploration strategy (like $\epsilon$ for epsilon-greedy).
2. Episode Loop: Repeat for a number of episodes.
3. State Initialization: Start at the initial state $S$ of the episode.
4. Step Loop: Repeat until the current state $S$ is terminal.
5. Action Selection: Choose an action $A$ based on the current state $S$ and the current Q-values. An epsilon-greedy strategy is common: with probability $1-\epsilon$, choose the action with the highest Q-value ($\arg\max_a Q(S, a)$), and with probability $\epsilon$, choose a random action. This is the behavior policy.
6. Execution & Observation: Perform action $A$, observe the reward $R$ and the next state $S'$.
7. Q-Value Update: Apply the Q-Learning update rule using $S, A, R, S'$. Note again that the update uses $\max_a Q(S', a)$, representing the target policy (greedy).
8. State Transition: Update the current state: $S \leftarrow S'$.
9. Termination Check: If $S'$ is a terminal state, the episode ends.

Q-Learning is proven to converge to the optimal action-value function $Q^*$ under standard stochastic approximation conditions, provided that all state-action pairs continue to be visited. Using an epsilon-greedy behavior policy where $\epsilon$ decays over time ensures sufficient exploration initially and eventual convergence towards exploiting the learned optimal policy.

Because Q-Learning directly learns the optimal Q-function, it's often considered more sample-efficient for finding the optimal policy compared to on-policy methods like SARSA, especially when exploration is extensive. However, this direct pursuit of optimality means it doesn't account for the costs or risks associated with the exploration policy itself, which can be a consideration in safety-critical applications where SARSA might be preferred during the learning phase.