\section{Introduction}
Online machine learning (OML) algorithms such as multi-armed bandit (MAB) and reinforcement learning offer a simple but very powerful framework to enable decision making over time in an unknown uncertain environment \cite{MAB1, MAB2}. The MAB algorithm aims to identify the best arm among several arms and various extensions such as multi-play, multi-player, adversarial, contextual, and linear MABs have been explored to cater a wide range of applications \cite{MAB1}. Few of them include content (news or advt.) selection to maximize the number of clicks, dynamic pricing to maximize the total profit, medical trials to identify suitable drug and resource selection in robotics, data-center, IoT and wireless networks \cite{MAB1, MAB2, MAB3}. 

An optimal MAB algorithm guarantees logarithmic regret (i.e. loss due to sub-optimal arm selection) by achieving a balance between exploration of all arms to gain knowledge that may improve future performance and exploitation of an arm which can maximize the immediate performance.
The Kullback-Leibler divergence based upper confidence bound (KLUCB) is the state-of-the-art MAB algorithm that optimizes such trade-off but it is computationally complex due to underlining optimization routine \cite{klucb}. Other algorithms include UCB, Bayes\_UCB and Thompson Sampling (TS) which incur higher regret than KLUCB \cite{MAB1, MAB2, MAB3}. From an architecture perspective, none of these algorithms have ever been realized on the hardware. The usefulness of MAB algorithms in robotics, IoT and wireless applications and strict latency constraints demand efficient mapping to area and power-efficient architecture and tight integration with the physical layer (PHY) algorithms \cite{CA1}.

In this paper, we explore synthesizable computation to replace the optimization routine in KLUCB along with the hardware-software co-design approach to efficiently map the KLUCB algorithm on the Zynq system on chip (ZSoC) and validate its performance. To the best of our knowledge, this work is the first attempt towards the hardware realization and performance analysis of MAB algorithms.
Next, we explore dynamic partial reconfiguration (DPR) to realize reconfigurable architecture that allows on-the-fly configuration of a number of arms as well as the type of algorithm. We demonstrate around 10-factor improvement in latency and throughput by enabling on-the-fly switch from KLUCB to light-weight UCB after initial learning. Since learning duration depends on the unknown arm statistics, intelligence embedded in architecture offers the capability to optimize switching instant. We validate the functional correctness and usefulness of the proposed architecture via a realistic wireless application and detailed complexity analysis demonstrates its feasibility in realizing intelligent radios/robots. Please refer to \cite{Github} for additional supplementary tutorial and source codes.





\vspace{-0.25cm}
	\section{Synthesizable UCB and KLUCB Algorithms}
	
	
	In MAB setup, each experiment consists of $N, n\in\{1,2,..,N\}$ sequential slots with $K, k\in\{1,2,..K\}$ arms and the aim is to select the arm with highest reward as many times as possible. However, the reward distribution of the arms is unknown and needs to be learned. In this paper, we limit our discussion to Bernoulli reward distribution though proposed architectures can be tuned for Exponential and Poisson distributions as well. We consider single-play MAB where the algorithm can select only one arm in each slot. The arm selected in slot $n$ is denoted by, $I_{n}$ and $R_n$ denotes the reward received for the selected arm (i.e. only one feedback in each slot). Both UCB and KLUCB algorithms select each arm once in the beginning (i.e. first $K$ slots). Thereafter, in each subsequent time slot, quality factor (QF), $Q(k,n)$ is calculated for each arm
	In UCB, the value of $Q_u(k,n)$ is given by \cite{MAB1},
	
	\begin{equation}
	\label{qf_ucb}
	    Q_u(k,n) = \frac{X(k,n)}{T(k,n)} + \sqrt{\frac{\alpha \log(n)}{T(k,n)}}
	\end{equation}
	where
	\begin{equation}
	\label{X}
	    X(k,n) = X(k,n-1) + R_{n-1} \cdot \textbf{1}_{\{I_{n-1}==k\}} \quad \forall k
	\end{equation}
	\begin{equation}
	\label{T}
	    T(k,n) = T(k,n-1) + \textbf{1}_{\{I_{n-1}==k\}} \quad \forall k
	\end{equation}
	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, $\alpha$, is an exploration factor that can take any value between 0.5 and 2.  Based on calculated QFs, the arm with the highest QF is selected and it is denoted by, $I_n$ \cite{MAB1}.
	\begin{equation}
	\label{I}
	    I_n = \argmax_k Q_u(:,n)
	\end{equation}
	
	In the literature, various extensions of UCB such as UCB\_V and UCB\_T have been discussed and they slightly differ in terms of number of the arithmetic operations in QF calculation. We have realized all three UCB algorithms on ZSoC and compared their performance in Section V. However, due to limited space constraints, we limit the discussion to UCB and KLUCB since KLUCB QF calculation is significantly different and needs computationally complex optimization routine along with KL divergence, $d$, as shown below \cite{klucb}.
 \begin{equation}
 \label{qkl}
     Q_{kl}(k,n) = \max \bigg\{q \in \left [ 0,1 \right ],d\bigg(\frac{X(k,n)}{T(k,n)},q\bigg) \leq Y(k,n)\bigg\}
 \end{equation}
 where
 \begin{equation*}
     Y(k,n)=\frac{\log n+c\log(\log n)}{T(k,n)}
     \vspace{-0.15cm}
 \end{equation*}
and
\begin{equation}
\vspace{-0.1cm}
\label{kl}
    d(p,q) = p\log\bigg(\frac{p}{q}\bigg) + (1-p) \log\bigg(\frac{1-p}{1-q}\bigg)
\end{equation}
	
	To realize Eq.~\ref{qkl}, we need KL divergence computation for large possible values of $q\in[0,1]$ which makes QF computation extremely expensive to realize in hardware. To overcome this limitation, we present an alternative heuristic approach shown in Algorithm 1 for Bernoulli reward distribution. The main idea is to dynamically and intelligently refine the range of $q$ based on comparison of the KL divergence between learned arm statistic, i.e. $\frac{X(k,n)}{T(k,n)}$ and expected arm statistics, $m_{id}$ (line 8) with the exploration factor, $S_2$ (line 9). Number of iterations of \textit{for} loop, i.e. parameter $\beta$, depends on $\Delta>0$ which is the minimum gap between statistics of any two arms and we set $\beta = \frac{1}{\Delta}$. We denote $\hat{\mu}(k,n)=\frac{X(k,n)}{T(k,n)}$ which is the learned mean of the reward distribution of $k^{th}$ arm till slot $n$ and $\mu(k)$ is its actual value which is unknown. Then, we have,
	\begin{equation}
	    	\Delta= \min_{i,j \in [N], i\neq j} |\mu(i)- \mu(j)|
	\end{equation}
	 We assume $\epsilon > \Delta$ and hence, $\beta = \frac{1}{\epsilon}$.
	
	
		\begin{algorithm}[!h]
    \caption{Modified $Q_{kl}(k,n)$ Calculation in KLUCB}
			
			\begin{algorithmic}[1]
				
				\State Input: $X(k,n), T(k,n), n$
			
				\State Parameter: $\beta$
			
				\State Output: $Q(k,n)$
   
    \State $l_{id} = S_1 = X(k,n)/T(k,n)
    \State $S_2 = [\log n+c\log(\log n)]/T(k,n) 
    \State $u_{id} = \min(1, S_1 + \sqrt{S_2/2})$
    \For{$i=1:1:\beta$}
    \State $m_{id} =(l_{id} + u_{id})/2$ 
   
    \If{$d(S_1,m_{id})>S_2$}
    \State $u_{id} = m_{id}$
    \Else
    \State $l_{id} = m_{id}$
    \EndIf
    \EndFor
    \State $Q(k,n)=u_{id}$
    			\end{algorithmic}
		\end{algorithm}
		
		
		
		
		
\section{Proposed Architecture}
We first discuss the KLUCB architecture details followed by a brief discussion on modifications needed for UCB realization. Each slot in the KLUCB algorithm consists of three tasks: 1)~Initialization (only for first $K$ slots) and parameter update based on the reward feedback, 2)~QF calculation for each arm, and 3)~Arm selection using calculated QF values. 
    
    \subsection{Initialization and Parameter Update Block}
    The initialization (INIT) and parameter update block is identical in both algorithms. At the beginning of a new experiment ($n=0$), the algorithm enters into the INIT phase and its duration is $K$ slots. The aim is to select each arm only once and in our architecture, this is accomplished using a pseudo-random sequence generator of length $K$.
    
   In each slot, values of $\{X,T\}$ are updated based on the feedback as shown in Eq.~2 and 3 in Section II and the value of $n$ is incremented by 1.  The parameter update can be done at the end of the current slot after receiving the reward for the chosen arm or in the beginning of the subsequent slot. We choose the latter approach and hence, the feedback signal contains the information, $I_{n-1}$ and $R_{n-1}$ i.e., the reward received from the selected arm in $(n-1)^{th}$ slot. The format of the feedback signal is shown in Fig.~\ref{feedback}. The first bit is the reward (0 or 1 for Bernoulli case), second is the restart bit (1 to begin new experiment and 0 to continue the same experiment) and the remaining bits indicate the arm selected in the previous time slot resulting in total $\log_2(K_{max})+2$ bits. For easier understanding, the arms are shown to be selected in deterministic order in the INIT phase. For reward distributions with non-integer rewards, additional bits are needed.
       \begin{figure}[!h]
 	\vspace{-0.15cm}
 	\centering
 	\captionsetup{justification=centering}
 	\includegraphics[width=0.45\textwidth]{fb.pdf}
 	\vspace{-0.25cm}
 	\caption{ Feedback signal format which is an input to parameter update block.}
 	\label{feedback}
 	\vspace{-0.15cm}
 \end{figure}
 
    The architecture for the first task is shown in Fig.~\ref{pua}. In all figures, a double-headed arrow indicates AXI4 protocol where M and S symbols denote master and slave ports, respectively. In Fig.~\ref{pua}, the input decoder decodes the AXI4 feedback signal and generates various enable signals. For instance, $n\_{en}$ is generated once every slot which increments $n$ by 1 using \textit{update} block as shown in Fig.~\ref{pua}. If the $k^{th}$ arm is selected in the previous slot, then only $Tk\_{en}$ is generated. Similarly, $Xk\_{en}$ is generated only if $k^{th}$ arm is chose and its reward is 1. 
   
    
    
    
  
 
  \begin{figure}[!b]
 	\vspace{-0.15cm}
 	\centering
 	\captionsetup{justification=centering}
 	\includegraphics[width=0.45\textwidth]{pu.pdf}
 	\vspace{-0.25cm}
 	\caption{Architecture for initialization and parameter update block.}
 	\label{pua}
 	\vspace{-0.25cm}
 \end{figure}
 
  
    
   
    
   
    
    \vspace{-0.2cm}
    
    \subsection{QF Calculation}
    
   
    
     	\begin{figure*}[!t]
 	\centering
 		\vspace{-0.15cm}
 	\captionsetup{justification=centering}
 	\includegraphics[width=0.85\textwidth]{qkl.pdf}
 	\vspace{-0.25cm}
 	\caption{QF calculation for a single arm of KLUCB. Note that AXI dewrapper at the input, AXI wrapper at the output and AXI stream signals are omitted for maintaining the clarity of the figure.}
 	\label{qf}
 	\vspace{-0.45cm}
    \end{figure*}



  

 
 In each slot after the INIT phase, the algorithm calculates the value of QF for each arm using the updated parameters, $X(k,n), T(k,n)$ and $n$. We map the QF calculation steps of the modified KLUCB discussed in Algorithm 1 to the suitable architecture shown in Fig.~\ref{qf}. Since the QF calculation is identical for each arm and can be done in parallel without any interdependence, we limit our discussion to a single arm.

The QF calculation needs three AXI4 stream inputs which are pre-processed to get $S_1, S_2, l_{id}$ and $u_{id}$ using the Steps 4-6 in Algorithm 1. Note that all operations are performed using the IPs with the AXI4 stream interface and for maintaining the clarify of architecture, we have omitted the AXI4 signals in Fig.~\ref{qf}. Furthermore, though reward, $X(k,n)$, can have only integer (1 and 0) values for Bernoulli distribution, the architecture supports single-precision floating-point arithmetic incurred in exponential and Poisson distributions. 

After pre-processing, QF calculation needs $\beta$ number of sequential loops. Note that due to interdependence between loops, these loops cannot be executed in parallel. For illustration, we have shown the architecture depicting various arithmetic operations and KL divergence (Eq.~\ref{kl}) calculation in each iteration of the loop. Necessary care has been taken to generate appropriate valid signals for each intermediate outputs so that the arithmetic blocks are enabled only when needed. Since only one iteration is active at a time, the same hardware is re-utilized for all $\beta$ iterations in KLUCB

Using the reconfigurable and intelligent architecture discussed later in Section IV, the proposed architecture can switch to a light-weight UCB algorithm after the initial learning period. To highlight the need for such switch from a complexity perspective, the difference in computational complexity of QF calculations in two algorithms is highlighted in Fig.~\ref{qf}. It can be observed that QF UCB is obtained by disabling all iteration blocks of KLUCB along with logarithm, additional and minimum number identification sub-blocks in the pre-processing block (shown using the shaded pattern). Though savings in power and latency is evident, we need embedded intelligence and reconfigurability to auto-enable such switch.



  
 
 
     
    
    
    
    
    \vspace{-0.2cm}
     \subsection{Arm Selection}
     
    In each slot, a new arm with maximum QF value is selected by comparing the updated QF values as shown in Eq.~\ref{I}. Corresponding architecture for $K=4$ is shown in  Fig.~\ref{sel} where the output is $I_n$ i.e. index of an arm having the highest QF. Note that QF and arm selection blocks are bypassed in the INIT phase. Using these three blocks, proposed reconfigurable and intelligent architecture is presented in the next section.
     
     
	
	
	\begin{figure}[!h]
 	\vspace{-0.25cm}
 	\centering
 	\captionsetup{justification=centering}
 	\includegraphics[width=0.425\textwidth]{comp.pdf}
 	\vspace{-0.25cm}
 	\caption{Arm selection block to select the arm with highest QF ($K=4$).}
 	\label{sel}
 	\vspace{-0.35cm}
 \end{figure}
 
 
 	\begin{table*}[!b]
\centering
\vspace{-0.4cm}
\caption{Comparison of Resource Utilization and Power Consumption}
\label{res}\vspace{-0.2cm}
\renewcommand{\arraystretch}{1.2}
\resizebox{\textwidth}{!}{%
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\multirow{2}{*}{\textbf{Row}} & \multirow{2}{*}{\textbf{Architectures with $K_{max}$ = 4}} & \multicolumn{3}{l|}{\textbf{Slice LUT usage}} & \multicolumn{3}{l|}{\textbf{Slice DSP48 usage}} & \multicolumn{3}{l|}{\textbf{Slice FF usage}} & \multicolumn{3}{l|}{\textbf{Dynamic Power}} \\ \cline{3-14} 
                              &                                               & K=2           & K=3           & K=4           & K=2            & K=3            & K=4           & K=2           & K=3           & K=4          & K=2           & K=3          & K=4          \\ \hline
1                             & Reconfigurable Modified KLUCB                   & \textbf{23958}         & \textbf{37287}         & 50616         & \textbf{80}             & \textbf{120}            & \textbf{160}           & \textbf{6089}          & \textbf{10500}         & 14911        & \textbf{1.608}         & \textbf{1.647}        & \textbf{1.696}        \\ \hline
2                             & Conventional Modified KLUCB                               & 49980         & 49980         & \textbf{49980}         & 160            & 160            & \textbf{160}           & 14911         & 14911         & \textbf{14911}        & 1.697         & 1.697        & 1.697        \\ \hline \hline
3                           & Reconfigurable Modified KLUCB+UCB                   & \textbf{30175}         & \textbf{45122}         & 60069         & \textbf{92}             & \textbf{138}            & \textbf{184}           & \textbf{6718}          & \textbf{11233}         & \textbf{18748}        & \textbf{1.639}         & \textbf{1.723}        & \textbf{1.807}        \\ \hline

4                           & Conventional Modified KLUCB+UCB                     & 59433         & 59433         & \textbf{59433}         & 184             & 184            & \textbf{184}           & 18748          & 18748         & \textbf{18748}        & 1.807         & 1.807        & \textbf{1.807}        \\ \hline \hline

5                           & Reconfigurable Modified KLUCB+X                   & \textbf{31511}         & \textbf{47124}         & 62737         & \textbf{108}             & \textbf{162}            & \textbf{216}           & \textbf{10806}          & \textbf{15865}         & \textbf{20924}        & \textbf{1.648}         & \textbf{1.737}        & \textbf{1.826}        \\ \hline

6                           & Conventional Modified KLUCB+X                   & 62101         & 62101         & \textbf{62101}         & 216             & 216            & \textbf{216}           & 20924          & 20924         & \textbf{20924}        & 1.826         & 1.826        & \textbf{1.826}        \\ \hline

7                             & Only ARM based implementation                            & \multicolumn{9}{c|}{None. Only a single processor core used.}                                                                                  & 1.567         & 1.567        & 1.567        \\ \hline


\end{tabular}
}\vspace{-0.45cm}
\end{table*}

    \section{Intelligent and Reconfigurable Architecture}
    
       \begin{figure}[!b]
		\vspace{-0.2cm}
		\centering
		\captionsetup{justification=centering}
		\includegraphics[width=0.475\textwidth]{block.pdf}
		\vspace{-0.2cm}
		\caption{ Proposed DPR based intelligent and reconfigurable architecture for MAB algorithm with tunable number of arms and type of algorithm.}
		\label{block}
		\vspace{-0.2cm}
	\end{figure}
	
The proposed intelligent and reconfigurable architecture on ZSoC consisting of ARM processor (processing system i.e. PS) and FPGA (programmable logic i.e. PL) is shown in Fig.~\ref{block}. PL contains three blocks (1-3) corresponding to three tasks discussed in the previous section. The fourth task of generating the feedback signal with appropriate reward is realized in the ARM processor (PS) thereby making PS act as an environment. The INIT and parameter update block in PL can be integrated with the QF calculation block. However, resultant architecture demands four AXI4 handshakes between PS and PL in each slot which in turn incurs significantly penalty due to $K$ AXI write transactions compared to one transaction for architecture in Fig.~\ref{block}. Other realizations such as 1) Only ARM, and 2) ARM+NEON Co-processor, are also considered and please refer to Section V for details. 
	
The proposed architecture is made reconfigurable via the DPR property of ZSoC. Specifically, PS is responsible for generating appropriate DPR signals for changing the number of arms and types of algorithms, i.e., on-the-fly configuration to UCB, UCB\_T, UCB\_V and KLUCB algorithm. To enable such reconfiguration, we have incorporated PS controlled DPR via Processor Configuration Access Port (PCAP). For our architecture in Fig.~\ref{block} with $K_{max}=4$, we have four reconfiguration regions (RR), i.e. the region whose functionality can be changed on-the-fly. Since, each region can be configured with blank, UCB, UCB\_V, UCB\_T or KLUCB QF block, these five partial bit-streams are stored in the main memory or SD card. Via bare-metal application deployed on the ARM processor, the desired bit-streams are sent to the FPGA for appropriate RR configuration using the device configuration (DevC) direct memory access (DMA).
	
Reconfiguration of the number of arms depends on the environment and hence, can be user-controlled. Similarly, the user can decide the type of algorithm at the beginning of the experiment. The proposed architecture offers additional intelligence to automatically switch between the algorithms in an ongoing experiment to optimize latency and power without compromising on performance. For example, KLUCB is optimal because it reduces exploration by quick identification of optimal arm compared to UCB. This means though both KLUCB and UCB  are asymptotically optimal, i.e. they both can identify the optimal arm, KLUCB is better as it identifies the optimal arm in fewer exploration than UCB. Based on this observation, we embed additional intelligence in our architecture to deploy KLUCB in the initial slots and on-the-fly automatic switch to light-weight UCB after an initial learning period. As shown in Fig.~\ref{qf}, we obtain $Q_u(k,n)$ as well as $Q_{kl}(k,n)$ simultaneously. These two values are then compared in arm selector block to see whether both leads to the selection of the same arm. Based on this comparison, $C_n$ is generated which is 1 when the same arm is selected else 0. The intelligence unit in the ARM processor regularly checks $C_n$ over a suitably chosen window period and enable a switch to UCB if $C_n$ is observed 1 for the majority of times in the window period (indicating completion of the KLUCB exploration).
	
	
    
    
   

	

	
 
 
 
    
 
    
    
  
	
    
    
   
    
   
  


In Fig.~\ref{scan}, we demonstrate the functioning of the proposed architecture. As shown, the user can add a new arm or remove the arm by choosing the appropriate option. When a user runs a new experiment with 3 machines, it can be observed that the switch between KLUCB to UCB happens at slot number 1526 and arm 3 with the highest reward is chosen maximum number of times. Next, the user adds new arm on-the-fly via DPR and in an experiment with four arms, algorithm needs more time for exploration which means KLUCB to UCB switch is delayed till slot 1809. As expected, arm 4 is chosen highest number of times. Please refer to \cite{Github,arxiv} containing a supplementary tutorial explaining detailed block design, DPR steps, and source codes.




 \begin{figure}[!h]
		\centering
		\captionsetup{justification=centering}
		\includegraphics[width=0.475\textwidth]{change.png}
		\vspace{-0.25cm}
		\caption{Snapshot of the baremetal application running on ARM depicting functionality of the proposed intelligent and reconfigurable architecture.}
		\vspace{-0.4cm}
		\label{scan}
	\end{figure}
	
	
	\section{Performance and Complexity Analysis}
	\label{result}
	
	To begin with, we compare the reward performance of the modified KLUCB in Algorithm 1 (referred to as KLUCB+UCB) with $\beta=16$, KLUCB \cite{klucb} and UCB \cite{MAB1} algorithms realized on ZSoC. We consider $K=4$ arms with a horizon consisting of $N=10000$ slots. The arms offer Bernoulli rewards with two different sets of mean distributions: 1)~$\mu_1=\{0.2, 0.4, 0.6, 0.8\}$ and $\mu_2=\{0.51, 0.52, 0.53, 0.54\}$. For easier analysis, the last arm has been chosen as the best arm i.e. arm with the highest reward. The average reward per slot for $\mu_1$ and $\mu_2$ is 0.54 and 0.8, respectively and this happens when the algorithm consistently selects the fourth arm. However, algorithms need exploration to learn arm distribution before converging to ideal average reward as shown in Fig.~\ref{rew}. As expected, optimization-based KLUCB offers the highest reward while proposed KLUCB+UCB (modified KLUCB with an intelligent switch to UCB after exploration) closely matches with the KLUCB and significantly outperforms UCB.
	
	 \begin{figure}[!h]
	 \vspace{-0.35cm}
     \centering
     \subfloat[]{\includegraphics[width=0.225\textwidth]{reward_mu1.pdf}%
         \label{rew1}}
         \hspace{0.05cm}
     \subfloat[]{\includegraphics[width=0.225\textwidth]{reward_mu2.pdf}%
         \label{rew2}}
          \vspace{-0.15cm}
     \caption{ Average reward of UCB, optimization based KLUCB and integrated modified KLUCB (Algorithm 1) and UCB algorithm for (a) $\mu_1$, and (b) $\mu_2$. The horizontal dotted line indicates ideal reward.}
     \vspace{-0.15cm}
     \label{rew}
 \end{figure}

	Next, we compare the resource utilization of various architectures in Table~\ref{res}. First, we consider two architectures for modified KLUCB discussed in Algorithm 1: 1) Reconfigurable via DPR, and 2) Velcro (conventional) approach. In the Velcro approach, all arms and hence, all QF calculation blocks are active at all times while the proposed reconfigurable architecture allows dynamic activation and deactivation of each arm. Note that none of these algorithms have been mapped to architectures yet in the literature. As shown in Row 1 and 2 of Table~\ref{res}, a reconfigurable approach offers lower resource utilization and power consumption except for a small increase in LUT when $K=K_{max}$. Similarly, we consider two more architectures for the proposed KLUCB+UCB algorithm where embedded intelligence enables the automatic switch from KLUCB to UCB. Corresponding results are given in Row 3 and 4 of Table~\ref{res}. In addition, two more architectures for the proposed KLUCB+X approach are considered where X stands for any one of the UCB extensions such as UCB, UCB\_V, and UCB\_T. Such architecture allows on-the-fly reconfiguration at the number of arms, type of algorithm as well as switching between the algorithms. 

All versions of the proposed reconfigurable architectures (Rows 2, 4, 6 in Table~\ref{res}) offer lower resource utilization and power consumption. Furthermore, when $K_{max}=4$ and $K=2$, the proposed approach consumes only 1.648W compared to 1.826W in the Velcro approach thereby offering around 5-10\% power saving for small-to-medium ($K/K_{max}$) ratio. Also, if we replace algorithm X in row 5 and 6 with more complex algorithms such as Bayesian UCB or TS or KLUCB extension or when the number of arms is large, i.e. $K_{max}>20$, there will be further improvement in these savings due to proposed reconfigurable approach. In Row 7, we consider only the ARM-based realization of the algorithm. Though its power consumption is around 1.567W and lowest due to hard processor, it has poor latency and hence, throughput as discussed next.
	

In Table~\ref{exetime}, we compare the execution time of various algorithms on three platforms: 1) Complex ZSoC (ARM + FPGA) as shown in Fig.~\ref{block}, 2) Only ARM, 3) ARM+NEON Co-processor. The execution time on the ARM is highest followed by the ARM+NEON platform while ZSoC offers the best performance validating the proposed hardware-software co-design approach. Between KLUCB and KLUCB+UCB approach, the latter offers more than 88\% reduction in execution time over the former. Thus, the proposed KLUCB+UCB approach offers lower execution time (Table~\ref{exetime}) without compromising on reward performance (Fig. 7). In wireless applications, MAB algorithms are realized in upper layers (MAC/Network) i.e. in ARM or other processors while the PHY is present in the SoC \cite{CA1,CA2}. The proposed architecture enables the shifting of the MAB algorithms from MAC to PHY layers along with an embedded intelligence unit that offers an accelerator factor ranging 50-100. Based on the results, we can say that the acceleration factor increases with the increase in $K$
\begin{table}[!h]
\centering
\vspace{-0.25cm}
\caption{ Comparison of Execution Time Expressed in Microseconds ($\mu$s)}
\vspace{-0.25cm}
\label{exetime}
\renewcommand{\arraystretch}{1.2}
\resizebox{0.5\textwidth}{!}{%
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\multirow{2}{*}{} & \multirow{2}{*}{\textbf{\begin{tabular}[c]{@{}c@{}}ZSoC\\ (in us)\end{tabular}}} & \multicolumn{3}{c|}{\textbf{\begin{tabular}[c]{@{}c@{}}PS (ARM)\\ (in us)\end{tabular}}} & \multicolumn{3}{c|}{\textbf{\begin{tabular}[c]{@{}c@{}}PS (ARM + NEON)\\ (in us)\end{tabular}}} \\ \cline{3-8} 
 &  & \textbf{K = 2} & \textbf{K = 3} & \textbf{K = 4} & \textbf{K = 2} & \textbf{K = 3} & \textbf{K = 4} \\ \hline
\textbf{UCB} & \textbf{792} & 7210 & 10820 & 15520 & 4170 & 6262 & 8349 \\ \hline
\textbf{UCB\_T} & \textbf{2773} & 18650 & 28970 & 37370 & 13109 & 19633 & 26187 \\ \hline
\textbf{UCB\_V} & \textbf{2760} & 17670 & 27290 & 34910 & 12673 & 19010 & 25361 \\ \hline
\textbf{KL\_UCB} & \textbf{30414} & 201458 & 302179 & 402900 & 164490 & 242163 & 331968 \\ \hline
\textbf{KL\_UCB + UCB} & \textbf{3756} & 26635 & 39956 & 54258 & 20202 & 29852 & 40711 \\ \hline
\textbf{KL\_UCB + UCB\_T} & \textbf{5531} & 46071 & 69951 & 92200 & 35816 & 53012 & 72054 \\ \hline
\textbf{KL\_UCB + UCB\_V} & \textbf{6078} & 39725 & 60277 & 79069 & 30891 & 45788 & 62154 \\ \hline
\end{tabular}%
}
\vspace{-0.25cm}
\end{table}

Next, we highlight the effect of $\beta$ on the performance of the KLUCB algorithm. As shown in Table~\ref{beta}, as the value of $\beta$ increases, the execution time increases due to sequential iterations in Algorithm 1. However, the rate of increases is substantially low in the proposed hardware-software co-design approach. In addition, we can see that the reward improves with $\beta$ and thus, the appropriate value of $\beta$ should be chosen to meet the desired trade-off between execution time and performance. In terms of learning performance, we observed that the error between actual and learned statistics decreases with an increase in $\beta$.

\begin{table}[!h]
\centering
\vspace{-0.25cm}
\caption{Execution Time vs. Reward Trade-off for Different $\beta$ Values}
\label{beta}
\renewcommand{\arraystretch}{1.2}
\resizebox{0.5\textwidth}{!}{%
\begin{tabular}{|c|c|c|l|c|l|}
\hline
\multirow{2}{*}{\textbf{}} & \multirow{2}{*}{\textbf{\begin{tabular}[c]{@{}c@{}}ZSoC\\ (Time in us, {[}$\mu_1$ Reward, $\mu_2$ Reward{]})\end{tabular}}} & \multicolumn{4}{c|}{\textbf{\begin{tabular}[c]{@{}c@{}}PS (ARM) \\ (Time in us, {[}$\mu_1$ Reward, $\mu_2$ Reward{]})\end{tabular}}} \\ \cline{3-6} 
 &  & \multicolumn{2}{c|}{\textbf{ARM + NEON}} & \multicolumn{2}{c|}{\textbf{Only ARM}} \\ \hline
\textbf{$\beta$ = 4} & \textbf{11700, {[}7718, 5330{]}} & \multicolumn{2}{c|}{101288, {[}7871, 5112{]}} & \multicolumn{2}{c|}{129592, {[}7701, 5294{]}} \\ \hline
\textbf{$\beta$ = 8} & \textbf{18100, {[}7774, 5112{]}} & \multicolumn{2}{c|}{169824, {[}7745, 5111{]}} & \multicolumn{2}{c|}{220122, {[}7771, 5281{]}} \\ \hline
\textbf{$\beta$ = 12} & \textbf{24500, {[}7856, 5411{]}} & \multicolumn{2}{c|}{242468, {[}7912, 5311{]}} & \multicolumn{2}{c|}{310345, {[}7832, 5304{]}} \\ \hline
\textbf{$\beta$ = 16} & \textbf{30414, {[}8102, 5387{]}} & \multicolumn{2}{c|}{331922, {[}8127, 5421{]}} & \multicolumn{2}{c|}{402900, {[}8106, 5430{]}} \\ \hline
\end{tabular}%
}
\vspace{-0.25cm}
\end{table}
	
	We also analyze the usefulness of the proposed architecture in for cognitive ad-hoc wireless networks where radio user aims to select the optimum channel for throughput maximization \cite{CA1}. Here, throughput refers to the number of bits transmitted per second (bps). We assume $K=4$, $N=10000$ and consider two different types of channels with statistics, $\mu$, randomly generated. As shown in Table~\ref{throughput}, proposed ZSoC based architecture offers a higher number of transmission of data bits as well as throughput than ARM+NEON based architecture. Another interesting observation is that KLUCB leads to the transmission of a higher number of bits but the proposed KLUCB+UCB offers significantly higher throughput due to lower execution time. For applications where FPGA is not available, the throughput of ARM+NEON based KLUCB+UCB realization is closed to that of ZSoC based KLUCB and at least 10 times higher than ARM-based KLUCB. We may be able to achieve further improvement in throughput if we select an appropriate UCB algorithm (UCB, UCB\_V or UCB\_T). Embedding such intelligence to select an algorithm is a challenging problem and focus of future work

\begin{table}[!h]
\centering
\vspace{-0.25cm}
\caption{Throughput Comparison for Cognitive Ad-Hoc Networks}
\vspace{-0.25cm}
\renewcommand{\arraystretch}{1.2}
\label{throughput}
\resizebox{0.45\textwidth}{!}{%
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{2}{|c|}{\multirow{2}{*}{\textbf{Algorithm}}} & \multicolumn{2}{c|}{\textbf{Data (Kbits)}} & \multicolumn{2}{c|}{\textbf{Throughput (Mbps)}} \\ \cline{3-6} 
\multicolumn{2}{|c|}{} & \textbf{$\mu_1$} &  \textbf{$\mu_2$} & \textbf{$\mu_1$} &\textbf{$\mu_2$} \\ \hline
\multirow{2}{*}{\textbf{KLUCB}} & \textbf{ZSoC} & \textbf{458.18} & \textbf{309.65} & 15.10 & 10.20 \\ \cline{2-6} 
 & \textbf{ARM+NEON} & \textbf{457.81} & \textbf{310.01} & 1.4 & 0.93 \\ \hline
\multirow{2}{*}{\textbf{KLUCB+UCB}} & \textbf{ZSoC} & 453.43 & 295.54 & \textbf{120.7} &\textbf{88.2} \\ \cline{2-6} 
 & \textbf{ARM+NEON} & 452.21 & 300.87 & 11.1 & 7.4 \\ \hline
\end{tabular}%
}\vspace{-0.25cm}
\end{table}
	
	\section{Conclusions and Future Directions}
A novel intelligent, reconfigurable, fast and computationally efficient architecture for Kullback–Leibler based Upper Confidence Bound (KLUCB) algorithm is presented in this paper. The performance analysis based on average reward, execution time, resource utilization and throughput highlights the advantages of the proposed architecture and its suitability for applications such as intelligent radio based wireless networks. Building on this state-of-the-art platform, future work will focus on open research problems such as intelligence to select the algorithm as well as optimal adaption strategy in dynamic and uncertain environment.
	
