Ties In Optimal Treatment Decisions

Why ties matter

A treatment rule is often described as choosing an action with the largest Q-value at each history. That description does not always specify one action: two or more feasible actions may have the same maximal Q-value. A tie is not necessarily a defect in the optimization. It can mean that distinct treatments have equal expected value for the history under the model, even if they lead to different outcomes or future histories.

The practical task is to characterize where these ties occur and decide how a rule should represent them. A deterministic rule must select one action; a set-valued rule records all optimal actions; and a randomized rule may choose among them. Under the assumptions below, each choice that is supported entirely on the maximizing actions has the same optimal expected value. That equality does not imply that the actions are clinically interchangeable for every outcome, or equally safe by criteria not included in the reward.

Q-values and the tie set

Consider a finite-horizon treatment problem with stages $t=1,\ldots,T$. Let $H_t$ denote the observed history available just before treatment at stage $t$, and let $\mathcal A_t(h)$ be the nonempty feasible action set at history $h$. Write $R_t(h,a,h')$ for the reward received at stage $t$ when action $a$ is taken and the next history is $h'$. The transition law under that action is $K_t(dh'\mid h,a)$. Rewards can be negative, as when they include treatment burden or cost.

Assume throughout that the action sets are finite, rewards are measurable and bounded, and the transition kernels are well-defined. Assume also that the available actions and the functions defining the model are measurable in history. These conditions ensure that the conditional expectations below exist and that a measurable maximizing action can be selected. For a causal interpretation of the transition and reward laws, the usual identification assumptions, including consistency, sequential exchangeability, and positivity for the strategies being evaluated, are needed.

Definition: Set $W_{T+1}(h)=0$. Working backward, define the Q-value and optimal continuation value by $$ Q_t(h,a)=\int \left\{R_t(h,a,h')+W_{t+1}(h')\right\}K_t(dh'\mid h,a), \qquad W_t(h)=\max_{a\in\mathcal A_t(h)}Q_t(h,a). $$ The maximizing-action correspondence is $$ \mathcal M_t(h)=\operatorname*{arg\,max}_{a\in\mathcal A_t(h)}Q_t(h,a) =\{a\in\mathcal A_t(h):Q_t(h,a)=W_t(h)\}. $$ The tie set at stage $t$ is $\mathcal T_t=\{h:|\mathcal M_t(h)|\geq 2\}$.

The immediate reward term is part of the recursion: a treatment can affect value both through its immediate reward and through the distribution of the next history. The tie set contains histories with multiple actions that attain the maximum, not histories where two actions merely have similar estimated Q-values. With finite nonempty action sets, the maximum is attained and $\mathcal M_t(h)$ is nonempty at every history.

Ways to resolve a tie

A deterministic optimal rule is a measurable selector $d_t(h)\in\mathcal M_t(h)$. One common convention is to fix an ordering of the finite action labels and choose the first maximizing feasible action. This convention produces one action even when the data do not distinguish the tied actions by value. If actions are indexed $1,\ldots,K$, a tie-breaking selector can be written as $$ d_t(h)=\min\{a\in\mathcal A_t(h):Q_t(h,a)=W_t(h)\}. $$ For finite action labels and measurable Q-functions and availability sets, the conditions defining this selector are measurable, so the rule is measurable.

A set-valued rule reports $\mathcal M_t(h)$ itself. It is useful when preserving the full decision information matters more than immediately naming one treatment. It is not, by itself, a single treatment assignment: implementation requires either a prespecified selector or an additional decision criterion.

A randomized tie rule assigns probabilities $p_t(a\mid h)$ over feasible actions, with $p_t(a\mid h)=0$ for every $a\notin\mathcal M_t(h)$ and probabilities summing to one. Such randomization does not improve the optimal value in this setup; it only mixes actions already attaining that value. A rule assigning positive probability to a strictly suboptimal action does not have this guarantee.

Worked Example: Finding a Tie in a Categorical Q-Model

At a terminal stage, suppose three feasible actions have Q-values, for a scalar history feature $x$, $$ Q(x,A)=4+x,\qquad Q(x,B)=8-x,\qquad Q(x,C)=5. $$ Find the maximizing action and tie histories for $x\in[0,4]$.

Action $A$ ties $B$ when $4+x=8-x$, so $x=2$, where both values are 6. At that history, $Q(2,C)=5$, so $A$ and $B$ are both maximal. To check whether other ties are maximal, $A=C$ at $x=1$, but $Q(1,B)=7$, which is larger than 5. Also $B=C$ at $x=3$, but $Q(3,A)=7$, which is larger than 5. Thus the only tie in the maximizing-action correspondence is at $x=2$.

For $x<2$, $Q(x,B)>Q(x,A)$; for $x>2$, $Q(x,A)>Q(x,B)$. Comparing with $C$ confirms that $B$ is maximal below 2 and $A$ is maximal above 2 on the stated interval. At $x=2$, a deterministic rule may choose $A$, choose $B$, or follow a prespecified ordering. The set-valued rule reports $\{A,B\}$.

Why optimal tie-breaking preserves value

The relevant result is about choosing among exact maximizers of the population Q-functions. Its statement includes the immediate reward in the recursion; omitting that term would generally give a different value and could change which actions tie.

Theorem: Suppose the finite-horizon recursion above is well-defined and each stage has a finite nonempty feasible action set. Let $d_t(h)$ be any measurable selector from $\mathcal M_t(h)$ at every stage. Then the expected remaining reward under the regime $d=(d_1,\ldots,d_T)$, conditional on $H_t=h$, equals $W_t(h)$ at every stage $t$. Consequently, any two such deterministic selectors have the same value from every initial history distribution.

Proof. At stage $T$, the continuation value is zero after the final reward. Since $d_T(h)\in\mathcal M_T(h)$, $$ E[R_T\mid H_T=h,\ A_T=d_T(h)] =Q_T(h,d_T(h))=W_T(h). $$ Now suppose the claimed equality holds at stage $t+1$ for every next history. Under the rule $d$, conditional expected remaining reward at stage $t$ is $$ \int \left\{R_t(h,d_t(h),h')+W_{t+1}(h')\right\}K_t(dh'\mid h,d_t(h)) =Q_t(h,d_t(h)) =W_t(h). $$ The first equality uses the induction hypothesis for the continuation reward at each $h'$; the last uses the selector property. Backward induction proves the equality at all stages. Integrating $W_1(h)$ over any initial history distribution gives the regime value, which is therefore the same for every such selector. $\square$

The same argument covers randomized tie-breaking. At a history, averaging Q-values over a distribution supported on $\mathcal M_t(h)$ gives $W_t(h)$, because every supported action has Q-value $W_t(h)$. Applying the same backward induction shows that the randomized rule also has value $W_t(h)$. This conclusion requires the later-stage rule to be optimal as well; a tied choice now followed by a suboptimal continuation need not preserve the optimal value.

Worked Example: A Two-Stage Tie With Immediate Costs

There are two stages. At stage 2, the history is $x\in\{0,1\}$, and the terminal reward is deterministic. At $x=0$, actions $L$ and $M$ each yield reward 5. At $x=1$, action $L$ yields 7 and action $M$ yields 6. Thus $W_2(0)=5$, with $\mathcal M_2(0)=\{L,M\}$, and $W_2(1)=7$, with $\mathcal M_2(1)=\{L\}$.

At stage 1, action $A$ gives immediate reward $-1$ and deterministically leads to $x=0$. Action $B$ gives immediate reward $-3$ and deterministically leads to $x=1$. Their Q-values are $$ Q_1(h,A)=-1+W_2(0)=-1+5=4, \qquad Q_1(h,B)=-3+W_2(1)=-3+7=4. $$ Therefore $W_1(h)=4$ and $\mathcal M_1(h)=\{A,B\}$.

Choosing $A$ and then either $L$ or $M$ gives total reward $-1+5=4$. Choosing $B$ and then $L$ gives $-3+7=4$. Choosing $B$ and then $M$ would give $-3+6=3$, which is below the optimal value: the stage-1 tie alone does not make a nonoptimal continuation optimal. This calculation checks both the immediate cost and the continuation reward in the recursion.

Worked Example: Equal Expected Value, Different Reward Distributions

In a one-stage problem, action $A$ yields reward 0 with probability $1/2$ and reward 10 with probability $1/2$. Action $B$ yields reward 5 with probability 1. Their expected rewards are $$ Q(A)=\tfrac12(0)+\tfrac12(10)=5,\qquad Q(B)=1(5)=5. $$ Both actions are in the maximizing-action set, and either has optimal expected value 5.

Their reward distributions are not the same: $A$ has variance $\tfrac12(0-5)^2+\tfrac12(10-5)^2=25$, while $B$ has variance 0. Thus equality of Q-values is equality of expected reward under the specified objective, not equality of outcome distributions or of every clinical consequence. If the decision objective includes a penalty for variability or another outcome, that objective must be incorporated into the reward or constraints before identifying its maximizing actions.

Diagnostics, alternatives, and limitations

In an estimated Q-model, an apparent tie can arise from rounding, limited precision, or a small estimated contrast. Exact population ties and numerical near-ties are different concepts. Diagnostics should retain the unrounded Q-values, compare all feasible actions at each history, verify the feasible set, and report the maximizing gap between the largest and second-largest Q-values. A gap of zero indicates a tie in the fitted values; a small positive gap indicates a near-tie, not an exact tie. Neither check alone establishes what the population Q-functions do.

A deterministic tie-break is operationally simple and reproducible, but its selected action can depend on an arbitrary label ordering. A set-valued rule communicates that the value model does not distinguish certain actions, but requires a further choice for implementation. Randomizing among tied actions also preserves expected value under the stated objective, though it may be undesirable operationally or under additional objectives not represented in Q. In contrast, adding a clinical restriction changes the feasible action set and can change the optimum; it is not merely a way to resolve a tie.

The equality result is limited to the Q-functions, reward, feasible actions, and continuation rules in the model. It does not say that estimated ties are known population ties, that all outcomes are equivalent, or that a rule chosen for value is optimal for unmodeled safety or resource criteria. In continuous-action problems, a maximum need not exist without conditions on the action space and Q-function; the finite-action result here should not be applied without checking existence and measurable selection in that setting.

Pitfall: “The two fitted Q-values are close, so the actions are tied.” Closeness is not equality. Report the contrast and its scale, retain numerical precision, and distinguish an estimated near-tie from an exact tie.
Pitfall: “Either tied action can be followed by any later treatment.” The theorem permits tied choices when continuation is optimal. A suboptimal future action can lower the total value, as the second worked example demonstrates.
Pitfall: “Tied means clinically identical.” A tie means equal expected value under the specified reward and model. Distributional or clinical differences can remain.

Key takeaway: The tie set consists of histories where at least two feasible actions attain the maximum Q-value. Any measurable deterministic or randomized choice supported on the maximizing actions preserves optimal expected value when subsequent decisions are also optimal.

Check Your Understanding

Answer each question, then compare with the solutions.

If three feasible actions have Q-values 4, 4, and 2 at a history, what is the maximizing-action set, and is the history in the tie set?
At a history, two actions have Q-values 6 and 5.5. Is this an exact tie? What should be reported?
In the two-stage example, what value results from choosing $B$ at stage 1 and $M$ at stage 2?
Why does a randomized rule supported on tied actions preserve the optimal expected value?

Solutions. (1) The maximizing-action set contains the first two actions, both with value 4. Its size is 2, so the history is in the tie set. (2) No. The maximum is 6 and the gap is $6-5.5=0.5$; report the values and gap, and call it a near-tie only relative to a stated practical threshold. (3) The immediate reward is $-3$ and the stage-2 reward under $M$ at $x=1$ is 6, so the total is $-3+6=3$. (4) Every action receiving positive probability has the same Q-value $W_t(h)$, so their probability-weighted average Q-value is also $W_t(h)$; with optimal continuations, backward induction gives the same value.