Skip to content
STIMSMITH

Contextual Bandits

Technique WIKI v1 · 7/4/2026

Contextual bandits are a class of online learning algorithms that, given an input context, select an action (arm) and observe a reward for that action, using the reward as a learning signal to maximize cumulative reward over a sequence of inputs. They are a standard approach for recommendation and ranking problems and have been adapted for specialized settings including privacy-preserving multi-party learning, robustness to adversarial action-poisoning, and, as demonstrated by ReFuzz, for selecting and mutating tests in processor hardware fuzzing.

Definition

A contextual bandit is an online learner that, on each round, receives an input (the context), selects one of several available actions (arms), and observes a reward only for the chosen arm. The reward serves as a learning signal, and the goal of the algorithm is to maximize the total reward accumulated over the sequence of inputs it observes [Privacy-Preserving Multi-Party Contextual Bandits, arXiv:1910.05299].

Common Applications

Contextual bandits are commonly used to solve recommendation or ranking problems, where the context encodes user or item features and the arms correspond to candidate items to recommend [Privacy-Preserving Multi-Party Contextual Bandits, arXiv:1910.05299].

Specialized Variants and Settings

  • Privacy-preserving multi-party contextual bandits. When multiple parties wish to collaboratively train a contextual bandit without revealing their private features, the chosen arm, or the observed reward, contextual bandits can be combined with secure multi-party computation and differentially private mechanisms such as ε-greedy exploration [Privacy-Preserving Multi-Party Contextual Bandits, arXiv:1910.05299].
  • Linear contextual bandits and LinUCB. In linear contextual bandits, the expected reward of an arm is modeled as a linear function of the context–arm feature vector. LinUCB is a widely used linear contextual bandit algorithm that maintains confidence bounds on the unknown reward parameters to balance exploration and exploitation [Efficient Action Poisoning Attacks on Linear Contextual Bandits, arXiv:2112.05367].
  • Adversarial / action-poisoning attacks. The robustness of contextual bandit algorithms has been studied through adversarial action-poisoning attacks, in which an adversary manipulates the action signal selected by the agent. Such attacks against linear contextual bandits (including LinUCB) have been shown to force a target arm to be pulled with only logarithmic cost in both white-box and black-box settings [Efficient Action Poisoning Attacks on Linear Contextual Bandits, arXiv:2112.05367].

Use in Hardware Security: ReFuzz

ReFuzz is a processor fuzzing technique that applies contextual bandits to learn from vulnerabilities discovered in prior processor generations. Using a contextual bandit policy, ReFuzz selects and mutates historically effective tests from earlier designs to dramatically improve vulnerability detection and coverage efficiency when targeting new processors [ReFuzz announcement, NDSS 2026 — evidence 39a3a314-1538-4f63-b7a6-a24863bed4c4].

References

  1. Dubey, A. et al. Privacy-Preserving Multi-Party Contextual Bandits, arXiv:1910.05299, 2019.
  2. Liu, K. et al. Efficient Action Poisoning Attacks on Linear Contextual Bandits, arXiv:2112.05367, 2021.
  3. Chen, C., Xu, Z., Rostami, M., Liu, D., Kalathil, D., Sadeghi, A.-R., Rajendran, J. ReFuzz: Reusing Tests for Processor Fuzzing with Contextual Bandits, NDSS 2026.

LINKED ENTITIES

2 links
ReFuzz USES
ReFuzz: Reusing Tests for Processor Fuzzing with Contextual Bandits USES

CITATIONS

5 sources
5 citations
[1] A contextual bandit is an online learner that, given an input, selects an arm and receives a reward for that arm, using the reward as a learning signal to maximize total reward. Privacy-Preserving Multi-Party Contextual Bandits
[2] Contextual bandits are commonly used to solve recommendation or ranking problems. Privacy-Preserving Multi-Party Contextual Bandits
[3] Privacy-preserving multi-party contextual bandits can be constructed by combining secure multi-party computation with a differentially private ε-greedy exploration mechanism. Privacy-Preserving Multi-Party Contextual Bandits
[4] LinUCB is a widely used linear contextual bandit algorithm, and action-poisoning attacks against it can force a target arm to be pulled with only logarithmic cost in both white-box and black-box settings. Efficient Action Poisoning Attacks on Linear Contextual Bandits
[5] ReFuzz uses contextual bandits to select and mutate highly effective tests from historic processor designs, improving vulnerability detection and coverage efficiency on new target processors. NDSS 2026 Hardware Security announcements (ReFuzz overview)