Video summary

Median Elimination

Main summary

Key takeaways

Educational

Main ideas / lesson conveyed

  • Median Elimination is a round-based algorithm for multi-armed bandits.
  • It aims, with high probability, to identify an ε-optimal arm—an arm whose mean reward is within ε of the best mean reward.

How the algorithm works

  1. Maintain a set of candidate arms.
  2. For each round, sample every remaining arm a prescribed number of times to estimate its mean reward.
  3. Compute the median of these estimated means.
  4. Eliminate arms whose estimated mean is below the median.
  5. Repeat until only one arm remains, then output it.

Methodology / step-by-step instructions (algorithm + proof structure)

Median Elimination algorithm (as described)

Inputs / parameters

  • Number of arms: K
  • Accuracy: ε
  • Failure probability: Δ
  • Rounds indexed by L (levels)
    • Goal: shrink the candidate set from size K down to 1

Initialization

  • Start with the full candidate set: [ S_1={\text{all } K \text{ arms}} ]

For each round / level (L)

Sampling budget per arm

  • Pull each arm in the current set (S_L) a number of times determined by a “magic quantity,” with the intent to use something of the form: [ \text{pulls per arm} \;\propto\; \frac{1}{\varepsilon_L}\cdot \frac{L}{2}\cdot \log!\left(\frac{3}{\Delta_L}\right) ]

  • (Note: the original subtitles contained formatting/notation glitches; the key idea is that the sample count depends on (\varepsilon_L), (\Delta_L), (L), and (\log(3/\Delta_L)).)

Estimate mean rewards
  • For each arm (a\in S_L), form an empirical estimate (Q_L(a)) of its mean reward.
Median-based elimination

  • Compute the median (m_L) of: [ {Q_L(a): a\in S_L} ]

  • Eliminate every arm with: [ Q_L(a) < m_L ]

  • Update the candidate set: [ S_{L+1}={a\in S_L : Q_L(a)\ge m_L} ]

Guaranteed shrinking
  • Because elimination is based on the median:
    • At least half the arms are removed each round.
    • So the candidate size shrinks roughly as: [ K,\; K/2,\; K/4,\; \dots ]

Termination

  • Run for about (\log K) rounds so the remaining set size becomes 1.
  • Output the single remaining arm.

How ε and Δ are scheduled across rounds

  • Constants are updated each level so errors don’t accumulate beyond overall tolerances.

Key scheduling idea

  • Per-level failure probabilities (\Delta_L) decrease geometrically so that the total probability of failure across rounds is at most Δ.
  • Per-level accuracy allowances (\varepsilon_L) also decrease geometrically so that total loss across rounds is at most ε.

Example values mentioned (with subtitle noise)

  • Accuracy schedule:
    • Start with something like (\varepsilon_1=\varepsilon/4),
    • update so that (\varepsilon_{L+1}) is a constant multiple of (\varepsilon_L) (e.g., involving factors like (3/4)).
  • Failure schedule:
    • Start with (\Delta_1=\Delta/2),
    • update so that (\Delta_{L+1}=\Delta_L/2) (i.e., (\Delta_L) halves each round).

Proof plan: “pack” guarantee (ε-optimal arm with high probability)

The instructor outlines a proof with two main parts.

1. Show the algorithm is an ((\varepsilon,\Delta))-PAC algorithm

  • Define a “good event” each level where the best arm among the remaining candidates is not eliminated.
  • Central concern:
    • Since elimination removes everything below the median, it is only possible to eliminate all (\varepsilon)-optimal arms if estimates are sufficiently wrong.
  • Strategy:
    • Bound the probability that the best candidate gets eliminated in each round by (\Delta_L) (or something that sums to (\Delta)).
    • Use a union bound / additive probability bound over all (\log K) rounds so total failure probability remains (\le \Delta).

2. Sample complexity computation

  • The subtitles indicate this part is mostly algebraic summation:
    • Total samples = (sum over levels of: number of surviving arms at that level × pulls per arm at that level).

  • Claimed target order: [ O!\left(\frac{K}{\varepsilon^2}\log!\left(\frac{1}{\Delta}\right)\right) ]

  • Constants are ignored in order notation.

Technical intuition for correctness (what goes wrong / why bounds work)

Safety of elimination at level (L)

  • Let (a^) be the true best arm among the arms currently under consideration* (not necessarily the global best arm).
  • The elimination step is “safe” when estimates are not too distorted:
    • If the best arm’s estimate stays competitive relative to the median threshold, it won’t be eliminated.
    • Failure cases include:
      • Underestimating the best arm too much, or
      • Overestimating suboptimal arms too much.

Tools implied in the subtitles

  • Tail bounds (enabled by the chosen sample counts),
  • A counting argument about how many “bad” arms could beat the best arm estimate,
  • An inequality mentioned: Markov’s inequality,
  • Finally, union bound to combine per-round failure probabilities.

High-level failure-probability accounting across rounds

  • Per-round failure probabilities resemble: [ \Delta/2,\; \Delta/4,\; \Delta/8,\;\dots ]

  • Their sum over finitely many rounds (up to (\log K)) stays < (\Delta).

  • Similarly, total “loss” is bounded by a geometric decrease in the (\varepsilon_L) contributions, ensuring overall (\varepsilon)-loss (\le \varepsilon).

Sources / speakers

  • No specific named speakers or external sources are identified.
  • The content appears to be from a single instructor/lecturer explaining the median elimination algorithm and a PAC/sample-complexity proof.

Original video