HD-CB: The First Exploration of Hyperdimensional Computing for Contextual Bandits Problems
Marco Angioli, Antonello Rosato, Marcello Barbirotta, Rocco Martino, Francesco Menichelli, Mauro Olivieri · 2025
Read HD-CB: The First Exploration of Hyperdimensional Computing for Contextual Bandits Problems by Marco Angioli, Antonello Rosato, Marcello Barbirotta, Rocco Martino, Francesco Menichelli, Mauro Olivieri (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-16863.txt.
Introduction
Marco Angioli and five co-authors bring a brain-like computing style to a class of choice problems, in a 2025 paper. The problems, called contextual bandits, ask a system to pick the best act for each state while learning from rewards. Classic solvers lean on heavy matrix math. The new style uses very long vectors that can be added and compared in parallel.
Each act gets its own long vector, and states are mapped into the same space. Picks and updates then use simple vector steps in place of costly fits. Four variants cover unlike search tactics and memory trims. Tests on fake and real data matched or beat classic solvers, with faster settling and lower cost.
Catalog record
| CREATOR | Marco Angioli, Antonello Rosato, Marcello Barbirotta, Rocco Martino, Francesco Menichelli, Mauro Olivieri |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-16863
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
HD-CB: The First Exploration of Hyperdimensional Computing for Contextual Bandits Problems Marco Angioli, Antonello Rosato, Marcello Barbirotta, Rocco Martino, Francesco Menichelli, Mauro Olivieri Abstract Hyperdimensional Computing (HDC), also known as Vector Symbolic Architectures, is a computing paradigm that combines the strengths of symbolic reasoning with the efficiency and scalability of distributed connectionist models in artificial intelligence. HDC has recently emerged as a promising alternative for performing learning tasks in resource-constrained environments thanks to its energy and computational efficiency, inherent parallelism, and resilience to noise and hardware faults. This work introduces the Hyperdimensional Contextual Bandits (HD-CB): the first exploration of HDC to model and automate sequential decision-making Contextual Bandits (CB) problems. The proposed approach maps environmental states in a high-dimensional space and represents each action with dedicated hypervectors (HVs). At each iteration, these HVs are used to select the optimal action for the given context and are updated based on the received reward, replacing computationally expensive ridge regression procedures required by traditional linear CB algorithms with simple, highly parallel vector operations. We propose four HD-CB variants, demonstrating their flexibility in implementing different exploration strategies, as well as techniques to reduce memory overhead and the number of hyperparameters. Extensive simulations on synthetic datasets and a real-world benchmark reveal that HD-CB consistently achieves competitive or superior performance compared to traditional linear CB algorithms, while offering faster convergence time, lower computational complexity, improved scalability, and high parallelism. I Introduction Many real-world applications require sequential decision-making, where the goal is to select the optimal action from a finite set of alternatives based on the observed context or state of the environment [ 1 ] . These tasks can be formally modelled as Contextual Bandits (CB) problems, where an agent iteratively interacts with the environment, observes the context, selects an action, and receives a reward related to the chosen option. This reward updates the model parameters and guides the agent in refining its decision-making process, enabling it to adapt and improve through continuous interaction with the environment. The goal of the agent is to maximize cumulative reward over time by balancing exploring less-known actions with exploiting previously gathered knowledge [ 2 ] . CB problems are prevalent across various domains, including online advertising [ 2 ] , personalized recommendations [ 3 , 4 , 5 , 6 ] , hardware reconfiguration [ 7 ] , edge computing [ 8 , 9 ] , and medical decision-making [ 10 , 11 ] . In this work, we propose a novel, lightweight, and highly parallel approach for modelling and automating CB problems using Hyperdimensional Computing (HDC). HDC is a computing paradigm that mimics the cognitive processes of the human brain by mapping concepts to high-dimensional distributed representations called hypervectors (HVs), which are combined and compared using simple vector arithmetic. In recent years, HDC has found applications across various fields, demonstrating concrete advantages in computational and energy efficiency, scalability, convergence time, resilience, and parallelism [ 12 , 13 , 14 , 15 ] . The approach presented in this paper, referred to as Hyperdimensional Contextual Bandits (HD-CB), builds on the mathematical foundation of HDC to generate representative vectors in the high-dimensional space that compactly encapsulate information about the expected quality of each action in a given context. During the online decision-making process, the current state is mapped into the high-dimensional space and compared with the representative HV of each action to determine the one with the highest expected reward. After the chosen action is executed and a reward is received, the model updates the corresponding action HV, moving it closer to or further away from the encoded context to better reflect the expected quality of the action. The main contributions of the proposed study are the following: • The work represents the first exploration of HDC to model and automate CB problems. • It details the proposed approach in four variants tailored to different exploration strategies and resource constraints. • It analyzes the performance of HD-CB in terms of average reward, execution time and convergence speed while varying the problem parameters and the HV size. • It compares all of the proposed schemes with traditional CB algorithms from the literature using synthetic datasets and real benchmarks. II Background and Related Works II-A Contextual Bandits Contextual Multi-Armed Bandits, or simply Contextual Bandits, are a class of sequential decision-making problems where an agent interacts with the environment to learn and adapt in real-time through a reward-driven process [ 1 ] . Given a finite set of N possible actions (or “arms“), at each time step t , the agent interacts with the environment observing a context vector x_{t,a}\in\mathbb{R}^{d} for each action a , selects an action a_{t} , and receives a reward (or payoff) r_{t,a_{t}} , as depicted in Figure 1 . This reward is then used to update the model parameters, enabling it to adapt and gather information to predict the relationship between the observed context and the reward associated with each action [ 7 ] . Fig. 1: Schematic representation of contextual bandits problems. At each iteration, the algorithms observe a context, pick an action and receive a reward related to the chosen option. A widely studied branch of algorithms for modelling CB problems, which will be considered as a reference for comparison in this work, assumes a linear relationship between the reward and the context [ 2 , 16 ] . These algorithms analytically model each action a through a d\times d matrix \mathbf{A}_{a} and a d\times 1 vector \mathbf{b}_{a} . At each time step t , the algorithm employs the ridge regression described in ( 1 ) to estimate the expected reward ( p_{t,a} ) for each action a as a function of the current context. p_{t,a}=(\mathbf{A}_{a}^{-1}\mathbf{b}_{a})^{\top}\mathbf{x}_{t,a} (1) After computing the expected reward, the algorithm employs exploration strategies to select an action, balancing exploring less-known options with exploiting previously gathered information, ensuring the model can adapt and improve over time while avoiding premature convergence to suboptimal solutions. Two widely used strategies in CB algorithms are the epsilon-greedy and the Upper Confidence Bound (UCB), which, when integrated into linear algorithms, are referred to as LinearEPS and LinearUCB, respectively [ 1 , 2 , 17 ] . In the epsilon-greedy technique, at each time step, with a probability of 1-\epsilon , the model selects the action with the highest estimated reward, while in the remaining cases, it explores by selecting a random action. This strategy ensures continuous exploration over time but does not take into account the confidence of the model, potentially resulting in inefficient choices. The UCB exploration strategy [ 2 ] , on the other hand, incorporates a second factor into the reward estimation as shown in ( 2 ). p_{t,a}=(\mathbf{A}_{a}^{-1}\mathbf{b}_{a})^{\top}\mathbf{x}_{t,a}+\alpha\sqrt{\mathbf{x}_{t,a}^{\top}\mathbf{A}_{a}^{-1}\mathbf{x}_{t,a}} (2) This term ( \sqrt{\mathbf{x}_{t,a}^{\top}\mathbf{A}_{a}^{-1}\mathbf{x}_{t,a}} ), modulated by the hyperparameter \alpha\in[0,1] , represents the confidence interval for the predicted payoff and thus accounts for the uncertainty of the model in the reward estimation, dynamically balancing exploration and exploitation effectively. Regardless of the exploration strategy employed, once an action is selected, the environment yields a reward ( r_{t,a} ) to the model, which is used to update the matrices associated with the chosen action, as shown in ( 3 ). \begin{array}[]{l}\mathbf{A}_{a_{t}}=\mathbf{A}_{a_{t}}+\mathbf{x}_{t,a_{t}}\mathbf{x}_{t,a_{t}}^{\top}\\ \mathbf{b}_{a_{t}}=\mathbf{b}_{a_{t}}+r_{t}\mathbf{x}_{t,a_{t}}\end{array} (3) II-B Hyperdimensional Computing HDC