The UCB pull bound
ProofGraduate⏱ 3 hoursAgentsucbbanditshoeffdingunion bound
Problem
Prove that UCB1 pulls a suboptimal arm at most times in expectation. Identify the three events whose union must occur when a suboptimal arm is selected, and show why the third becomes impossible once the pull count is large enough.
Write a complete argument. Every inequality you use should be one you could state precisely.
Hints
Hints — 0 of 3 revealed
Solution
Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.
Related problems
All problems| Solved | Problem | Field | Type | Difficulty | Time |
|---|---|---|---|---|---|
| When is the union bound tight? | Probability | Proof | 15 min | ||
| Generalisation for a finite class | Learning Theory | Proof | 30 min | ||
| Derive Hoeffding's inequality from Hoeffding's lemma | High-Dim Probability | Proof | 30 min | ||
| Locating the Bernstein crossover | High-Dim Probability | Numerical | 30 min | ||
| Majority voting via Hoeffding | Agents | Proof | 30 min |