Contextual Bandits for Resource-Constrained Devices using Probabilistic Learning

Marco Angioli, Kevin Johansson, Antonello Rosato, Amy Loutfi, Denis Kleyko · 2026

Read Contextual Bandits for Resource-Constrained Devices using Probabilistic Learning by Marco Angioli, Kevin Johansson, Antonello Rosato, Amy Loutfi, Denis Kleyko (2026) 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-2605-13346.txt.

Introduction

Angioli and colleagues adapt contextual bandits, online choice problems under partial feedback, for tiny devices. Standard linear methods scale badly in memory and compute, while hyperdimensional HD-CB grows action values until low precision hardware overflows. Their probabilistic HD-CB updates only a random subset of components each step, with a decaying chance and bounded values. At just 3 bits per component it beats binarized HD-CB and nears full precision HD-CB on standard benchmarks.

Catalog record

CREATORMarco Angioli, Kevin Johansson, Antonello Rosato, Amy Loutfi, Denis Kleyko
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32503
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.13346

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Contextual Bandits for Resource-Constrained Devices using Probabilistic Learning Thanks: The work of AL and DK was supported by Knut and Alice Wallenberg Foundation under the Wallenberg Scholars program (Grant KAW2023.0327). DK acknowledges funding from the Swedish Strategic Research Foundation under the Future Research Leaders program (Grant FFL24-0111), the Swedish Research Council under the Starting Grant program (Grant 2025-05421), and the Swedish Knowledge Foundation (Contract 20210016). Marco Angioli, Kevin Johansson, Antonello Rosato, Amy Loutfi, Denis Kleyko Abstract Contextual bandits (CB) are online sequential decision-making problems under partial feedback that underpin many adaptive services. There is a growing demand to deploy CB agents directly on-device, under strict constraints on memory, compute, and energy. However, standard linear CB algorithms are often impractical for resource-constrained devices with their unfavorable scaling in computational and memory costs. Recently, HD-CB, a CB approach based on hyperdimensional computing principles, has been proposed to model and solve CB problems by moving into high-dimensional spaces. HD-CB offers faster convergence, favorable scalability, and improves memory efficiency compared to linear CB algorithms. However, its learning rule is accumulation-based: the values of action vectors grow over time, requiring high precision. While periodic binarization can prevent overflow in low-precision components, it may discard important information about magnitudes and degrade decision quality. This paper introduces probabilistic HD-CB, a low-precision variant that replaces deterministic accumulation with a probabilistic update rule. At each step, only a random subset of vector components is updated, with a time-decaying update probability, and component values are constrained to a predefined range [ − κ , + κ ] [-\kappa,+\kappa] . This approach enables low-precision components, prevents overflow without periodic binarization, and reduces the expected update cost in proportion to the fraction of updated components. Off-policy evaluation on standardized synthetic CB benchmarks using the Open Bandit Pipeline shows that probabilistic HD-CB consistently outperforms binarized HD-CB at equal precision, while approaching the performance of HD-CB with as few as 3 bits per component. I Introduction Contextual multi-armed bandits (CB) formalize sequential decision-making processes in which an agent repeatedly selects an action based on side information (the context) and observes only the reward of the chosen action. This setting captures the exploration-exploitation trade-off that arises in many interactive systems, including online advertising [ 20 ] , personalized recommendations [ 2 , 1 , 11 , 24 ] , hardware reconfiguration [ 5 ] , edge computing [ 22 , 30 ] , and clinical decision support [ 12 ] , where the agent must adapt while limiting negative impact on the user [ 20 ] . CB can be seen as a particular case of reinforcement learning, where the selected action does not affect the next context, and the agent aims to maximize the immediate rewards after each action selection. Deploying CB agents on resource-constrained devices remains challenging, despite a demand to move decision-making from cloud to resource-constrained devices. The issue is that standard linear CB algorithms have to maintain covariance matrices whose memory footprint scales quadratically with the dimensionality of the context features and whose updates require nontrivial linear-algebra kernels that can not be easily parallelized [ 4 ] . These operations are not only computationally expensive, but also memory- and bandwidth-intensive, often conflicting with resource constraints where energy and on-chip memory are the primary bottlenecks. It was proposed to alleviate these problems of standard linear CB algorithms using hyperdimensional computing, also known as vector symbolic architectures (HD/VSA) [ 15 , 17 ] . HD/VSA was applied to the CB setting, resulting in an HD-CB approach [ 3 ] that models and solves the entire sequential decision-making process in high-dimensional spaces, using lightweight component-wise operations. This approach can be interpreted as a shallow randomized neural network [ 26 ] , in which the early (frozen) layers encode context vectors, while the trainable output layer learns high-dimensional representations of actions through associative learning rules [ 28 ] . HD-CB achieves linear time complexity, faster convergence, improved scalability, and reduced memory footprint, making it suitable for hardware acceleration and deployment on resource-constrained devices. However, the standard HD-CB update is accumulation-based : vectors representing actions are incremented or decremented at every action selection, and the growth of their components is not limited over time. Preventing overflow, requires either numeric types with high precision, causing high computational and memory costs. To address this problem and reduce these costs, the study in [ 6 ] introduced HD-CB BIN , a low-precision variant that uses vectors with Q -bit integer components and periodically applies binarization. During action selection, vectors are binarized to enable Hamming-distance similarity, and every Q updates the accumulated values are discretized back to the binary domain to keep the components bounded. However, while effective in reducing resource usage, this strategy relies on a deterministic, hard binarization operation that may discard useful magnitude information accumulated in the vectors and lead to non-negligible performance degradation, especially in noisy or data-scarce regimes where retaining historical information with higher fidelity is beneficial. This paper addresses the limitation of HD-CB from a different perspective by introducing a probabilistic variant of HD-CB, namely, HD-CB PROB . Instead of periodically binarizing action vectors, this approach bounds the learning by design to a predefined precision , introducing a probabilistic update rule, which in turn is inspired by previous work on low-precision neural networks [ 7 , 19 ] . The proposed HD-CB PROB approach updates only a randomly selected subset of vector components at each action selection, enabling the use of low-precision, saturated integer counters by controlling the learning rate with time-decaying update probabilities. This allows the agent to retain historical information with the high-fidelity in low-precision components. As a result, the overflow is avoided, update costs are decreasing over time, and learning no longer relies on periodic binarization steps that may severely affect the usefulness of learned representations. II Background II-A Contextual bandits In a multi-armed CB setting, an agent interacts with an external environment over discrete time steps t=1,\dots,T . At each time step, the agent observes a context vector \mathbf{x}_{t}\in\mathbb{R}^{d} (this notation is used even if contexts are action-dependent) describing the current state of the environment. Given a finite set of N possible actions, the agent selects an action a_{t} , and receives a scalar reward r_{t,a_{t}} , derived from an unknown probability distribution conditioned on the context and action. Rewards for the remaining N-1 actions (a\neq a_{t}) are not observed. Agent’s objective is to maximize the cumulative reward \sum_{t=1}^{T}r_{t} over time. CB algorithms’ ability to adapt policies online from logged interactions makes them particularly suitable for a wide range of real-world systems [ 9 ] . They are widely adopted in interactive systems such as online advertising and recommendation, clinical decision support, and adaptive resource management, where decisions must be made from partial feedback [ 9 ] . Recent deployments further highlight the growing relevance of CB at the edge, where decisions must be made locally under tight memory and compute constraints [ 29 , 10 ] . For example, CB have been deployed on mobile and wearable devices to personalize interventions [ 29 ] . Similarly, CB has been used on resource-constrained aerial devices to adaptively offload inference between edge and cloud [ 10 ] . In the domain

Read the complete text