📈 BigData Junction

Bandits

Main idea: making repeated decisions based on feedback, factoring in the tradeoff between exploring new decisions or keeping existing good decisions

Multi-Armed Bandit Framework #

The Multi-Armed bandit problem arises when the following are true:

  • We need to get the data as a part of the process
  • Exploration/exploitation tradeoff (both have a cost)
  • Stochastic: rewards are random

Setup:

  • Selection rounds $1, \cdots, T$
  • Arms (choices) $1, \cdots, K$
  • $P_i$: reward distribution for arm $i$
  • $\mu_i$: mean reward for $P_i$ distribution
  • At each round $t$, choose an arm $A_t$ such that a reward $X_t \sim P_{A_t}$ is procured
  • Define pseudo-regret at time $T$ as $\bar R_t = \sum_{t=1}^T (\mu^* - \mu_{A_t})$ where $\mu^*$ is the best mean possible.
    • The term in the sum is also known as the optimality gap, $\Delta_a$ (how much worse arm $a$ is than the best arm).

Goal: maximize total expected reward

Known: only $A_t$ and $X_t$

Examples:

  • AB testing
  • Advertising
  • Gambling
  • Optimizing blog posts
  • Training hyperparameters for ML models

Algorithms:

  • Explore then commit (ETC): choose the arm with the highest sample mean
    • not optimal: will never choose the true best arm if not explored
  • Upper Confidence Bound (UCB): choose arm with highest upper bound in the confidence interval
    • Confidence interval calculation (derived from Hoeffding’s Inequality): $$UCB_i(t) = \hat\mu_i(t) + \sqrt{\frac{\log(1/\delta)}{2T_i(t)}}$$
    • (where $\delta$) is something like .05, that specifies how wide our confidence interval should be
    • Choose a $\delta$ as a decreasing function of $t$ to ensure that confidence intervals will get narrower as we explore something more
    • Hoeffding requires variables to be independent, which isn’t actually true for the UCB algorithm (which arm we choose depends on which arms we chose before). However, the result still holds.
      • UCB regret is bounded by $3 \sum_{a=1}^K \Delta_a + 24 \log(T) \sum_{a=1}^K \frac{1}{\Delta_a}$ which says that the regret grows logarithmically with respect to $T$.
  • Thomson Sampling: draw a sample from the posterior for each arm, and choose arm according to $argmax_a \bar\mu_a$

Other Bandit Problems #

Adversarial Bandits: rewards are chosen by an adversarial actor Contextual bandits: rewards are correlated with confounding variables Linear bandits: arms are a vector of arm choices (online linear regression) Non-stationary bandits: arm reward distributions change over time Structured bandits: previous choices affect future choices (such as navigation on a road network)