Multiarmed Bandit Algorithms on Zynq System-on-Chip: Go Frequentist or Bayesian?

Abstract

Multiarmed Bandit (MAB) algorithms identify the best arm among multiple arms via exploration-exploitation trade-off without prior knowledge of arm statistics. Their usefulness in wireless radio, Internet of Things (IoT), and robotics demand deployment on edge devices, and hence, a mapping on system-on-chip (SoC) is desired. Theoretically, the Bayesian-approach-based Thompson sampling (TS) algorithm offers better performance than the frequentist-approach-based upper confidence bound (UCB) algorithm. However, TS is not synthesizable due to Beta function. We address this problem by approximating it via a pseudorandom number generator (PRNG)-based architecture and efficiently realize the TS algorithm on Zynq SoC. In practice, the type of arms distribution (e.g., Bernoulli, Gaussian) is unknown, and hence, a single algorithm may not be optimal. We propose a reconfigurable and intelligent MAB (RI-MAB) framework. Here, intelligence enables the identification of appropriate MAB algorithms in an unknown environment, and reconfigurability allows on-the-fly switching between algorithms on the SoC. This eliminates the need for parallel implementation of algorithms resulting in huge savings in resources and power consumption. We analyze the functional correctness, area, power, and execution time of the proposed and existing architectures for various arm distributions, word length, and hardware-software codesign approaches. We demonstrate the superiority of the RI-MAB algorithm and its architecture over the TS and UCB algorithms.