Stochastic Approximation Form of Allocation Recursions

From Allocation Counts to a Stochastic Recursion

An adaptive allocation rule is often described by the probability it assigns to each treatment at the next participant. But asymptotic arguments concern the evolving allocation proportions, which are random because assignments are random. Stochastic approximation gives a useful way to represent that evolution: each update is a step of a specified size, with a systematic conditional drift and a centered random fluctuation.

Begin with a two-arm trial. Let $I_{n+1}=1$ if participant $n+1$ is assigned to arm 1 and $I_{n+1}=0$ otherwise. Let $K_n=\sum_{j=1}^{n} I_j$ be the number assigned to arm 1 after $n$ assignments, and let $q_n=K_n/n$ for $n\geq 1$ be the observed allocation proportion to arm 1. Let $\mathcal{F}_n$ denote the information available just before assignment $n+1$. The adaptive design specifies the conditional probability $\pi_{n+1}=P(I_{n+1}=1\mid\mathcal{F}_n)$.

The probability $\pi_{n+1}$ is a design quantity known from the trial history just before the draw; $q_n$ is a realized fraction from assignments already made. They are not interchangeable. The assignment indicator has conditional mean $\pi_{n+1}$, so its centered version $I_{n+1}-\pi_{n+1}$ has conditional mean zero given $\mathcal{F}_n$.

Definition: For the two-arm empirical allocation proportion, the stochastic-approximation decomposition is $$ q_{n+1}=q_n+\gamma_{n+1}\{h_{n+1}+M_{n+1}\},\qquad \gamma_{n+1}=\frac{1}{n+1},\quad h_{n+1}=\pi_{n+1}-q_n,\quad M_{n+1}=I_{n+1}-\pi_{n+1}. $$ Here $\gamma_{n+1}$ is the step size, $h_{n+1}$ is the conditional drift before the step is applied, and $M_{n+1}$ is the martingale-difference noise.

Why the Decomposition Is Exact

This representation follows directly from the count update. After the next assignment, $K_{n+1}=K_n+I_{n+1}$. Since $K_n=nq_n$,

q_{n+1} =\frac{K_n+I_{n+1}}{n+1} =\frac{nq_n+I_{n+1}}{n+1} =q_n+\frac{I_{n+1}-q_n}{n+1}.

Add and subtract the predictable assignment probability $\pi_{n+1}$ inside the numerator. This gives $I_{n+1}-q_n=(\pi_{n+1}-q_n)+(I_{n+1}-\pi_{n+1})$, which yields the stated decomposition. Thus the separation is an algebraic identity, not an approximation. Its stochastic content comes from the fact that the second term is centered conditionally:

E(M_{n+1}\mid\mathcal{F}_n) =E(I_{n+1}\mid\mathcal{F}_n)-\pi_{n+1} =0.

Because $I_{n+1}$ is Bernoulli conditionally on $\mathcal{F}_n$, $M_{n+1}$ is bounded between $-1$ and $1$, and $E(M_{n+1}^2\mid\mathcal{F}_n)=\pi_{n+1}(1-\pi_{n+1})$. These facts describe the one-step noise. They do not, by themselves, establish that $q_n$ converges or identify its limit.

Worked Example: Checking a Realized Fraction and One Update

Suppose a hypothetical trial has made $n=10$ assignments, with $K_{10}=4$ on arm 1. Thus $q_{10}=4/10=0.4$. The design assigns the next participant to arm 1 with conditional probability $\pi_{11}=0.7$. Work out the recursion if the next assignment is to arm 1.

The step size is $\gamma_{11}=1/11$, the drift is $h_{11}=0.7-0.4=0.3$, and, for an arm 1 assignment, the noise is $M_{11}=1-0.7=0.3$. Therefore

q_{11}=0.4+\frac{1}{11}(0.3+0.3) =\frac{5}{11}\approx 0.4545.

The count check agrees: the new count is $5$ out of $11$. If instead the assignment were to arm 2, then $M_{11}=0-0.7=-0.7$, so $q_{11}=0.4+(0.3-0.7)/11=4/11\approx0.3636$, matching the unchanged arm 1 count.

The fraction $q_9=0.4$ would not be possible as an empirical allocation proportion after 9 assignments: it would require $K_9=9(0.4)=3.6$ assignments. Always check that an asserted realized fraction corresponds to an integer count.

Drift Under a Target-Based Allocation Rule

The drift records how the design’s next assignment probability differs from the current realized proportion. If an allocation rule uses only $q_n$ and can be written as $\pi_{n+1}=g(q_n)$, then the drift is the function $h(q_n)=g(q_n)-q_n$. If it also depends on response estimates or other trial information, the drift generally depends on those quantities too. It may then be more accurate to write $h_{n+1}$ than to suggest that it is a function of $q_n$ alone.

For example, suppose a hypothetical design uses a fixed target proportion $t=0.6$ and sets its next assignment probability to $\pi_{n+1}=(1-\lambda)q_n+\lambda t$, where $\lambda=0.5$. This rule is a convex combination of values in $[0,1]$, so it produces a valid probability. It yields the drift $h_{n+1}=\lambda(t-q_n)$. This example illustrates how a target-based rule can be expressed as a drift without claiming that the random allocation proportion equals the target.

Worked Example: A Proportion Pulled Toward a Fixed Target

Suppose, hypothetically, $n=10$, $q_{10}=0.4$, and the design uses $t=0.6$ and $\lambda=0.5$. Calculate the conditional assignment probability, the drift and the two possible updates.

The rule gives $\pi_{11}=(1-0.5)(0.4)+0.5(0.6)=0.5$, so $h_{11}=\pi_{11}-q_{10}=0.1$. If $I_{11}=1$, then $M_{11}=1-0.5=0.5$, and $q_{11}=0.4+(0.1+0.5)/11=5/11\approx0.4545$. If $I_{11}=0$, then $M_{11}=-0.5$, and $q_{11}=0.4+(0.1-0.5)/11=4/11\approx0.3636$.

Before the random assignment is observed, the conditional mean of the next proportion is $E(q_{11}\mid\mathcal{F}_{10})=q_{10}+h_{11}/11=0.4+0.1/11\approx0.4091$. The drift determines this conditional expected change; the actual change also includes the realized assignment noise.

Response-Adaptive Rules and Predictable Drift

In a response-adaptive design, the assignment probability can depend on estimated treatment performance as well as on past allocation. Let $\widehat{t}_n$ be a response-based target estimate available before assignment $n+1$. If the rule sets $\pi_{n+1}=(1-\lambda)q_n+\lambda\widehat{t}_n$, with $0\leq\lambda\leq1$ and $\widehat{t}_n\in[0,1]$, then $\pi_{n+1}$ is a valid, $\mathcal{F}_n$-measurable probability. The drift is $h_{n+1}=\lambda(\widehat{t}_n-q_n)$. The response estimate makes the drift adaptive: it changes as the available trial information changes. The martingale-noise term remains the centered assignment indicator, provided $\pi_{n+1}$ is the actual conditional probability used by the randomization procedure.

Worked Example: A Response-Estimated Target

Consider a hypothetical trial with $n=10$, $K_{10}=4$, and thus $q_{10}=0.4$. Suppose the response-based target estimate available at that time is $\widehat{t}_{10}=0.7$, and the design uses $\lambda=0.4$ in the rule above. Calculate the update if the next participant is assigned to arm 2.

The conditional probability is $\pi_{11}=0.6(0.4)+0.4(0.7)=0.52$. The drift is $h_{11}=0.52-0.4=0.12$. For an arm 2 assignment, $I_{11}=0$, so $M_{11}=0-0.52=-0.52$. Hence

q_{11}=0.4+\frac{1}{11}(0.12-0.52) =0.4-\frac{0.4}{11} =\frac{4}{11}\approx0.3636.

The result matches the count: the arm 1 count remains $4$ among $11$ participants. The response estimate affects the probability and therefore the drift, but it does not change the observed count unless the assignment indicator is $1$.

Reading and Checking the Terms

The decomposition is useful only when its terms are interpreted from the actual design. Before using it, verify that the probability is conditional on the information available before the assignment, and that the allocation proportion is defined from the realized count. The following checks help locate common errors.

Check the time index. The probability $\pi_{n+1}$ governs assignment $n+1$, while $q_n$ summarizes the first $n$ assignments. Using a probability calculated after observing $I_{n+1}$ would not give the stated conditional-mean decomposition.
Check the step size. For an empirical proportion after $n$ assignments, the exact next step size is $1/(n+1)$, not $1/n$. A different step size may arise for a different recursively updated quantity, but it should be derived from that quantity’s update.
Check the probability against the implementation. The centered term $I_{n+1}-\pi_{n+1}$ has conditional mean zero only when $\pi_{n+1}$ is the probability actually used. Replacing a clipped or otherwise modified implementation probability with an unmodified target map can create a nonzero conditional residual.
Check whether the state is complete. If the probability depends on response estimates, covariates or allocation constraints, $h_{n+1}$ need not be a function of $q_n$ alone. Omitting those inputs can make a claimed drift formula incorrect.
Check feasible counts. For an empirical proportion, $nq_n$ must be an integer between 0 and $n$. A proposed value that fails this check cannot describe the observed allocation fraction.

Common mistake: “The design’s assignment probability is $0.7$, so the observed fraction after the next assignment must be $0.7$.” This confuses a conditional probability with a realized proportion. The probability determines the conditional distribution of the next indicator; the observed fraction changes according to the indicator that is actually drawn.

What This Formulation Does—and Does Not—Say

The exact stochastic recursion is preferable when the realized path matters: it retains both the systematic conditional change and the random assignment fluctuation. Taking the conditional expectation gives $E(q_{n+1}-q_n\mid\mathcal{F}_n)=h_{n+1}/(n+1)$, which is useful for describing the average one-step change but is not itself the realized recursion. Dropping $M_{n+1}$ and treating that conditional-mean equation as if it described every trial path loses assignment variability.

The stochastic-approximation form also makes explicit that the empirical fraction’s step size shrinks as the number of assignments grows. It is a bookkeeping and analysis framework, not a convergence theorem. To establish a limiting allocation proportion requires additional conditions on the allocation rule, the evolving response estimates and the accumulated noise. Whether such a limit exists, and how to analyze it through a differential equation, are separate questions.

The representation has limits as well. It applies here to the two-arm empirical proportion and a Bernoulli assignment indicator. With more arms, one can write a vector of assignment indicators and proportions, but the components are dependent because exactly one arm is assigned at each step. Constraints, delayed responses or other state variables may also require an expanded description. The essential procedure remains: derive the exact update for the quantity of interest, condition on the pre-assignment information, and center the random increment using its true conditional mean.

Write the realized update.
For the arm 1 proportion, use $q_{n+1}=(nq_n+I_{n+1})/(n+1)$.

Identify the conditional probability.
State $\pi_{n+1}=P(I_{n+1}=1\mid\mathcal{F}_n)$ using only information available before the next draw.

Separate drift and noise.
Set $h_{n+1}=\pi_{n+1}-q_n$ and $M_{n+1}=I_{n+1}-\pi_{n+1}$, then verify their sum reproduces the exact increment.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions below.

If $n=12$, $K_n=5$, and the next assignment probability is $0.4$, what are $q_n$, $h_{n+1}$, and the step size?
In that setting, calculate $q_{n+1}$ if the next assignment is to arm 1. Check the result using the count.
Why is $q_9=0.4$ not a possible empirical allocation proportion after 9 assignments?
Suppose a rule uses $\pi_{n+1}=(1-\lambda)q_n+\lambda t$, where $q_n,t\in[0,1]$ and $0\leq\lambda\leq1$. State its drift and explain why its probability is valid.

Solutions. (1) $q_n=5/12\approx0.4167$, $h_{n+1}=0.4-5/12=-1/60\approx-0.01667$, and the step size is $1/13$. (2) If $I_{n+1}=1$, then $M_{n+1}=1-0.4=0.6$, so $q_{n+1}=5/12+(1/13)(-1/60+0.6)=6/13\approx0.4615$. The count check gives $6$ arm 1 assignments among $13$. (3) It would require $K_9=9(0.4)=3.6$, which is not an integer count. (4) The drift is $h_{n+1}=\lambda(t-q_n)$. The probability is a convex combination of two numbers in $[0,1]$, so it also lies in $[0,1]$.