Gamma-ray telescopes looking for dark matter spend hundreds of hours a season staring at a few targets, mostly dwarf galaxies, chosen in advance from a ranking of how bright a dark-matter signal should be there. A dark matter signal here means photons from dark matter particles annihilating each other. That ranking is fragile. The expected brightness depends on a target's dark-matter density, and these estimates have been revised before. Segue 1 was once the favourite dwarf galaxy and later lost that status when its density estimate became more uncertain. Meanwhile the data actually collected, photon counts on and off the target, are never used to redirect time during the season. This proposal treats each season as a fixed-budget pure-exploration problem. A pure-exploration problem is one where the only goal is to make a good final choice, not to collect reward along the way. The season ends by naming the single target that deserves a deep follow-up campaign of 500 hours or more. Along the way, the season spends its hours adaptively so as to maximise the chance that this choice is right and that any faint signal is detected.
The ingredient that existing bandit methods lack is that the targets are not independent "arms". Every target sees the same unknown particle-physics signal strength, scaled by its own uncertain density factor and buried under its own background. A hint of excess photons in one dwarf galaxy therefore changes what we expect from all the others. We propose a phased elimination algorithm built for Poisson counts with known, heterogeneous backgrounds and a shared signal parameter. We also make a falsifiable prediction about when it helps. If no signal is present, it should do no better than the astronomers' static ranking, and it must not do worse. Any gain should appear only when a signal sits near the detection threshold. We think that is exactly the regime that matters as limits approach the thermal relic cross-section, the annihilation rate expected if dark matter was produced thermally in the early universe.
What the two literatures give us, and the gap
Fixed-budget best-arm identification asks a learner with $T$ pulls over $K$ arms to output the arm with the highest mean while minimising error probability. The canonical method is Successive Rejection: split the budget into phases, sample the surviving arms equally, and drop the worst at each phase boundary. Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem shows that this method is minimax optimal up to an unavoidable $\log K$ penalty, which arises because the learner does not know the instance difficulty in advance. Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors supplies a conversion that turns any fixed-confidence algorithm into a fixed-budget one through staged confidence levels. We reuse it as a baseline generator, not as our method.
Two lines of work handle unequal noise across arms. Variance-Dependent Best Arm Identification proves sample complexity scaling as $\sum_i \sigma_i^2/\Delta_i^2$, where $\sigma_i^2$ is arm $i$'s variance and $\Delta_i$ its gap to the best arm. That result holds only at fixed confidence and on synthetic data. Thresholding Bandits with Augmented UCB learns variances on the fly under a fixed budget. It shows that methods fed a wrong difficulty parameter fail badly, but it solves thresholding rather than best-arm selection and assumes bounded rewards. Best Arm Identification in Rare Events is the closest in spirit: it handles Poisson-like rare rewards with an approximate likelihood-based Track-and-Stop. It remains fixed-confidence, has no background floor, and treats its arms as independent. These works supply the method. None of them models the structure of a dark matter search.
On the astrophysics side, MAGIC's combined dwarf galaxy analysis (Combined searches for dark matter in dwarf spheroidal galaxies observed with the MAGIC telescopes, including new data from Coma Berenices and Draco) pools 354.3 hours over Draco, Coma Berenices, Ursa Major II and Segue 1 in a joint likelihood. The resulting limit is about $10^{-24}$ cm³/s at 1 TeV, and the error budget is dominated by uncertainty in the density factors. The MAGIC review (A review of the past and present MAGIC dark matter search program and a glimpse at the future) puts current limits roughly two orders of magnitude above the thermal relic value. It also estimates that about 500 hours on a single optimal target would be needed to reach it. Together these papers motivate the problem: time is the bottleneck, the choice of target is uncertain, and allocation is currently decided offline. The Galactic Centre line searches (Search for Gamma-Ray Spectral Lines from Dark Matter Annihilation up to 100 TeV toward the Galactic Center with MAGIC, Search for Gamma-ray Line emission from Dark Matter annihilation in the Galactic Centre with the MAGIC telescopes) constrain the design. There, the density profile uncertainty (cusp versus core) moves the expected flux by orders of magnitude, so any allocation rule has to carry density uncertainty as a broad prior rather than a point estimate. The research file found no paper that applies fixed-budget best-arm identification to indirect detection.
Core Claim
Model target $i$, observed for $t_i$ hours, as yielding on-region counts
$$N_i \sim \mathrm{Poisson}\big((J_i\,\Phi + b_i)\,t_i\big),$$
where $\Phi \ge 0$ is the particle-physics signal strength shared by all targets, $J_i$ is the target's density factor (known only through a prior from stellar kinematics), and $b_i$ is the background rate. The background is measured in parallel from off-source regions, so it is nearly known after a few hours. The quantity to rank is each target's sensitivity, $J_i/\sqrt{b_i}$. This form comes from the background-dominated limit, where the Poisson divergence between signal and no-signal reduces to $(J_i\Phi)^2 t_i/(2b_i)$.
Two consequences follow, and they shape the whole proposal. First, the background plays the role of a known variance, so the effective difficulty is a variance-weighted quantity like that of Variance-Dependent Best Arm Identification. The extra cost of having to estimate variances, which Thresholding Bandits with Augmented UCB worries about, largely disappears here. Second, counts carry information about $J_i$ only through $J_i\Phi$. When there is no signal, adaptivity can learn nothing about the ranking beyond the backgrounds. Our claim is therefore conditional. A shared-signal elimination rule matches static ranking when $\Phi=0$. For $\Phi$ near the detection threshold, it improves both detection power and correct follow-up selection, because a weak excess in one target updates the shared $\Phi$ and sharpens the density factors of every target relative to one another.
Research Program
The algorithm, which we call stack-aware successive rejection, keeps a joint posterior over $\Phi$ and all $J_i$. The posterior is updated with the Poisson likelihood above, using the measured off-region backgrounds as plug-in values. Phases follow the geometric schedule of Successive Rejection. At each phase boundary, the algorithm drops the target with the lowest posterior probability of being the final best target, measured in sensitivity. Within a phase, it allocates hours in proportion to each surviving target's expected contribution to the stacked test statistic.
Two practical pieces sit on top. Switching between targets has a calibration cost of several hours, so phases have a minimum length. The final detection test is the same stacked likelihood ratio MAGIC uses, recalibrated by simulation. The likelihood itself is unchanged by an adaptive design, but the frequentist false-alarm rate of an adaptively allocated stack must be checked, not assumed.
On the theory side, we will bound the misidentification probability in terms of the background-weighted complexity $H_b = \sum_{i\ne i^*} b_i/(J_i\Phi - J_{i^*}\Phi)^2$, adapting the fixed-budget lower-bound construction to Poisson arms. We will also ask whether the $\log K$ penalty survives once variances are known, which is the open question in Gap 4 of the research file.
Baselines
The do-nothing reference is uniform allocation, $t_i = T/K$, followed by the stacked likelihood. It is the default a cautious observer would choose under deep uncertainty about the density factors, so it is the floor every method must clear.
The strongest practical competitor is static figure-of-merit allocation: hours fixed in advance in proportion to $(\hat J_i/\sqrt{b_i})^2$ using prior-mean density factors. This is essentially how campaigns like the 354.3-hour dwarf galaxy programme (Combined searches for dark matter in dwarf spheroidal galaxies observed with the MAGIC telescopes, including new data from Coma Berenices and Draco) are planned. The reported anchor is its 95% upper limit of about $10^{-24}$ cm³/s at 1 TeV. We will first verify that our simulator, with the same hours and target set, reproduces a limit of that order. Every method will then run on the same simulated seasons and background draws, with the same total hours and switching costs.
The strongest bandit competitor is Track-and-Stop with the Poisson-plus-background divergence (Optimal Best Arm Identification with Fixed Confidence), converted to fixed budget via FC2FB (Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors). We will also run it with a naive cutoff at $T$. For Track-and-Stop, no reported result was found on Lacuna for any telescope or Poisson-background setting. The only anchors are synthetic: about 4,000 draws for Track-and-Stop versus over 8,000 for KL-LUCB on a 5-arm instance, and 6 to 12 times faster runtime for the rare-event approximation at a 1% to 13% sample overhead (Best Arm Identification in Rare Events). All bandit baselines get the same posterior or likelihood machinery and the same tuning budget for confidence schedules, chosen on held-out simulated seasons.
The key ablation is independent-arm successive rejection with the same Poisson likelihood but no shared $\Phi$. Each target's excess is then estimated separately, which isolates the coupling as the claimed ingredient.
Beating the field means meeting three conditions together. The proposal must match static allocation's median upper limit within simulation error when $\Phi=0$. It must raise detection power at a fixed false-alarm rate for injected $\Phi$ near threshold. And it must lower the probability of choosing the wrong target for follow-up, by a margin outside the spread across simulated seasons.
Why not just…?
Why not just run Track-and-Stop and stop when the hours run out? Its sampling rule plans around a confidence threshold rather than a horizon. Cutting it off can leave the budget spent on separating two poor targets, a failure noted in On Universally Optimal Algorithms for A/B Testing. We include both the cutoff and the principled FC2FB conversion as baselines, so the experiments measure this cost directly rather than assuming it.
Why not just allocate by the static signal-to-noise ranking? This is the real threat, and our own analysis says it is unbeatable when there is no signal: counts then reveal backgrounds but not density factors. We therefore do not claim a win in the null regime. The experiment sweeps the injected $\Phi$ and the width of the density-factor priors, and reports the crossover point where adaptivity starts to pay. If that point lies far above the current limits, the honest conclusion is that static ranking suffices, and the paper reports that.
Why not just split time uniformly and stack? When backgrounds and density factors differ widely across targets, uniform time spends hours on targets that contribute almost nothing to the stacked statistic. Box Thirding: Anytime Best Arm Identification under Insufficient Sampling reports uniform sampling losing to hierarchical elimination on the 5,513-arm caption benchmark, though the file gives no numbers. Our simulations include a near-homogeneous target set where uniform allocation should be competitive, which checks this directly.
Why not just use off-the-shelf variance-aware elimination with independent arms? This is our ablation. In rare-event regimes, independent confidence-bound methods like lilUCB and LUCB are reported to need millions more samples or to fail to converge (Best Arm Identification in Rare Events). If the independent version matches the coupled one, the shared-signal structure is not doing the work, and we would say so.
Proposed Experiments
The main testbed is a season simulator for MAGIC-like dwarf galaxy campaigns. It has four real targets plus synthetic candidates up to $K=30$, budgets of 200 to 350 hours, minimum visits of 5 to 10 hours, and density-factor priors whose widths span the Segue 1 revision story. Background rates are tuned so that static allocation over 354.3 hours reproduces a limit of order $10^{-24}$ cm³/s at 1 TeV. The exact instrument response functions are not in the file, which limits absolute calibration. Our claims are therefore relative across methods.
A second testbed adds a Galactic Centre arm whose density factor is drawn from a cusp-or-core mixture. This tests whether the algorithm correctly abandons or commits to a high-background, high-uncertainty target.
The decisive checks follow from the claims. First, the null-regime upper limit must not degrade relative to static allocation. Second, we will plot power and follow-up misidentification against injected $\Phi$ to locate the crossover. Third, the coupled-versus-independent ablation tests whether the shared signal matters. Fourth, the empirical false-alarm rate of the adaptively allocated stack must stay at nominal level.
For an external sanity check of the elimination machinery, we will run it on the synthetic rare-event benchmark of Best Arm Identification in Rare Events and on the $N>T$ caption benchmark against Box Thirding. Neither benchmark is evidence for the astrophysical claim.
References
- Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
- Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors
- Variance-dependent best arm identification
- Thresholding Bandits with Augmented UCB
- Best Arm Identification in Rare Events
- Combined searches for dark matter in dwarf spheroidal galaxies observed with the MAGIC telescopes, including new data from Coma Berenices and Draco
- A review of the past and present MAGIC dark matter search program and a glimpse at the future
- Search for Gamma-Ray Spectral Lines from Dark Matter Annihilation up to 100 TeV toward the Galactic Center with MAGIC
- Search for Gamma-ray Line emission from Dark Matter annihilation in the Galactic Centre with the MAGIC telescopes
- Optimal Best Arm Identification with Fixed Confidence
- On Universally Optimal Algorithms for A/B Testing
- Box Thirding: Anytime Best Arm Identification under Insufficient Sampling