yzj527415955/bandit-algorithms

A small collection of Bandit Algorithms (ETC, E-Greedy, Elimination, UCB, Exp3, LinearUCB, and Thompson Sampling)

Bandit Algorithms

Multi-arm bandit algorithms are fundamental to enabling recommendation systems, online advertising, clinical trials, online resource allocation and online search. Here is a small collection of them in Python Implementation: ETC, E-Greedy, Elimination, UCB, Exp3, LinearUCB, and Thompson Sampling.

Vis-a-vis Bandits used in Reinforcement Learning settings, three key assumptions apply:

• Reward observed only conrrespond to the action taken (feedback).
• Action does not alter the environment.
• Taking an action does not restrict future actions.

Furthermore, these algorithms differ in their requirement of the time horizon and suboptimality gap , and in their scaling of regret bounds.

Algorithm	Environment	Requirement	Regret Scaling
Explore-then-Commit (ETC)	Unstructured / Stochastic	,
Epsilon-Greedy (E-Greedy)	Unstructured / Stochastic
Elimination	Unstructured / Stochastic
Upper-Confidence Bound (UCB) - Infinite Horizon	Unstructured / Stochastic	---
Exponantiate-Explore-Exploit (Exp3) - Partial feedback	Adversarial / Non-stochastic	---
Linear UCB (LinUCB)	Contextual / Linear	---
Thompson Sampling	Structured	---

For detailed background of each algorithm, refer to Bandit Algorithms (2020) by Lattimore & Szepesvari.