Fix a horizon \(H\in \mathbb N\), finite nonempty observed-history sets \(\mathcal H_t\) for \(0\leq t\leq H\), an initial law \(\mu \) on \(\mathcal H_0\), and finite nonempty permitted-action sets \(A_t(h)\) for \(t<H\). An environment kernel \(K_t(\cdot \mid h,a)\) is a probability law on histories extending \(h\) by action \(a\) and its observed outcome. The initial law and all kernels are fixed before choosing a controller.

A controller \(\pi \) assigns a probability law \(\pi _t(\cdot \mid h)\) on \(A_t(h)\). It may depend on every observed component of \(h\), including retained traces, generated programs, and previous updates. Random choices may be recorded in the history. The class \(\Pi (\mathbf B)\) consists of all such controllers under the declared hard resource vector \(\mathbf B\in \mathbb R_+^m\). It does not require a fixed prompt, a memoryless policy, or independent worker outputs. Full-history access is allowed in this mathematical class; it may enlarge the class of executable controllers with limited memory or computation.

Each history records accumulated nonnegative cost \(\mathbf c(h)\preceq \mathbf B\). Every permitted non-stop action has a declared worst-case increment \(\bar {\mathbf c}_t(h,a)\) satisfying

Every successor in the kernel's support must have realized increment between zero and this declared bound, componentwise. Proposal work, controller computation, worker calls, communication, verification, failed attempts, and persistent updates must be included in whichever resource coordinates are bounded; the units remain those of Definition [ftip-005H]. This is the enforced-contract assumption of Theorem [ftip-00CK].

A stop action is always permitted: it commits the current terminal artifact and pads the remaining steps with no further cost or change in its evaluated quality. At the horizon a fixed evaluator assigns \(q(h_H)\in [0,1]\) to the committed artifact recorded in the terminal history. If the evaluator has random outcomes, include them in the history law. Evaluation work must be charged before the zero-cost padding begins. Define

The artifact identity, evaluator, observations, kernels, and action sets are part of the mathematical problem. A training procedure or new tool belongs to this frontier only if it is among the permitted actions and its effects and costs are represented. Finiteness is an explicit restriction on histories, representations, and horizon; a theorem for this class does not bound an unrestricted agent that can extend them.

For an executable system, an upper bound applies only after its observations, actions, outcomes, and charged costs are represented by this model. Conversely, a mathematical policy supplies an executable lower bound only when it has an implementation respecting the stated resource cap; an arbitrary history-to-action table does not establish that fact.

Let \(X,Y\) be independent uniform bits. The terminal artifact is a guess for \(X\mathbin \oplus Y\); its quality is one if correct and zero otherwise. Two observation actions reveal \(X\) and \(Y\), respectively, at cost \(c\) each, where \(0<c<1/4\). The hard budget permits both observations. A terminal guess requires no additional observation cost.

Without observations, the best expected quality is \(1/2\). Given only \(X\), the unrevealed bit \(Y\) remains uniform, so the best expected quality is still \(1/2\); the same holds with \(X,Y\) exchanged. Thus a rule that compares stopping with taking one observation and then stopping assigns either observation net value \(1/2-c<1/2\). It stops immediately.

Observing both bits determines their parity. Its expected quality is one and its quality minus observation cost is \(1-2c>1/2\). Hence neither zero one-step information value nor a myopic stopping decision certifies the full controller frontier. This is a finite calculation, not an empirical claim about a language model. The scalar cost penalty is used only to exhibit the myopic decision; the hard-budget quality frontier itself is defined in Definition 1.1.

An initial observation reveals a uniform bit \(Z\). The terminal action is a bit \(a\), and quality is \(q=\mathbf 1\{a=Z\}\). Both actions are permitted at either history and have the same cost. A full-history controller chooses \(a=Z\) and attains quality one.

Now restrict the controller's entire input to a summary that is constant at the two initial histories. Its private randomness is independent of \(Z\). If it chooses one with probability \(p\), its expected quality is \(p/2+(1-p)/2=1/2\). No such summary controller can do better.

A model that averages the reward of either fixed action over the two histories obtains \(1/2\). This is the correct summary-controller value, but it underestimates the full-history frontier by \(1/2\). For the history \(Z=a\), the actual reward is one, so the averaged value fails as a reward upper bound at that history. A pointwise reward upper bound must hold at every represented history; agreement only under a tested policy's average history distribution does not establish such a certificate. The loss of an evaluator caveat in Example [ftip-00CU] illustrates why such retained distinctions can matter in a research harness.

Use the finite controller model of Definition 1.1. For each time, choose a finite nonempty state set \(S_t\) and a map \(\phi _t:\mathcal H_t\to S_t\). Require finite nonempty action sets \(A_t(s)\) such that \(A_t(h)=A_t(\phi _t(h))\) at every history. The state retains residual budgets and enough information for the same hard admission rule. The controller still observes the full history.

Let \(Q_t(\cdot \mid h,a)\) be the image of the fixed history kernel under \(\phi _{t+1}\), and let \(\widehat P_t(\cdot \mid s,a)\) be a proposed state transition law. Choose finite errors \(\epsilon _t(s,a)\geq 0\) so that, for every permitted history and action,

This condition includes histories unvisited by a chosen policy: the kernel there is part of the model. For finite functions \(\widehat q:S_H\to \mathbb R\) and \(e_H:S_H\to \mathbb R_+\), require

Write \(\nu (s)=\mu \{h:\phi _0(h)=s\}\) for the initial state law. Low average prediction error on sampled histories does not establish these uniform inequalities. The erased-bit example in Example 1.3 shows why policy-relevant information cannot simply be averaged away.

Under Definition 2.1, let finite functions \(W_t:S_t\to \mathbb R\) satisfy \(W_H(s)\geq \widehat q(s)+e_H(s)\) and, for every \(t<H\), \(s\in S_t\), and \(a\in A_t(s)\),

Here \(\operatorname {span}(f)=\max f-\min f\). Every permitted history-dependent randomized controller then satisfies

For any feasible controller \(\pi _0\) with a justified finite lower bound \(L\leq J(\pi _0)\), the frontier of Definition 1.1 obeys

A numerical supersolution is a certificate only after all of its inequalities and the abstraction hypotheses are justified. If the model bounds hold jointly with probability at least \(1-\delta _M\) and the lower bound with probability at least \(1-\delta _E\), the bracket holds with probability at least \(1-\delta _M-\delta _E\) by a union bound. Each coverage statement must apply to the selected model or policy; no independence between the two events is required.

Suppose the abstraction is exact: \(Q_t(\cdot \mid h,a)= P_t(\cdot \mid \phi _t(h),a)\) for all histories and actions, and terminal quality is exactly \(q(h_H)=r(\phi _H(h_H))\). A one-sided terminal bound with zero error would not imply this equality. Retain the exact legal actions and hard-budget state from Definition 2.1.

Introduce nonnegative state masses \(z_t(s)\) and action masses \(x_t(s,a)\), with \(z_0=\nu \). For \(0\leq t<H\), impose

The linear program maximizes \(\sum _s z_H(s)r(s)\). Every full-history controller induces these flows because the next-state law given a state and action is exact. Conversely, at positive mass choose action \(a\) with probability \(x_t(s,a)/z_t(s)\); at zero mass choose any legal action. Induction on time reproduces the flows in the original history model. Hence the LP optimum equals its mathematical controller frontier. For \(H=0\), there are no action flows and the value is \(\nu r\).

Set \(W_H=r\) and recurse with \(W_t(s)=\max _{a\in A_t(s)}\sum _{s'}P_t(s'\mid s,a)W_{t+1}(s')\). A maximizing action exists by finiteness and gives a policy attaining \(\nu W_0\); the Bellman upper bound gives the reverse inequality. This proves equality with the optimum and exhibits matching lower and upper certificates. It does not establish an efficient implementation of the policy. The flow construction is the scalar finite-horizon specialization of Mifrani and Noll, Section 3; the hard-budget encoding is an additional modeling requirement here.

If hard admission is replaced by constraints on expected cost, the resulting program describes a different class. For \(B>0\), a one-step cost equal to \(2B\) or zero with probability \(1/2\) each has expectation \(B\), yet violates cap \(B\) with probability \(1/2\). An expected-cost model can upper-bound the hard-budget frontier only when it is a valid relaxation containing every hard-feasible policy. Its own policies need not respect the realized cap.

Fix the task law, evaluator, initial model, tools, observations, horizon, and intervention class. For \(\mathbf B\preceq \mathbf B'\), assume every controller feasible at \(\mathbf B\) remains permitted at \(\mathbf B'\) with the same outcome law. If a feasible controller at \(\mathbf B\) gives lower bound \(L_{\mathbf B}\) and Theorem 2.2 gives upper bound \(U_{\mathbf B'}\) at \(\mathbf B'\), then

If the certified gap is at most \(\varepsilon \), this instantiates Theorem [ftip-00LM]'s conditional saturation statement. An observed plateau alone supplies no such upper certificate. Changing an excluded tool, representation, or training procedure changes the comparison class.

Fix a finite nonempty directed acyclic task graph, positive task durations \(p_j\), and \(m\) identical processors, where \(m\in \mathbb N\) and \(m\geq 1\). All tasks are available at time zero subject only to their precedence constraints. Each task uses one processor without interruption; there are no further resource, communication, or setup constraints. Let \(W=\sum _j p_j\), let \(D\) be the longest precedence-chain duration, and let \(T^*\) be the minimum makespan. A work-conserving list schedule starts a ready task whenever a processor is free. Its makespan \(T_{\mathrm {list}}\) satisfies

The ratio \(T_{\mathrm {list}}/\max (W/m,D)\) compares the schedule with a lower bound that need not be attainable; it is not generally the ratio to the optimum. Communication and verification must be modeled as work with constraints satisfying these assumptions, or the displayed upper bound need not apply. Neither bound certifies the quality of the chosen task graph or an unrestricted agent's attainable output quality.