# Contextual Bandits for Resource-Constrained Devices using Probabilistic Learning

arXiv: https://arxiv.org/abs/2605.13346 · HTML: https://mlsanity.com/paper/2605.13346/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 30 references that are in the map.
- First posted on arXiv 13 May 2026.

## Builds on (most cited first, 10 of 10)

- [A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations](https://mlsanity.com/paper/2111.06077/) (2021)
- [Open Bandit Dataset and Pipeline: Towards Realistic and Reproducible Off-Policy Evaluation](https://mlsanity.com/paper/2008.07146/) (2020)
- [A comparison of Vector Symbolic Architectures](https://mlsanity.com/paper/2001.11797/) (2020)
- [Vector Symbolic Architectures as a Computing Framework for Emerging Hardware](https://mlsanity.com/paper/2106.05268/) (2021)
- [Density Encoding Enables Resource-Efficient Randomly Connected Neural Networks](https://mlsanity.com/paper/1909.09153/) (2019)
- [Contextual-Bandit Anomaly Detection for IoT Data in Distributed Hierarchical Edge Computing](https://mlsanity.com/paper/2004.06896/) (2020)
- [Edge Computing in the Dark: Leveraging Contextual-Combinatorial Bandit and Coded Computing](https://mlsanity.com/paper/1912.09512/) (2019)
- [Efficient Implementation of LinearUCB through Algorithmic Improvements and Vector Computing Acceleration for Embedded Learning Systems](https://mlsanity.com/paper/2501.13139/) (2025)
- [To Ask or Not To Ask: Human-in-the-loop Contextual Bandits with Applications in Robot-Assisted Feeding](https://mlsanity.com/paper/2405.06908/) (2024)
- [HD-CB: The First Exploration of Hyperdimensional Computing for Contextual Bandits Problems](https://mlsanity.com/paper/2501.16863/) (2025)

## Abstract (arXiv)

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 [-k,+k]. 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.