Almost-Sure Rates for Adaptive Proportions

Why an Almost-Sure Rate Is More Than Convergence

Knowing that an allocation proportion approaches its target does not say how quickly it does so, or whether the claim holds along almost every realized trial. An almost-sure rate supplies both kinds of information: it bounds the size of the error as the trial grows, with probability one. For adaptive allocation, the error has two sources. Random assignment contributes cumulative martingale noise; the conditional assignment probabilities may also approach their target only gradually.

This tutorial studies rates for the proportion assigned to an arm. It does not require the allocation probabilities to be independent over time. Instead, the key assumptions concern their conditional means and the size of assignment increments. Those assumptions also make clear why a rate for conditional probabilities is not automatically a rate for realized proportions.

Martingale Noise in the Observed Allocation Proportion

Consider a two-arm trial. At assignment \(k\), let \(I_k=1\) if the participant is assigned to arm 1 and \(I_k=0\) otherwise. Let \(\mathcal{F}_{k-1}\) contain the trial information available before that assignment, and write \(p_k=P(I_k=1\mid\mathcal{F}_{k-1})\). The number assigned to arm 1 by time \(n\) is \(N_{1,n}=\sum_{k=1}^n I_k\), and the observed allocation proportion is \(N_{1,n}/n\).

The assignment error \(I_k-p_k\) has conditional mean zero and is bounded in absolute value by 1. Consequently, \(M_n=\sum_{k=1}^n(I_k-p_k)\) is a martingale with bounded increments. The proportion separates exactly into an average conditional allocation probability and a martingale term:

The first term is random assignment noise; the second is the accumulated deviation of the conditional probabilities from the target \(q\). Separating them prevents a common error: convergence of \(p_k\) to \(q\) alone does not give the rate of \(N_{1,n}/n\) without controlling both terms.

For justification, the Azuma–Hoeffding inequality gives \(P(|M_n|\ge t)\le 2\exp(-t^2/(2n))\). Choose \(t=\sqrt{2c n\log n}\) for a constant \(c>1\). Then the probability is at most \(2n^{-c}\), and these probabilities have finite sum. The Borel–Cantelli lemma implies that, with probability one, the selected bound is violated only finitely often. Dividing by \(n\) gives the stated rate. The logarithm is part of this convenient almost-sure bound; it should not be silently omitted when citing this argument.

From Conditional-Probability Drift to Proportion Rates

Suppose the conditional assignment probability approaches a fixed target at a polynomial rate: for some \(\gamma>0\), \(|p_k-q|\le C k^{-\gamma}\) eventually, almost surely, where \(C\) may be finite and random. Summing this inequality and dividing by \(n\) controls the drift term. For \(0<\gamma<1\), comparison with an integral gives a sum of order \(n^{1-\gamma}\); for \(\gamma=1\), the sum is of order \(\log n\); and for \(\gamma>1\), it is bounded. Combining the drift bound with the martingale result yields the following rates.

In particular, if the conditional probabilities approach the target more slowly than the martingale term, their drift can determine the overall rate. If they approach it sufficiently quickly, the martingale bound determines the displayed rate. These are upper bounds under the stated assumptions, not claims that every allocation procedure attains a matching lower bound.

Stochastic Approximation and Stability-Determined Rates

Conditional allocation probabilities often depend on an evolving estimate or state. A useful local model for the error \(e_n\) from a stable target is the scalar stochastic-approximation recursion \(e_n=(1-a/n)e_{n-1}+\xi_n/n\), where \(a>0\) is a stability coefficient and \(\xi_n\) is a bounded martingale difference: \(E(\xi_n\mid\mathcal{F}_{n-1})=0\), with \(|\xi_n|\le B\). Take \(n\) sufficiently large that \(0<1-a/n<1\). These assumptions describe a local linear contraction plus mean-zero noise; they do not automatically hold for every adaptive rule.

The contraction repeatedly shrinks the initial error, while the noise is accumulated with weights that depend on \(a\). Iterating the recursion gives a product multiplying the initial value and weighted martingale increments. The product from indices \(j+1\) to \(n\) is of order \((j/n)^a\), since summing the logarithms of \(1-a/\ell\) gives \(-a\log(n/j)\) up to bounded terms. Thus an increment \(\xi_j/j\) has weight of order \(n^{-a}j^{a-1}\). The squared weights sum at order \(n^{-2a}\sum_{j\le n}j^{2a-2}\). This sum is bounded in order by \(n^{-2a}\) for \(a<1/2\), by \(n^{-1}\log n\) for \(a=1/2\), and by \(n^{-1}\) for \(a>1/2\).

The threshold at \(a=1/2\) arises from whether the squared weights are summable at their lower endpoint, not from a change in the allocation rule’s target. A related recursion with a predictable forcing term \(r_n/n\), where \(|r_n|=O_{\mathrm{a.s.}}(n^{-b})\), has a forcing contribution of order \(n^{-\min(a,b)}\), with an additional \(\log n\) factor when \(a=b\). This follows by summing the weighted forcing terms \(n^{-a}j^{a-1}r_j\); the other contributions, including martingale noise, must still be included when stating the overall rate.

Assumptions, Diagnostics, and Alternatives

Rate arguments are only as sound as their assumptions. In a trial analysis, check that assignment increments really are bounded and centered after conditioning on the history, and that the conditional-probability drift bound applies along the adaptive process. For a stochastic-approximation argument, also check that the target is a stable equilibrium and that the recursion’s local contraction and noise conditions hold in the region being studied. A drift bound asserted only in expectation is not the same as an almost-sure bound.

Several warning signs call for a different argument. If assignments can have unbounded increments, the Azuma–Hoeffding step above is unavailable without an appropriate replacement moment or tail condition. If conditional allocation probabilities fail to approach a fixed target, the drift average need not vanish. If stability is absent or the recursion has multiple possible limiting states, a single scalar contraction rate is not justified. In practice, plots of cumulative proportions and conditional allocation probabilities can reveal persistent drift, abrupt changes, or instability; such plots are diagnostics, not proofs of an almost-sure rate.

The main alternative is to report convergence without a quantitative rate, which requires weaker information but answers a less detailed question. A central limit approximation addresses distributional fluctuations on a different scale and requires its own assumptions; an almost-sure upper bound is not a confidence interval or a sampling distribution. Compared with a direct drift bound, stochastic approximation explains how feedback and local stability can generate polynomial rates, but it relies on a more specific recursion. Neither method proves a sharp rate unless matching lower-bound arguments are also supplied.