Multi-Armed Bandit

Principles

• Naive exploration - add randomization to greed policy (e.g., $\epsilon$-greedy)
• Optimistic initialization - assume the best until proven otherwise
• Optimism in the face of uncertainty - prefer actions with uncertain values
• Probability matching - select actions according to probability they are best

Overview

A multi-armed bandit is a tuple $\langle \mathcal{A},\mathcal{R} \rangle$. $\mathcal{A}$ is a known set of $M$ actions or arms.

$\mathcal{R}^a(r)=\mathbb{P}[r|a]$ is unknown probability distribution of rewards. At each step t the agent selects an action $a_t \in \mathcal{A}$.

The environment generates a reward $r_t \sim \mathcal{R}^{a_t}$ and the goal is to maximize total reward $\sum_{\mathcal{T}=1}^t{r_{\mathcal{t}}}$.

Regret

The action-value is the mean reward for action a, $Q(a)=\mathbb{E}[r|a]$. The optimal value $V^*$ is $V^*=Q(a^*)=\max\limits_{a\in\mathcal{A}}Q(a)$.

Regret is the opportunity loss for one step. Regret is a function of gaps $\Delta_a = V^* - Q(a_{\mathcal{T}})$: Total regret is the total opportunity loss: $L_t = \sum\limits_{a \in \mathcal{A}} \mathbb{E}[N_t(a)\Delta_a]$. Maximizing total reward is equivalent to minimizing total regret.

Average sampling and $\epsilon$-greedy have linear total regret. Decaying $\epsilon$-Greedy has logarithmic regret, which is a theoretical lower bound on complexity of regret. UCB also achieves logarithmic regret. Thompson sampling hits theoretical minimum.

Strategies

Objective is find a policy $\pi$ that maximizes total cumulated reward, $\pi^*= \arg\max_\pi \sum\limits_{t=0}^{T} r_{\pi_t,t}$ , where $\pi_t \in \{1,\dots,K\}$ is the arm selected by $\pi$ at time $t$, and $r_{i,t}$ is the reward obtained at time $t$ after selecting the arm $i \in \{1,\dots,K\}$.

e-greedy

The $\epsilon$-greedy strategy sometimes acts greedily, and sometimes selects a random action to improve exploration:

$$\forall t,\pi^\mathrm{greedy}_t = \begin{cases} \arg \max_i \hat\mu_{i,t} & \text{with probability 1-}\epsilon \\ i \sim \mathcal{U}\{1,K\} & \text{with probability }\epsilon \\ \end{cases}$$

Incremental Implementation of Sample Averaging

$$Q_{n+1} = \frac{1}{n}\sum\limits^n_{i=1}R_i = Q_n + \frac{1}{n}[R_n - Q_n]$$

The fraction $\frac{1}{n}$ has nice convergence properties–diverging at $\infty$ while its square $\frac{1}{n^2}$ converges at $\infty$.

An $\epsilon$-greedy average-sampling bandit algorithm from the Sutton book:

• Initialize, for a = 1 to $k$:

  • $Q(a) \gets 0$

  • $N(a) \gets 0$

• Loop forevers:

  • $A \gets \begin{cases} \arg \max_n Q(a) & \text{with probability 1-}\epsilon \text{ (breaking ties randomly)} \\ \text{a random action} & \text{with probability }\epsilon \end{cases}$
  • $R \gets bandit(A)$
  • $N(A) \gets N(A) + 1$
  • $Q(A) \gets Q(A) + \frac{1}{N(A)}[R - Q(A)]$

Discounting

We can use discounting instead of averaging to overcome nonstationarity.

$Q_{n+1} \doteq Q_n + \alpha[R_n - Q_n]$

$$\begin{align}Q_{n+1} &= Q_n + \alpha[R_n - Q_n]\\ &= \alpha R_n + (1-\alpha)Q_n \\ &= (1-\alpha)^nQ_1 + \sum_{i=1}^n \alpha(1-\alpha)^{n-i} R_i\end{align}$$

Upper Confidence Bounds (UCB)

UCB follows an optimistic strategy and selects the best arm in the best case scenario, i.e., according to the upper bounds $B_t(i)$ on the arms value estimates:

$\pi_t = \arg \max_i B_t(i) \quad \text{with} \quad B_t(i)= \hat\mu_{i,t} + \sqrt{\frac{2 \ln t}{T_i}} \quad \text{or} \quad \hat\mu_{i,t} + c\sqrt{\frac{\ln t}{T_i}}$

$A_t = \arg\max (Q_t(a) + c\sqrt{\frac{\ln(t)}{N_t(a)}})$

Gradient Bandit

$H_t(a)$ is a preference function in which only the relative ranking order matters. The function has no other interpretability. The function is updated using a stochastic gradient ascent process. The policy function uses the softmax probabilities of H over all actions.

$\pi_t(a) \doteq Pr\{A_t=a\} \doteq \frac{e^{H_t(a)}}{\sum^k_{b=1} e^{H_t(b)}}$

$H_t(a)$ is updated on each step after selecting action $A_t$ by:

$H_{t+1}(a) \doteq H_t(a) + \alpha\frac{\delta\mathbb{E}[R_t]}{\delta H_t} \doteq H_t(a) + \alpha(R_t - \bar R_t)(\mathbb{1}_{a=A_t}-\pi_t(A_t))$

$\bar R_t$ is the average of rewards up to but not including time t and $\bar R_1 = R_1$. $\alpha$ is the step-size parameter.

The expected reward is the probability weighted reward of each action: $\mathbb{E}[R_t] = \sum\limits_x \pi_t(x)q_*(x)$

Baselines reduce variance by subtracting the mean and centering values at zero and reducing the magnitudes. We are not subtracting from the gradient but from a number that multiplies the gradient.

Thompson Sampling

“Thompson Sampling follows a Bayesian approach and considers a parametric model $P(\mathcal{D}|\theta)$ with a prior $P(\theta)$. For instance, in the linear case: $P(r_{i,t}|\theta) = \mathcal{N}(\theta^Tx_i, v^2)$ and $P(\theta) = \mathcal{N}(0, \sigma^2)$. Then, at each iteration t, we sample $\theta$ from $P(\theta | \mathcal{D}) \varpropto P(\mathcal{D}|\theta)P(\theta)$ and select the arm $\pi_t = \arg \max_i \mathbb{E}[r{i,t} | x_{i,t},\theta]$.”

In other words, Thompson sampling constructs a sample distribution or rewards for each arm based on sampling statistics from past rewards such as mean and variance. Then, at each iteration, a sample item is taken from each arm based on its distribution and the policy is the choose the arm with the highest sampled value.

Thompson sampling is useful for multi-armed bandits but does not easily extend to other reinforcement learning techniques.