Q-Learning

Q-learning is an off-policy TD control algorithm that directly learns the optimal action-value function $Q^*$.

Update rule:

Off-policy: the $\max_{a'}$ means we update toward the best possible action, regardless of what action the behavior policy actually took. The agent can explore (e.g., $\epsilon$-greedy) while learning the optimal policy.

Algorithm (tabular):

1. Initialize $Q(s,a)$ arbitrarily
2. For each step: observe $S_t$, take action $A_t$ (e.g., $\epsilon$-greedy), observe $R_{t+1}, S_{t+1}$
3. Apply the update rule above
4. Converges to $Q^*$ given sufficient exploration and decaying learning rate

$\epsilon$-greedy exploration:

• With probability $\epsilon$: random action (explore)
• With probability $1-\epsilon$: greedy action $\arg\max_a Q(s,a)$ (exploit)
• Decay $\epsilon$ over time for convergence

Convergence: guaranteed to converge to $Q^*$ in the tabular case under standard conditions (all state-action pairs visited infinitely often, learning rate decays appropriately).

Scaling up: tabular Q-learning fails for large/continuous state spaces → Deep Q-Network uses a neural network to approximate $Q$.

See also: SARSA, Miscoral Difference Learning, Deep Q-Network