Reinforcement Learning (Q-Learning)

• The core framework: agent, environment, state, action, reward
• What a Q-table stores and how it is updated
• The Bellman equation — the heart of Q-Learning
• Epsilon-greedy exploration vs exploitation
• The roles of learning rate (α) and discount factor (γ)
• A concrete example: navigating a grid world

The Reinforcement Learning Framework

An agent learns by interacting with an environment:

1. Agent observes the current state (s).
2. Agent chooses an action (a).
3. Environment transitions to a new state (s').
4. Environment gives the agent a reward (r).
5. Agent updates its knowledge and repeats.

The goal: learn a policy — a mapping from states to actions — that maximises total cumulative reward.

Q-Table

A Q-table stores the expected total reward for taking each action in each state.

Q(s, a) = Expected cumulative reward starting from state s, taking action a, then acting optimally.

Example Q-table fragment (4-state, 4-action grid):

At each state, the agent picks the action with the highest Q-value.

The Bellman Equation (Q-Learning Update)

After taking action a from state s and arriving in state s', the Q-value is updated:

Q(s, a) ← Q(s, a) + α × [r + γ × max Q(s', a') − Q(s, a)]

• γ close to 1 → agent plans far ahead (long-sighted)
• γ close to 0 → agent is greedy (only cares about immediate reward)

Epsilon-Greedy Exploration

The agent faces the exploration-exploitation dilemma:

• Exploit: Choose the best-known action (maximise Q).
• Explore: Try a random action (discover better options).

Epsilon-greedy strategy:

• With probability ε, take a random action (explore).
• With probability 1 − ε, take the best-known action (exploit).

Typically, ε starts high (lots of exploration early on) and decays over time as the agent learns.

Grid World Example

Start  .  .  .
 .     .  .  .
 .     .  .  Goal(+10)
Wall(−5) at (1,1)

Training episode 1:

• Agent at (0,0), Q-table all zeros.
• ε = 0.9 → takes random action → moves Right to (0,1).
• Reward = −1 (step cost). Update Q(0,0, Right).
• Continues until reaching Goal → reward +10.

After many episodes:

• Q-table values converge.
• Agent reliably navigates from Start to Goal in minimum steps.

1. Describe the interaction loop in reinforcement learning: what are the four things that cycle between the agent and the environment?

2. In the Bellman equation, what does the discount factor γ control? What behaviour results when γ = 0 versus γ = 0.99?

3. An agent always picks the action with the highest Q-value (ε = 0). What is the risk of this strategy early in training?

4. After 1000 training episodes in a grid world, the Q-table at state (2,3) shows Q-values: Up=1.2, Down=0.3, Left=0.8, Right=9.1. What action will the trained agent take, and why?

5. Why do we need a learning rate (α) less than 1.0? What would happen if α = 1.0 every update?