W1_L3: Immediate RL and bandits

Main Ideas and Concepts

• Reinforcement learning (RL) setting

  • RL is trial-and-error learning (not learning from a fixed dataset).
  • You receive feedback only after you take actions.
  • Therefore, to learn the quality of actions, an agent must explore to discover what works; otherwise it cannot evaluate alternatives.

• Core RL mechanism: exploration vs. exploitation

  • Exploration: try different actions to figure out which action is best.
  • Exploitation: after learning which action seems best, repeatedly choose it to obtain higher rewards.
  • The central dilemma:
    • How long should you explore?
    • When do you know enough to start exploiting?
  • Too much exploration wastes time; too little exploration can cause the agent to get stuck with a suboptimal action.

• Immediate reinforcement learning simplification

  • Classic RL often involves sequences of actions before receiving an outcome (e.g., tic-tac-toe has multiple moves before win/loss).
  • The lecture simplifies the problem to one action → immediate payoff:
    • Each action’s evaluation occurs right away (no long temporal buildup).
  • This reduces the RL tradeoff to the exploration-exploitation dilemma in its simplest form.

• Multi-armed bandit formulation

  • The simplified problem is formulated as a multi-armed bandit:
    • There are n actions (“arms”).
    • Pulling arm i yields a random reward drawn from a distribution (assumed Gaussian for explanation).
    • Each arm has an unknown mean payoff μᵢ.
  • Goal: identify and then repeatedly choose the arm with the highest expected reward:
    • Define μ* = maxᵢ μᵢ
    • The best achievable long-run average reward is μ*.

• Why “bandit” (slot machine analogy)

  • A slot machine: each pull may give different payouts stochastically.
  • In multi-armed bandits, there are multiple levers/arms, each with its own probability of reward.
  • Learning consists of choosing the arm that yields the best long-run reward, not just pulling blindly.

---

Formal Setup and Key Notation (Bandit Problem)

• Arms/actions

  • Actions are labeled 1 … n.
  • Pulling action i gives a reward Rᵢ, sampled from a distribution.
  • For simplicity, each reward distribution is modeled as Gaussian with mean μᵢ.

• Rewards over time

  • rᵢ,k: the reward received when arm/action i is selected for the k-th time.

• True vs. estimated value

  • The true expected reward for action i is μᵢ (unknown).
  • The estimated value of action i is Q(aᵢ), based on observed samples so far:
    • Conceptually: average of past received rewards from that action.

• Estimated best action

  • Define:
    • a* such that Q(a*) = maxᵢ Q(aᵢ)
  • Interpretation: a* is the action that currently looks best based on current estimates.

---

Learning / Estimation Mechanics (Average and Updating)

• Estimating average reward

  • For action i, after it has been tried nᵢ times:
    • The estimated value Q(aᵢ) is computed as the average of its observed rewards:
      • Sum of all received rewards from that action divided by nᵢ.

• Incremental update idea

  • The lecture derives an update-style relationship showing how a new estimate can be computed from the previous average plus the newest sample.
  • Two weighting modes are mentioned:
    • Simple average (older and newer samples weighted roughly uniformly)
    • Exponential / recency-weighted form (implemented by using a constant step-size/α), giving higher weight to recent rewards.

---

Demonstrated Problem with Naive “Greedy” Selection

• The lecture gives a two-arm example:

  • Action 1: reward +1 with probability 0.8, else 0.
  • Action 2: reward +1 with probability 0.6, else 0.
  • The optimal arm by true mean: action 1 (since 0.8 > 0.6).

• Failure mode when starting with unlucky samples

  • If the agent initially samples action 2 and gets +1 first, then Q(a₂) may look higher.
  • With pure greedy behavior, the agent keeps selecting action 2, and may take a very long time to correct the mistake (or never switch in practice).

• Lesson

  • The agent cannot just exploit current estimates immediately; it needs systematic exploration.

---

Exploration Methods Described (Algorithm-Like)

1) ε-greedy exploration

• Rule
  • Let a* be the currently estimated best action (argmax of Q values).
  • Choose:
    • a* with probability 1 − ε
    • a random action (uniform among all actions) with probability ε
• Typical ε values
  • Mentioned: 0.1 or 0.01 (generally small values like 0.1, 0.01).
• Intended effect
  • Ensures the agent continues to sometimes try other actions instead of permanently locking into the current best estimate.

2) Softmax / Boltzmann exploration

• Rule
  • Convert estimated action values (Q-values) into a probability distribution using exponentiation:
    • Probability of choosing action i is proportional to exp(Q(aᵢ)/τ).
• Why softmax is used
  • Unlike a naive normalization that could fail with negative Q-values, softmax always yields positive exponentiated weights.
• Temperature parameter τ
  • High τ (→ ∞):
    • Probabilities become nearly uniform across actions (strong exploration).
  • Low τ (→ 0):
    • Even small differences in Q values cause large probability differences (near-greedy behavior).
• Intended effect
  • Gradually adjusts exploration intensity by tuning τ.

---

Theoretical / Asymptotic Guarantees Mentioned

• ε-greedy

  • Because every action has non-zero probability to be chosen at each step:
    • Over infinite time, each action gets infinitely many samples.
    • Estimated Q-values converge to true μ-values.
    • Greedy choice w.r.t. those estimates yields the best arm eventually.

• Softmax

  • With appropriate temperature settings (specifically, not letting τ go to zero):
    • The policy continues to sample all actions infinitely often.
    • Convergence reasoning is similar to ε-greedy.

---

Practical Behavior and Example Outcomes (What the Curves Show)

• Graph comparing different ε values (e.g., for 10 arms)

  • Smaller ε (e.g., 0.01) → slower learning, can get “fooled” longer by early successes.
  • Larger ε (e.g., 0.1) → faster learning, eventually converges to better performance, though it may take some time.

• Graph described

  • x-axis: number of steps
  • y-axis: percentage of times the agent played the true optimal arm (arm with μ*)
• Key qualitative outcomes
  • Pure greedy can converge to a suboptimal arm early (getting stuck).
  • ε-greedy improves:
    • moderate ε can approach high optimal-arm usage (around ~80–90% described)
    • smaller ε may reach even higher eventual optimal usage given enough time (described as approaching ~99% in the narrative)

---

Speakers or Sources Featured

• No explicit named speakers or external sources are mentioned in the subtitles.
• The lecture refers to a textbook (source named only indirectly: “the book”), but no title/author is provided.