Exploration-Exploitation Trade-off

The exploration-exploitation trade-off is the core tension in bandit problems: an algorithm must spend some decisions learning about uncertain actions while also taking actions that appear to maximise reward now.

Key points

• In Multi-Armed Bandits, feedback is partial: an algorithm observes the outcome of the arm it chose, not the outcomes it would have received from all other arms ^[src-019].
• Exploration gathers information that can improve future decisions, while exploitation uses current evidence to collect reward immediately ^[src-019].
• Regret analysis formalises the cost of learning by comparing the algorithm’s cumulative reward with a benchmark that already knows the best action or policy for the model class ^[src-019].
• The right exploration strategy depends on assumptions: uniform exploration can be a useful baseline, confidence-bound methods adapt exploration in Stochastic Bandits, and Thompson Sampling explores through posterior sampling ^[src-019].
• In sponsored search, the trade-off appears as showing currently relevant ads versus exploring potentially relevant ads whose click-through rates are uncertain for a query or nearby query cluster ^[src-020].
• Yildirim translates the trade-off into traffic allocation: after early evidence suggests one treatment is better for a segment, teams should increase its probability without reducing the alternative to zero too soon ^[src-021].
• Three practical exploration strategies for contextual bandits are Epsilon-Greedy, Upper Confidence Bound, and Thompson Sampling ^[src-021].
• AB Tasty maps exploration to equal or broad variation testing and exploitation to shifting more traffic to the variation that has already paid off; the bandit value proposition is balancing both during a live experiment ^[src-022].
• Hightouch applies the same trade-off to marketing decisions across content, channel, timing, frequency, and offers: agents must try new possibilities while still optimising toward known business outcomes ^[src-023].
• Hightouch’s RL article makes this the handoff from learning to optimisation: after an agent learns from experience, it still needs a mechanism for deciding how long to keep using what works and when to try new messages, times, or channels ^[src-024].
• Hightouch groups marketing bandit strategies into fixed exploration rate, confidence-based exploration, and adaptive exploration. Epsilon-greedy reserves a fixed share for testing, Thompson Sampling explores more when uncertain, and SquareCB adjusts exploration based on problem complexity and data collected ^[src-025].

Related entities

• Aleksandrs Slivkins

Related concepts

• Multi-Armed Bandits
• Stochastic Bandits
• Thompson Sampling
• Contextual Bandits
• Query-Ad-Clustering
• Sponsored Search Ad Ranking
• Epsilon-Greedy
• Upper Confidence Bound
• Dynamic Traffic Allocation
• A/B Testing vs Bandits
• AI Decisioning
• Reinforcement Learning for Marketing
• Marketing Bandit Optimisation

Source references

• ^[src-019] Aleksandrs Slivkins — “Introduction to Multi-Armed Bandits” (2019-04-15; revised 2024-04-03)
• ^[src-020] Tyler Lu, David Pál, Martin Pál — “Contextual Multi-Armed Bandits” (AISTATS 2010)
• ^[src-021] Ugur Yildirim — “An Overview of Contextual Bandits” (2024-02-02)
• ^[src-022] AB Tasty — “Multi-Armed Bandits: A/B Testing with Fewer Regrets”
• ^[src-023] Hightouch — “Under the hood of AI Decisioning, part one: Overcoming the personalization gap”
• ^[src-024] Hightouch — “Under the hood of AI Decisioning, part two: Reinforcement learning”
• ^[src-025] Hightouch — “Under the hood of AI Decisioning, part three: Multi-armed bandits”