Bandits and Online Algorithms

The question

A bandit algorithm picks one of several options each round and sees the reward of only the one it picked. It has to balance trying options it knows little about against using the best one so far. Regret measures what that costs against the best choice in hindsight. Online algorithms have a related problem. They make each decision before the rest of the input arrives, and they can use a machine-learned prediction of what’s coming.

What I studied

Over two years I worked through bandits in five settings, from random rewards to an adversary that chooses them, and online algorithms that use predictions. I presented each topic as a seminar deck and wrote the derivations up in a report. The original code was lost with an old computer, so I rebuilt it from those notes and tested every algorithm against its proven guarantee.

Random rewards

With random rewards, UCB1 plays the arm whose average plus a confidence bonus is highest, so every arm gets tried until the data rules it out. Explore-then-commit pays its whole exploration cost up front. ε-greedy never stops exploring, so its regret keeps growing.

With a prior over the arms, Thompson sampling did better still, ending at regret 8 where UCB1 reached 76 on three Bernoulli arms. For discounted rewards the Gittins index is the optimal rule. I computed it with the report’s dynamic program, and it matches a published table in all 64 cells.

An adversary

An adversary that pays only the arm the learner is least likely to pull can hold a deterministic rule like UCB1 at zero reward. Exp3 picks arms at random from a weighted distribution and estimates every arm’s reward from the one it sees, which keeps its regret under a bound that holds for any reward sequence.

Exp3’s bound holds in expectation. On a table whose best arm switches, 8.8 percent of its runs ended above it. Exp3-IX adds implicit exploration, which caps what one unlucky round can cost an arm, and none of its runs crossed the bound.

Context and restless arms

When each round comes with a context, such as a user’s features, the right arm depends on it. Scored offline on logged news recommendations with every parameter fixed in advance, LinUCB, which fits a model of clicks per article, earned twice the click rate of the best single article.

Restless arms change state whether they are pulled or not, like machines that wear out when worked and recover when rested. Exact planning there is intractable, and the Whittle index splits the problem into one arm at a time. On ten such arms it reached 98 to 99 percent of the best achievable reward when most arms could be worked each round, against 86 to 90 percent for a myopic rule.

Online algorithms with predictions

The learning-augmented algorithms take a trust parameter. It trades consistency, how well they do with a perfect prediction, against robustness, their worst case with any prediction. In every case below, the measured ratio matched the proven bound.

The classical primal-dual algorithms reach their guarantees too. The knapsack threshold rule meets its bound of 1 + ln θ where greedy can be a thousand times worse than the optimum, and water-filling matching reaches 1 − 1/e on the hard instance where greedy falls to one half.