Multi-armed Bandit Problem

In Computer Science, one of the most popular problem in the realm of Explore-exploit trade-off is the Multi-armed bandit problem. The term derived from the casino slot machine “one-armed bandit”, and as the name suggests, the problem entails multiple slot machines and how to win as much as possible.¹

The real problem, however, is getting an idea of the odds of each slot machine to know when to keep playing or move on to the next one.

Multi-Armed Bandits: A Cartoon Introduction - DCBA #1²

Algorithms to Live By by Brian Christian and Tom Griffiths - Explore/Exploit
↩︎
https://www.youtube.com/watch?v=bkw6hWvh_3k&ab_channel=AcademicGamer (Multi-Armed Bandits: A Cartoon Introduction - DCBA)
↩︎

2022-01-27

The Gittins Index
- Gittins discovered what he called “dynamic allocation index”, or more famously the Gittins index, that also put to rest the long overdue multi-armed bandit riddle with geometrically discounted payoffs.¹ The competing demand to explore or exploit dissolves into maximization of a single quantity that accounts for both.
  1. Geometric discounting refers to each decision to explore is worth a constant fraction of the last one.
    ↩︎
- Here, the rules are simple. Using the Multi-armed bandit slot machine problem, with a record of 0 win and 0 losses we start at column 0 and row 0 and each win we go to the right of the table and each losses we go down. Gittins index follows a Markov model, that is the future state depends only on the current state, and never on the prior events. The table assumes that the next arm pull is worth 90% of the payoff now (much like a discount), and notice that the Gittins index at the start point is already \(.7029\) or a 70% probability of payout. In other words, Gittins index gives the benefit of the doubt to a fresh start with no payout knowledge of the slot machine.
Zettel Posts
Computer Science
Book Notes

🧠 Index 🧠#