Q-Learning Update Rule

Chapter 2 ended with Bellman equations. For Q-learning, the key bridge is the Bellman optimality equation for actions:

$$Q^*(s,a)=\mathbb{E}\left[R_{t+1}+\gamma\max_{a'}Q^*(S_{t+1},a')\mid S_t=s,A_t=a\right]$$

The optimal Q-value equals the expected immediate reward plus the discounted value of the best next action. In a delivery robot example, $Q^*(s,a)$ asks: if the robot takes this first move from this situation, how much return should it expect if it behaves optimally afterward?

If we knew $P$ and $R$, we could compute the expectation by averaging over all possible next states and rewards. In real learning problems, the agent usually cannot compute that expectation. It can sample it: take action $a_t$, observe reward $r_{t+1}$, and see the next state $s_{t+1}$.

So, we need a way to learn $Q^*(s,a)$ directly from experience, without knowing $P$ or $R$. That is Q-learning.

After taking action $a_t$ in state $s_t$, receiving reward $r_{t+1}$, and observing next state $s_{t+1}$, Q-learning updates only the table entry for the state-action pair it just used.

The update rule is $$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]$$

The bracketed quantity is the temporal-difference error, often written $$\delta_t=r_{t+1}+\gamma\max_{a'}Q(s_{t+1},a')-Q(s_t,a_t)$$ It measures surprise: how different the sampled target was from the current estimate. If $\delta_t=0$, the prediction matched the sampled target.