Exploration & Exploitation – Game AI (Multi-Armed Bandits)

One-Armed Bandit Problem

• Simplest possible slot-machine scenario: a single lever that returns either a jackpot (reward $=1$) or a loss (reward $=0$).
• Unknown but fixed “true” probability of winning is denoted $p_*$.
• Learner repeatedly “pulls” and forms a belief $\hat p_t$ after each trial.
  • Example belief trajectory given in the slides:
  • Pull 1 → WIN → $\hat p_1 = 1.0$ (optimistic – based on only one sample)
  • Pull 2 → LOSS → $\hat p_2 = 0.5$
  • Pull 3 → LOSS → $\hat p_3 \approx 0.33$
  • Pull 4 → LOSS → $\hat p_4 = 0.25$
  • …
  • Pull N → LOSS → $\hat p_N = \tfrac{1}{N}$
• Highlights the tension: with limited data, our estimate wanders and confidence is poor.

Multi-Armed Bandit (MAB) Problem

• Generalisation: $K$ different machines, each with unknown win probability $p<em>1,\,p</em>2,\,\dots,\,p_K$.
• Objective: maximise total expected reward (e.g.
  $\max<em>{\text{policy}} \; \mathbb E\big[\sum</em>{t=1}^{T} r_t\big]$)
  which is equivalent to minimising regret (defined later).
• Games shown as examples: Borderlands, GTA 5, Yakuza 5, Super Mario slot mini-game, etc.

Exploration vs. Exploitation Trade-off

• If we exploit only the current best-looking machine, we might be wrong forever.
• If we explore forever, we waste pulls on sub-optimal options.
• Goal: find a principled way to balance making money now with learning for the future.

Pure Exploration Policy (Random)

• Always choose a random arm; no memory of statistics.
• Guarantees maximal information gathering but terrible short-term reward.
• Example from slide: randomly visit Mario-themed slots → illustrated outcome distribution (50 % blue, 25 % red, 10 % green, etc.).

Naïve / Heuristic Strategies Mentioned

0. No stats – pick a favourite and stick with it.
1. Initialise $\hat p=0$ for all machines and always pick the highest belief (ties → fewest losses).
   • First positive reward locks agent onto that arm forever (can be catastrophically wrong).
2. “Optimistic prior” – start every arm at $\hat p=1.0$ with fictitious count $N_0$.
   • Large $N_0$ lowers risk of a good arm falling behind due to early bad luck.
3. “Switch-on-loss” – move to next-best arm after every failure.
   • Never settles; oscillates; incurs perpetual exploration cost.
4. “Epsilon-First / Round-Robin” – visit every arm exactly $N$ times, then stick with the currently best.
   • Works only if chosen $N$ is large enough for statistical significance.

$\epsilon$-Greedy Strategy

• Parameters: $\epsilon \in [0,1]$ (e.g. $\epsilon=0.1$).
• Policy:
  • With probability $1-\epsilon$ → exploit: pull arm with highest current belief $\hat p$.
  • With probability $\epsilon$ → explore: pick a random arm.
• Benefits:
  • Simple; computationally cheap.
  • Can “escape” early greedy traps because of the forced randomness.
• Numbers from slide: 90 % best-believed, 10 % random when $\epsilon=0.1$.

Decaying $\epsilon$-Greedy

• Schedule $\epsilon<em>t \downarrow 0$ over time, e.g. $\epsilon</em>t = \frac{1}{\log(t+1)}$.
• Yields logarithmic asymptotic regret: $R_T = \mathcal O(\log T)$.
• Downside: requires domain knowledge to pick a good decay schedule.

Regret – Formal Performance Measure

• At each step $t$ the optimal arm’s expected reward is $r_t^*$.
• Agent receives $r_t$.
• Instantaneous regret: $\Delta<em>t = r</em>t^* - r_t$.
• Cumulative regret after $T$ pulls:
  $R<em>T = \sum</em>{t=1}^{T} \big(r<em>t^* - r</em>t\big).$
• Minimising $R_T$ ⇔ maximising total reward.
• Plot shown in slides compares regret growth for:
  • Pure greedy (sky-rockets).
  • Fixed $\epsilon$-greedy (sub-linear).
  • Decaying $\epsilon$-greedy (logarithmic, best of those displayed).

Reinforcement Learning Connection

• Bandit = single-state reinforcement-learning problem (no state transitions).
• Core RL concepts illustrated:
  • Policy (mapping from observations → actions).
  • Reward signal.
  • Exploration/exploitation dilemma.
• Games/visual metaphors: DuckTales remastered (Scrooge swimming in coins) emphasises maximising long-term return.

Practical / Philosophical Takeaways

• Early optimism (strategy 2) is a simple yet powerful fix to “premature convergence.”
• Regret gives us a yard-stick independent of reward scale; critical for algorithm comparison.
• Real-world applicability: ad selection, A/B testing, recommendation engines — anywhere we repeatedly choose among alternatives with uncertain payoffs.
• Ethical caution: aggressive exploration on real users can lower their experience (e.g. showing many bad ads) → need to tune $\epsilon$ responsibly.

Numerical & Statistical References Recap

• Win probabilities in example table: $1.0 \to 0.5 \to 0.33 \to 0.25 \to \dots\, \tfrac{1}{N}$.
• Super-Mario mini-game pictogram probabilities: 50 %, 25 %, 10 % (illustrative, not exact).
• $\epsilon=0.1$ ⇒ 90 % exploitation, 10 % exploration.
• Logarithmic regret bound for decaying $\epsilon$-greedy: $R_T \le C\log T$ for some constant $C$.