Step-Size Regimes and Convergence Rates

Why the Step-Size Exponent Matters

An adaptive allocation updates its assignment probabilities as evidence accumulates. If updates remain large, new response noise can move the allocation noticeably even late in the trial. If updates shrink too quickly, the allocation can retain the influence of its early path and respond slowly to new information. A step-size schedule controls this balance. Its exponent affects both how quickly the allocation forgets its past and the scale of its remaining random fluctuations.

The focus here is the local behavior near an allocation target. The earlier material on linearization near an allocation target motivates representing the error by a stable linear drift plus random noise. The purpose of this tutorial is to compare what happens when the step size is proportional to \(n^{-\gamma}\), especially when \(0<\gamma<1\) versus \(\gamma=1\).

Local Recursion and Assumptions

The rate comparisons below rely on assumptions that make this local approximation informative. The target is fixed and interior; the recursion remains in a neighborhood where the linearization is valid; and the eigenvalues of \(A\) have positive real parts, so the drift \(-Ae\) pulls small errors back toward zero. The noise has conditional mean zero given the trial history before assignment \(n\), and its conditional covariance approaches a finite matrix \(\Sigma\). For the stated variance calculations, its second moments are bounded. The remainder \(\rho_n\) must be small enough near the target not to change the leading rate.

To see the essential rate, consider one stable scalar direction, with local drift coefficient \(\lambda>0\), gain \(a\), and noise variance \(\sigma^2\). Ignoring a negligible remainder gives \(e_n=(1-a\lambda n^{-\gamma})e_{n-1}+a n^{-\gamma}\xi_n\). Write \(c=a\lambda\). The stability condition is not simply “choose a small exponent”: the gain and local drift together determine how strongly this direction is pulled toward its target.

Step Sizes with \(0<\gamma<1\)

For \(0<\gamma<1\), the accumulated contraction through time \(n\) grows on the order of \(n^{1-\gamma}\). In particular, the product of the one-step retention factors is approximately \(\exp\{-c\sum_{j=1}^n j^{-\gamma}\}\), which decays roughly as \(\exp\{-c n^{1-\gamma}/(1-\gamma)\}\). Thus the effect of a fixed initial error is reduced faster than any fixed power of \(n^{-1}\), under the scalar stable approximation.

The random error is not eliminated at that speed because recent noise continues to enter. A useful variance calculation balances the contraction of the previous variance against the new noise variance. If \(V_n=\operatorname{Var}(e_n)\), then, to leading order, \(V_n\) behaves like \((1-2c n^{-\gamma})V_{n-1}+a^2\sigma^2 n^{-2\gamma}\). At equilibrium on this slowly changing scale, the variance removed is approximately \(2c n^{-\gamma}V_n\). Equating this to the new variance gives \(2c n^{-\gamma}V_n\approx a^2\sigma^2 n^{-2\gamma}\), and hence \(V_n\approx \frac{a^2\sigma^2}{2c}n^{-\gamma}=\frac{a\sigma^2}{2\lambda}n^{-\gamma}\).

Consequently, the typical fluctuation scale is \(n^{-\gamma/2}\), subject to the stated local and moment conditions. This is a statement about scale; it does not by itself assert a particular limiting distribution. In a vector recursion, the corresponding rates are determined direction by direction by the local stability and noise in those directions.

The Boundary Case \(\gamma=1\)

With a step size \(a/n\), the scalar recursion becomes \(e_n=(1-c/n)e_{n-1}+a\xi_n/n\). Its contraction accumulates only at a logarithmic rate: the initial-error multiplier is of order \(n^{-c}\). Unlike the \(0<\gamma<1\) case, the initial error and the ongoing noise can therefore have the same polynomial order. The value of \(c=a\lambda\) determines which contribution sets the leading scale.

For clarity, suppose the noise terms are uncorrelated across time, have mean zero, and have variance \(\sigma^2\). The variance recursion is \(V_n=(1-c/n)^2V_{n-1}+a^2\sigma^2/n^2\). If \(V_n\) is of order \(n^{-1}\), then replacing \(V_{n-1}\) by its leading approximation gives a variance decrease of about \(2cV_{n-1}/n\); the new noise contributes about \(a^2\sigma^2/n^2\). Matching these terms yields \(V_n\approx a^2\sigma^2\{(2c-1)n\}^{-1}\), which is positive only when \(c>1/2\). At the boundary \(c=1/2\), contributions accumulate across scales and produce a logarithmic factor. Below that boundary, the initial condition and early noise remain influential at the leading order.

How to Compare the Regimes

For \(0<\gamma<1\), the effective window of recent observations is roughly of order \(n^\gamma\): updates older than that window have been substantially damped, while noise within it still contributes to the current error. A larger \(\gamma\) in this range shrinks the step size more quickly and gives a smaller asymptotic noise scale, but it also makes the procedure less responsive to changes in the target. At \(\gamma=1\), increasing the gain may improve contraction relative to noise, but an excessively aggressive gain can undermine stability of the discrete recursion.

Assumptions, Diagnostics, and Limitations

The familiar general stochastic-approximation conditions often use \(1/2<\gamma\leq 1\): the step sizes then decrease to zero while their squares have a finite sum. This is a useful sufficient framework for controlling accumulated martingale noise, not a claim that convergence is impossible for \(\gamma\leq 1/2\). Special linear models can still converge outside that framework, but the general guarantee needs additional justification. If \(\gamma>1\), the sum of step sizes is finite, so the total corrective movement can be insufficient to reach the target. These broad observations do not replace checking the drift, noise, and remainder assumptions for a particular allocation rule.

Diagnostics should focus on whether the observed allocation path is consistent with the local model and intended rate. Examine whether the target is approximately stable, whether allocation errors decrease rather than persist or grow, and whether late-stage updates remain unusually large. In simulation, compare errors across repeated runs at increasing \(n\): slopes on a log-error versus log-\(n\) plot can suggest a power-law scale, but finite samples, transient behavior, and a small noise level can obscure the asymptotic rate. Also check whether the allocation stays near the target and whether the direction-specific drift appears restoring. If the allocation is often far from the target, the local rate calculation may not apply.

These comparisons are local asymptotic descriptions, not a guarantee about every adaptive design. A moving target, boundary target, unstable direction, heavy-tailed or poorly controlled noise, or non-negligible nonlinear remainder can change the behavior. The variance calculations also do not establish a Gaussian limit; a distributional limit requires further conditions and results. In particular, do not infer a limiting distribution solely from a calculated variance scale.

Common Pitfall