W1_L4: Regret and (probably Approximately Correct) frameworks

Main ideas / concepts

• Multi-armed bandit (MAB) setup

  • There are multiple actions/arms.
  • Each time you choose an arm, you receive a reward drawn from a Gaussian distribution (unknown mean per arm).
  • The goal is to learn which arm is best (highest expected reward).

• Core baseline strategy: estimate-and-choose with exploration

  • Maintain running averages of observed rewards for each arm.
  • Exploration vs exploitation:
    • Choose the arm with the highest estimated reward, but
    • include exploration using strategies such as:
      • ε-greedy
      • softmax
  • Challenge: these methods must balance learning quickly while still providing guarantees during learning.

• News recommendation as a bandit example

  • An editor provides a candidate set of (about) 20 stories.
  • The system shows one story to a user.
  • Reward definition:
    • If the user clicks → reward 1
    • If the user doesn’t click → reward 0
  • The environment is time-varying: every hour the “hot” stories change.
  • Therefore, the system must learn quickly; waiting for long-run convergence is not enough.
  • Even if you don’t reach the optimal arm immediately, you want performance guarantees during learning (time-bounded behavior).

Notions of correctness / performance during learning

1) Regret (time-bounded learning objective)

• Instead of only being correct “at the end,” you want to:

  • maximize reward over time while learning.

• Conceptual learning curve:

  • At time (t), you get some payoff.
  • If you knew the best arm from the start, you’d achieve (\mu^*) (the best arm’s true expected reward).
  • Because you must explore, you initially fall short.

• Regret definition (conceptual)

  • Regret = cumulative loss caused by not playing the best arm early.
  • If you explore too little, you may converge too soon to a suboptimal arm, causing a persistent gap, leading to large total regret.
  • If you explore too much, learning is slow, also increasing regret.
  • Goal: find the right learning rate that gets close to (\mu^*) quickly while still exploring enough to be confident.

• Key relationship mentioned:

  • Asymptotic correctness alone is not sufficient for regret minimization.
  • If you were only asymptotically correct, the cumulative regret can still blow up (or remain large) when summed over infinite time; more importantly, time-varying settings require good transient performance.

2) PAC / Probably Approximately Correct (pack framework)

• This provides a different “correctness” notion than regret.

• Main objective: minimize sample complexity, i.e., the number of arm pulls needed.

• PAC framing:

  • Run an algorithm to collect samples,
  • then output one arm to use.
  • During sampling, you don’t have strict performance requirements; the emphasis is on what you output afterward.

Epsilon-optimal arm requirement

• Let:
  • (\mu^*) = expected reward of the true best arm
  • (\mu’) = expected reward of the arm your algorithm outputs

• You want: [ \mu^* - \mu’ \le \varepsilon ]

  • i.e., the returned arm is within (\varepsilon) of the best.

Probably (confidence) requirement: (1-\delta)

• The guarantee holds with high probability:

  • with probability at least (1-\delta), the returned arm is (\varepsilon)-optimal.

• Interpretation given:

  • If (\delta = 0.01), then in repeated runs you expect about 99% of runs to return an (\varepsilon)-optimal arm.

Intuition for why (\delta) matters

• Early sampling randomness can cause the algorithm to temporarily believe the wrong arm is better.

• With enough samples you can recover, but PAC allows:

  • a small probability that the algorithm ends up outputting a non-(\varepsilon)-optimal arm.

• Designer chooses (\varepsilon) and (\delta) to trade off:

  • allowed performance loss ((\varepsilon))
  • allowed failure probability ((\delta))
  • and thereby influences how many samples are needed.

Generality mentioned

• PAC ideas can apply beyond bandits:
  • classification/regression analogies (e.g., “(\varepsilon)-optimal” relates to classification error tolerance).
• Also noted:
  • asymptotically correct methods are PAC with (\varepsilon \to 0) as time → ∞, but PAC emphasizes achieving the guarantee with minimal samples.

Methodologies / algorithm families described

A) Median elimination (pack-optimal algorithm approach)

• A round-based algorithm designed to achieve PAC/pack guarantees.

• Procedure (conceptual):

  • Suppose there are (n) arms.
  • Split learning into rounds; each round eliminates about half the arms.

• Per-round process:

  • Round 1:
    • Take (L_1) samples from all arms.
    • Compute each arm’s average reward estimate.
    • Eliminate arms with estimated reward below the median.
    • Keep roughly the top half.
  • Round 2:
    • For remaining arms (about (n/2)):
      • Take (L_2) samples from each remaining arm.
      • Recompute averages.
      • Eliminate the bottom half by median.
  • Continue similarly:
    • Round (k): sample the remaining arms, keep the better half.

• Number of rounds:

  • After (\log_2 n) rounds, only 1 arm remains.

• Total sample complexity:

  • Add up the samples taken each round: (L_1 + L_2 + \dots).

• Correctness idea:

  • Ensure with high probability you never eliminate the (\varepsilon)-optimal arms too early.
  • The analysis is nontrivial because elimination happens repeatedly across rounds.

• Impact mentioned:

  • This “round-based, batch sampling” idea became influential.
  • Many later bandit algorithms for regret/pack tradeoffs used similar batch/round structures.

B) UCB (Upper Confidence Bound) approaches (regret-optimality)

• Contrast with median elimination:

  • Median elimination → pack optimality
  • UCB → regret optimality

• Historical notes given:

  • 1998: original UCB1 proposed by Auer, Peter, and others (not round-based).
  • Later: a round-based UCB variant by the same general line of work that improved upon UCB1.

• Motivation in the application:

  • In news/ad placement, you want to minimize revenue loss while learning, aligning with minimizing regret.

C) Thompson sampling (Bayesian approach to regret optimality)

• A Bayesian bandit learning approach.

• Timeline/notes provided:

  • Bayesian bandit ideas existed earlier (mentions “before Agrawal and Goyal” and even earlier conceptual predecessors).
  • The original Thompson sampling work ~2001 is mentioned.
  • Notable later results: 2012 is mentioned.

• Main challenge historically:

  • Proving Thompson sampling achieves regret optimality.

• Agarwal and Goyal paper (mentioned):

  • Provided proof techniques showing:
    • Thompson sampling can achieve regret optimality
    • and can have better constants than UCB-style methods.

Overall lesson of the lecture segment

• Bandit learning can be evaluated via different “correctness” notions:
  • Regret: optimize cumulative performance while learning, especially in time-varying settings
  • PAC / pack framework: approximate optimality after limited sampling, with probability guarantees
• Different algorithm families align with different objectives:
  • Median elimination → pack/PAC guarantees (batch/round-based)
  • UCB → regret minimization
  • Thompson sampling → Bayesian strategy with regret-optimality guarantees

Speakers / sources featured (as named in the subtitles)

• Auer (subtitle also mentions “Peter Oyer,” likely referring to Peter Auer)
• Agrawal and Goyal
• Agarwal and Goyal (appears again; likely the same authors as above)
• Mentions of “the paper” by the above authors without full bibliographic detail
• No other clear named speakers are identified beyond these authors mentioned.