Exploration vs Exploitation in Feeds

The Feed Optimization Trade-off

Every news feed (TikTok, Twitter, LinkedIn) and ad server faces a daily dilemma:

Should we recommend a video that we KNOW the user will click with $90%$ probability (Exploitation)?

Or should we recommend a brand new video uploaded 5 minutes ago whose true CTR is completely unknown (Exploration)?

┌──────────────────────────┬──────────────────────────┐
│ 1. EXPLOITATION          │ 2. EXPLORATION           │
├──────────────────────────┼──────────────────────────┤
│ Serve known high-CTR     │ Serve un-tested / new    │
│ items matching past user │ items with high score    │
│ history.                 │ uncertainty.             │
│ Goal: MAXIMIZE SHORT-TERM│ Goal: GATHER DATA FOR    │
│ CLICK REVENUE TODAY!     │ LONG-TERM OPTIMIZATION!  │
└──────────────────────────┴──────────────────────────┘

• Pure Exploitation ($0%$ Exploration): The feed becomes stale. New creators receive zero impressions, and users get bored of repetitive content.
• Pure Exploration ($100%$ Exploration): The feed serves random noise, driving users away.

Balance is achieved using Multi-Armed Bandit Algorithms.

Multi-Armed Bandit Exploration Algorithms

┌──────────────────────────┬──────────────────────────┬──────────────────────────┐
│ 1. EPSILON-GREEDY        │ 2. UCB (Upper Conf Bound)│ 3. THOMPSON SAMPLING     │
├──────────────────────────┼──────────────────────────┼──────────────────────────┤
│ With probability 1 - ε,  │ Adds an Uncertainty      │ Maintains a Bayesian     │
│ exploit best item. With  │ Bonus σ(i) to predicted  │ Beta distribution over   │
│ probability ε, explore   │ CTR: Score = μ(i) + c*σ. │ CTRs; samples from Beta! │
│ random item. Simple!     │ Optimism in uncertainty! │ Bayesian SOTA!           │
└──────────────────────────┴──────────────────────────┴──────────────────────────┘

1. $\epsilon$-Greedy (Epsilon-Greedy)

Set $\epsilon = 0.05$ ($5%$ Exploration):

• $95%$ of the time: Serve the item with highest predicted CTR ($\hat{\mu}$).
• $5%$ of the time: Serve a random item chosen uniformly from candidate pool.

2. Upper Confidence Bound (UCB1)

Applies the principle of "Optimism in the Face of Uncertainty":

$$\text{Score}(i) = \hat{\mu}_i + c \cdot \sqrt{\frac{\ln N}{n_i}}$$

• $\hat{\mu}_i$: Estimated average CTR for item $i$.
• $n_i$: Number of times item $i$ has been displayed so far.
• $N$: Total impressions across all items.

If item $i$ has rarely been displayed ($n_i$ is tiny), its Uncertainty Bonus is huge, forcing the algorithm to explore it until its CTR estimate stabilizes!

3. Thompson Sampling (Bayesian Bandits)

Maintains a Beta Distribution $\text{Beta}(\alpha_i, \beta_i)$ for each item $i$:

• $\alpha_i = \text{Clicks} + 1$ (Successes)
• $\beta_i = \text{Non-Clicks} + 1$ (Failures)

For each feed slot:

1. Draw a random sample $\theta_i \sim \text{Beta}(\alpha_i, \beta_i)$ for every candidate item.
2. Serve the item with the highest sampled value $\theta_i$.

Uncertain items (small $\alpha_i + \beta_i$) have wide Beta distributions, naturally producing high sample draws that trigger exploration!

Say this out loud

Exploration vs Exploitation balances short term click revenue against long term content discovery. Exploitation serves known high CTR items matching user history. Exploration serves un tested items to estimate true engagement. Multi Armed Bandits like Upper Confidence Bound and Thompson Sampling balance this trade off dynamically using uncertainty confidence bounds.

Followups to expect

1. What is Contextual Bandits (LinUCB / Contextual Thompson Sampling)? Extending Multi-Armed Bandits to incorporate user state vectors $x$ (location, device, time) so exploration decisions depend on contextual user features $P(\text{Click} \mid x, \text{Item})$.
2. How do you measure Regret in Bandit algorithms? Cumulative Regret measures total lost revenue/clicks compared to an omniscient oracle that always selected the single optimal item: $R(T) = \sum_{t=1}^T (\mu^* - \mu_{a_t})$. Good bandit algorithms achieve logarithmic regret $O(\log T)$.