Multi-armed bandit

In the paper "Asymptotically efficient adaptive allocation rules", Lai and Robbins[18] (following papers of Robbins and his co-workers going back to Robbins in the year 1952) constructed convergent population selection policies that possess the fastest rate of convergence (to the population with highest mean) for the case that the population reward distributions are the one-parameter exponential family. Then, in Katehakis and Robbins[19] simplifications of the policy and the main proof were given for the case of normal populations with known variances. The next notable progress was obtained by Burnetas and Katehakis in the paper "Optimal adaptive policies for sequential allocation problems",[20] where index based policies with uniformly maximum convergence rate were constructed, under more general conditions that include the case in which the distributions of outcomes from each population depend on a vector of unknown parameters. Burnetas and Katehakis (1996) also provided an explicit solution for the important case in which the distributions of outcomes follow arbitrary (i.e., non-parametric) discrete, univariate distributions.

Later in "Optimal adaptive policies for Markov decision processes"[21] Burnetas and Katehakis studied the much larger model of Markov Decision Processes under partial information, where the transition law and/or the expected one period rewards may depend on unknown parameters. In this work, the authors constructed an explicit form for a class of adaptive policies with uniformly maximum convergence rate properties for the total expected finite horizon reward under sufficient assumptions of finite state-action spaces and irreducibility of the transition law. A main feature of these policies is that the choice of actions, at each state and time period, is based on indices that are inflations of the right-hand side of the estimated average reward optimality equations. These inflations have recently been called the optimistic approach in the work of Tewari and Bartlett,[22] Ortner[23] Filippi, Cappé, and Garivier,[24] and Honda and Takemura.[25]

For Bernoulli multi-armed bandits, Pilarski et al.[26] studied computation methods of deriving fully optimal solutions (not just asymptotically) using dynamic programming in the paper "Optimal Policy for Bernoulli Bandits: Computation and Algorithm Gauge."[26] Via indexing schemes, lookup tables, and other techniques, this work provided practically applicable optimal solutions for Bernoulli bandits provided that time horizons and numbers of arms did not become excessively large. Pilarski et al.[27] later extended this work in "Delayed Reward Bernoulli Bandits: Optimal Policy and Predictive Meta-Algorithm PARDI"[27] to create a method of determining the optimal policy for Bernoulli bandits when rewards may not be immediately revealed following a decision and may be delayed. This method relies upon calculating expected values of reward outcomes which have not yet been revealed and updating posterior probabilities when rewards are revealed.

When optimal solutions to multi-arm bandit tasks [28] are used to derive the value of animals' choices, the activity of neurons in the amygdala and ventral striatum encodes the values derived from these policies, and can be used to decode when the animals make exploratory versus exploitative choices. Moreover, optimal policies better predict animals' choice behavior than alternative strategies (described below). This suggests that the optimal solutions to multi-arm bandit problems are biologically plausible, despite being computationally demanding.[29]

Many strategies exist which provide an approximate solution to the bandit problem, and can be put into the four broad categories detailed below.

Semi-uniform strategies were the earliest (and simplest) strategies discovered to approximately solve the bandit problem. All those strategies have in common a greedy behavior where the best lever (based on previous observations) is always pulled except when a (uniformly) random action is taken.

• Epsilon-greedy strategy:[30] The best lever is selected for a proportion ${\displaystyle 1-\epsilon }$ of the trials, and a lever is selected at random (with uniform probability) for a proportion ${\displaystyle \epsilon }$. A typical parameter value might be ${\displaystyle \epsilon =0.1}$, but this can vary widely depending on circumstances and predilections.
• Epsilon-first strategy: A pure exploration phase is followed by a pure exploitation phase. For ${\displaystyle N}$ trials in total, the exploration phase occupies ${\displaystyle \epsilon N}$ trials and the exploitation phase ${\displaystyle (1-\epsilon )N}$ trials. During the exploration phase, a lever is randomly selected (with uniform probability); during the exploitation phase, the best lever is always selected.
• Epsilon-decreasing strategy: Similar to the epsilon-greedy strategy, except that the value of ${\displaystyle \epsilon }$ decreases as the experiment progresses, resulting in highly explorative behaviour at the start and highly exploitative behaviour at the finish.
• Adaptive epsilon-greedy strategy based on value differences (VDBE): Similar to the epsilon-decreasing strategy, except that epsilon is reduced on basis of the learning progress instead of manual tuning (Tokic, 2010).[31] High fluctuations in the value estimates lead to a high epsilon (high exploration, low exploitation); low fluctuations to a low epsilon (low exploration, high exploitation). Further improvements can be achieved by a softmax-weighted action selection in case of exploratory actions (Tokic & Palm, 2011).[32]
• Adaptive epsilon-greedy strategy based on Bayesian ensembles (Epsilon-BMC): An adaptive epsilon adaptation strategy for reinforcement learning similar to VBDE, with monotone convergence guarantees. In this framework, the epsilon parameter is viewed as the expectation of a posterior distribution weighting a greedy agent (that fully trusts the learned reward) and uniform learning agent (that distrusts the learned reward). This posterior is approximated using a suitable Beta distribution under the assumption of normality of observed rewards. In order to address the possible risk of decreasing epsilon too quickly, uncertainty in the variance of the learned reward is also modeled and updated using a normal-gamma model. (Gimelfarb et al., 2019).[33]

Probability matching strategies reflect the idea that the number of pulls for a given lever should match its actual probability of being the optimal lever. Probability matching strategies are also known as Thompson sampling or Bayesian Bandits,[34][35] and are surprisingly easy to implement if you can sample from the posterior for the mean value of each alternative.

Probability matching strategies also admit solutions to so-called contextual bandit problems.[34]

Pricing strategies establish a price for each lever. For example, as illustrated with the POKER algorithm,[14] the price can be the sum of the expected reward plus an estimation of extra future rewards that will gain through the additional knowledge. The lever of highest price is always pulled.

Many strategies exist that provide an approximate solution to the contextual bandit problem, and can be put into two broad categories detailed below.

• LinUCB (Upper Confidence Bound) algorithm: the authors assume a linear dependency between the expected reward of an action and its context and model the representation space using a set of linear predictors.[37][38]
• LinRel (Linear Associative Reinforcement Learning) algorithm: Similar to LinUCB, but utilizes Singular-value decomposition rather than Ridge regression to obtain an estimate of confidence.[39][40]

• UCBogram algorithm: The nonlinear reward functions are estimated using a piecewise constant estimator called a regressogram in nonparametric regression. Then, UCB is employed on each constant piece. Successive refinements of the partition of the context space are scheduled or chosen adaptively.[41][42][43]
• Generalized linear algorithms: The reward distribution follows a generalized linear model, an extension to linear bandits.[44][45][46][47]
• KernelUCB algorithm: a kernelized non-linear version of linearUCB, with efficient implementation and finite-time analysis.[48]
• Bandit Forest algorithm: a random forest is built and analyzed w.r.t the random forest built knowing the joint distribution of contexts and rewards.[49]
• Oracle-based algorithm: The algorithm reduces the contextual bandit problem into a series of supervised learning problem, and does not rely on typical realizability assumption on the reward function.[50]

In practice, there is usually a cost associated with the resource consumed by each action and the total cost is limited by a budget in many applications such as crowdsourcing and clinical trials. Constrained contextual bandit (CCB) is such a model that considers both the time and budget constraints in a multi-armed bandit setting. A. Badanidiyuru et al.[51] first studied contextual bandits with budget constraints, also referred to as Resourceful Contextual Bandits, and show that a ${\displaystyle O({\sqrt {T}})}$ regret is achievable. However, their work focuses on a finite set of policies, and the algorithm is computationally inefficient.

Framework of UCB-ALP for constrained contextual bandits

A simple algorithm with logarithmic regret is proposed in:[52]

• UCB-ALP algorithm: The framework of UCB-ALP is shown in the right figure. UCB-ALP is a simple algorithm that combines the UCB method with an Adaptive Linear Programming (ALP) algorithm, and can be easily deployed in practical systems. It is the first work that show how to achieve logarithmic regret in constrained contextual bandits. Although[52] is devoted to a special case with single budget constraint and fixed cost, the results shed light on the design and analysis of algorithms for more general CCB problems.

An example often considered for adversarial bandits is the iterated prisoner's dilemma. In this example, each adversary has two arms to pull. They can either Deny or Confess. Standard stochastic bandit algorithms don't work very well with these iterations. For example, if the opponent cooperates in the first 100 rounds, defects for the next 200, then cooperate in the following 300, etc. then algorithms such as UCB won't be able to react very quickly to these changes. This is because after a certain point sub-optimal arms are rarely pulled to limit exploration and focus on exploitation. When the environment changes the algorithm is unable to adapt or may not even detect the change.

EXP3 is a popular algorithm for adversarial multiarmed bandits, suggested and analyzed in this setting by Auer et al. [2002b]. Recently there was an increased interest in the performance of this algorithm in the stochastic setting, due to its new applications to stochastic multi-armed bandits with side information [Seldin et al., 2011] and to multi-armed bandits in the mixed stochastic-adversarial setting [Bubeck and Slivkins, 2012]. The paper presented an empirical evaluation and improved analysis of the performance of the EXP3 algorithm in the stochastic setting, as well as a modification of the EXP3 algorithm capable of achieving “logarithmic” regret in stochastic environment

 Parameters: Real ${\displaystyle \gamma \in (0,1]}$
 
 Initialisation: ${\displaystyle \omega _{i}(1)=1}$ for ${\displaystyle i=1,...,K}$
 
 For each t = 1, 2, ..., T
  1. Set ${\displaystyle p_{i}(t)=(1-\gamma ){\frac {\omega _{i}(t)}{\sum _{j=1}^{K}\omega _{j}(t)}}+{\frac {\gamma }{K}}}$       ${\displaystyle i=1,...,K}$
  2. Draw ${\displaystyle i_{t}}$ randomly according to the probabilities ${\displaystyle p_{1}(t),...,p_{K}(t)}$
  3. Receive reward ${\displaystyle x_{i_{t}}(t)\in [0,1]}$
  4. For ${\displaystyle j=1,...,K}$ set:
      ${\displaystyle {\hat {x}}_{j}(t)={\begin{cases}x_{j}(t)/p_{j}(t)&{\text{if }}j=i_{t}\\0,&{\text{otherwise}}\end{cases}}}$
 
      ${\displaystyle \omega _{j}(t+1)=\omega _{j}(t)\exp(\gamma {\hat {x}}_{j}(t)/K)}$

Exp3 chooses an arm at random with probability ${\displaystyle (1-\gamma )}$ it prefers arms with higher weights (exploit), it chooses with probability ${\displaystyle \gamma }$ to uniformly randomly explore. After receiving the rewards the weights are updated. The exponential growth significantly increases the weight of good arms.

The (external) regret of the Exp3 algorithm is at most ${\displaystyle O({\sqrt {KTlog(K)}})}$

 Parameters: Real ${\displaystyle \eta }$
 
 Initialisation: ${\displaystyle \forall i:R_{i}(1)=0}$
 
 For each t = 1,2,...,T
  1. For each arm generate a random noise from an exponential distribution ${\displaystyle \forall i:Z_{i}(t)\sim Exp(\eta )}$
  2. Pull arm ${\displaystyle I(t)}$: ${\displaystyle I(t)=arg\max _{i}\{R_{i}(t)+Z_{i}(t)\}}$
     Add noise to each arm and pull the one with the highest value
  3. Update value: ${\displaystyle R_{I(t)}(t+1)=R_{I(t)}(t)+x_{I(t)}(t)}$
     The rest remains the same

We follow the arm that we think has the best performance so far adding exponential noise to it to provide exploration.[55]

The dueling bandit variant was introduced by Yue et al. (2012)[62] to model the exploration-versus-exploitation tradeoff for relative feedback. In this variant the gambler is allowed to pull two levers at the same time, but they only get a binary feedback telling which lever provided the best reward. The difficulty of this problem stems from the fact that the gambler has no way of directly observing the reward of their actions. The earliest algorithms for this problem are InterleaveFiltering,[62] Beat-The-Mean.[63] The relative feedback of dueling bandits can also lead to voting paradoxes. A solution is to take the Condorcet winner as a reference.[64]

More recently, researchers have generalized algorithms from traditional MAB to dueling bandits: Relative Upper Confidence Bounds (RUCB),[65] Relative EXponential weighing (REX3),[66] Copeland Confidence Bounds (CCB),[67] Relative Minimum Empirical Divergence (RMED),[68] and Double Thompson Sampling (DTS).[69]

Approaches using multiple bandits that cooperate sharing knowledge in order to better optimize their performance started in 2013 with "A Gang of Bandits",[70] an algorithm relying on a similarity graph between the different bandit problems to share knowledge. The need of a similarity graph was removed in 2014 by the work on the CLUB algorithm.[71] Following this work, several other researchers created algorithms to learn multiple models at the same time under bandit feedback. For example, COFIBA was introduced by Li and Karatzoglou and Gentile (SIGIR 2016),[72] where the classical collaborative filtering, and content-based filtering methods try to learn a static recommendation model given training data.

The Combinatorial Multiarmed Bandit (CMAB) problem[73][74][75] arises when instead of a single discrete variable to choose from, an agent needs to choose values for a set of variables. Assuming each variable is discrete, the number of possible choices per iteration is exponential in the number of variables. Several CMAB settings have been studied in the literature, from settings where the variables are binary[74] to more general setting where each variable can take an arbitrary set of values.[75]