Multi-Armed Bandits in Python: Epsilon Greedy, UCB1, Bayesian UCB, and EXP3

Abstraction: Four bandit algorithm implementations evaluated on MovieLens recommendation task

Key points:

• Four algorithms compared: Epsilon Greedy (explore ε% at random), UCB1 (Hoeffding-based confidence bounds), Bayesian UCB (swaps UCB term for c·σ/√n), and EXP3 (exponential weight updates with exploration parameter γ)
• Evaluated offline on MovieLens 25M using the Replay method, recasting 5-star ratings to binary like/no-like (base rate 0.309)
• Final mean rewards: Bayesian UCB 0.567, Epsilon Greedy 0.548, EXP3 0.468; all beat random guessing
• Bayesian UCB surpassed Epsilon Greedy but required ~25,000 iterations to overtake it due to initial exploration bias
• EXP3 significantly underperformed both UCB variants; epsilon greedy's simplicity makes it the "linear regression" of bandits
• Contextual bandits (using user/content features) are the logical next step beyond these context-free algorithms

Connections: Movielens · Multi Armed Bandit · Exploration Exploitation · Recommender Systems

Source: https://jamesrledoux.com/algorithms/bandit-algorithms-epsilon-ucb-exp-python/