Exploration vs exploitation
A learning agent has to try things to find out what they're worth, but every untried action might be a waste. Too little exploring and it settles for the first decent option; too much and it never uses what it knows.
Kind: not an agent: how a learning agent picks its actions while it learns.
Week: 4 (slides 41 to 43).
Book: not in Wooldridge. Sutton and Barto 2.2, 2.3 and 2.6.
Techniques on this page: the dilemma, ε-greedy, decaying ε, optimistic initial values and Thompson sampling.
The problem it solves
Q-learning can only learn \(Q(s, a)\) by actually doing \(a\) in \(s\). An agent that always picks the action that currently looks best (exploitation) never collects evidence about the others, and can lock onto a mediocre choice for ever. An agent that always acts at random (exploration) learns a lot but never benefits. The behaviour policy has to balance both (slide 41).
Words you’ll hear
| Word or symbol | Plain meaning |
|---|---|
| exploit | take \(\arg\max_a Q(s, a)\), the action believed best |
| explore | try something else to check the belief |
| greedy | always exploit |
| \(\varepsilon\) (epsilon) | the chance of acting at random |
| decay | shrinking ε as learning goes on |
| optimistic initialisation | starting every Q-value high |
| Thompson sampling | act greedily on a random draw from what the values might plausibly be |
Technique 1: the dilemma, in a tiny world
Problem it solves: shows how pure greed fails.
Worked example (the tempting exit). A corridor 0 – 1 – 2 – 3 – 4, start at 0. West from 0 exits at once with reward 0.3; reaching 4 gives 1; \(\gamma = 0.95\). Best at 0 is East: \(0.95^3 \approx 0.857 > 0.3\).
A greedy agent with \(Q = 0\) that breaks ties towards West exits on its first try: \(Q(0, W)\) becomes positive, \(Q(0, E)\) stays exactly 0 because East is never tried, and it exits for ever. It never learns East was better.
Technique 2: ε-greedy
Problem it solves: the simple default way to keep exploring (slide 42).
\[\pi(s) = \begin{cases}\text{a random action from } A & \text{with probability } \varepsilon\\ \arg\max_a Q(s, a) & \text{with probability } 1 - \varepsilon\end{cases}\]
Worked example. \(|A| = 4\), \(\varepsilon = 0.2\), random choice over all of \(A\) (as on the slide): greedy action \(1 - \varepsilon + \varepsilon/|A| = 0.8 + 0.05 = 0.85\); each other action \(\varepsilon/|A| = 0.05\).
\(|A| = 3\), \(\varepsilon = 0.3\): greedy \(0.7 + 0.1 = 0.8\), others \(0.1\) each.
Because Q-learning is off-policy, learning from ε-greedy behaviour still gives the greedy policy’s values.
Technique 3: decaying ε
Problem it solves: explore while \(Q\) is unreliable, exploit once it’s good.
For example \(\varepsilon_k = \max(0.05, 0.995^k)\) after episode \(k\): 0.61 after 100 episodes, 0.08 after 500, then it stays at the 0.05 floor.
Technique 4: optimism and Thompson sampling
Problem it solves: smarter exploration than random dithering (slide 43, “optional contrasts”).
- Optimism in the face of uncertainty: start every \(Q\) high (above any real return). Untried actions look great until trying them brings them down, so even a purely greedy agent tries everything. In the tempting-exit world, starting \(Q\) at 1 finds East straight away.
- Thompson sampling: keep a distribution over plausible Q-values, sample one, act greedily on the sample. Uncertain actions sometimes sample high, so they get tried about as often as they plausibly deserve.
Both can need fewer samples than ε-greedy, which has to stumble on a good route at random (in the tempting exit, East at four cells in a row). ε-greedy stays the workhorse because it’s simple with one parameter. RLHF (topic 5) carries these ideas into fine-tuning LLMs.
Two versions of ε-greedy. Some books choose the random action only among the non-greedy ones (then the greedy action has exactly \(1 - \varepsilon\)). Slide 42 says “random \(a_t \in A\)”, so the greedy action can also come up at random.
What to read
| Source | Read? | Why |
|---|---|---|
| Wooldridge | Not covered | |
| Sutton and Barto 2.2 to 2.3, 2.6 | Optional | ε-greedy on bandits, optimistic initial values |
Practice prompt
I'm studying CS5940 Intelligent Agents, week 4 (MDPs and reinforcement learning). I want practice on EXPLORATION VS EXPLOITATION:
- why a purely greedy learner can lock onto a poor action, with a small example
- epsilon-greedy action probabilities for different |A| and epsilon (random choice over all actions)
- decaying epsilon schedules
- how optimistic initial values make a greedy agent explore, and what Thompson sampling does
- why Q-learning can learn the greedy policy from epsilon-greedy behaviour (off-policy)
Please:
1. Use plain, everyday language and explain any symbol in one short sentence.
2. Give me ONE question at a time, easy first, then harder, with friendly numbers.
3. Wait for my answer, then mark it and show the full working.
4. If I get it wrong, explain the mistake and give me a similar question.
5. Every 5 questions, summarise my strengths and what to practise.