Bandits

Slides: html pdf

n-armed bandits

RL evaluates actions through trial-and-error rather than comparing its predictions to the correct actions. This is called evaluative feedback, as the feedback depends completely on the action taken. Oppositely, supervised learning is a form of instructive feedback, as the targets (labels / ground truth) do not depend at all on the prediction.

Evaluative feedback indicates how good the action is, but not whether it is the best or worst action possible. Two forms of RL learning can be distinguished:

  • Associative learning: inputs are mapped to the best possible outputs (general RL).

  • Non-associative learning: finds one best output, regardless of the current state or past history (bandits).

The n-armed bandit (or multi-armed bandit) is a non-associative evaluative feedback procedure. Learning and action selection take place in the same single state, while the n actions have different reward distributions. The goal is to find out through trial and error which action provides the most reward on average.

10-armed bandit with the true value of each action.

We have the choice between N different actions (a_1, ..., a_N). Each action a taken at time t provides a reward r_t drawn from the action-specific probability distribution r(a). The mathematical expectation of that distribution is the expected reward, called the true value of the action Q^*(a).

Q^*(a) = \mathbb{E} [r(a)]

The reward distribution also has a variance: we usually ignore it in RL, as all we care about is the optimal action (but see distributional RL later).

a^* = \text{argmax}_a Q^*(a)

If we take the optimal action an infinity of times, we maximize the reward intake on average. The question is how to find out the optimal action through trial and error, i.e. without knowing the exact reward distribution r(a).

We only have access to samples of r(a) by taking the action a at time t (a trial, play or step).

r_t \sim r(a)

The received rewards r_t vary around the true value over time. We need to build estimates Q_t(a) of the value of each action based on the samples. These estimates will be very wrong at the beginning, but should get better over time.

Sampling-based evaluation

The expectation of the reward distribution can be approximated by the mean of its samples (sampling average):

\mathbb{E} [r(a)] \approx \frac{1}{N} \sum_{t=1}^N r_t |_{a_t = a}

Suppose that the action a had been selected t times, producing rewards

(r_1, r_2, ..., r_t)

The estimated value of action a at play t is then:

Q_t (a) = \frac{r_1 + r_2 + ... + r_t }{t}

Over time, the estimated action-value converges to the true action-value:

\lim_{t \to \infty} Q_t (a) = Q^* (a)

The sampling average can correctly approximate the true value of an action given enough samples.

The drawback of maintaining the mean of the received rewards is that it consumes a lot of memory:

Q_t (a) = \frac{r_1 + r_2 + ... + r_t }{t} = \frac{1}{t} \, \sum_{i=1}^{t} r_i

It is possible to update an estimate of the mean in an online or incremental manner:

\begin{aligned} Q_{t+1}(a) &= \frac{1}{t+1} \, \sum_{i=1}^{t+1} r_i \\ &= \frac{1}{t+1} \, (r_{t+1} + \sum_{i=1}^{t} r_i )\\ &= \frac{1}{t+1} \, (r_{t+1} + t \, Q_{t}(a) ) \\ &= \frac{1}{t+1} \, (r_{t+1} + (t + 1) \, Q_{t}(a) - Q_t(a)) \end{aligned}

The estimate at time t+1 depends on the previous estimate at time t and the last reward r_{t+1}:

Q_{t+1}(a) = Q_t(a) + \frac{1}{t+1} \, (r_{t+1} - Q_t(a))

The problem with the exact mean is that it is only exact when the reward distribution is stationary, i.e. when the probability distribution does not change over time. If the reward distribution is non-stationary, the \frac{1}{t+1} term will become very small and prevent rapid updates of the mean.

The sampling average have problems when the reward distribution is non-stationary.

The solution is to replace \frac{1}{t+1} with a fixed parameter called the learning rate (or step size) \alpha:

\begin{aligned} Q_{t+1}(a) & = Q_t(a) + \alpha \, (r_{t+1} - Q_t(a)) \\ & \\ & = (1 - \alpha) \, Q_t(a) + \alpha \, r_{t+1} \end{aligned}

The computed value is called a moving average (or sliding average), as if one used only a small window of the past history.

Q_{t+1}(a) = Q_t(a) + \alpha \, (r_{t+1} - Q_t(a))

or:

\Delta Q(a) = \alpha \, (r_{t+1} - Q_t(a))

The moving average is much more flexible for non-stationary distributions.

The moving average adapts very fast to changes in the reward distribution and should be used in non-stationary problems. It is however not exact and sensible to noise. Choosing the right value for \alpha can be difficult.

The form of this update rule is very important to remember:

\text{new estimate} = \text{current estimate} + \alpha \, (\text{target} - \text{current estimate})

Estimates following this update rule track the mean of their sampled target values. \text{target} - \text{current estimate} is the prediction error between the target and the estimate.

Action selection

Greedy action selection

Let’s suppose we have formed reasonable estimates of the Q-values Q_t(a) at time t. Which action should we do next? If we select the next action a_{t+1} randomly (random agent), we do not maximize the rewards we receive, but we can continue learning the Q-values. Choosing the action to perform next is called action selection and several schemes are possible.

Greedy action selection.

The greedy action is the action whose estimated value is maximal at time t based on our current estimates:

a^*_t = \text{argmax}_{a} Q_t(a)

If our estimates Q_t are correct (i.e. close from Q^*), the greedy action is the optimal action and we maximize the rewards on average. If our estimates are wrong, the agent will perform sub-optimally.

This defines the greedy policy, where the probability of taking the greedy action is 1 and the probability of selecting another action is 0:

\pi(a) = \begin{cases} 1 \; \text{if} \; a = a_t^* \\ 0 \; \text{otherwise.} \end{cases}

The greedy policy is deterministic: the action taken is always the same for a fixed Q_t.

Exploration-exploitation dilemma

Greedy action selection only works when the estimates are good enough.

Estimates are initially bad (e.g. 0 here), so an action is sampled randomly and a reward is received.

The Q-value of that action becomes positive, so it becomes the greedy action.

Greedy action selection will always select that action, although the second one would have been better.

This exploration-exploitation dilemma is the hardest problem in RL:

  • Exploitation is using the current estimates to select an action: they might be wrong!
  • Exploration is selecting non-greedy actions in order to improve their estimates: they might not be optimal!

One has to balance exploration and exploitation over the course of learning:

  • More exploration at the beginning of learning, as the estimates are initially wrong.
  • More exploitation at the end of learning, as the estimates get better.

\epsilon-greedy action selection

\epsilon-greedy action selection

\epsilon-greedy action selection ensures a trade-off between exploitation and exploration. The greedy action is selected with probability 1 - \epsilon (with 0 < \epsilon <1), the others with probability \epsilon:

\pi(a) = \begin{cases} 1 - \epsilon \; \text{if} \; a = a_t^* \\ \frac{\epsilon}{|\mathcal{A}| - 1} \; \text{otherwise.} \end{cases}

The parameter \epsilon controls the level of exploration: the higher \epsilon, the more exploration. One can set \epsilon high at the beginning of learning and progressively reduce it to exploit more. However, it chooses equally among all actions: the worst action is as likely to be selected as the next-to-best action.

Softmax action selection

Softmax action selection

Softmax action selection defines the probability of choosing an action using all estimated value. It represents the policy using a Gibbs (or Boltzmann) distribution:

\pi(a) = \dfrac{\exp \dfrac{Q_t(a)}{\tau}}{ \displaystyle\sum_{a'} \exp \dfrac{Q_t(a')}{\tau}}

where \tau is a positive parameter called the temperature.

Just as \epsilon, the temperature \tau controls the level of exploration:

  • High temperature causes the actions to be nearly equiprobable (random agent).

  • Low temperature causes the greediest actions only to be selected (greedy agent).

Example of action selection for the 10-armed bandit

Procedure:

  • N = 10 possible actions with Q-values Q^*(a_1), ... , Q^*(a_{10}) randomly chosen in \mathcal{N}(0, 1).

  • Each reward r_t is drawn from a normal distribution \mathcal{N}(Q^*(a), 1) depending on the selected action.

  • Estimates Q_t(a) are initialized to 0.

  • The algorithms run for 1000 plays, and the results are averaged 200 times.

Greedy action selection

Greedy action selection allows to get rid quite early of the actions with negative rewards. However, it may stick with the first positive action it founds, probably not the optimal one. The more actions you have, the more likely you will get stuck in a suboptimal policy.

Greedy action selection on a 10-armed bandit for 200 plays.

\epsilon-greedy action selection

\epsilon-greedy action selection continues to explore after finding a good (but often suboptimal) action. It is not always able to recognize the optimal action (it depends on the variance of the rewards).

\epsilon-greedy action selection on a 10-armed bandit for 200 plays.

Softmax action selection

Softmax action selection explores more consistently the available actions. The estimated Q-values are much closer to the true values than with (\epsilon-)greedy methods.

Softmax action selection on a 10-armed bandit for 200 plays.

Comparison

Average reward per step.

Frequency of selection of the optimal action.

The greedy method learns faster at the beginning, but get stuck in the long-term by choosing suboptimal actions (50% of trials). \epsilon-greedy methods perform better on the long term, because they continue to explore. High values for \epsilon provide more exploration, hence find the optimal action earlier, but also tend to deselect it more often: with a limited number of plays, it may collect less reward than smaller values of \epsilon.

Average reward per step.

Frequency of selection of the optimal action.

The softmax does not necessarily find a better solution than \epsilon-greedy, but it tends to find it faster (depending on \epsilon or \tau), as it does not lose time exploring obviously bad solutions. \epsilon-greedy or softmax methods work best when the variance of rewards is high. If the variance is zero (always the same reward value), the greedy method would find the optimal action more rapidly: the agent only needs to try each action once.

Exploration schedule

A useful technique to cope with the exploration-exploitation dilemma is to slowly decrease the value of \epsilon or \tau with the number of plays. This allows for more exploration at the beginning of learning and more exploitation towards the end. It is however hard to find the right decay rate for the exploration parameters.

Exploration parameters such as \epsilon or \tau can be scheduled to allow more exploration at the beginning of learning.

The performance is worse at the beginning, as the agent explores with a high temperature. But as the agent becomes greedier and greedier, the performance become more optimal than with a fixed temperature.

Average reward per step.

Frequency of selection of the optimal action.

Optimistic initial values

The problem with online evaluation is that it depends a lot on the initial estimates Q_0.

  • If the initial estimates are already quite good (expert knowledge), the Q-values will converge very fast.

  • If the initial estimates are very wrong, we will need a lot of updates to correctly estimate the true values.

\begin{aligned} &Q_{t+1}(a) = (1 - \alpha) \, Q_t(a) + \alpha \, r_{t+1} \\ &\\ & \rightarrow Q_1(a) = (1 - \alpha) \, Q_0(a) + \alpha \, r_1 \\ & \rightarrow Q_2(a) = (1 - \alpha) \, Q_1(a) + \alpha \, r_2 = (1- \alpha)^2 \, Q_0(a) + (1-\alpha)\alpha \, r_1 + \alpha r_2 \\ \end{aligned}

The influence of Q_0 on Q_t fades quickly with (1-\alpha)^t, but that can be lost time or lead to a suboptimal policy. However, we can use this at our advantage with optimistic initialization.

By choosing very high initial values for the estimates (they can only decrease), one can ensure that all possible actions will be selected during learning by the greedy method, solving the exploration problem. This leads however to an overestimation of the value of other actions.

Optimistic initialization.

Reinforcement comparison

Actions followed by large rewards should be made more likely to recur, whereas actions followed by small rewards should be made less likely to recur. But what is a large/small reward? Is a reward of 5 large or small? Reinforcement comparison methods only maintain a preference p_t(a) for each action, which is not exactly its Q-value. The preference for an action is updated after each play, according to the update rule:

p_{t+1}(a_t) = p_{t}(a_t) + \beta \, (r_t - \tilde{r}_t)

where \tilde{r}_t is the moving average of the recently received rewards (regardless the action):

\tilde{r}_{t+1} = \tilde{r}_t + \alpha \, (r_t - \tilde{r}_t)

  • If an action brings more reward than usual (good surprise), we increase the preference for that action.

  • If an action brings less reward than usual (bad surprise), we decrease the preference for that action.

\beta > 0 and 0 < \alpha < 1 are two constant parameters.

The preferences can be used to select the action using the softmax method just like the Q-values (without temperature):

\pi_t (a) = \dfrac{\exp p_t(a)}{ \displaystyle\sum_{a'} \exp p_t(a')}

Reinforcement comparison.

Reinforcement comparison can be very effective, as it does not rely only on the rewards received, but also on their comparison with a baseline, the average reward. This idea is at the core of actor-critic architectures which we will see later. The initial average reward \tilde{r}_{0} can be set optimistically to encourage exploration.

Average reward per step.

Frequency of selection of the optimal action.

Gradient bandit algorithm

One can even go further than reinforcement comparison: Instead of only increasing the preference for the executed action if it brings more reward than usual, we could also decrease the preference for the other actions. The preferences are used to select an action a_t via softmax:

\pi_t (a) = \dfrac{\exp p_t(a)}{ \displaystyle\sum_{a'} \exp p_t(a')}

The update rule for the action taken a_t is:

p_{t+1}(a_t) = p_{t}(a_t) + \beta \, (r_t - \tilde{r}_t) \, (1 - \pi_t(a_t))

The update rule for the other actions a a \neq a_t is:

p_{t+1}(a) = p_{t}(a) - \beta \, (r_t - \tilde{r}_t) \, \pi_t(a)

The reward baseline is updated with:

\tilde{r}_{t+1} = \tilde{r}_t + \alpha \, (r_t - \tilde{r}_t)

The preference can increase become quite high, making the policy greedy towards the end. No need for a temperature parameter!

Reinforcement comparison.

Gradient bandit is not always better than reinforcement comparison, but learns initially faster (depending on the parameters \alpha and \beta).

Average reward per step.

Frequency of selection of the optimal action.

Upper-Confidence-Bound action selection

In the previous methods, exploration is controlled by an external parameter (\epsilon or \tau) which is global to each action an must be scheduled. A much better approach would be to decide whether to explore an action based on the uncertainty about its Q-value:

  • If we are certain about the value of an action, there is no need to explore it further, we only have to exploit it if it is good.

The central limit theorem tells us that the variance of a sampling estimator decreases with the number of samples:

  • The distribution of sample averages is normally distributed with mean \mu and variance \frac{\sigma^2}{N}.

S_N \sim \mathcal{N}(\mu, \frac{\sigma}{\sqrt{N}})

The more you explore an action a, the smaller the variance of Q_t(a), the more certain you are about the estimation, the less you need to explore it.

Upper-Confidence-Bound (UCB) action selection is a greedy action selection method that uses an exploration bonus:

a^*_t = \text{argmax}_{a} \left( Q_t(a) + c \, \sqrt{\frac{\ln t}{N_t(a)}} \right)

Q_t(a) is the current estimated value of a and N_t(a) is the number of times the action a has already been selected. It realizes a balance between trusting the estimates Q_t(a) and exploring uncertain actions which have not been explored much yet.

The term \sqrt{\frac{\ln t}{N_t(a)}} is an estimate of the variance of Q_t(a). The sum of both terms is an upper-bound of the true value \mu + \sigma. When an action has not been explored much yet, the uncertainty term will dominate and the action be explored, although its estimated value might be low. When an action has been sufficiently explored, the uncertainty term goes to 0 and we greedily follow Q_t(a). The exploration-exploitation trade-off is automatically adjusted by counting visits to an action.

Upper-Confidence-Bound action selection.

The “smart” exploration of UCB allows to find the optimal action faster.

Average reward per step.

Frequency of selection of the optimal action.

Summary of evaluative feedback methods

Greedy, \epsilon-greedy, softmax, reinforcement comparison, gradient bandit and UCB all have their own advantages and disadvantages depending on the type of problem: stationary or not, high or low reward variance, etc…

These simple techniques are the most useful ones for bandit-like problems: more sophisticated ones exist, but they either make too restrictive assumptions, or are computationally intractable.

Take home messages:

  1. RL tries to estimate values based on sampled rewards.
  2. One has to balance exploitation and exploration throughout learning with the right action selection scheme.
  3. Methods exploring more find better policies, but are initially slower.

Contextual bandits

In contextual bandits, the obtained rewards do not only depend on the action a, but also on the state or context s:

r_{t+1} \sim r(s, a)

For example, the n-armed bandit could deliver rewards with different probabilities depending on who plays, the time of the year or the availability of funds in the casino. The problem is simply to estimate Q(s, a) instead of Q(a)

Contextual bandits are an intermediary problem between bandits and the full RL setup, as rewards depend on the state, but the state is not influenced by the action. Source: https://medium.com/emergent-future/simple-reinforcement-learning-with-tensorflow-part-1-5-contextual-bandits-bff01d1aad9c

Contextual bandits are for example useful for Recommender systems: actions are the display of an advertisement, the context (or state) represents the user features / identity (possibly learned by an autoencoder), and the reward represents whether the user clicks on the ad or not.

Some efficient algorithms have been developed recently, for example (Agarwal et al., 2014), but we will not go into details in this course.