Dwell Time as the Block Size: Fixed-Budget Best-Source Identification under Heavy-Tailed Signals

When an observer has a fixed amount of time to split across many noisy sources, they face two coupled choices: which source to watch, and for how long to watch it before switching. The source might be a telescope target, a trading venue or a sensor channel. Each switch costs time, such as a telescope slewing or a system warming up, so long stays are attractive. But the signals that matter in these settings are often heavy-tailed, meaning rare, huge excursions dominate the average. One long stay that happens to catch a flare can mislead the observer badly. We propose to treat each contiguous stay on a source (a dwell) as one block of a median-of-means estimator. The median-of-means estimator splits data into blocks, averages each block and reports the median of the block averages, so one wild block cannot move it. Under this view, choosing dwell length is the same as choosing the block size, and the time lost to switching sets the price of robustness.

The core claim follows from this. For fixed-budget best-arm identification, where the goal is to name the best source when time runs out, the right dwell length can be read off the data. It is set by how fast the spread of dwell averages shrinks as dwells get longer. That scaling exponent can be estimated online from robust quantiles, with no prior knowledge of the tail index. The resulting algorithm addresses two open problems in one design. The first is fixed-budget best-arm identification under heavy tails, which Optimal δ-Correct Best-Arm Selection for Heavy-Tailed Distributions explicitly leaves open. The second is the dependence of nearly all robust bandit methods on a known moment order.

Why this gap and not the obvious one

The most obvious idea at this intersection is to make Box Thirding heavy-tailed. Box Thirding is an anytime best-arm identification method for the data-poor regime with more arms than budget. It promotes, defers or drops arms through three-way comparisons, and it assumes light-tailed noise. A heavy-tailed version would swap its means for median-of-means. A reviewer would rightly call that a plug-in exercise likely to work about as well as any careful version, so we do not propose it.

What no paper in the file models is the observer choosing how long each observation lasts. Time-varying GP bandits with non-constant evaluation time handles evaluation durations, but only as exogenous, Gaussian latencies it predicts rather than controls. Two further papers motivate the dwell trade-off from the observation side. Aielli et al. shows that 3-day gamma-ray integration washes out hourly blazar flares. Exploring short-term optical variability of blazars using TESS shows that 21–28 day windows of red-noise light curves have spectral slopes of 1.7 to 3.2 and often look bimodal (17 of 27 fits). Together they show that integration length is a statistical lever, not a nuisance.

Several heavy-tailed bandit papers supply the robust estimators we reuse, and all of them treat the unit of observation as fixed and the tail parameters as known. These are the median-of-means and truncation work in No-Regret Algorithms for Heavy-Tailed Linear Bandits, the Catoni confidence sequences of Robust-CPD-UCB, and Robust α-TS.

Core Claim

Consider $K$ sources and a total time budget $T$. A dwell of length $\tau$ on source $k$ returns the time-average of that source's signal over the dwell, and every switch costs a fixed overhead $c$.

Let $s_k(\tau)$ be a robust scale of the dwell average, for instance its interquartile range, which exists even when the variance does not. For many heavy-tailed and self-similar processes this scale follows a power law:

$$s_k(\tau) \approx s_k(1)\,\tau^{-\beta_k}.$$

Here $\beta_k = 1 - 1/\alpha$ for independent symmetric $\alpha$-stable increments, which follows from the stable-sum scaling of $n$ draws as $n^{1/\alpha}$. The exponent $\beta_k$ falls further below $1/2$ when there are heavy tails or long-range correlation. This is useful because a single measured exponent absorbs both effects.

Suppose we give source $k$ a budget $T_k$ split into $m$ dwells of length $\tau$, with $m(\tau + c) = T_k$. The median of the $m$ dwell averages misorders two sources separated by a mean gap $\Delta$ with probability roughly

$$P_{\text{err}} \lesssim \exp\!\big(-\kappa\, m\big) \quad \text{provided} \quad s_k(\tau) \le \Delta/2.$$

In this bound, $\kappa$ is a constant from the standard binomial argument for median-of-means. So the best dwell is the shortest one whose block scale falls below half the gap:

$$\tau^\star \approx (2 s_k(1)/\Delta)^{1/\beta_k}.$$

All remaining time then goes into as many such dwells as the switching overhead allows. Long dwells waste robustness, and short dwells waste time on switching and yield block medians too noisy to resolve the gap.

The new contribution is an algorithm that estimates $\beta_k$ and $s_k(1)$ during the run. It does so from the interquartile ranges of dwell averages at two or three lengths, and it plugs round-specific gap estimates into a sequential-halving schedule. Sequential halving splits the budget into rounds and discards the worse half of surviving sources after each round. No tail index is supplied.

Research Program

The first component is the algorithm, which we call Dwell-Halving. It runs sequential halving over $\lceil \log_2 K \rceil$ rounds. At the start of each round it spends a small fixed fraction of the round's budget on paired short and double-length dwells. These give an estimate of $\beta_k$ from the log-ratio of interquartile ranges, pooled across surviving sources with shrinkage because a single source yields few dwells. It then estimates the gap between the median-ranked and top-ranked survivors from the previous round's block medians, sets $\tau^\star$, and fills the round with dwells of that length. Dwells from earlier rounds are reused when their length is within a factor of two of the new $\tau^\star$. This answers the sample-waste concern raised against Box Thirding, which discards history on promotion, and we analyze the bias that reuse introduces.

The second component is theory. We aim for a fixed-budget error bound of the form $\exp(-T/(H_\beta \log K))$, where the complexity measure $H_\beta$ replaces the usual $\sum_k \Delta_k^{-2}$ with dwell-scaled terms. These terms are roughly proportional to $\Delta_k^{-1/\beta_k}$ plus an additive switching term of order $c$ times the number of dwells needed. We will prove a matching lower-bound instance in the stable family, extending the impossibility construction of Optimal δ-Correct Best-Arm Selection to the fixed-budget case with a moment condition. We will also quantify the price of estimating $\beta$ rather than knowing it.

The third component tests the premise that correlation and tails can be folded into one exponent. It is the main risk, and we treat it as an empirical question rather than an assumption.

Baselines

The naive reference is uniform time allocation with a single dwell per source, reporting the source with the highest raw mean. This is exactly the "integrate long" practice that Aielli et al. and the TESS study document. It is run on the same budget and switching overhead. Dwell-Halving should beat it by a wide margin at tail index 1.3; failing to do so would falsify the whole premise.

The strongest competitor is sequential halving with median-of-means over fixed-length dwells, where the dwell length is tuned by grid search on held-out instances with the true tail index available. This is the honest threat. It uses the same estimator and elimination schedule and differs only in that dwell length is tuned offline rather than chosen online, so it isolates our key ingredient. It gets the same budget and the same overhead, plus a tuning budget of twenty grid values per environment family, a budget Dwell-Halving does not receive. Beating it means matching its misidentification probability within statistical error across tail indices without any tuning. Strictly beating it would additionally require winning in mixed environments, where different sources have different tail indices or the gap shrinks across rounds, so that no single tuned dwell length is right.

We also run heavy-tailed plug-ins of existing methods. The first is Box Thirding with median-of-means block estimates and unit-length dwells, which has the strongest data-poor screening reported in the file. The second is the AL1 fixed-confidence method, stopped at the budget and forced to recommend its current best arm. The third is sequential halving with Catoni's estimator from Robust-CPD-UCB, given the true moment parameters.

Reported figures are sparse. For Box Thirding, the file reports only that it attains lower simple regret than Uniform Sampling, BUCB and Anytime Sequential Halving on NYCCC contest 893; no reported numeric result found on Lacuna for its simple regret. For AL1, the file reports a sample-complexity-to-lower-bound ratio of 28 at $\delta = 10^{-3}$ falling to 16 at $\delta = 10^{-8}$, but that is a fixed-confidence figure. There is no reported result found on Lacuna for fixed-budget heavy-tailed best-arm identification, so all fixed-budget numbers here will be produced by us under shared protocols.

Two ablations complete the set. One removes history reuse. The other fixes $\beta$ at the Gaussian value $1/2$, which tests whether estimating the exponent is what carries the gain.

Why not just…?

Why not just tune a fixed dwell length and run median-of-means sequential halving? This is the real threat. On a single environment family with a single tail index, a tuned fixed dwell may match us, and we will report that plainly. The case for the adaptive design rests on two conditions. The first is heterogeneous sources, where one dwell length cannot suit every source. The second is shrinking gaps across halving rounds, where the optimal $\tau^\star$ grows by the factor $(\Delta_r/\Delta_{r+1})^{1/\beta}$ each round. The mixed-environment experiments test exactly these. If the tuned baseline still ties there, the contribution reduces to the theory and a tuning-free default, and we would say so.

Why not just use one long integration per source? The empirical mean of a heavy-tailed source is dominated by its largest excursion. Thompson Sampling on Symmetric Alpha-Stable Bandits found that Gaussian-TS often fails to converge at $\alpha = 1.3$ for exactly this reason. A single dwell also produces the snapshot artifacts, such as spurious bimodality, seen in the TESS sample. The naive baseline measures this directly.

Why not just make Box Thirding robust with median-of-means? It is a sensible baseline, but it answers a different question. It controls which arms get time, whereas our question is how the time on an arm is cut into dwells. The two combine: our dwell rule could sit inside Box Thirding's comparisons. We therefore run both robust Box Thirding alone and robust Box Thirding with our dwell rule. That comparison shows whether dwell choice adds value beyond arm screening.

Why not just clip observations at a fixed threshold? Best-of-Both-Worlds for Heavy-Tailed MDPs needed a calibrated skipping bonus precisely because fixed clipping biases the mean estimate. For a best-source question, a fixed threshold also biases unevenly across sources with different scales. A clipped-mean arm is included in the Catoni and median-of-means comparison.

Proposed Experiments

The synthetic testbeds follow the file's heavy-tailed setups. The first is 50 symmetric $\alpha$-stable sources at $\alpha \in \{1.3, 1.5, 1.8\}$, as in Robust α-TS. The second is Pareto sources as in AL1. We add continuous-time versions with switching overhead $c$ swept from zero to ten base cadences, and correlated versions that use fractional noise with spectral slopes in the 1.7–3.2 range. The metric is misidentification probability over 2,000 seeds, plotted against budget.

The first decisive check covers the independent-noise case. The estimated $\beta$ should track $1 - 1/\alpha$, and the error curve of Dwell-Halving should lie within confidence bands of the oracle-tuned baseline. The second check introduces mixed tail indices and shrinking gaps, where the oracle's single dwell length must lose.

The semi-real testbeds are three. The first replays the 2-minute-cadence TESS blazar light curves of the 29 sources in Exploring short-term optical variability of blazars using TESS. A simulated observer with a budget far below 29 sectors must identify the highest-mean-flux source, with ground truth taken as the full-sector mean. This tests whether one scaling exponent handles real red noise and the bimodality artifacts; if not, the premise that correlation and tails fold into one exponent fails on real data. The second uses the Kaggle cryptocurrency prices with injected Pareto noise from Robust-CPD-UCB, restricted to single stationary segments. The third uses the NYCCC dataset with contest 893's 5,513 captions and ratings perturbed by Pareto noise, which tests the data-poor regime with more sources than dwells.

The experiment that would most change our view is the correlated TESS replay. If dwell averages there do not follow a stable power law in $\tau$, the method loses its footing and the project reverts to studying when the scaling holds.