Bandit Learning with Positive Externalities

on YouTube ↗32m

" summary

Model with arrivals more likely to prefer arms that have earned rewards; positive externality f(x)=x^α (typically linear). Shows UCB can suffer linear expected regret and even has positive probability of never seeing the best arm. Embeds arms in branching processes, derives lower bound, and gives a simple balanced exploration algorithm (pull arm with lowest cumulative rewards for Θ(log T) periods, then exploit) that achieves matching log^2 T regret and does not need α.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 1:31Motivation: Recommendations in online platforms
3. 3:14A simple setting
4. 3:36What could go wrong?
5. 6:10Our results: Summary
6. 6:52The model: Standard bandit
7. 8:31The model: Positive externalities
8. 12:09The baseline oracle
9. 14:10UCB and the standard bandit
10. 15:06UCB with positive externalities
11. 16:51Random explore-then-exploit
12. 19:29What's going wrong?
13. 20:35Balanced exploration
14. 26:47Lower bound
15. 28:18The complete picture