Q-learning, one of the oldest and most widely taught reinforcement learning algorithms, learns a table (or, for large state spaces, a function) $Q(s, a)$: the expected total future reward of taking action $a$ in state $s$, and then acting optimally afterward. The agent updates its estimate after every step, nudging $Q(s, a)$ toward the reward just observed plus the best value achievable from the next state.
- Observe the current state $s$.
- Choose an action $a$: usually the action with the highest known $Q(s, a)$, but occasionally a random action (exploration) so the agent keeps discovering better options rather than settling early on a merely adequate policy.
- Take the action, observe the reward $r$ and the new state $s'$.
- Update: $Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma \max_{a'} Q(s',a') - Q(s,a) \right]$, where $\alpha$ is the learning rate and $\gamma$ discounts future reward relative to immediate reward.
- Repeat for many episodes, until $Q$ stops changing meaningfully.
ML concept: Exploration versus Exploitation
An agent that always picks the action it currently believes is best (pure exploitation) can get permanently stuck on a mediocre policy it never tests alternatives against. An agent that always picks randomly (pure exploration) never uses what it has learned. Nearly every practical RL agent, including the honeypot agent in the next topic, uses an $\epsilon$-greedy policy: act greedily with probability $1-\epsilon$, act randomly with probability $\epsilon$, and shrink $\epsilon$ as training progresses.
Try it yourself: Trace One Update by Hand
An agent in state $s=3$ takes action $a=1$ and observes reward $r=0.4$, landing in state $s'=4$, where the best known value is $\max_{a'} Q(4,a') = 2.0$. Using $\alpha=0.1$ and $\gamma=0.9$, and given that $Q(3,1)$ currently equals $1.5$, compute the updated value of $Q(3,1)$ using the update rule above.