Contextual Bandits for Resource-Constrained Devices using Probabilistic Learning

Technical Summary: Contextual Bandits for Resource-Constrained Devices using Probabilistic Learning

Problem Statement
Contextual bandits (CB) are fundamental to online sequential decision-making in adaptive services such as personalized recommendations and edge computing. However, deploying CB agents directly on resource-constrained devices (e.g., mobile, wearables, aerial devices) presents significant challenges. Standard linear CB algorithms, while effective, require maintaining covariance matrices that scale quadratically with context dimensionality ($O(Nd^2)$ memory) and involve computationally expensive linear algebra operations ($O(d^3)$ complexity), making them unsuitable for devices with strict memory, compute, and energy constraints.

Recent work introduced Hyperdimensional Contextual Bandits (HD-CB), which leverages Hyperdimensional Computing (HDC) to solve CB problems in high-dimensional spaces using lightweight vector operations. While HD-CB offers linear time complexity and improved scalability, its standard implementation relies on accumulation-based updates where action vector components grow indefinitely. This necessitates high-precision numeric types (e.g., 32-bit floats) to prevent overflow, negating memory efficiency gains. A previous low-precision variant, HD-CBBIN, addressed overflow by periodically binarizing vectors and resetting counters. However, this deterministic binarization discards accumulated magnitude information, leading to performance degradation, particularly in noisy or data-scarce regimes.

Methodology: Probabilistic HD-CB (HD-CBPROB)
This paper proposes HD-CBPROB, a low-precision variant of HD-CB that replaces deterministic accumulation with a probabilistic update rule. The core innovation is to bound learning by design rather than through periodic resets.

1. Bounded Integer Components: Instead of allowing vector components to grow indefinitely, HD-CBPROB constrains each component to a predefined integer range $[-\kappa, +\kappa]$. This allows the use of low-precision saturated integer counters (e.g., 2, 3, or 4 bits).
2. Probabilistic Update Rule: To enable learning within these tight bounds without losing information, the algorithm replaces the magnitude-based update with a frequency-based update. At each time step $t$, only a random subset of vector components is updated based on a time-decaying probability $\alpha_t$.
   • The update probability is defined as $\alpha_t = \alpha_0 \max(0, 1 - \frac{t-1}{T})$.
   • For each component $i$, a random value $m_{t,i} \sim U(0, 1)$ is sampled. An update occurs only if $m_{t,i} \leq \alpha_t$.
   • When an update occurs, the component is incremented or decremented by $\pm 1$ (based on the binding of the context and reward hypervectors) and then clipped to the range $[-\kappa, +\kappa]$.
3. Mechanism: This approach effectively implements a "saturating random walk." By controlling the frequency of updates rather than the magnitude of stored values, the agent retains historical information with high fidelity even in low-precision components. This eliminates the need for auxiliary counters and periodic binarization steps required by HD-CBBIN.

Key Contributions

• Algorithmic Innovation: Introduction of a probabilistic update rule for HD-CB that enables the use of low-precision, saturated integer components without periodic information loss.
• Resource Efficiency: The method reduces memory footprint by eliminating the need for auxiliary counters and separate binarized copies of vectors required by previous low-precision variants. It also reduces computational cost as the expected number of updates decreases over time due to the decaying probability $\alpha_t$.
• Performance Preservation: The approach maintains the ranking quality of actions by preserving magnitude information through update frequency, avoiding the degradation associated with hard binarization.

Experimental Results
The authors evaluated HD-CBPROB using off-policy evaluation on standardized synthetic CB benchmarks via the Open Bandit Pipeline (OBP), comparing it against:

1. LinEPS: Standard linear CB (baseline).
2. HD-CBREAL: Real-valued HD-CB.
3. HD-CBBIN: Binarized HD-CB with periodic resets.
4. HD-CBPROB: The proposed probabilistic variant.

Key findings include:

• Superiority over Binarized Variants: HD-CBPROB consistently outperforms HD-CBBIN at equal precision levels across all tested configurations (varying context dimensionality $d$ and number of actions $N$). Specifically, a 3-bit HD-CBPROB implementation improved cumulative rewards by approximately 5.8% over a 3-bit HD-CBBIN implementation.
• Approaching Real-Valued Performance: A 3-bit HD-CBPROB configuration (with saturation threshold $\kappa=3$) achieved performance approaching the real-valued HD-CBREAL baseline, with an average gap of only 2.5%.
• Diminishing Returns on Precision: Increasing precision from 3 to 4 bits yielded diminishing or slightly negative returns for HD-CBPROB, suggesting that 3 bits are sufficient to capture action quality in these synthetic settings.
• Memory Efficiency: HD-CBPROB requires strictly less memory than HD-CBBIN at the same bitwidth because it does not require auxiliary machinery (counters and temporary binarized copies). Unlike linear CB, its memory footprint remains constant with respect to context dimensionality.

Significance and Claims
The paper claims that probabilistic HD-CB resolves the trade-off between memory footprint and information loss inherent in previous hyperdimensional approaches. By shifting from magnitude-based accumulation to frequency-based probabilistic updates, the method enables the deployment of adaptive, autonomous agents on devices with tight power, memory, and compute budgets. The authors position HD-CBPROB as a compelling alternative for edge intelligence, offering a way to achieve near-optimal decision-making performance with significantly reduced resource requirements compared to both standard linear algorithms and existing low-precision hyperdimensional variants.

Future work identified by the authors includes evaluating the approach on real-world logged bandit datasets, testing under more complex reward distributions, and obtaining direct latency and energy measurements on embedded hardware to substantiate edge-deployment claims.