SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 1906.00547 · 2019

MaxGap Bandit: Adaptive Algorithms for Approximate Ranking

arXiv · PDF · Open in the Atlas

Code that ran

7 of 9 samples (functions and classes) lifted from this paper's linked repositories executed on a synthesized input in Syntology's jail (0 of them constructed an object rather than computing a result; 0 honoured the contract we drafted, 0 violated it and 7 have no contract verdict; 0 failures of our instrument; 2 no recorded run), measured 2026-11-21; repository links from the Papers with Code archive attributed under CC BY-SA, no affiliation; bodies inline only under a permissive licence as GitHub detects it. Not a reproduction of the paper's results.

"Ran" means the function executed on a synthesized input and returned a value. It is not a reproduction of the paper's results. This record, dated, as JSON: /api/ran/1906.00547.json · badge: /api/ran/1906.00547.svg

Each repository's role is a label: a classifier's output recorded on the link, or, where no role is recorded, what the Papers with Code archive marked. The line under it names its basis. Neither says who wrote the code.

RepositoryRoleRan
sumeetsk/maxgap_bandit canonical (classifier label)
classifier basis: census
7 ran · 2 no recorded run
FunctionStatusWhere it lives
alg_stop_gap Ran
ran on a synthesized input
sumeetsk/maxgap_bandit/stopping_times/stopping_times_plot.py
code served (permissive licence) · get_code("6d2915f14974e9f5")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned float, ndim 0, dtype family float, shape () as a later run recorded it. The image it ran in was not recorded. If your copy returns the same type, ndim and shape on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import torch
import numpy as np

torch.manual_seed(0)

# Analyzing the function:
# - left_gap_ub: needs to be indexable, len() works, elements support max()
# - right_gap_ub: needs to be indexable, len() works, elements support max()
# - best_lower_bound: numeric value for subtraction
# The function computes max of pairs, sorts them, and subtracts best_lower_bound from second element

# Create simple lists of floats for left_gap_ub and right_gap_ub
left_gap_ub = [0.5, 1.2, 0.8]
right_gap_ub = [0.9, 0.7, 1.5]
best_lower_bound = 0.3

ARGS = {
    "left_gap_ub": left_gap_ub,
    "right_gap_ub": right_gap_ub,
    "best_lower_bound": best_lower_bound
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy, torch — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type float, ndim 0, dtype family float, shape () — shape () as a later run recorded it
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
calculate_ci Ran
ran on a synthesized input
sumeetsk/maxgap_bandit/simulated_data/generate_data.py
code served (permissive licence) · get_code("349deae2840730b9")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned float64, ndim 0, dtype family float; no output shape is stated. The image it ran in was not recorded. If your copy returns the same type and ndim on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import numpy as np

def calculate_ci(pulls, delta, K):
    beta = 0.5
    a = 1.0 + 10.0 / K
    if pulls > 0:
        ci = (1.0 + beta) * 0.05 * np.sqrt(2.0 * np.log(np.log(5.0 * pulls / delta)) / pulls)
    else:
        ci = 10000
    return ci

ARGS = {
    "pulls": 100,
    "delta": 0.1,
    "K": 5
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type float64, ndim 0, dtype family float — no output shape is stated: observe_signature.py recorded float ndim 0, which disagrees with the fixture run
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
calculate_ci Ran
ran on a synthesized input
sumeetsk/maxgap_bandit/streetview_data/generate_data.py
code served (permissive licence) · get_code("1cdf5e8762149dce")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned float64, ndim 0, dtype family float; no output shape is stated. The image it ran in was not recorded. If your copy returns the same type and ndim on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import numpy as np

delta = 0.1
sigma = 0.1

def calculate_ci(pulls, delta, K):
    beta = 0.5
    a = 1.0 + 10.0 / K
    ci = (1.0 + beta) * sigma * np.sqrt(2.0 * np.log(np.log(5.0 * pulls / delta)) / pulls)
    return ci

ARGS = {
    "pulls": 100,
    "delta": 0.1,
    "K": 5
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type float64, ndim 0, dtype family float — no output shape is stated: observe_signature.py recorded float ndim 0, which disagrees with the fixture run
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
calculate_ci Ran
ran on a synthesized input
sumeetsk/maxgap_bandit/stopping_times/utils/utils.py
code served (permissive licence) · get_code("df110628f5dabffd")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned float64, ndim 0, dtype family float; no output shape is stated. The image it ran in was not recorded. If your copy returns the same type and ndim on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import numpy as np

ARGS = {
    "pulls": 100,
    "delta": 0.1,
    "K": 5,
    "sigma": 0.5
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type float64, ndim 0, dtype family float — no output shape is stated: observe_signature.py recorded float ndim 0, which disagrees with the fixture run
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
get_best_lower_bound Ran
ran on a synthesized input
sumeetsk/maxgap_bandit/simulated_data/generate_data.py
code served (permissive licence) · get_code("9dde95fb2ab4f0ef")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned float, ndim 0, dtype family float, shape () as a later run recorded it. The image it ran in was not recorded. If your copy returns the same type, ndim and shape on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import torch
import numpy as np

torch.manual_seed(0)

# Analyzing the function:
# - get_best_lower_bound takes two parameters: lcbs and rcbs
# - Both are indexed with range(K), so they need to be sequences of length K
# - lcbs and rcbs are compared with >= and <=, so they should be numeric values
# - The function accesses lcbs[x], rcbs[x], lcbs[k], rcbs[x] - so they're indexable sequences
# - min() is called on tuples of (index, lcbs[x]) - lcbs values need to be comparable
# - Arithmetic operations: lcbs[k] - rcbs[x] - so they need to support subtraction

# Create simple numeric lists for lcbs and rcbs
# These represent lower confidence bounds and right confidence bounds
# Let's create a scenario with some overlap and non-overlap

K = 4

# lcbs: lower confidence bounds - increasing sequence
lcbs = [1.0, 3.0, 5.0, 7.0]

# rcbs: right confidence bounds - values that create some overlap patterns
rcbs = [2.0, 4.0, 6.0, 8.0]

ARGS = {
    "lcbs": lcbs,
    "rcbs": rcbs,
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy, torch — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type float, ndim 0, dtype family float, shape () — shape () as a later run recorded it
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
left_gap_ub_fixedpos Ran
ran on a synthesized input
sumeetsk/maxgap_bandit/simulated_data/generate_data.py
code served (permissive licence) · get_code("09dcd23db9a22d77")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned float, ndim 0, dtype family float, shape () as a later run recorded it. The image it ran in was not recorded. If your copy returns the same type, ndim and shape on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import torch
import numpy as np

torch.manual_seed(0)

# Analyzing the function:
# - lcbs: indexed with range(len(lcbs)), compared with rcbs[i], curpos, and lcbs[i]
#   Appears to be a list of numeric values
# - rcbs: indexed with range(len(lcbs)), compared with curpos
#   Appears to be a list of numeric values, same length as lcbs
# - curarm: compared with i (integer index)
#   Appears to be an integer
# - curpos: numeric value compared with rcbs[i] and lcbs[i]
#   Appears to be a numeric value

# The function iterates through indices and compares values, so we need:
# - lcbs: list of numbers
# - rcbs: list of numbers (same length as lcbs)
# - curarm: integer index
# - curpos: numeric value

# Create simple test data
lcbs = [1.0, 2.5, 3.2, 4.1]
rcbs = [0.5, 2.0, 3.5, 5.0]
curarm = 1  # index into the lists
curpos = 3.0  # current position value

ARGS = {
    "lcbs": lcbs,
    "rcbs": rcbs,
    "curarm": curarm,
    "curpos": curpos
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy, torch — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type float, ndim 0, dtype family float, shape () — shape () as a later run recorded it
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
testrun Ran
ran on a synthesized input
sumeetsk/maxgap_bandit/stopping_times/generate_data.py
code served (permissive licence) · get_code("0fc0646337ae1d38")
How it ran

Ran in Syntology's sandbox on this synthesized input (drafted by a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API) and returned int, ndim 0, dtype family int, shape () as a later run recorded it. The image it ran in was not recorded. If your copy returns the same type, ndim and shape on these inputs, it matched what we observed; nothing here checks that. It does NOT mean the output is correct: nothing has compared it to the paper.

import numpy as np
import copy

class SimpleAlgorithm(object):
    """Minimal bandit algorithm that satisfies the interface used in testrun"""
    
    def __init__(self, num_arms=3):
        self.num_arms = num_arms
        self.arm_counts = np.zeros(num_arms)
        self.arm_rewards = np.zeros(num_arms)
        self.t = 0
        self.stop_threshold = 50  # Stop after 50 pulls
    
    def get_arm(self):
        """Select an arm to pull"""
        # Simple strategy: select arm with highest average reward, or random if tied
        if np.sum(self.arm_counts) == 0:
            return np.random.randint(0, self.num_arms)
        avg_rewards = self.arm_rewards / (self.arm_counts + 1e-10)
        return np.argmax(avg_rewards)
    
    def update(self, reward):
        """Update algorithm with observed reward"""
        self.t += 1
        # Track which arm was last pulled (simplified - just alternate)
        arm_idx = self.t % self.num_arms
        self.arm_counts[arm_idx] += 1
        self.arm_rewards[arm_idx] += reward
    
    def has_stopped(self):
        """Return -1 if not stopped, or stopping gap if stopped"""
        if self.t >= self.stop_threshold:
            return 1.0  # Return positive value to indicate stopping
        return -1


# Set random seed for reproducibility
np.random.seed(0)

# Create test arguments
thetastar = np.array([0.3, 0.6, 0.9])  # True means of 3 arms
algorithm = SimpleAlgorithm(num_arms=3)
ind = 0

ARGS = {
    'thetastar': thetastar,
    'algorithm': algorithm,
    'ind': ind
}
Setup block drafted by
a language model, Claude Haiku 4.5, prompt python_fixture_v1, through the batch API
Imports
numpy — import names as written, not package names to install; a name the repository itself provides is not a package
Returned
type int, ndim 0, dtype family int, shape () — shape () as a later run recorded it
dtype family
int means an integer dtype; float means any other dtype the instrument saw, bool and complex included (fixture_check.py records only these two families)
Environment
image not recorded; re-verify against syntology-harvest-sandbox:v5-deps; not recorded for this sample: the harness installs a cuda-to-cpu shim (cuda_shim.py) before every sample and no run records whether a sample needed it; seed: none by the harness; any seed is in the setup block
compute_hardness Not yet run
unverified (harvested, no recorded run)
sumeetsk/maxgap_bandit/stopping_times/stopping_times_plot.py
code served (permissive licence) · get_code("347fbbf0ecd16389")
How it ran

no invocation recorded.

single_sim Not yet run
unverified (harvested, no recorded run)
sumeetsk/maxgap_bandit/stopping_times/generate_data.py
code served (permissive licence) · get_code("bd144fb49355868d")
How it ran

no invocation recorded.

Also present in other papers' code

Of 9 samples lifted from this paper's linked repositories, 9 carry a function identity and 0 do not. Of the 9 distinct functions with an identity, 0 are also present in other papers whose code we hold (0 with at least one paper dated earlier, 0 the same month, 0 later) and 9 are only here among the 52,977 papers whose code Syntology holds (as of 2026-09-26).

Only here means: among the 52,977 papers whose code Syntology holds (51,887 with lifted samples, 1,090 through their assemblies only), as of 2026-09-26, no other paper's lifted samples or current assembly bricks contain an identical function body after normalisation.

Presence, not direction: an identical function body in two papers' repositories does not say who wrote it, which came from which, or that either paper's method rests on it. Matching is exact after normalisation, so a renamed or edited function is not matched. Dates are when papers appeared, not when code was written. Only .py files the harvester lifted are covered; notebooks are not read. A new-style arXiv id YYMM.NNNN dates a paper to the month 20YY-MM; otherwise Paper.year dates it to the year; otherwise it is undated. Dates are when the paper appeared, not when the code was written. Read 2026-11-21.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

This paper studies the problem of adaptively sampling from K distributions (arms) in order to identify the largest gap between any two adjacent means. We call this the MaxGap-bandit problem. This problem arises naturally in approximate ranking, noisy sorting, outlier detection, and top-arm identification in bandits. The key novelty of the MaxGap-bandit problem is that it aims to adaptively determine the natural partitioning of the distributions into a subset with larger means and a subset with smaller means, where the split is determined by the largest gap rather than a pre-specified rank or threshold. Estimating an arm's gap requires sampling its neighboring arms in addition to itself, and this dependence results in a novel hardness parameter that characterizes the sample complexity of the problem. We propose elimination and UCB-style algorithms and show that they are minimax optimal. Our experiments show that the UCB-style algorithms require 6-8x fewer samples than non-adaptive sampling to achieve the same error.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("1906.00547")
get_code_for_paper("1906.00547")
have("1906.00547")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/1906.00547.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/1906.00547.svg)](https://syntology.ai/paper/1906.00547)

Connect an agent — have() is free.