Q-Learning

Q-Learning Mechanics

Q-Learning maintains a table (or function approximator) $Q(s, a)$ storing expected cumulative return for taking action $a$ in state $s$.

                        Q-LEARNING ITERATION LOOP
  1. Observe State s
  2. Select Action a using ε-Greedy (Exploration vs Exploitation)
  3. Execute Action a ──► Observe Reward r and Next State s'
  4. Compute TD Target:   Target = r + γ max_{a'} Q(s', a')
  5. Compute TD Error:    δ = Target - Q(s, a)
  6. Update Q Table:      Q(s, a) ← Q(s, a) + α · δ

The Single-Step Update Formula

$$Q(s, a) \leftarrow Q(s, a) + \alpha \overbrace{\Big( \underbrace{r + \gamma \max_{a'} Q(s', a')}_{\text{TD Target}} - Q(s, a) \Big)}^{\text{TD Error } \delta_t}$$

• $\alpha \in (0, 1]$: Learning rate.
• $\gamma \in [0, 1)$: Discount factor.
• $\max_{a'} Q(s', a')$: Greedy Off-Policy Target (Assumes optimal action will be chosen in $s'$).

Exploration vs Exploitation ($\epsilon$-Greedy Policy)

To avoid getting trapped in local sub-optimal actions, actions are selected via $\epsilon$-greedy:

$$a_t = \begin{cases} \text{Random Action } a \in A & \text{with probability } \epsilon \quad \text{(Exploration)} \ \arg\max_a Q(s_t, a) & \text{with probability } 1 - \epsilon \quad \text{(Exploitation)} \end{cases}$$

Typically, decay $\epsilon \to 0.01$ over training iterations.

Convergence Proof

Watkins & Dayan (1992) proved that Tabular Q-Learning converges to optimal action-values $Q^*(s, a)$ with probability 1 if:

1. All state-action pairs $(s, a)$ are visited infinitely often.
2. Learning rate satisfies Robbins-Monro conditions: $\sum \alpha_t = \infty$ and $\sum \alpha_t^2 < \infty$.

Say this out loud

"Q-Learning is a model-free, off-policy TD control algorithm. It updates action values using Q(s,a) ← Q(s,a) + α [r + γ max_{a'} Q(s',a') - Q(s,a)]. It is off-policy because it uses a greedy max target max_{a'} Q(s',a') to evaluate optimal behavior while executing an ε-greedy behavior policy for exploration."

Follow-ups to expect

• What is Overestimation Bias in Q-Learning? The $\max$ operator $\max_{a'} Q(s', a')$ uses noisy Q estimates, systematically overestimating action values. Solved by Double Q-Learning (Double DQN).
• What happens when state space S is continuous? Tabular Q-tables crash due to infinite states. Replace the lookup table with a Deep Neural Network $Q(s, a; \theta)$, deriving Deep Q-Networks (DQN).