Persistent Exploration and Infinite Sampling

Why Persistent Exploration Needs a Condition

An adaptive trial can assign participants using information from earlier responses. This flexibility creates a basic risk: if the rule gives one treatment an increasingly small chance of assignment, that arm may receive only finitely many participants. Estimates based on that arm then cannot keep being updated. A useful guarantee is persistent exploration: each treatment has enough cumulative conditional assignment probability that it is assigned infinitely often.

The guarantee is about conditional probabilities at each assignment, not about independent randomization. The assignment probabilities may depend on the entire observed history. The key question is whether their lower bounds add up to infinity over an indefinitely continuing trial.

Setup and Definitions

Consider a sequential trial with a fixed finite number \(K\) of treatment arms. At assignment time \(n\), let \(\mathcal{F}_{n-1}\) denote the information available immediately before the new assignment, including previous assignments and observed responses. Let \(I_{n,k}=1\) if participant \(n\) is assigned to arm \(k\), and \(I_{n,k}=0\) otherwise. Define

q_{n,k}=P(I_{n,k}=1\mid \mathcal{F}_{n-1}), \qquad N_{n,k}=\sum_{t=1}^{n} I_{t,k}, \qquad Q_{n,k}=\sum_{t=1}^{n} q_{t,k}.

The quantity \(q_{n,k}\) is the conditional assignment probability for arm \(k\); it is known given the pre-assignment history. Since exactly one arm is assigned, \(0\le q_{n,k}\le 1\) and \(\sum_{k=1}^{K}q_{n,k}=1\). The count \(N_{n,k}\) is the number of assignments to arm \(k\) by time \(n\), while \(Q_{n,k}\) is its cumulative conditional assignment probability.

Definition: A predictable lower bound for arm \(k\) is a sequence \(\varepsilon_{n,k}\) that is known given \(\mathcal{F}_{n-1}\) at assignment time \(n\), satisfies \(0\le\varepsilon_{n,k}\le q_{n,k}\), and is therefore available before the assignment is drawn. Persistent exploration for arm \(k\) is guaranteed by such a bound when \(\sum_{n=1}^{\infty}\varepsilon_{n,k}=\infty\) with probability one.

A lower bound may be deterministic, such as \(c/n\), or may depend on the observed history. For simultaneous lower bounds across arms to be feasible, they must satisfy \(\sum_{k=1}^{K}\varepsilon_{n,k}\le 1\) at every assignment time. No independence between assignments is assumed.

The Infinite-Sampling Result

Theorem: For a fixed arm \(k\), if \(Q_{n,k}\to\infty\) with probability one, then \(N_{n,k}\to\infty\) with probability one. In particular, if a predictable lower bound satisfies \(q_{n,k}\ge \varepsilon_{n,k}\) and \(\sum_{n=1}^{\infty}\varepsilon_{n,k}=\infty\) with probability one, then arm \(k\) is assigned infinitely often with probability one. For finitely many arms, if these conditions hold for every arm, then every arm is assigned infinitely often with probability one.

The statement does not require a constant floor. It requires that the conditional probabilities accumulate without bound. The proof shows a little more: when \(Q_{n,k}\) diverges, the realized assignment count tracks it in relative terms.

Derivation: The Assignment Count Tracks Its Conditional Total

Fix one arm and omit its subscript. The centered assignment indicators \(I_n-q_n\) have conditional mean zero:

E(I_n-q_n\mid\mathcal{F}_{n-1})=0, \qquad E\bigl((I_n-q_n)^2\mid\mathcal{F}_{n-1}\bigr)=q_n(1-q_n)\le q_n.

The cumulative difference \(N_n-Q_n\) is therefore a martingale. To control it when \(Q_n\) grows at an arbitrary rate, weight each increment by \(1+Q_n\). This denominator is known before assignment \(n\), because \(q_n\), and hence \(Q_n\), is determined by the pre-assignment history.

The total conditional variance of the weighted increments is bounded. Since \(Q_n-Q_{n-1}=q_n\le 1\), with \(Q_0=0\),

\sum_{n=1}^{\infty} E\left[ \left. \left(\frac{I_n-q_n}{1+Q_n}\right)^2 \right|\mathcal{F}_{n-1} \right] \le \sum_{n=1}^{\infty}\frac{q_n}{(1+Q_n)^2} \le \int_{0}^{\infty}\frac{dx}{(1+x)^2} =1.

For the second inequality, the integral over \([Q_{n-1},Q_n]\) is at least \(q_n/(1+Q_n)^2\), because the integrand is decreasing. Thus the weighted martingale series has finite total conditional variance and converges with probability one. Kronecker’s lemma then gives, on any path where \(Q_n\to\infty\),

\frac{N_n-Q_n}{1+Q_n}\longrightarrow 0, \qquad\text{so}\qquad \frac{N_n}{Q_n}\longrightarrow 1.

Consequently \(Q_n\to\infty\) implies \(N_n\to\infty\). If \(q_n\ge\varepsilon_n\) and the sum of the lower bounds diverges, then \(Q_n\ge\sum_{t=1}^{n}\varepsilon_t\to\infty\), proving the theorem. Applying this result to each of a finite number of arms and intersecting their probability-one events proves the simultaneous statement.

Worked Examples: What Different Lower Bounds Guarantee

Worked Example: A Fixed Exploration Floor

Suppose a hypothetical three-arm trial continues indefinitely and the assignment rule ensures \(q_{n,k}\ge 0.05\) for every arm \(k\) at every assignment. The bounds are feasible because \(3(0.05)=0.15\le 1\).

For each arm, the cumulative lower bound after \(n\) assignments is

\sum_{t=1}^{n}\varepsilon_{t,k}=0.05n\longrightarrow\infty.

The theorem therefore guarantees infinitely many assignments to each arm with probability one. In fact, \(Q_{n,k}\ge 0.05n\), and \(N_{n,k}/Q_{n,k}\to1\) almost surely. It follows that \(\liminf_{n\to\infty}N_{n,k}/n\ge0.05\) almost surely. This stronger frequency conclusion uses the fixed floor; a merely divergent lower-bound sum need not imply a positive limiting fraction.

Worked Example: A Diminishing Harmonic Floor

In a hypothetical two-arm trial, suppose arm 1 has conditional assignment probability \(q_{n,1}\ge0.4/n\). This is feasible alongside a lower bound \(q_{n,2}\ge0.4/n\), since their sum is at most \(0.8\) for \(n\ge1\).

The lower bound for arm 1 decreases to zero, but its cumulative total diverges:

\sum_{t=1}^{n}\frac{0.4}{t}=0.4H_n, \qquad H_n=\sum_{t=1}^{n}\frac{1}{t}\longrightarrow\infty.

For scale, \(H_{1000}\approx7.485\), so the cumulative lower bound by assignment 1000 is \(0.4(7.485)\approx2.994\). The theorem guarantees infinitely many assignments to arm 1, even though this schedule does not guarantee a positive long-run fraction for it.

There is also a finite-horizon implication. Repeatedly conditioning on the history gives \(P(\text{no assignment to arm 1 by time }n)\le\prod_{t=1}^{n}(1-0.4/t)\). Since \(1-x\le e^{-x}\), at \(n=1000\) this is at most \(e^{-2.994}\approx0.0501\). Thus the probability of at least one assignment to arm 1 by then is at least \(1-0.0501=0.9499\). This is a bound, not an exact probability.

Worked Example: A Summable Schedule Does Not Guarantee Infinite Sampling

Consider a hypothetical two-arm design with \(q_{n,1}=0.2/n^{1.2}\) and \(q_{n,2}=1-q_{n,1}\). These are valid conditional probabilities, but the arm 1 probabilities have a finite sum. Indeed, using an integral bound,

\sum_{n=1}^{\infty}q_{n,1} =0.2\sum_{n=1}^{\infty}n^{-1.2} \le 0.2\left(1+\int_{1}^{\infty}x^{-1.2}\,dx\right) =0.2(1+5)=1.2.

The expected total number of assignments to arm 1 is therefore at most 1.2: for every \(m\), \(E(N_{m,1})=\sum_{n=1}^{m}q_{n,1}\le1.2\). By monotone convergence, \(E(N_{\infty,1})\le1.2\), where \(N_{\infty,1}=\lim_{m\to\infty}N_{m,1}\). A nonnegative count that is infinite with positive probability has infinite expectation, so \(N_{\infty,1}<\infty\) with probability one. Here the arm is assigned only finitely often almost surely. The example shows why a lower bound must have a divergent sum to provide the stated guarantee.

Diagnostics, Alternatives, and Limitations

In an implemented design, calculate or record the conditional assignment probabilities from the actual randomization rule, then track their cumulative sums \(Q_{n,k}\) alongside the realized counts \(N_{n,k}\). The theorem is useful only if the probabilities used are the probabilities actually used to draw assignments. A coding error, deterministic rounding, or an unrecorded change to the rule can invalidate the claimed lower bound.

Check the sum, not just each term. A probability that is positive at every time may still have a finite cumulative sum. Positivity alone does not ensure infinite sampling.
Check predictability. A proposed lower bound must be determined from the history before the assignment. A bound chosen after seeing the assignment cannot justify the conditional-probability argument.
Check the time horizon. The result concerns a trial that continues through infinitely many assignment opportunities. A finite trial cannot literally assign infinitely many participants.
Check feasibility across arms. Simultaneous proposed floors cannot sum to more than one at any assignment time.

A fixed probability floor is simple to verify and can ensure a positive asymptotic sampling fraction, but it may constrain how strongly the design adapts. A diminishing floor such as \(c/n\) relaxes the per-assignment constraint over time and still guarantees infinite sampling, though it does not ensure a positive limiting fraction. Without a floor, a target-based adaptive rule may assign an arm a sequence of positive probabilities whose sum is finite; the theorem then offers no infinite-sampling guarantee. Target shares describe intended allocation proportions, whereas the result here concerns the conditional assignment probabilities that drive actual draws.

Common mistake: “The probability of assigning arm \(k\) is positive at every step, so arm \(k\) must be assigned infinitely often.” Positivity alone does not imply this. For example, \(q_{n,k}=0.2/n^{1.2}>0\) at every step but has a finite sum. The relevant condition is divergence of the cumulative conditional probabilities (or of a predictable lower bound on them).

Persistent exploration guarantees repeated access to every arm; it does not by itself establish that response estimates are accurate, that an allocation target is optimal, or that a trial has adequate power. Those conclusions require additional assumptions and analyses. Nor does infinite sampling mean that assignments occur at a regular rate: a divergent cumulative probability can grow very slowly.

Check Your Understanding

Answer each question, then compare with the solutions below.

In a four-arm trial, each arm has conditional assignment probability at least \(0.02\) at every step. What does the theorem guarantee?
For one arm, \(q_{n,k}\ge 1/(5n)\). Does this schedule guarantee infinitely many assignments? Explain.
Why is a strictly positive conditional assignment probability at every step insufficient on its own?
What must be true about a history-dependent lower bound before the assignment draw?

Solutions. (1) The floors are feasible because \(4(0.02)=0.08\le1\), and their sum for each arm is \(0.02n\to\infty\); every arm is assigned infinitely often almost surely. (2) Yes. Its cumulative lower bound is \((1/5)H_n\), which diverges, so the theorem applies. (3) Positive terms can have a finite sum, as \(0.2/n^{1.2}\) does; the theorem requires divergence, not just positivity. (4) The bound must be predictable, meaning it is determined by the pre-assignment history, and its cumulative sum must diverge with probability one.