Geometric Resampling for Efficient Bandit Learning

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 120 papers24 conceptsfrozen 2026-10-04

In many online learning problems, a decision-maker must choose an action and only observes the outcome of that specific choice. To improve over time, the learner needs to estimate what would have happened if they had chosen differently. Traditionally, this requires importance weighting: dividing the observed reward by the probability of having chosen that action.

However, in complex scenarios—like selecting a subset of items from a massive dataset or choosing a path in a large graph—calculating these selection probabilities is often computationally impossible. Geometric Resampling (GR) provides a way to estimate these weights without ever calculating a probability.

The Intuition: Waiting for Lightning to Strike Twice

Imagine you are using a randomized strategy to pick an action. You pick action $A$. To use importance weighting, you need to know $P(A)$, the probability your strategy would pick $A$.

Instead of doing complex math to find $P(A)$, geometric resampling suggests a simulation-based approach:

  1. Observe: You pick action $A$ using your current randomized rule.
  2. Resample: Using the exact same rule and internal state, you keep picking actions (simulating them in your head) until you happen to pick action $A$ again.
  3. Count: The number of trials it took to see $A$ again is your estimate for $1/P(A)$.

This works because the number of trials until a specific event occurs follows a geometric distribution. The expected number of trials is exactly the reciprocal of the event's probability. By using this count as a proxy for the importance weight, researchers like Gergely Neu and Gábor Bartók showed in Importance weighting without importance weights that you can achieve unbiased loss estimates for unobserved actions.

Scaling Follow-the-Perturbed-Leader

The most impactful application of this technique is in Follow-the-Perturbed-Leader (FTPL) algorithms. FTPL makes decisions by adding random noise to the historical performance of all options and picking the "leader." While FTPL is robust, calculating the probability that a specific action will be the leader under random noise is often an intractable integral.

Geometric resampling bypasses this integral. In Bandit-Driven Batch Selection, Michal Lisicki and colleagues use GR to efficiently select training batches from noisy data. By treating batch selection as a combinatorial problem, they use GR to estimate which samples are "clean" without the overhead of auxiliary neural networks.

Optimizing the Simulation

While GR is simpler than exact calculation, it can still be slow if the probability $P(A)$ is very small, leading to many resamples. Recent refinements have focused on making this process "oracle-efficient":

  • Conditional Logic: Botao Chen and Junya Honda introduced Conditional Geometric Resampling (CGR) in Note on Follow-the-Perturbed-Leader, which uses value-swapping to reduce complexity from quadratic to nearly linear.
  • Geometric Skipping: In the context of auditing and large-scale sampling, Peter J. Stuckey and Vanessa Teague utilize a related concept called geometric skipping. Instead of checking every item in a stream, they calculate the "distance" to the next selected item, allowing them to jump over irrelevant data while maintaining a rigorous Bernoulli sample.

By turning a probability calculation problem into a "waiting time" simulation, geometric resampling allows sophisticated bandit algorithms to scale to high-dimensional problems like Markov Decision Processes and massive subset selection.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_geometric_resampling_for_efficient_bandi_48fd7ba1,
  title = {Geometric Resampling for Efficient Bandit Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geometric-resampling-for-efficient-bandit-learning/rdr_48fd7ba1107f40cfaa56a441c4e02ed0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_geometric_resampling_for_efficient_bandi_48fd7ba1_v1,
  title = {Geometric Resampling for Efficient Bandit Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geometric-resampling-for-efficient-bandit-learning/rdr_48fd7ba1107f40cfaa56a441c4e02ed0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}