Multi-armed Bandit Algorithms on System-on-Chip: Go Frequentist or Bayesian?

Multi-armed bandit (MAB) algorithms are designed to identify the best arm among multiple arms without prior knowledge of type of arm distribution and their statistics [1, 2, 3, 4, 5]. They achieve this by optimizing an exploration-exploitation trade-off over a finite horizon (i.e. time slots) [4, 5]. Here, exploration refers to selection of all arms sufficient number of times to accurately learn their statistics and exploitation refers to selection of the best arm as often as possible. Their applications include online advertisement selection to increase the number of clicks [6, 7], clinical trails to identify best drugs [6, 7], news personalization [6, 7], decision making in financial markets [6, 7], and resource selection in wireless networks [8, 9, 10], internet of things (IoT) [11, 12, 13, 14] and robotics [15, 16].

The performance metric for the MAB algorithm is the regret which is proportional to the number of selection of the sub-optimal arms and it should be as low as possible [1, 2, 3, 4, 5]. An optimal MAB algorithm guarantees a logarithmic regret which is the best one can achieve. The upper confidence bound (UCB) algorithm [4], Kullback Leibler UCB (KL-UCB) [2], and Thompson Sampling (TS) [3] are the popular optimal MAB algorithms. The KL-UCB algorithm is computationally complex due to underlining optimization routine and hence, TS and UCB algorithms are preferred in [17].

In wireless radio, IoT, and robotics applications, MAB algorithms are used for decision-making tasks in the media-access control (MAC) layer. With tight integration of MAC and physical (PHY) layer, there is an option to accelerate the MAB and other MAC algorithms on hardware such as ASIC or FPGA instead of sequential processors based software implementation. The hardware implementation exploits the parallel architecture thereby offering lower execution time i.e. latency. Such applications also demand deployment on edge devices and hence, mapping of the MAB algorithms on system-on-chip (SoC) is desired. Recently, we discussed the implementation of UCB and KL-UCB algorithms on the heterogeneous Zynq SoC from Xilinx consisting of the dual-core ARM processor and 7-series FPGA [17]. In this work, we focus on the TS algorithm which has not been realized on SoC yet.

Considering two types of distributions, Bernoulli and Gaussian, frequentist approach based UCB algorithm remains the same while there are two variants of KL-UCB and Bayesian approach based TS algorithm, one each for Bernoulli and Gaussian distribution [4, 2, 3, 6, 7, 5]. When arm distribution is known, we can select the appropriate algorithm and both guarantee lower regret than the UCB algorithm [3]. When arm distribution is unknown, the challenge is to decide the correct variant of the KLUCB/TS algorithm, and error in algorithm selection leads to significant degradation in performance. Specifically, the use of the Bernoulli variant of the KLUCB/TS algorithm for Gaussian distribution or vice-versa leads to high regret compared to the UCB algorithm [18, 19]. This demands intelligence to select the appropriate algorithm in an unknown environment.

In this paper, we design and implement a reconfigurable and intelligent architecture for MAB algorithms (RI-MAB) that can learn and select an appropriate algorithm in an unknown environment so as to minimizes regret. The main contributions of this paper are summarized as below:

1. 1.

   We propose a synthesizable TS algorithm for Bernoulli distribution (BTS) by approximating the Beta function via pseudo-random number generator-based approach and map it on Zynq SoC via hardware-software co-design. The architecture is optimized to reduce the computational complexity without compromising on the regret performance.

2. 2.

   For an environment with unknown arm distribution, we propose RI-MAB architecture. Here, intelligence enables the identification of appropriate algorithm (UCB or BTS) for a given environment, and reconfigurability allows anytime on-the-fly switching between UCB and BTS algorithms via dynamic partial reconfiguration (DPR). The DPR on FPGA eliminates the need for parallel implementation of algorithms resulting in huge savings in resources and power consumption.

3. 3.

   The functional correctness, resource requirement, power consumption, and execution time of the proposed BTS and RI-MAB architectures are analyzed for various arm distributions, word-length, and hardware-software co-design approaches.

4. 4.

   We also demonstrate the superiority of the proposed RI-MAB architecture over BTS and UCB only architectures.

The rest of the paper is organized as follows. The MAB problem setup and a review of the relevant works are done in Section II followed by the synthesizable TS algorithm in Section III. The improved version of the TS algorithm and its architecture on SoC is presented in Section IV. In Section V, in-depth performance analysis and comparison with the UCB algorithm is done. The RI-MAB algorithm and its architecture are discussed in Section VI followed by its performance analysis in Section VII. Section VIII concludes the paper. Please refer to [20] for source codes and tutorial to reproduce results presented in this paper.

In this section, we discuss the MAB setup, review state-of-the-art MAB algorithms, and feasibility on the SoC.

In MAB setup, each experiment consists of a horizon of $N$, $n\in\{1,2,...,N\}$ sequential slots and and the aim is to select the optimal arm from $K$, $k\in\{1,2,...,\}$ arms as often as possible. Let’s denote the arm selected in slot $n$ as $I_{n}$, and the reward received from the selected arm $I_{n}$ in slot $n$ as $R_{n}$. The reward of an arm $k$ is generated from a distribution with mean, $\mu_{k}$. The mean rewards are unknown and the performance metric, regret, is given as [4, 2, 3, 6, 7, 5]

where $\mu^{*}$ is the mean reward of an optimal arm and $T_{k}$ is the number of times the arm $k$ selected in an experiment of horizon size $N$. Note that the distribution of arm rewards is unknown but fixed over a horizon. In this paper, we focus on Bernoulli (reward $R_{n}$ is either 0 or 1) and Gaussian distribution (reward $R_{n}$ is between 0 and 1) though the discussion can be extended to Exponential and Poisson distributions.

As discussed in Section I, UCB, KL-UCB, and TS algorithms are the popular regret-minimization MAB algorithms with logarithmic regret guarantees. In the case of the UCB and KL-UCB algorithms, the first phase is initialization where each arm is selected once in the first $K$ time slots. Thereafter, in each slot, quality factor (QF) $Q(k,n)$ is calculated for each arm. For UCB, the QF, $Q_{u}(k,n)$, is given by, [4]

where

where $\textbf{1}_{cond}$ is an indicator function and it is equal to 1 (or 0) if the condition, $cond$ is TRUE (or FALSE). The parameter $X(k,n)$ is the total reward received using the arm $k$ which has been selected for $T(k,n)$ time slots in total $n$ time slots. The parameter, $\alpha$, is the exploration factor that quantifies the aggression by which the UCB algorithm explores all arms and theoretically, it lies between 0.5 and 2. Then, the arm with the highest QF is selected and it is denoted by, $I_{n}$.

After the arm $I_{n}$ is played, its parameters, $T$ and $X$, are updated using the received reward, $R_{n}$ as shown in Eq. 3 and Eq. 4. The KL-UCB algorithm is similar to UCB except for the calculation of QF which is denoted as $Q_{kl}(k,n)$ [2]. As shown in Eq. 6, QF is computationally complex due to underlining optimization function [2, 17].

where

The term, $d(p,q)$, in Eq. 8 denotes the KL divergence between $p$ and $q$. The TS algorithm does not need an initialization phase and it uses Beta function for QF calculation. It is discussed later in Section II.

All these algorithms have been extended for various other settings. The multi-play setting is the same as above except that the aim is to identify the best $L$ arms instead of one arm [21, 22]. In a time-limited pure exploration setting, the aim is to identify the best arm within a given number of time-slots such that the regret incurred during these slots is not considered i.e. pure exploration phase [23, 24, 25]. In a confidence-driven pure exploration setting, the aim is to identify the best arm with given confidence and in as few time slots as possible [23, 24, 25]. In a delayed and complex case, the reward of the selected arm in time slot $n$ is delayed by few time slots and such delay is not deterministic [26, 27, 28]. Also, the received reward might be a function of arms selected in multiple time slots instead of a separate reward for each slot [26, 27, 28]. Existing works mainly focus on the design and performance analysis of these algorithms while the focus of this work is on efficient mapping of MAB algorithms on the SoC. Since all these extensions are based on UCB/KLUCB/TS algorithms, an efficient implementation of these three algorithms is the first and important step towards the realization of all other algorithms on the SoC.

In [29], we discussed the mapping of the UCB algorithm and its extensions on Zynq SoC via a hardware-software co-design approach. In [17] we proposed the modified KL-UCB algorithm by replacing optimization function in Eq. 6 with finite-iteration based synthesizable function. Though KL-UCB offers lower regret, the resource, latency, and power consumption of the KL-UCB is high compared to the UCB. To reduce the latency and power consumption without compromising on the regret performance, we proposed reconfigurable KL-UCB architecture that enables on-the-fly switch from KL-UCB to light-weight UCB after initial exploration [17]. In the proposed architecture, UCB QF calculation is accomplished using the KL-UCB QF blocks and hence, parallel implementation of two architectures is not needed. Since the TS is the most popular MAB algorithm, efficient mapping of the TS on SoC and performance analysis for different word-length is an important research problem. Furthermore, an intelligence to identify the appropriate algorithm in an unknown environment is critical to get optimal regret performance. The work presented in this paper offers innovative solutions to these challenges.

The frequentist modeling-based UCB and KLUCB algorithms assume the mean reward of an arm is proportional to the average reward in repeated plays of a given experiment [4, 2, 3, 6, 7, 5]. On the other hand, the Bayesian modeling-based TS algorithm assumes the mean reward of an arm is proportional to a degree of belief that the arm is optimal [3]. These beliefs are updated based on the observations from the environment via Baye’s rule that takes a prior belief as an argument and returns a posterior belief for a given likelihood. Since the arm statistics are unknown, the uncertainty about arm optimality is modeled as probabilities and the arm with the highest probability of being optimal under the posterior distribution is selected [3].

In the MAB setup, posterior belief becomes a prior in subsequent time slots, and the distributions which exhibit such behavior are known as conjugate prior. For example, Beta distribution is a conjugate prior for Bernoulli likelihood function [3]. Similarly, Gamma and Pareto distributions are a conjugate prior for Poisson and Gamma distributions, respectively [3]. Thus, the Bayesian approach needs to explicitly specify prior beliefs upfront in the form of the distribution and hence, each likelihood distributions have a specific variant of the TS algorithm. None of these TS variants are realized on the SoC yet and the proposed work on the implementation of the BTS algorithm on SoC is the first contribution in this direction.

The mapping of the BTS algorithm on the SoC consists of three steps: 1) Parameter update (Eq. 3 and Eq. 4), 2) QF Calculation, 3) Arm selection (Eq. 5). Since steps 1 and 3 are identical to UCB and KL-UCB algorithms, we request readers to refer to [17, 29] for in-depth understanding and implementation. Due to limited page constraints, the discussion is focused only on Step 3: QF calculation though our implementation and tutorials include all three steps. In the BTS algorithm, the QF for each arm, denoted by $Q_{ts}(k,n)$, is calculated by drawing the random sample from the Beta distribution with parameters, $\alpha=X(k,n)$ and $\beta=T(k,n)-X(k,n)$. For the Bernoulli distribution, $\alpha$ refers to a number of successes and $\beta$ refers to a number of failures. The probability distribution function (PDF), $y_{beta}$, of Beta distribution is given by [3],

where $B(\cdot)$ is the Beta function. The indicator function $I_{[0,1]}(x)$ ensures that only values of x $\in(0,1)$ have nonzero probability. The QF calculation of the BTS algorithm involves two steps:
1) Integration of the PDF, $y_{beta}$ given in Eq. 9, over $x$ to generate the cumulative distribution function (CDF), $F(x|\alpha,\beta)$ and computation of its inverse $F^{-1}(x|\alpha,\beta)$.
2) Generation of a uniformly distributed random number $x$ and its substitution into inverse CDF. The value obtained is the random number sampled from the Beta distribution and it is considered as the QF of the arm.

The implementation of the above steps is computationally intensive and not well suited for hardware implementation due to the need for $gamma$ random generators followed by the division of random numbers. Please refer to the in-built Matlab function, $betarnd$ for more details. In the proposed approach, we approximate the $betarnd$ function using an alternative synthesizable function. In each time slot $n$, we generate $T(k,n)$ uniform random numbers for each arm $k$. These random numbers are sorted in ascending order and $X(k,n)^{th}$ random number in the sorted array is taken as the QF of the arm $k$. This approach needs the generation of random numbers in hardware and we implement a popular Mersenne Twister pseudo-random number generator (PRNG) due to its high throughput [30, 31, 32]. We referred to it as a synthesizable BTS (SBTS) algorithm.

In Fig. 1, the functionality of the proposed SBTS algorithm is verified by comparing its regret performance with the BTS algorithm realized using the $betarnd$ function. We consider $K=6$, $N=10000$ and 150 experiments. In each experiment, arm statistics are chosen randomly and the plots in Fig. 1 include the cumulative regret averaged over 150 experiments, and standard deviation (shown with a shaded region). We observed that the proposed approach selected the best arm on an average 9436 number of times ($\approx 94\%$) compared to 9445 times ($\approx 94\%$) in the $betarnd$ based BTS algorithm. The regret of both algorithms is nearly identical validating the correctness of the proposed QF calculation approach.

The proposed SBTS QF calculation approach is synthesizable on the SoC but it suffers from two drawbacks:

1. 1.

   In each time slot, a large number of random numbers need to be generated. For $K$ arms, we need to generate $\sum_{k=1}^{k=K}T(k,n)=n$ random numbers in each time slot $n$. This is followed by $K$ sorting operations, one for each arm. In the worst case (when n=N i.e. end of the horizon), we need to generate and sort $N$ random numbers in a slot. Thus, the time required to generate random numbers is not fixed and increases with $n$. This is not desirable for most applications.

2. 2.

   Even if each random number is represented using fewer bits, say 8 bits, we need total storage of $N$ bytes (For example, 10 Kbytes when $N$=10000) which is not feasible due to cost and area constraints of the majority of the embedded applications.

Ideally, MAB execution time should be fixed and as small as possible. The time taken by the MAB algorithm to select the arm affects the time available for subsequent tasks. For instance, in wireless radio, communication is time-slotted which means arm (channel) selection is followed by transmission in each time slot. The higher the time taken for channel selection, the lower is the time available for actual data communication resulting in lower throughput. In the BTS algorithm, the time required to calculate QF for all arms increases with time due to an increase in the number of random numbers and subsequent sorting tasks. Please refer to Section for the detailed resource requirement and execution time comparison. To overcome the above drawbacks of the SBTS algorithm, we present a further improvements to simplify the sorting operation and minimize the number of random number generation in each slot.

In this section, we verify the functional correctness of the proposed SBTS algorithms on Zynq SoC and compare its regret performance with state-of-the-art UCB algorithms for different WLs. The rewards are assumed to have Bernoulli distribution. All results are obtained after averaging over 100 different experiments to consider the non-deterministic nature of the online machine learning algorithms. Later, the resource utilization, power consumption, and execution time of these algorithms are analyzed. MAB algorithms such as KL-UCB, UCB_v, and UCB_t are not considered since UCB offers regret which is close to these algorithms with significant savings in resources, power consumption and execution time [17, 29].

The SBTS-ESSR algorithm is well-suited only for arm rewards with Bernoulli distribution and hence, it may not outperform the UCB algorithm when arm distribution is unknown and random [3]. For example, in wireless Radio, arm i.e. wireless channel distribution is usually Bernoulli at high signal-to-noise ratios (SNR) and Gaussian at medium and low SNRs. In IoT and robotics applications, the type of arm distribution is unknown. Such applications demand architecture which can learn, identify and deploy appropriate MAB algorithm.

Very few works have addressed this problem and [18] is one of the recent works in which the aggregator algorithm selects the arm chosen by one of the candidate MAB algorithms in each time slot. The aim is to identify an optimal algorithm for a given unknown environment and this is achieved by learning from the past performance of various algorithms i.e algorithm exploration-exploitation trade-off in addition to arm exploitation-exploration trade-off. The major problem with [18] is the need for hardware implementation of all candidate MAB algorithms in parallel (referred here as Velcro MAB). Such architecture is area and power inefficient. The proposed RI-MAB algorithm augmented with DPR-based reconfigurable architecture overcomes this problem.

The proposed RI-MAB algorithm is given in Algorithm 2. The number of candidate algorithms, number of arms, and horizon size is $A$, $K$, and $N$, respectively. The RI-MAB algorithm maintains the probability distribution on all candidate algorithms to indicate their optimality. Since all algorithms are equally likely to be optimal at the beginning of each experiment, the prior belief, $\pi_{0}$, is initialized as uniform distribution (Line 2). To update the belief and identify the optimal algorithm, the RI-MAB algorithm performs epoch-based exploration in the initial $N_{learn}$ time slots (Lines 5-19). In this phase, each algorithm is selected for $2^{e}$ time slots before incrementing the parameter $e$ by 1 (Line 12-17). This allows a sufficient number of learning samples of each algorithm before finalizing the algorithm for the rest of the horizon i.e. after $N_{learn}$ (Line 20). Such approach allows only one MAB algorithm to be active in hardware in each time slot and increasing length epoch reduces the number of algorithm switching. Even though only one algorithm is active, the parameters, $X$, and $T$, are common across all candidate algorithms which means there is no compromise on arm learning aspects of MAB setup.

During algorithm exploration (Lines 6-18), RI-MAB updates the parameter, $\pi_{n}$ in each time slot based on the selected algorithm and received reward. Similar to [18], we obtain the unbiased estimate of received reward using the probability of the arm selection i.e. belief of the selected algorithm (Line 9). Then, the belief of the selected algorithm is updated using the exponential multiplicative factor (Line 10) and learning rate (Line 8) [18]. In the end, the beliefs of all algorithms are normalized.

The functionality of the RI-MAB algorithm is explained using Fig 8. In the beginning, the prior belief, $\pi_{0}=\{0.5,0.5\}$. The algorithm starts by selecting UCB for the first $2^{1}=2$ slots. It should be noted that we simulate the algorithm with Bernoulli arm rewards for ease of understanding. In slot 1, UCB selects the arm, $I_{1}=4$ and receives a reward, $R_{1}=1$. This results in an increase in the belief value of UCB by a factor of $exp(\eta_{1}*1)$. The same happens in slot 2 when the belief of UCB further increases by receiving $R_{2}=1$ for the selected arm, $I_{2}=2$. In slots 3 and 4, the algorithm selects SBTS-ESSR, which receives rewards, $R_{3}=0$ and $R_{4}=0$ on arms 4 and 2 respectively. Hence, the belief of TS is not updated in both slots (as $exp(\eta_{n}*0)=1$). This is when the parameter $e$ is incremented by 1. Skipping over to slots 19 and 24, the algorithm selects UCB, which receives a reward, $R_{19}=1$ and $R_{24}=1$ respectively, improving the belief of UCB. In slots 128 and $N_{learn}=500$, the selected candidate algorithm, SBTS-ESSR, receives a reward of 1, which improves its belief. In summary, the belief of the selected candidate algorithm increases when it receives a reward, $R_{n}=1$, and is not updated when $R_{n}=0$. After slot $N_{learn}=500$, the algorithm finalizes SBTS-ESSR for the rest of the horizon, pertaining to its higher belief in slot $N_{learn}$.

The proposed RI-MAB algorithm is mapped on SoC and the corresponding architecture is shown in Fig. 9. Compared to Fig. 4, an additional algorithm selection unit is included in the ARM processor and the QF calculation block is reconfigured via DPR depending on the selected candidate algorithm.

We first begin with the regret comparison of the proposed RI-MAB architecture with the UCB, SBTS-ESSR, and Velcro MAB architectures. To begin with, we consider $N=10000$, $K=8$ and choose $\mu_{3}$ as the probability distributions. Note that rewards are modeled as Gaussian instead of Bernoulli distribution.

In Fig. 10 (a), we compare the regret of the four algorithms at different instances of the horizon. The regret is averaged over 20 independent experiments. The final regret (i.e. regret at the end of the horizon) for each experiment is shown in Fig. 10 (c). In all 20 experiments, SBTS-ESSR offers the lowest regret while UCB incurs the highest regret though both are able to identify the optimal arm. Velcro MAB offers performance closer to SBTS-ESSR in most of the experiments except 16 and 20 where it takes more time to learn TS is better than UCB. On the other hand, RI-MAB selects SBTS-ESSR in all experiments. Despite that, the regret of RI-MAB is higher than Velcro MAB in all experiments except 16 and 30. This happens due to the initial $N_{learn}$ period of exploration to choose between UCB and SBTS-ESSR algorithm. Still, averaged regret of RI-MAB and Velcro-MAB is nearly identical as shown in Fig. 10 (a) since regret incurred by Velcro-MAB is very high in experiments 16 and 20. Such high regret events are avoided in the RI-MAB algorithm.

In Fig. 10 (b) and (d), we repeat the above simulations by increasing the number of independent experiments to 200. It can be observed that Velcro MAB and RI-MAB offer lower regret than individual UCB and SBTS-ESSR algorithms. This is because, for experiments 31, 35, 125, 167, 174, 183, SBTS-ESSR fails to identify the optimal arm and hence, incurs huge regret. Also, as expected, UCB incurs slightly higher regret in all experiments. Though Velcro MAB avoids selection of SBTS-ESSR in experiments 31, 35, 125, 167, 174, 183, it wrongly selects UCB in few other experiments (i.e. experiments where the final regret of UCB is same as Velcro MAB). Though RI-MAB incurs higher average regret in experiments where SBTS-ESSR is optimal, it avoids the wrong selection of algorithm as well as optimal arm in the rest of the experiments. It can be observed that Velcro-MAB and RI-MAB offer lower regret than UCB and SBTS-ESSR in some experiments. This happens because learning due to switching between the two algorithms helps to avoid the wrong selection of optimal arm in SBTS-ESSR. These experiments demonstrate the need for careful algorithm switching and selection for a given environment since a single algorithm does not offer optimal performance in all experiments.

Next, we select the arm statistics randomly in each of the experiments instead of fixed $\mu_{3}$ in Fig. 10. We consider $N=10000$, $K=8$ and two types of arm statistics such that the minimum difference between two arm statistics is 1) 0.07 (Case 1), and 2) 0.025 (Case 2). Corresponding results are shown in Fig. 11 (a)-(d). It can be observed that SBTS-ESSR offers significantly higher regret in almost 25% of the experiments. Though UCB offers an overall higher average regret, it successfully identifies optimal arm in all experiments leading to better performance than SBTS-ESSR. Proposed RI-MAB offers similar performance as UCB but with lower average regret. On the other hand, Velcro UCB fails to identify the appropriate algorithm and hence, the optimal arm in some experiments while in other experiments it offers lower regret than RI-MAB. On average, both offer nearly identical average regret but RI-MAB eliminates high regret events.

To gain further insights into the regret performance, we study various statistical properties of the final regret over 100 experiments in Fig. 12. Using the Boxplot feature in Matlab, we consider median (central red line), and percentile (bottom and top edges of the box indicate the 25th and 75th percentiles, respectively). The outliers are plotted individually using the ’+’ symbol. It can be observed that the SBTS-ESSR and Velco-MAB have large size boxes indicating large variation in regret performance and the number of outliers are more indicating wrong selection of algorithm or arm. On the other hand, UCB and RI-MAB guarantee the selection of optimal arm in all experiments and RI-MAB offers lower regret between them.

Next, we compare the resource utilization and power consumption of RI-MAB and Velcro-MAB architectures in Table III. Both architectures are on-the-fly reconfigurable in terms of the number of arms and type of the algorithm. Proposed RI-MAB with SP-FP WL architecture offers around 44-65%, 36-59%, 27-56% and 15-49% savings in LUTs, FFs, DSPs, and BRAMs over Velcro-MAB architecture. Similarly, it offers 44-65% lower dynamic power consumption. The savings improve further when the WL is optimized via fixed-point representation. With the increase in the number of arms (i.e. for $K_{max}>20$, the proposed architecture and DPR approach further improvements in resource utilization. In addition, savings will increase further with the increase in the number of candidate algorithms.

In this paper, we present synthesizable and reconfigurable architecture of the Thompson Sampling (TS) multi-armed bandit (MAB) algorithm for arms with Bernoulli distribution. The functional correctness, execution time, resource, and power consumption comparisons demonstrate its superiority over the upper confidence bound (UCB) algorithm. For an environment with unknown arm distribution, a reconfigurable and intelligent MAB (RI-MAB) algorithm is proposed along with its architecture. The RI-MAB offers significant savings in resources and power consumption without compromising on the regret performance. In the future, we plan to integrate the proposed RI-MAB with wireless radio and analyze the gain in throughput using real radio signals. Other possibilities include the extension of the RI-MAB architecture for an environment where the number of arms, as well as arm statistics, are not fixed i.e. the non-stationary environment in which an optimal arm changes over time.