Finite independent Pandora model with positive and zero multiplier index rules

Box. For each natural number $n$, the box set is $I=\{0,\ldots,n\}$, with exactly $n+1$ elements. In particular, $n=0$ means one box, never an empty box set.

History. For each natural number $n$, a history is any function on the $n+1$ ordered slots $0,\ldots,n$ whose value is a triple consisting of a Boolean, a box in $I=\{0,\ldots,n\}$, and a real number. This type itself imposes no validity, occupancy, uniqueness, or reward-support restrictions; even inactive slots have box and reward coordinates.

Decision. For each natural number $n$, a decision is either no box, written stop, or one specified box in $I=\{0,\ldots,n\}$.

decisionMeasurableSpace. For each natural number $n$, the measurable structure on the finite decision set consisting of stop and the $n+1$ individual box choices is the top measurable structure, so every subset of this decision set is measurable.

Instance. For each natural number $n$, an instance assigns to every box $i\in I=\{0,\ldots,n\}$ a measure $\mu_i$ on the real line that is a probability measure and for which the identity real-valued function is integrable, together with a deterministic real cost $c_i$ satisfying $0<c_i$. These requirements apply to every box, including when $n=0$; the structure adds no budget, multiplier, reward-sign, bounded-support, or optimality assumptions.

seedLaw. The seed law is Lebesgue measure restricted to the closed real interval $[0,1]$.

Outcome. For each natural number $n$, an outcome is a pair $(r,u)$ consisting of an arbitrary real reward vector $r:I\to\mathbb R$ on $I=\{0,\ldots,n\}$ and an arbitrary real seed $u$. The type itself does not restrict $u$ to $[0,1]$.

jointLaw. For every natural number $n$ and instance with box laws $\mu_i$, the law of the outcome $(r,u)$ is the product of the finite product measure $\bigotimes_{i=0}^{n}\mu_i$ and Lebesgue measure restricted to $[0,1]$. Thus the coordinate rewards have their given probability laws independently, and the uniform seed is independent of all rewards.

occupied. For any natural number $n$, history $h$, and slot $k\in\{0,\ldots,n\}$, the slot is occupied exactly when the Boolean coordinate of $h(k)$ is true.

observedBox. For any natural number $n$, history $h$, and slot $k\in\{0,\ldots,n\}$, the observed-box function returns the box coordinate of $h(k)$, regardless of whether the slot is occupied.

observedReward. For any natural number $n$, history $h$, and slot $k\in\{0,\ldots,n\}$, the observed-reward function returns the real reward coordinate of $h(k)$, regardless of whether the slot is occupied.

wasOpened. For any natural number $n$, history $h$, and box $i\in\{0,\ldots,n\}$, box $i$ was opened exactly when there exists a slot whose Boolean is true and whose box coordinate equals $i$. A box appearing only in inactive slots does not satisfy this predicate.

validHistory. For any natural number $n$, a history $h$ is valid exactly when slot zero is occupied, occupancy is downward closed in slot order (if $k\le l$ and $l$ is occupied then $k$ is occupied), and two occupied slots having the same box must be the same slot. Therefore occupied slots form a nonempty prefix with distinct boxes. Observed rewards may be arbitrary real numbers; inactive-slot coordinates have no constraints.

Policy. For each natural number $n$, a policy consists of a measurable map from real seeds to boxes for the mandatory first choice and a measurable map from pairs of a history and real seed to either stop or a box for subsequent choices. For every history, every real seed, and every box, if the subsequent-choice map returns that box, there is no occupied slot of the supplied history bearing it. This last requirement applies even to invalid histories and seeds outside $[0,1]$. No optimality or index condition is part of the structure; the structure alone also does not require consistent responses when a previously stopped history is supplied again.

initialHistory. For any natural number $n$, policy, and outcome $(r,u)$, the initial history occupies slot zero with the first-choice box selected using $u$ and reward equal to that box’s coordinate of $r$. Every other slot is set to the inactive triple with box zero and reward zero. There is always a first opening, including for $n=0$.

rolloutAux. For any natural number $n$, policy, outcome $(r,u)$, natural fuel, natural insertion step, and history, the rollout returns the supplied history when fuel is zero. With positive fuel it evaluates the next decision on the current history and the same seed $u$: stop returns the history immediately; a box choice updates the slot at the insertion step to that box and its coordinate of $r$ and recurses with one less fuel and insertion step increased by one, provided the step is less than $n+1$; an out-of-range step returns the current history. These arguments are unrestricted, so an arbitrary call can overwrite an occupied slot; a stop returns without further recursion.

terminalHistory. For any natural number $n$, policy, and outcome, the terminal history is the preceding rollout started from the mandatory first-opening history with insertion step one and fuel $n$. Thus the execution has one mandatory opening followed by at most $n$ further opening opportunities, and it never resumes after a stop. When $n=0$ it is simply the initial history.

historyReward. For any natural number $n$ and history, the history reward starts from the real coordinate of slot zero and scans all slots in order, replacing the running value by its maximum with each occupied slot’s reward and ignoring inactive slots. For a valid history it is exactly the maximum occupied reward, with no extra outside option such as zero. For an arbitrary invalid history the slot-zero reward contributes even if slot zero is inactive.

historyCost. For any natural number $n$, instance with costs $c_i$, and history, the history cost is the sum over its $n+1$ slots of $c_i$ for an occupied slot bearing box $i$ and zero for an inactive slot. It counts slots, so repeated boxes in an invalid history contribute repeatedly.

terminalReward. For any natural number $n$, policy, and outcome, the terminal reward is the history-reward fold applied to the policy’s terminal history obtained from its mandatory first opening and at most $n$ further rollout steps.

terminalCost. For any natural number $n$, instance, policy, and outcome, the terminal cost is the sum of the costs of the occupied slots in the terminal history generated by the mandatory first opening and at most $n$ further rollout steps.

expectedReward. For any natural number $n$, instance, and policy, expected reward is the real-valued Bochner integral of its terminal reward under the product law of all independent box rewards and the independent uniform seed. The definition has no separate integrability hypothesis on this terminal function; the integral is the library’s total integral operation, which returns zero on a nonintegrable function.

expectedCost. For any natural number $n$, instance, and policy, expected cost is the real-valued Bochner integral of its terminal cost under the product law of all independent box rewards and the independent uniform seed. The definition has no separate integrability hypothesis on this terminal function; the integral is the library’s total integral operation, which returns zero on a nonintegrable function.

value. For any natural number $n$, instance, arbitrary real multiplier $\lambda$, and policy $\pi$, its value is $R(\pi)-\lambda C(\pi)$, where $R(\pi)$ and $C(\pi)$ are the joint-law integrals of its terminal reward and terminal cost. This definition also accepts zero and negative multipliers.

optimal. For any natural number $n$, instance, arbitrary real multiplier $\lambda$, and policy $\pi$, optimality means that for every policy $\rho$ on the same boxes, $R(\rho)-\lambda C(\rho)\le R(\pi)-\lambda C(\pi)$, where $R$ and $C$ are expected terminal reward and cost. It imposes no budget constraint or uniqueness requirement.

optimalValue. For any natural number $n$, instance, and arbitrary real multiplier $\lambda$, optimal value is the real supremum of all numbers $R(\pi)-\lambda C(\pi)$ as $\pi$ ranges over policies on the same boxes. This uses the real, conditionally complete supremum operation; the definition does not itself assert boundedness, attainment, or existence of a maximizing policy.

dualValue. For any natural number $n$, instance, and arbitrary real budget $B$ and multiplier $\lambda$, the dual value is $D_B(\lambda)=\sup_{\pi}(R(\pi)-\lambda C(\pi))+\lambda B$, with the supremum taken in the reals over all policies on the instance.

dualMinimizer. For any natural number $n$, instance, real budget $B$, and real multiplier $\lambda$, being a dual minimizer means both $0\le\lambda$ and $D_B(\lambda)\le D_B(t)$ for every real $t\ge0$, where $D_B(t)=\sup_{\pi}(R(\pi)-tC(\pi))+tB$. There is no uniqueness requirement and no comparison to negative multipliers.

budgetFeasible. For any natural number $n$, instance, arbitrary real budget $B$, and policy $\pi$, budget feasibility means $C(\pi)\le B$, where $C(\pi)$ is expected terminal opening cost. It is an expectation constraint and does not assert that the realized cost is always at most $B$.

budgetOptimal. For any natural number $n$, instance, arbitrary real budget $B$, and policy $\pi$, budget optimality means that $C(\pi)\le B$ and that every policy $\rho$ with $C(\rho)\le B$ satisfies $R(\rho)\le R(\pi)$, where $C$ and $R$ are expected terminal cost and reward. Feasibility of $\pi$ is an explicit conjunct.

fullInformationPayoff. For any natural number $n$ and arbitrary real reward vector $r$ on boxes $0,\ldots,n$, the full-information payoff starts from $r(0)$ and successively takes the maximum with $r(i)$ over all boxes. It equals $\max_{0\le i\le n}r(i)$ and has no outside option of zero; when $n=0$ it is $r(0)$.

fullInformationReward. For any natural number $n$ and instance, full-information reward is the real Bochner integral of the maximum of all $n+1$ reward coordinates under the joint product law of the independent box rewards and independent uniform seed. This is a reward integral, with no costs subtracted.

zeroCostOptimal. For any natural number $n$, instance, and policy $\pi$, zero-cost optimality means optimality at multiplier zero: every policy $\rho$ satisfies $R(\rho)\le R(\pi)$. Actual box costs remain strictly positive; this predicate merely gives them zero coefficient in the objective and imposes no budget constraint.

budgetValue. For any natural number $n$, instance, and arbitrary real budget $B$, budget value is the real supremum of $R(\pi)$ over policies satisfying $C(\pi)\le B$. The definition includes budgets with no feasible policies and uses the total real supremum operation on the resulting set; it does not assert nonemptiness, boundedness, or attainment.

genuinelyActiveBudget. For any natural number $n$, instance, and real budget $B$, genuine activity means that at least one policy has expected cost at most $B$ and that the real supremum of expected rewards over all such policies is strictly less than the expected maximum of all box rewards. Both feasibility and a strict value gap are required.

belowEveryFullInformationPolicy. For any natural number $n$, instance, and real budget $B$, this condition says that for every policy whose expected terminal reward equals the expected maximum of all box rewards, its expected cost is strictly greater than $B$. It is an implication quantified over all policies and has no explicit feasible-policy, supremum-gap, or multiplier assumption; if no policy met the equality, it would hold vacuously.

expectedImprovement. For any natural number $n$, instance, box $i$, and real threshold $z$, expected improvement is the real Bochner integral $\int_{\mathbb R}\max(y-z,0)\,d\mu_i(y)$, using only that box’s probability law. It is not an expectation over the other boxes or the seed.

reservationRoot. For any natural number $n$, instance, box $i$, and arbitrary real numbers $c,z$, being a reservation root means exactly $\int\max(y-z,0)\,d\mu_i(y)=c$. The predicate itself requires neither $c>0$ nor root existence or uniqueness.

reservationIndices. For any natural number $n$, instance, arbitrary real multiplier $\lambda$, and real-valued vector $z$ on all boxes, being reservation indices means that every box $i$ satisfies $\int\max(y-z_i,0)\,d\mu_i(y)=\lambda c_i$. All indices are finite real numbers; no positivity condition on $\lambda$ occurs in this predicate.

isGittinsPolicy. For any natural number $n$, instance, arbitrary real multiplier $\lambda$, and policy $\pi$, this condition asserts existence of finite real numbers $z_i$ satisfying $\int\max(y-z_i,0)\,d\mu_i(y)=\lambda c_i$ for every box. For every real seed $u$, the first box chosen has index at least every box’s index. For every valid history (a nonempty occupied prefix with distinct boxes and arbitrary real observed rewards) and every real seed, if the next decision is stop, each unopened box has index at most the current maximum observed reward; if it chooses box $i$, that maximum is at most $z_i$, and every unopened box has index at most $z_i$. The policy structure also requires the chosen box to be unopened. All comparisons are weak, so equality allows either decision, and the requirements cover histories and seeds of probability zero. The definition itself does not require a positive multiplier.

zeroReservationIndex. For any natural number $n$, instance, and box $i$, its zero reservation index is the infimum, in the extended reals $\mathbb R\cup\{-\infty,+\infty\}$, of all extended-real numbers $z$ such that $y\le z$ for $\mu_i$-almost every real reward $y$, with $y$ embedded in the extended reals. The set of bounds includes $+\infty$; the resulting essential supremum may be $+\infty$, and this definition is not a search for a finite root of an expected-improvement equation.

isZeroGittinsPolicy. For any natural number $n$, instance, and policy, let $s_i$ be the extended-real infimum of the almost-sure upper bounds on box $i$’s reward. For every real seed, the first chosen box must have $s_i$ at least every box’s index. For every valid history (a nonempty occupied prefix with distinct boxes and arbitrary real observed rewards) and every real seed, stopping requires $s_i$ to be at most the real incumbent reward embedded in the extended reals for every unopened box; choosing box $i$ requires the embedded incumbent to be at most $s_i$, and every unopened box’s index to be at most $s_i$. The underlying policy additionally forbids opening an already occupied box. Indices may be $+\infty$, comparisons are non-strict, and these requirements hold at all valid histories and all real seeds, with no budget condition.

isGeneralizedGittinsPolicy. For any natural number $n$, instance, real multiplier $\lambda$, and policy, this predicate is the disjunction of two cases: $\lambda>0$ and the finite reservation-index policy rule holds, or $\lambda=0$ and the extended-real essential-supremum policy rule holds. The finite rule uses roots $\int\max(y-z_i,0)\,d\mu_i=\lambda c_i$, whereas the zero rule uses infima of almost-sure extended-real reward upper bounds; in both cases the first choice maximizes the indices, continuation chooses a maximum unopened index at least the incumbent, and stopping requires every unopened index to be at most the incumbent, at every real seed and valid history. Negative multipliers satisfy neither branch.

complementarySlackness. For any natural number $n$, instance, arbitrary real budget $B$ and multiplier $\lambda$, and policy $\pi$, complementary slackness means exactly $\lambda(B-C(\pi))=0$, where $C(\pi)$ is expected terminal cost. No multiplier-sign or feasibility condition is included: at $\lambda=0$ the equation holds for every policy and budget, and at a nonzero multiplier it requires $C(\pi)=B$.