Bandit Algorithms

Slivkins (2019) formulates the multi-armed bandit problem as follows: an algorithm has \(K\) possible actions, called arms, and \(T\) rounds. In each round the algorithm chooses an arm and collects a reward for that arm. To find the best arm it has to explore, trying arms to gather information, and that conflicts with exploiting what it already knows to make the best near-term choice. Bandit algorithms are rules for managing that tradeoff.

Regret

Regret measures what the learning cost. With \(\mu^*\) the mean reward of the best arm and \(\mu(a_t)\) the mean reward of the arm chosen in round \(t\), \(R(T) = \mu^* T – \sum_{t=1}^{T} \mu(a_t)\). It is how much the algorithm regrets not knowing the best arm in advance.

A hypothetical example: three arms have mean success rates 0.10, 0.12, and 0.15, and \(T = 100\). Always playing the first arm gives a regret of \(100 \times (0.15 – 0.10) = 5.0\). Playing the second arm 50 times and the third 50 times gives \(50 \times (0.15 – 0.12) = 1.5\). Regret is defined with the true means, which an algorithm does not know, so it is a quantity for analysis and simulation, not one a live system can compute directly.

Main families

• Explore-first. Explore uniformly for an initial number of rounds, then play the empirically best arm.
• Epsilon-greedy. In each round, with probability \(\epsilon\) explore by choosing an arm uniformly at random, and otherwise exploit by choosing the arm with the highest average reward so far.
• UCB1. Play the arm that maximizes an upper confidence bound, which combines the arm’s empirical reward with an exploration bonus that is larger for arms tried less often.
• Thompson sampling. A Bayesian method that samples a plausible reward for each arm from its posterior and plays the largest. See Thompson Sampling (TS) in Bandits.

In recommendation and experimentation

In recommendation the arms can be items, layouts, or rankers, and the reward can be a click or a purchase. Unlike an A/B test, which fixes the allocation in advance, a bandit shifts traffic toward better arms while it learns, which reduces the cost of exploring. That adaptive allocation makes it harder to estimate effects afterward. The Bandits and Exploration article simulates uniform, greedy, epsilon-greedy, UCB, and Thompson policies, and covers effect estimation under adaptive allocation and evaluating a policy that was never run.

Assumptions to check

• Whether rewards are stable over time. If the best arm changes, an algorithm that has stopped exploring can miss it.
• Whether rewards arrive promptly and are observed for every choice, or are delayed or missing.
• Whether the reward matches the goal. A bandit maximizes whatever reward it is given.
• Whether the unit of decision is clear, such as a user, a session, or an impression.

References:

• Slivkins, Introduction to Multi-Armed Bandits, arXiv:1904.07272