Randomized Bandit Policies and Assignment Probabilities

Why Assignment Probabilities Matter

A bandit policy uses information accumulated during a trial to decide how to assign the next participant. Saying that it “favors the treatment with the better estimated response” is not a complete description: it does not specify how much more likely that treatment is to be assigned, or whether another treatment can still be selected. A precise description gives the probability of assigning each treatment at each point in the trial, conditional on the information available before that assignment.

These conditional probabilities separate the policy’s rule from the particular random assignments it happens to generate. Two trials can use the same rule and the same observed history up to a decision, yet assign different treatments because their random draws differ. Conversely, if a policy is deterministic at that history, its assignment probability for the selected treatment is one and is zero for the others.

Formal Representation

Suppose there are \(K\) treatments, indexed by \(k=1,\ldots,K\). At trial step \(t\), let \(A_t\) denote the treatment assigned. Write \(\mathcal H_{t-1}\) for the information available immediately before this assignment. It can include earlier assignments and observed outcomes, the current participant’s measured characteristics if they are available before assignment, and any internal state the policy uses. It must not include the current participant’s outcome, which has not yet been observed.

The vector \((\pi_{t,1}(h),\ldots,\pi_{t,K}(h))\) is the treatment-selection distribution at that decision. It is conditional: it describes selection given the stated history, not the overall proportion of all participants who will receive each treatment. The vector can change as the history changes, even when the policy’s rule stays fixed.

The policy specifies a distribution, not an assignment outcome. A convenient implementation draws \(U_t\) uniformly from \([0,1)\), partitions that interval into consecutive segments whose lengths are the treatment probabilities, and assigns the treatment whose segment contains \(U_t\). For example, with two treatments and probabilities \(0.7\) and \(0.3\), treatment 1 is assigned if \(U_t<0.7\), and treatment 2 otherwise. Other random-number implementations are possible, but the resulting conditional probabilities must agree with the stated policy.

How Probabilities Govern a Sequence of Assignments

At each step, the probability vector applies to the history that has actually been observed by that point. Thus, an assignment changes the history, and an observed outcome may change it again. The next probability vector is then evaluated at the updated history. The probability of an assignment sequence, conditional on the sequence of histories along which it is generated, is obtained by multiplying its successive conditional assignment probabilities.

The product rule is the chain rule applied sequentially. At step \(t\), the conditional probability of assigning \(a_t\) is \(\pi_{t,a_t}(h_{t-1})\). Multiplying these terms gives the probability of the sequence when each term is conditioned on its corresponding prior history. If an event is defined only by the assignments and not by the outcomes that formed those histories, the outcomes may also need to be accounted for; the product alone should not be misread as an unconditional probability that ignores them.

Randomized Policies, Deterministic Rules, and Zero Probabilities

A randomized policy can assign positive probability to several treatments at the same history. A deterministic policy is a special case: it assigns probability one to one treatment and zero to every other treatment. A policy can also be randomized at some histories and deterministic at others. If a treatment has probability zero at a history, it cannot be assigned at that decision under the specified policy.

A zero probability can arise intentionally, for example after a policy removes a treatment from consideration, or inadvertently because of a coding or configuration error. The probability vector alone does not establish whether that choice is scientifically or ethically appropriate; it records what the policy permits at that history. Likewise, positive probabilities do not mean that every treatment will be selected in a small trial.

An exploration mixture illustrates how one can combine a preferred allocation distribution with a minimum chance of exploring all treatments. If \(q_{t,k}(h)\) is a probability vector and \(0<\varepsilon\leq 1\), a mixture with uniform exploration is \(\pi_{t,k}(h)=(1-\varepsilon)q_{t,k}(h)+\varepsilon/K\). Since both component vectors sum to one, the mixture also sums to one. Each treatment has probability at least \(\varepsilon/K\).

Conditions for a Clear Policy Description

To interpret assignment probabilities correctly, specify what information is available when the assignment is made and how the policy uses it. The essential conditions are operational rather than restrictive assumptions about a particular reward distribution:

• Pre-assignment timing. The history includes only information available before \(A_t\) is selected. A current outcome cannot determine the assignment that preceded its observation.
• Well-defined treatment labels. The \(K\) treatment options are mutually exclusive choices for the assignment being described, and the policy’s probabilities refer to those same options.
• A valid probability distribution. At every reachable history, all entries lie between zero and one and sum to one. If a procedure produces unnormalized weights, an additional normalization rule is needed before they are assignment probabilities.
• Specified randomization. Given the history, the randomization mechanism implements the stated probabilities. If implementation also depends on a random state or constraint, that information must be represented in the history or incorporated into the stated assignment rule.

No assumption that treatment rewards follow a particular distribution is needed merely to define \(\pi_{t,k}(h)\). A reward model becomes relevant when the policy calculates its probabilities from estimated rewards, but the final assignment vector still has to be defined at each history. The earlier material on softmax exploration for treatment allocation gives one example of a rule for producing such a vector; the general representation here applies beyond that particular rule.

Diagnostics and Common Failure Modes

A practical audit starts with the probability vector actually used at each decision, not merely the policy name in a protocol. Check that probabilities are recorded with the pre-assignment history or a reproducible summary of it, that the values are between zero and one, and that their sum is one up to a stated numerical tolerance. Check that the realized assignment was one of the treatments with positive probability and that the randomization software used the same vector that was recorded.

Across many assignments made under the same probability vector and comparable conditions, the observed fraction assigned to treatment \(k\) will tend to be near \(\pi_{t,k}(h)\), but need not equal it. With a small number of assignments, noticeable differences are unsurprising. This check is therefore a diagnostic for gross discrepancies, not a requirement that every finite allocation match its target fraction. In an adaptive trial, pooling assignments from different histories can conceal a problem: the conditional probabilities may have changed over time.

• Confusing probability with a realized fraction. A 70% conditional assignment probability does not promise exactly 70 assignments out of each 100 decisions.
• Reporting only a policy label. “Softmax” or “greedy” alone does not give the probability vector used at a particular history; inputs and tuning choices can affect it.
• Using information from after assignment. Including a current outcome in \(\mathcal H_{t-1}\) reverses the timing of the decision and makes the conditional probability description invalid.
• Ignoring zero-probability options. A treatment with probability zero is not merely unlikely; it is excluded at that history under the stated rule.

How This Representation Differs From Other Allocation Descriptions

These are distinct ways to describe allocation, not necessarily mutually exclusive policy families. For example, a policy may use a fixed probability vector at every history, while a sequential bandit policy may update its vector as observations accrue. The conditional representation is useful in either case because it makes the probability governing each treatment selection explicit.

Why the Conditional Probabilities Matter

The conditional probabilities are the operational link between a policy’s rule and the assignments it generates. They make it possible to state precisely what “favoring” a treatment means at a given history, to reproduce the randomization decision, and to detect whether an implementation follows its specification. They also clarify what the policy does not guarantee: a high probability is not a promise of assignment, and a sequence of randomized decisions need not match its expected allocation exactly.

A common mistake is to say, “Treatment 1 has probability 0.7, so seven of the next ten participants will receive it.” The correction is that \(0.7\) is the conditional probability at a particular decision if the stated history holds. Subsequent histories may change the probabilities, and even if the vector remains fixed, the realized count is random rather than fixed in advance.