Pith Number

pith:GOGR4XTR

pith:2026:GOGR4XTRON5QMLJT5QF4672SRY

not attested not anchored not stored refs resolved

The Sample Complexity of Multiple Change Point Identification under Bandit Feedback

Maximilian Graf, Victor Thuot

Sample complexity for locating multiple change points under bandit feedback is governed jointly by jump sizes and their relative positions.

arxiv:2605.13252 v1 · 2026-05-13 · stat.ML · cs.LG · math.ST · stat.TH

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{GOGR4XTRON5QMLJT5QF4672SRY}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

We demonstrate, both empirically and theoretically, that for general δ and η, the complexity is jointly governed by the jumps and the relative positions of the change points.

C2weakest assumption

The number of change points is known in advance and the underlying function is exactly piecewise constant with jumps of unknown but fixed magnitudes; if the number is unknown or the function has smooth transitions instead of sharp jumps, the detection and refinement phases may fail to achieve the stated precision.

C3one line summary

An adaptive bandit algorithm for multiple change-point localization achieves non-asymptotic sample bounds jointly controlled by jump magnitudes and change-point spacing for any fixed δ and η.

References

45 extracted · 45 resolved · 0 Pith anchors

[1] Adaptive sensing performance lower bounds for sparse signal detection and support estimation , author=. Bernoulli , volume=. 2014 , publisher= 2014

[2] The 28th International Conference on Artificial Intelligence and Statistics , year=

[3] Proceedings of the 42nd International Conference on Machine Learning , pages = 2025

[4] Conference on Learning Theory , pages= 2016

[5] Safety Aware Changepoint Detection for Piecewise i.i.d. Bandits , author=. The 38th Conference on Uncertainty in Artificial Intelligence , year=

Formal links

2 machine-checked theorem links

Receipt and verification

First computed	2026-05-18T02:44:49.419270Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

338d1e5e71737b062d33ec0bcf7f528e3d454ffa526f315512032f918433a883

Aliases

arxiv: 2605.13252 · arxiv_version: 2605.13252v1 · doi: 10.48550/arxiv.2605.13252 · pith_short_12: GOGR4XTRON5Q · pith_short_16: GOGR4XTRON5QMLJT · pith_short_8: GOGR4XTR

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/GOGR4XTRON5QMLJT5QF4672SRY \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 338d1e5e71737b062d33ec0bcf7f528e3d454ffa526f315512032f918433a883

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "03b2efe4d06f3db9ba6b605f9705c38e299e43e62bd065eed055af1cd0216724",
    "cross_cats_sorted": [
      "cs.LG",
      "math.ST",
      "stat.TH"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "primary_cat": "stat.ML",
    "submitted_at": "2026-05-13T09:35:19Z",
    "title_canon_sha256": "1f6fddd5539c38240085eb11b30d33bd4ca86c4a81b524e50f048a2611ace688"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.13252",
    "kind": "arxiv",
    "version": 1
  }
}