A Beginner's Guide to the Median Elimination Algorithm in Reinforcement Learning

🎯 Median Elimination Algorithm in Reinforcement Learning (RL)

Reinforcement Learning is about making an agent learn the best decisions through trial and error. One powerful strategy for efficiently selecting the best action is the Median Elimination Algorithm.

This guide explains everything step-by-step in a simple, intuitive way with math, examples, and practical insights.

---

📚 Table of Contents

• 1. The Problem in RL
• 2. Core Idea of Median Elimination
• 3. Step-by-Step Algorithm
• 4. Mathematical Intuition (Simple)
• 5. Real-Life Example
• 6. Code Example
• 7. CLI Simulation Output
• 8. Why It Works
• 9. Limitations
• 10. Key Takeaways

---

❗ 1. The Problem in Reinforcement Learning

In RL, an agent must choose between multiple actions (called arms in bandit problems).

Each arm gives uncertain rewards → the agent does not know which is best initially.

The challenge:

• Too many options = expensive exploration
• Need to quickly find the best action

---

💡 2. Core Idea of Median Elimination

Instead of testing everything equally, we repeatedly:

• Estimate performance
• Find the median reward
• Eliminate weaker half

This is similar to narrowing choices in a competition round by round.

---

⚙️ 3. Step-by-Step Algorithm

Step 1: Initialization

• Start with all arms
• Set accuracy parameters:
  • ε (epsilon) → how close we want to be to best arm
  • δ (delta) → confidence level

---

Step 2: Sampling

Pull each arm multiple times and compute average reward:

\[ \hat{r_i} = \frac{1}{n} \sum_{t=1}^{n} r_{i,t} \]

👉 This gives estimated reward for each arm.

---

Step 3: Compute Median

Sort all rewards and find median:

\[ median = middle\ value\ of\ sorted\ rewards \]

👉 Arms below median are weaker candidates.

---

Step 4: Elimination

• Keep only arms ≥ median
• Discard the rest

This cuts the search space roughly in half each round.

---

Step 5: Repeat

Repeat sampling → median → elimination until one arm remains.

---

📐 4. Mathematical Intuition (Easy Version)

Confidence Guarantee

The algorithm ensures:

\[ P(\text{chosen arm is within } \epsilon \text{ of best}) \ge 1 - \delta \]

Simple Explanation:

• ε (epsilon): how wrong we can tolerate
• δ (delta): probability of failure

Meaning: We are almost sure (1−δ) that our result is very close (ε) to the best choice.

---

🎰 5. Real-Life Example (Slot Machines)

Imagine 10 slot machines:

1. Play each machine a few times
2. Calculate average reward
3. Find median performer
4. Remove weaker machines
5. Repeat until best machine remains

This avoids wasting time on bad machines.

---

💻 6. Code Example

import numpy as np arms = [0.2, 0.5, 0.7, 0.4, 0.9] epsilon = 0.1 delta = 0.1 def sample(arm, n=10): return np.mean(np.random.binomial(1, arm, n)) # simple simulation estimates = [sample(a) for a in arms] median = np.median(estimates) filtered = [a for a, est in zip(arms, estimates) if est >= median] print("Remaining arms:", filtered)

---

🖥️ 7. CLI Simulation Output

Click to Expand

Initial Arms: [0.2, 0.5, 0.7, 0.4, 0.9]

Round 1:
Estimates: [0.2, 0.6, 0.8, 0.3, 0.9]
Median: 0.6
Remaining: [0.5, 0.7, 0.9]

Round 2:
Estimates: [0.5, 0.7, 0.9]
Median: 0.7
Remaining: [0.7, 0.9]

Round 3:
Remaining best arm: 0.9 

---

🚀 8. Why It Works

• Reduces computation drastically
• Focuses only on promising actions
• Balances exploration and exploitation

Instead of checking everything deeply, it quickly filters out bad options.

---

⚠️ 9. Limitations

• Depends heavily on ε and δ
• Not efficient for very small problems
• Needs repeated sampling (still costly in some cases)

---

💡 10. Key Takeaways

• Median Elimination is a smart filtering algorithm
• Works by repeatedly removing weaker half
• Uses probability guarantees (ε, δ)
• Efficient for large action spaces

---

🎯 Final Summary

Median Elimination is like narrowing down contestants in a competition until only the best remains. It is simple, powerful, and widely used in reinforcement learning problems where decisions must be made efficiently under uncertainty.