Horizon-Aware Exploration

Why the Remaining Horizon Matters

In a bandit trial, assigning a participant to an arm has two consequences: it produces an outcome for that participant, and it may provide information that improves later assignments. The second consequence depends on how many later assignments remain. If enrollment has a known endpoint, an observation collected near the end has little or no opportunity to change treatment choices for future participants.

This is a decision objective, not just a change in how uncertainty is displayed. A rule that explores too much near completion can sacrifice reward for information that arrives too late to be useful. Conversely, eliminating exploration too early can leave enough of the trial to benefit from learning. The key quantity is the number of assignments still available after the current one.

Definition: Let \(T\) be a fixed total number of sequential assignments, and let \(t\) denote the current assignment, with \(1\le t\le T\). The remaining horizon including the current assignment is \(h=T-t+1\); the number of assignments after the current one is \(h-1\). A horizon-aware policy uses this remaining opportunity when deciding how much to value information from the current assignment.

Model and Finite-Horizon Decision Rule

Consider \(K\) treatment arms. For this tutorial, assume each assignment produces an observed reward in \([0,1]\), the reward distribution for each arm is stable over enrollment, and one participant's assignment and outcome do not alter another participant's reward distribution. Assume also that the total number of assignments \(T\) is known, outcomes are available before the next decision, and there are no additional safety or allocation constraints. These assumptions make the basic learning-versus-reward tradeoff clear; real trials may require modifications.

Let \(s\) denote the information available at a decision, including assignments and observed outcomes or, in a Bayesian formulation, the current posterior distributions for the arm rewards. Write \(\mu_i(s)\) for the predictive mean reward from assigning to arm \(i\) given \(s\). The finite-horizon objective is to maximize expected total reward over the remaining assignments. Define \(V_h(s)\) as the greatest expected total reward obtainable with \(h\) assignments left.

V_h(s)=\max_{i\in\{1,\ldots,K\}}\left\{\mu_i(s)+ \mathbb{E}\left[V_{h-1}(s')\mid s,\text{ assign to }i\right]\right\}, \qquad h\ge 2,

Here \(s'\) is the updated information after the current participant's reward is observed. At the final assignment, there is no later information value, so the recursion ends with

V_1(s)=\max_{i\in\{1,\ldots,K\}}\mu_i(s).

This terminal rule follows directly: with only one assignment left, choosing an arm affects the current expected reward but cannot affect a subsequent decision. Thus the arm with the largest predictive mean is optimal for the stated cumulative-reward objective. This does not say that uncertainty is irrelevant earlier; it says its value comes from the future decisions it can improve.

From the Decision Rule to a Simple Adjustment

The Bellman recursion is exact but can be difficult to solve for many arms, outcomes, and remaining assignments. A practical approximation is to use an optimistic score: an estimated mean plus an uncertainty bonus. An uncertainty bonus gives extra weight to arms whose means are less precisely estimated, encouraging information gathering. To reflect the known horizon, we can multiply that bonus by a factor that decreases to zero at the final assignment.

Horizon-scaled UCB-style rule: Suppose \(T>1\), and each arm has at least one observed reward. Let \(\hat{\mu}_i\) be the observed mean reward for arm \(i\), and \(n_i\) its number of observed outcomes. One simple index is \(I_i(h)=\hat{\mu}_i+g(h)\sqrt{2\log(T)/n_i}\), where \(g(h)=(h-1)/(T-1)\). Choose an arm with the largest index. At \(h=1\), the multiplier is zero and the rule chooses the largest observed mean. This is a heuristic horizon adjustment, not a claim that the index is an exactly optimal policy or a calibrated confidence bound.

The multiplier is a transparent interpolation: it is 1 at the start of a \(T\)-assignment horizon and 0 at the final assignment. It scales an optimism bonus that would otherwise remain positive even when no future decision can use the information. Other schedules are possible; the specific linear taper is chosen for simplicity, not because the Bellman equation implies linear decay. The optimal exploration value generally depends on the reward model, posterior uncertainty, gaps between arms, and the number of future decisions.

The expression \(\sqrt{2\log(T)/n_i}\) is an illustrative UCB-style bonus. It is not itself a probability that the arm is best, and its value can exceed 1 even when rewards lie in \([0,1]\). The index is a ranking device, not a predicted reward. If an arm has no observations, its displayed index is undefined; a policy must specify an initialization or another principled way to handle untried arms. If \(T=1\), the multiplier formula is undefined because \(T-1=0\), but no adjustment is needed: use the largest predictive mean directly.

Worked Example: The Last Assignment

Suppose a hypothetical two-arm trial has one assignment remaining. The posterior predictive reward for arm A is Beta with parameters 8 and 4, and for arm B it is Beta with parameters 5 and 4. Under a Beta-Bernoulli model, a Beta distribution with parameters \(a,b\) has predictive mean \(a/(a+b)\). Which arm maximizes expected reward for this participant?

For arm A, the predictive mean is \(8/(8+4)=8/12=0.6667\). For arm B, it is \(5/(5+4)=5/9=0.5556\). Since \(h=1\), there is no later assignment for which new information could improve a decision. The terminal rule therefore selects arm A, whose expected reward is higher by \(0.6667-0.5556=0.1111\) on the reward scale.

The Beta-Bernoulli assumption is used here to calculate predictive means; the terminal comparison itself only requires that the predictive means are well defined. This decision is about maximizing expected reward for the remaining assignment, not a statement that arm A is certainly better.

Calculating a Tapered Index

The next example uses empirical means and the stated horizon-scaled index. Rewards are hypothetical and bounded between 0 and 1. The index is used only to demonstrate the calculation and its horizon effect.

Worked Example: Comparing Arms Near Completion

A hypothetical trial has \(T=20\) assignments. At the current decision, \(h=5\) assignments remain, including this one. Arm A has \(n_A=16\) observed rewards with mean \(\hat{\mu}_A=0.625\); arm B has \(n_B=6\) with mean \(\hat{\mu}_B=0.600\). Calculate both indices and choose an arm.

First, the horizon multiplier is \(g(5)=(5-1)/(20-1)=4/19\approx0.2105\). The common logarithmic term is \(2\log(20)\approx5.9915\). For arm A, the unscaled bonus is \(\sqrt{5.9915/16}\approx0.6119\), so its scaled bonus is \((4/19)\sqrt{5.9915/16}\approx0.1288\). Thus \(I_A=0.625+0.1288\approx0.7538\).

For arm B, the unscaled bonus is \(\sqrt{5.9915/6}\approx0.9993\), and the scaled bonus is \((4/19)\sqrt{5.9915/6}\approx0.2104\). Thus \(I_B=0.600+0.2104\approx0.8104\). The rule selects arm B because \(0.8104>0.7538\), even though its observed mean is lower. Its smaller sample count gives it a larger uncertainty bonus, which remains relevant with four future assignments after the current one.

At the final assignment, the same estimates would give indices \(0.625\) and \(0.600\), since \(g(1)=0\); the rule would then select arm A. This is the intended horizon effect, not evidence that either arm's underlying mean has changed.

Worked Example: A Near-Term Switch in the Preferred Arm

Consider another hypothetical state in a \(T=20\) trial with five assignments left. Arm A has \(n_A=12\) observed rewards and mean \(0.620\); arm B has \(n_B=3\) observed rewards and mean \(0.580\). Use the same index and determine whether exploration can overcome the observed mean difference.

As above, \(g(5)=4/19\approx0.2105\) and \(2\log(20)\approx5.9915\). The arm-specific unscaled bonuses are \(\sqrt{5.9915/12}\approx0.7066\) for A and \(\sqrt{5.9915/3}\approx1.4132\) for B. After scaling, the bonuses are approximately \(0.1488\) and \(0.2975\), respectively. Therefore, \(I_A\approx0.620+0.1488=0.7688\), while \(I_B\approx0.580+0.2975=0.8775\). The index selects B at this decision.

With only one assignment left, the bonuses vanish and A is selected because \(0.620>0.580\). The calculation illustrates why a horizon-aware policy need not always choose the currently higher-mean arm, while also showing why its exploration preference can disappear at the endpoint. As in the preceding example, the index is an approximation rather than a proof of optimality.

Justification and Interpretation

The exact recursion separates immediate expected reward from the expected value of the information carried into later decisions. At \(h=1\), the second term is absent, giving the terminal rule. For \(h>1\), assigning to a less-sampled arm may produce an outcome that changes the posterior and therefore the best arm for a later participant. The expected benefit of that change is the value of information. The UCB-style approximation represents this benefit indirectly: less data typically means greater uncertainty and therefore a larger bonus.

The taper follows from the number of opportunities remaining. At \(h=T\), \(g(h)=1\); at \(h=1\), \(g(h)=0\); and for intermediate \(h\), the bonus is reduced in proportion to the fraction of post-current assignments remaining:

g(h)=\frac{h-1}{T-1}, \qquad 1\le h\le T,\; T>1.

This is a policy design choice, not a theorem that optimal exploration decays linearly. In particular, large uncertainty or a small estimated reward gap may make information valuable even late in a trial, while a very large gap may make extra sampling of a clearly inferior arm unattractive well before the endpoint. Exact finite-horizon optimization, when feasible under a specified model, accounts for those features more directly.

Diagnostics, Alternatives, and Limitations

A horizon-aware rule should be checked against the actual decision process, not applied mechanically. Confirm that \(h\) counts the current assignment and that \(h-1\) is the number of later decisions that can benefit from its outcome. If outcomes are delayed, the nominal number of remaining enrollees may overstate the number of usable updates. If the trial may stop early or enroll beyond its planned endpoint, a fixed \(T\) can misrepresent the actual opportunity to learn. Unequal follow-up, changing eligibility, or changing reward distributions also undermine the simple stationary model.

A finite-horizon bandit policy is not the only possible objective. The alternatives below make different choices about exploration or what is being optimized.

Approach	How the horizon enters	Typical distinction
Fixed UCB-style rule	Uses an uncertainty bonus without this explicit terminal taper	May continue to reward uncertainty even at the endpoint unless separately modified
Epsilon-greedy schedule	Exploration probability can be scheduled to decrease with time	Random exploration is controlled directly rather than through an uncertainty index
Explore-then-commit	Uses a predetermined exploration phase followed by exploitation	Easy to specify, but does not adapt the exploration phase to what the outcomes reveal
Best-arm identification	Uses a fixed budget or confidence target to identify a top arm	Prioritizes identifying an arm rather than maximizing reward accumulated during enrollment

The last distinction is important: a known enrollment endpoint does not by itself determine whether the goal is cumulative reward or accurate identification of the best arm. The horizon-scaled index here is motivated by cumulative reward; a design whose primary objective is a final recommendation may rationally continue gathering information near the end. Even for cumulative reward, the proposed linear taper is only a simple heuristic. Its performance should be evaluated under plausible reward distributions and operational constraints rather than assumed from the formula alone.

Common Mistakes

Counting the current assignment as a future learning opportunity. With \(h\) assignments including the current one, only \(h-1\) assignments follow it. At \(h=1\), the information from the last outcome cannot improve a later assignment.
Treating the index as a probability or a confidence interval. It is a ranking score. A value above 1 is possible and does not mean an outcome probability exceeds 1.
Calling the taper optimal. The linear multiplier is a simple adjustment motivated by finite opportunities. The Bellman recursion, not this heuristic, defines the exact objective under a specified model.
Using the planned horizon when the usable horizon differs. If outcomes arrive too late to affect later decisions, or enrollment may stop early, the nominal remaining enrollment can overstate the value of exploration.
Ignoring untried arms. The displayed empirical index requires \(n_i>0\). Initialization and any minimum sampling requirements must be explicitly handled, especially when \(T<K\).

Key takeaway: In a fixed-horizon cumulative-reward problem, exploration is valuable because it can improve later decisions. The terminal decision has no such future benefit, so it selects the arm with the largest predictive mean. A horizon-scaled uncertainty bonus is a useful, transparent approximation—but its schedule and assumptions must be checked in the trial setting.

Check Your Understanding

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

A trial has \(T=25\) assignments and is at assignment \(t=21\). Find \(h\) and the linear horizon multiplier \(g(h)\).
With one assignment remaining, arm A has predictive mean \(0.48\) and arm B has predictive mean \(0.52\). Which arm is chosen for the cumulative-reward objective, and why?
For \(T=20\) and \(h=5\), what fraction of the original UCB-style bonus remains under the stated taper?
Give one reason the nominal number of remaining enrollees may overstate the value of exploration in a clinical trial.

Solutions. (1) \(h=T-t+1=25-21+1=5\), so \(g(h)=(5-1)/(25-1)=4/24=1/6\approx0.1667\). (2) Choose B: the last assignment has no later decision to benefit from new information, and \(0.52>0.48\). (3) \(g(5)=4/19\approx0.2105\), so about 21.05% of the original bonus remains. (4) For example, outcomes may be delayed and unavailable before later assignments; then fewer decisions can use the information than the enrollment count suggests.

What You'll Learn