Answer: Yes. An algorithm with polynomial computation per round jointly guarantees proportionality at every round and regret \(O_{a,b,\sigma}(\rho_{\min}^{-1}\sqrt{\tau mT\log(\tau mT)})\) with probability at least \(1-1/T\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSuppose n, m, T, a, b are known and that the true mean values satisfy 0 < a ≤µ∗ ik ≤b for all i ∈[n], k ∈[m]. With probability 1 −1/T, Algorithm 1 will both satisfy the proportionality in expectation constraints for µ∗ and have regret for µ∗of ˜O(n5m3√ T). The initial exploration phase of Algorithm 1 uses the fact that the uniform at random allocation is guaranteed to sat- isfy proportionality in expectation constraints for any mean value matrix µ. After the exploration phase, at each step we calculate an estimated mean value matrix (ˆµt) and an uncer- tainty matrix (ϵt).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(\tau\) recipient types with masses \(\rho_\theta > 0\) satisfying \(\sum_\theta \rho_\theta = 1\), \(m\) uniformly arriving item types, and unknown sub-Gaussian reward laws with normalized means \(v_{\theta k} \in [a,b]\) satisfying \(\sum_k v_{\theta k} = 1\), choose before each arrival a nonnegative matrix \(x_t\) with \(\sum_\theta x_{t,\theta k} = 1\); assign an arriving type-\(k\) item to type \(\theta\) with probability \(x_{t,\theta k}\), then to a uniformly sampled member of that type, observing only its reward. Require with probability at least \(1 - 1/T\) that every type satisfies \(\sum_k x_{t,\theta k} v_{\theta k} / \rho_\theta \ge 1\) at every \(t < T\), and determine whether an algorithm can achieve regret \(T W^*(v) - \sum_t (1/m) \sum_{\theta,k} x_{t,\theta k} v_{\theta k}\) of \(\tilde{O}(\text{poly}(\tau,m,\rho_{\min}^{-1}) \sqrt{T})\) against the clairvoyant proportional optimum while computing each \(x_t\) in polynomial type-level time.
A society is given by its support: \(\tau\) recipient types with positive binary-rational masses \(\rho_\theta\), where \(\sum_\theta\rho_\theta=1\); \(\tau\) is the support size, not the number of possible types. Each type is an atomless population with its normalized probability measure. Write \(\rho_{\min}=\min_\theta\rho_\theta\).
Known inputs are \(m,\tau\geq1\), horizon \(T\geq2\), and binary-rational bounds \(0<a\leq b<\infty\), \(\sigma>0\). Unknown stationary reward laws have means \(v_{\theta k}\in[a,b]\) with \(\sum_{k=1}^m v_{\theta k}=1\), and centered rewards are \(\sigma\)-sub-Gaussian. Conditional on the selected pair, observations are fresh independent draws from its law, shared by all members of that type.
At each round \(0\leq t<T\), using only past item types, selected recipient types, and observed rewards, choose \(x_t\geq0\) with \(\sum_\theta x_{t,\theta k}=1\). An independent uniformly random item type \(k\) then arrives; select type \(\theta\) with probability \(x_{t,\theta k}\), sample a member according to that type's normalized measure, and observe only its reward.
Proportionality in expectation means \(\sum_k x_{t,\theta k}v_{\theta k}\geq\rho_\theta\) for every type and round. Define \(W^*(v)=\max\{m^{-1}\sum_{\theta,k}x_{\theta k}v_{\theta k}:x\geq0,\ \sum_\theta x_{\theta k}=1,\ \sum_kx_{\theta k}v_{\theta k}\geq\rho_\theta\}\) and \(R_T=TW^*(v)-m^{-1}\sum_{t=0}^{T-1}\sum_{\theta,k}x_{t,\theta k}v_{\theta k}\).
For bit complexity, reward observations are binary rationals; \(L\) is the total encoding length of known inputs and observations received so far. Polynomial computation per round means \(\operatorname{poly}(m,\tau,L,\log T)\) time, without enumerating population members.
Does an algorithm with polynomial computation per round exist that, for every admissible instance, jointly guarantees proportionality at every round and \(R_T\leq\widetilde O_{a,b,\sigma}(\operatorname{poly}(\tau,m,\rho_{\min}^{-1})\sqrt T)\) with probability at least \(1-1/T\), or is this guarantee impossible with polynomial computation per round?
For \(n\) discrete players, normalized positive means admit joint proportionality and \(\widetilde O(n^5m^3\sqrt T)\) regret with probability \(1-1/T\), but the exhibited algorithm has exponential running time in \(n,m\). [Schiffer–Zhang](https://arxiv.org/html/2501.07022v1)
No result settling the exact mass-supported problem with the stated computational requirement was located.
Yes. A polynomial-time algorithm exists. In fact, it achieves the stronger bound
\(R_T=O_{a,b,\sigma}\!\left(\rho_{\min}^{-1}\sqrt{\tau mT\log(\tau mT)}\right)\)
jointly with proportionality at every round, with probability at least \(1-1/T\).
The algorithm uses a mass-proportional initial exploration phase, followed by one rational linear program per round. Its confidence sets explicitly impose normalization. A sufficiently large linear exploration bonus then compensates for the cost of enforcing proportionality robustly.
This proof does not use the exponential maximization in the cited [Schiffer–Zhang algorithm](https://arxiv.org/html/2501.07022v1#S3.SS1).
Write \(d=\tau m\), and define the unnormalized welfare
\(F_v(x)=\sum_{\theta,k}x_{\theta k}v_{\theta k}\).
Thus the optimal unnormalized welfare is \(V^*(v)=mW^*(v)\).
Let \(B_{\theta k}=\rho_\theta\). This allocation is feasible for every normalized mean matrix, because
\(\sum_\theta B_{\theta k}=1\) and
\(\sum_kB_{\theta k}v_{\theta k}=\rho_\theta\).
Moreover, \(F_v(B)=1\).
Consider estimates \(\widehat v_{\theta k}\) and positive rational radii \(r_{\theta k}\). Define
\(\ell_{\theta k}=\max\{a,\widehat v_{\theta k}-r_{\theta k}\}\) and
\(u_{\theta k}=\min\{b,\widehat v_{\theta k}+r_{\theta k}\}\).
For each type, use the confidence polytope
\(C_\theta=\{w\in\mathbb R^m:\ell_{\theta k}\leq w_k\leq u_{\theta k}\ \text{for all }k,\ \sum_kw_k=1\}\).
Assume for now that every \(C_\theta\) is nonempty and contains \(v_\theta\). Define
\(g_\theta(x_\theta)=\min_{w\in C_\theta}\sum_kx_{\theta k}w_k\)
and
\(f(x)=\sum_{\theta,k}x_{\theta k}r_{\theta k}\).
An allocation is robustly proportional if
\(g_\theta(x_\theta)\geq\rho_\theta\) for every type. Such an allocation is proportional for the true means. Also, \(B\) is robustly proportional: normalization gives \(B_\theta\cdot w=\rho_\theta\) for every \(w\in C_\theta\).
For every nonnegative row \(x_\theta\),
\(0\leq x_\theta\cdot v_\theta-g_\theta(x_\theta)\leq2\sum_kx_{\theta k}r_{\theta k}\).
Indeed, any two vectors in \(C_\theta\) differ in coordinate \(k\) by at most \(2r_{\theta k}\), and the minimum is attained because \(C_\theta\) is compact.
Lemma. Suppose \(\max_{\theta,k}r_{\theta k}\leq a/4\). Let \(x\) be an allocation proportional for the true means. Then at least one of the following holds:
\(F_v(z)\geq F_v(x)-(2b/a)f(x)\) and
\(f(z)\geq f(x)/2\).
Proof. Put
\(c_\theta=g_\theta(x_\theta)\),
\(d_\theta=(\rho_\theta-c_\theta)_+\),
\(s_\theta=(c_\theta-\rho_\theta)_+\),
\(D=\sum_\theta d_\theta\), and \(S=\sum_\theta s_\theta\).
Since \(x_\theta\cdot v_\theta\geq\rho_\theta\), the preceding confidence bound gives
\(d_\theta\leq2\sum_kx_{\theta k}r_{\theta k}\).
Consequently, \(D\leq2f(x)\).
If \(D=0\), \(x\) itself is robustly proportional, so conclusion 2 holds with \(z=x\). Hence suppose \(D>0\).
Case 1: \(S<(b/a)D\). We have
\(F_v(x)\leq\sum_\theta c_\theta+2f(x)=1+S-D+2f(x)\).
Using \(b/a\geq1\) and \(D\leq2f(x)\), this implies
\(F_v(x)\leq1+(b/a-1)D+2f(x)\leq1+(2b/a)f(x)\).
This proves conclusion 1.
Case 2: \(S\geq(b/a)D\). We transfer allocation from types with positive robust surplus to types with a robust deficit.
For a donor \(\theta\), let \(M_\theta=\sum_kx_{\theta k}\), and remove total allocation mass
\(q_\theta=(D/a)(s_\theta/S)\),
distributed proportionally across its row:
\(\delta_{\theta k}=(q_\theta/M_\theta)x_{\theta k}\).
These expressions are well-defined because a donor has \(c_\theta>\rho_\theta>0\), hence \(M_\theta>0\). They do not remove more than the donor’s allocation: since \(s_\theta\leq c_\theta\leq bM_\theta\),
\(q_\theta/M_\theta\leq bD/(aS)\leq1\).
Let \(A_k=\sum_{\theta:s_\theta>0}\delta_{\theta k}\). Give each deficit type \(\eta\) the added allocation \((d_\eta/D)A_k\) of item type \(k\). Leave other types unchanged. Call the resulting allocation \(z\).
The total removed mass is
\(\sum_kA_k=\sum_{\theta:s_\theta>0}q_\theta=D/a\).
The deficit weights sum to one, so every column of \(z\) still sums to one.
For a donor, homogeneity of \(g_\theta\) gives
\(g_\theta(z_\theta)=(1-q_\theta/M_\theta)c_\theta\geq c_\theta-bq_\theta\).
The case assumption implies \(bq_\theta\leq s_\theta\), so this is at least \(\rho_\theta\).
For a deficit type \(\eta\), every candidate mean coordinate is at least \(a\). Therefore,
\(g_\eta(z_\eta)\geq c_\eta+a(d_\eta/D)\sum_kA_k=c_\eta+d_\eta=\rho_\eta\).
Thus \(z\) is robustly proportional.
Only donor removals can decrease true welfare, and their total mass is \(D/a\). Hence
\(F_v(z)\geq F_v(x)-bD/a\geq F_v(x)-(2b/a)f(x)\).
Similarly, additions cannot decrease \(f\), so
\(f(z)\geq f(x)-(a/4)(D/a)=f(x)-D/4\geq f(x)/2\).
This proves conclusion 2. \(\square\)
Set
\(K=4b/(a\rho_{\min})\)
and \(U_{\theta k}=\widehat v_{\theta k}+r_{\theta k}\).
Consider the optimization problem
\(\max_x\{\langle x,U\rangle+Kf(x):x\geq0,\ \sum_\theta x_{\theta k}=1,\ g_\theta(x_\theta)\geq\rho_\theta\ \text{for all }\theta\}\).
Proposition. Under the assumptions of the repair lemma, the optimum of this problem is at least \(V^*(v)\).
Proof. Let \(x^*\) attain \(V^*(v)\). Such an allocation exists because the true feasible set is nonempty and compact.
If conclusion 2 of the lemma holds, its allocation \(z\) satisfies, using \(U\geq v\),
\(\langle z,U\rangle+Kf(z)\geq V^*(v)-(2b/a)f(x^*)+(K/2)f(x^*)\geq V^*(v)\).
The last inequality follows from \(K/2\geq2b/a\).
Otherwise, conclusion 1 gives
\(V^*(v)\leq1+(2b/a)f(x^*)\).
Every allocation entry is at most one, so
\(f(B)=\sum_{\theta,k}\rho_\theta r_{\theta k}\geq\rho_{\min}f(x^*)\).
Consequently,
\(\langle B,U\rangle+Kf(B)\geq1+K\rho_{\min}f(x^*)\geq V^*(v)\).
The baseline is robustly proportional, so it is an admissible witness. \(\square\)
Let \(x\) maximize the robust bonus objective. Since
\(0\leq U_{\theta k}-v_{\theta k}\leq2r_{\theta k}\),
the proposition implies
\(V^*(v)-F_v(x)\leq(K+2)f(x)\).
After dividing by \(m\), this is the required one-round regret bound in terms of uncertainty on the allocation actually used.
The robust optimization above is an ordinary rational LP after introducing dual variables.
For each type, the minimization defining \(g_\theta\) has dual
\(g_\theta(x_\theta)=\max\{\lambda_\theta+\sum_k\ell_{\theta k}\alpha_{\theta k}-\sum_ku_{\theta k}\beta_{\theta k}:\lambda_\theta+\alpha_{\theta k}-\beta_{\theta k}=x_{\theta k},\ \alpha_{\theta k},\beta_{\theta k}\geq0\}\),
where \(\lambda_\theta\) is unrestricted.
This follows by attaching multipliers \(\lambda_\theta\), \(\alpha_{\theta k}\), and \(\beta_{\theta k}\) to normalization, lower bounds, and upper bounds respectively. Strong LP duality applies because \(C_\theta\) is nonempty and compact, so the primal has a finite attained optimum.
Therefore, robust proportionality is equivalent to the existence of these variables satisfying
\(\lambda_\theta+\sum_k\ell_{\theta k}\alpha_{\theta k}-\sum_ku_{\theta k}\beta_{\theta k}\geq\rho_\theta\).
The resulting LP has \(O(\tau m)\) variables and constraints. It is feasible because it contains \(B\), and its objective is bounded because allocation entries lie in \([0,1]\). Rational linear programming admits exact optimization in polynomial bit complexity; see, for example, the [Princeton presentation of the LP-in-\(\mathrm P\) theorem](https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/LinearProgrammingIII.pdf).
It remains to specify rational radii and prove the probability and cumulative regret bounds.
Let
\(h=\lceil\log_2(12dT^2)\rceil\),
\(N_0=\max\{1,\lceil128\sigma^2h/a^2\rceil\}\), and
\(H_0=\lceil(m/\rho_{\min})(2N_0+8h)\rceil\).
These integers are computable using rational arithmetic and integer comparisons.
For a positive sample count \(n\), let \(j_n\) be the least integer satisfying \(n2^{2j_n}\geq2h\), and define
\(r(n)=\sigma2^{j_n}\).
Then
\(\sigma\sqrt{2h/n}\leq r(n)<2\sigma\sqrt{2h/n}\).
In particular, \(n\geq N_0\) implies \(r(n)\leq a/4\).
The algorithm is:
Nonemptiness of a row confidence polytope is checked by
\(\ell_{\theta k}\leq u_{\theta k}\) for every coordinate and
\(\sum_k\ell_{\theta k}\leq1\leq\sum_ku_{\theta k}\).
Every step uses only the permitted history.
For each pair, imagine generating its independent reward sequence in advance and revealing successive elements when that pair is selected. This represents the stipulated fresh-draw model. Its first \(n\) observations are independent draws from that pair’s stationary law, regardless of when they are revealed.
The sub-Gaussian assumption gives
\(\Pr(|\widehat v_{\theta k,n}-v_{\theta k}|>r(n))\leq2e^{-h}\).
A union bound over all \(d\) pairs and \(1\leq n\leq T\) yields a simultaneous confidence event \(E_C\) with
\(\Pr(E_C^c)\leq2dTe^{-h}\leq1/(6T)\).
On \(E_C\), every confidence polytope formed by the algorithm contains its true normalized mean row.
Now suppose \(H_0<T\). During the initial phase, a pair \((\theta,k)\) is selected independently each round with probability \(\rho_\theta/m\). Its count is therefore binomial, with expectation
\(\mu_{\theta k}=H_0\rho_\theta/m\geq2N_0+8h\).
For a binomial variable of mean \(\mu\), the multiplicative Chernoff bound states
\(\Pr(N\leq\mu/2)\leq e^{-\mu/8}\).
Since \(N_0\leq\mu_{\theta k}/2\), it follows that
\(\Pr(N_{\theta k}<N_0)\leq e^{-h}\).
Thus the event \(E_N\) that every pair has at least \(N_0\) initial observations satisfies
\(\Pr(E_N^c)\leq de^{-h}\leq1/(12T^2)\).
When \(H_0\geq T\), define \(E_N\) to hold automatically.
On \(E_C\cap E_N\), all initial allocations are proportional, and every subsequent allocation is robustly proportional for a confidence set containing the truth. Proportionality therefore holds at every round on this same event.
Let \(I_t\) indicate that round \(t\) uses the robust LP. Define \(Y_t\) to equal the radius of the selected pair when \(I_t=1\), and zero otherwise.
Before the item arrives, the choice of \(I_t\), the allocation, and all radii are determined by the history. Uniform item arrivals therefore give
\(\mathbb E[Y_t\mid\mathcal H_t]=I_tf(x_t)/m\).
Pathwise, \(0\leq Y_t\leq a/4\): the algorithm uses the LP only after all counts reach \(N_0\). Hence the martingale differences
\(\mathbb E[Y_t\mid\mathcal H_t]-Y_t\)
have absolute value at most \(a/4\). Azuma–Hoeffding gives an event \(E_M\), of probability at least \(1-1/(3T)\), on which
\(\sum_tI_tf(x_t)/m\leq\sum_tY_t+(a/4)\sqrt{2T\ln(3T)}\).
The realized sum has a deterministic bound. Whenever a pair is selected, its count increases by one. Thus, writing \(N_{\theta k}^T\) for final counts,
\(\sum_tY_t\leq2\sigma\sqrt{2h}\sum_{\theta,k}\sum_{n=1}^{N_{\theta k}^T-1}n^{-1/2}\leq4\sigma\sqrt{2h}\sum_{\theta,k}\sqrt{N_{\theta k}^T}\).
Here \(\sum_{n=1}^{N-1}n^{-1/2}\leq2\sqrt N\), as follows by comparison with the integral of \(s^{-1/2}\). Since \(\sum_{\theta,k}N_{\theta k}^T=T\), Cauchy–Schwarz gives
\(\sum_tY_t\leq4\sigma\sqrt{2hdT}\).
On \(E_C\cap E_N\cap E_M\), every round after the initial phase uses the LP. Section 3 bounds its regret by \((K+2)f(x_t)/m\). Each initial round has regret at most \(b\), because \(W^*(v)\leq b\) and baseline welfare is nonnegative. Consequently,
\(R_T\leq b\min\{T,H_0\}+(K+2)\left(4\sigma\sqrt{2hdT}+(a/4)\sqrt{2T\ln(3T)}\right)\).
The joint event has probability at least
\(1-1/(6T)-1/(12T^2)-1/(3T)\geq1-1/T\).
Finally,
\(H_0=O_{a,\sigma}((m/\rho_{\min})h)\)
and
\(\min\{T,H_0\}\leq\sqrt{TH_0}\).
Together with \(K=4b/(a\rho_{\min})\) and \(h=O(\log(dT))\), this proves
\(R_T=O_{a,b,\sigma}\!\left(\rho_{\min}^{-1}\sqrt{\tau mT\log(\tau mT)}\right)\).
This covers also the case \(H_0\geq T\), where the algorithm uses the baseline throughout.
Empirical means are rational with encoding length polynomial in \(L+\log T\). The radii, confidence endpoints, bonus coefficient, and initial-phase thresholds also have polynomial encoding length. The exponent \(j_n\) is found by integer comparisons over \(O(\log T+\log h)\) possible exponents.
Thus each round requires polynomial-time rational arithmetic and at most one LP of polynomial size, giving computation time \(\operatorname{poly}(m,\tau,L,\log T)\).
The algorithm outputs probabilities for the explicitly supported types. Recipient selection and normalized member sampling are precisely the operations stipulated in the question; no population members or unsupported types are enumerated.
The guarantee is therefore resolved affirmatively.
⟨structured verdict parsed — rendered above⟩
The prover’s affirmative answer is correct and rigorous as written. The algorithm meets the requested computational requirement and establishes the stronger stated regret bound on the same event as proportionality at every round. I found no major or minor mathematical issues requiring repair.
The baseline allocation \(B_{\theta k}=\rho_\theta\) satisfies the column constraints because the masses sum to one. Its proportionality follows exactly from normalization:
\(\sum_k B_{\theta k}v_{\theta k}=\rho_\theta\).
Its unnormalized welfare is therefore \(F_v(B)=1\).
Under the explicitly stated assumption that each confidence polytope contains the true mean row, the confidence-error inequality is valid. The coordinate intervals have width at most \(2r_{\theta k}\), and nonnegative allocation entries preserve the coordinatewise bound when summed. Nonempty confidence polytopes are compact, so the minima defining \(g_\theta\) are attained.
Normalization also makes \(B\) robustly proportional, including when a confidence polytope has empty interior or consists of a single point.
Since the original allocation is proportional for the true means, every robust deficit satisfies
\(d_\theta\leq 2\sum_k x_{\theta k}r_{\theta k}\).
Hence \(D\leq 2f(x)\), as claimed.
When \(D=0\), choosing \(z=x\) satisfies both requirements of conclusion 2.
In Case 1, the identity
\(\sum_\theta c_\theta=1+S-D\)
follows from the definitions of surplus and deficit and from \(\sum_\theta\rho_\theta=1\). The subsequent bound uses \(b/a\geq1\) and \(D\leq2f(x)\) correctly:
\(F_v(x)\leq1+(2b/a)f(x)\).
There is no sign error in this calculation.
In Case 2, both divisions are justified: \(D>0\) by the case setup, and \(S\geq(b/a)D>0\). Each donor also has \(M_\theta>0\), because its robust value exceeds its positive mass.
The proposed removal fraction satisfies
\(q_\theta/M_\theta\leq bD/(aS)\leq1\).
Thus donor allocations remain nonnegative. The deficit weights sum to one, so redistribution preserves every column sum.
For donors, positive homogeneity of the already defined minimum gives the displayed robust-value formula. The inequalities
\(c_\theta\leq bM_\theta\) and \(bq_\theta\leq s_\theta\)
justify preservation of donor proportionality.
For deficit types, all candidate means are at least \(a\), so the added allocation supplies at least the claimed robust value. Types with neither surplus nor deficit remain feasible without modification.
The welfare-loss estimate correctly charges at most \(bD/a\) for removals. The uncertainty-loss estimate correctly charges at most \(D/4\), using the radius assumption. Together with \(D\leq2f(x)\), these establish both conclusions concerning \(z\). The lemma is valid.
The true feasible set is nonempty and compact, so an optimizer \(x^*\) exists.
If conclusion 2 of the lemma applies, the bonus compensates for its stated welfare loss because
\(K/2\geq2b/a\).
This uses \(\rho_{\min}\leq1\), which follows from the positive masses summing to one.
Otherwise, the baseline comparison is valid. Every allocation entry is at most one, and therefore
\(f(B)\geq\rho_{\min}f(x^*)\).
The chosen bonus is sufficient for conclusion 1 as well.
On the confidence event, the untruncated upper estimate satisfies
\(0\leq U_{\theta k}-v_{\theta k}\leq2r_{\theta k}\).
Comparing the maximizing objective with \(V^*(v)\) consequently gives exactly the stated one-round regret bound. Division by \(m\) matches the task’s welfare normalization.
The displayed dual has the correct signs, equality constraints, and unrestricted normalization multiplier. Its primal is feasible with a finite optimum whenever the confidence polytope is nonempty. Strong LP duality supplies an attained dual optimum, so the existential dual formulation of robust proportionality is exact.
The formulation has polynomially many variables and constraints. Its feasible set contains a representation of \(B\), and its objective is bounded because allocation entries lie in \([0,1]\). Unbounded auxiliary dual variables do not invalidate exact LP optimization.
The invoked polynomial-time theorem for rational LP applies to these hypotheses. The cited [Princeton presentation](https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/LinearProgrammingIII.pdf), particularly slides 8 and 15, addresses optimization through feasibility, bit complexity, and recovery of an exact solution. No strict feasibility or full-dimensionality assumption is needed here.
The integer \(j_n\) exists for every positive count, including when it is negative. Its minimality gives precisely
\(\sigma\sqrt{2h/n}\leq r(n)<2\sigma\sqrt{2h/n}\).
The threshold constant is sufficient: for \(n\geq N_0\), the latter upper bound is at most \(a/4\). Thus every round using the LP satisfies the repair lemma’s radius hypothesis, even outside the confidence event.
The confidence-polytope nonemptiness test is correct for a box intersected with the normalization hyperplane.
All branches use permitted history. Insufficient initial counts cause baseline allocation thereafter; empty confidence sets cause baseline allocation for that round. These branches make the algorithm defined on failure histories as well as successful ones.
The pre-generated reward-sequence representation is legitimate under the stipulated fresh independent draws. It permits the union bound over fixed sample counts despite adaptive selection.
The sub-Gaussian tail estimate has the correct constant. Since
\(h\geq\ln(12dT^2)\),
the confidence failure bound is at most \(1/(6T)\). Using a base-two logarithm in the definition of \(h\) does not weaken this inequality.
During baseline exploration, pair counts have the claimed binomial distribution. Their means satisfy
\(\mu_{\theta k}\geq2N_0+8h\).
Consequently, the stated Chernoff inequality yields the pairwise failure bound \(e^{-h}\), and the union bound gives \(1/(12T^2)\).
On the intersection of the confidence and count events, every allocation is proportional for the true means. This proves simultaneous proportionality across all rounds, rather than separate marginal guarantees.
Before an item arrives, the allocation, LP indicator, and applicable radii are history-measurable. Uniform item arrivals and the specified recipient probabilities therefore give the displayed conditional expectation of \(Y_t\).
The bound \(0\leq Y_t\leq a/4\) holds pathwise. Azuma–Hoeffding consequently gives the stated deviation term and failure probability without conditioning on the confidence event.
The realized uncertainty sum correctly uses pre-selection counts. Each selection increments its pair count, so a positive count can contribute at most once for that pair. The bound by reciprocal square roots, its integral estimate, and the subsequent Cauchy–Schwarz inequality all have the correct direction and constants.
On the joint event, all rounds after the initial phase use the LP. Each initial round has regret at most \(b\), and subsequent regret is bounded by the uncertainty estimate already verified.
The failure probabilities sum to at most
\(1/(6T)+1/(12T^2)+1/(3T)\leq1/T\).
Independence between these events is unnecessary.
The estimates for \(H_0\), \(K\), and \(h\), together with
\(\min\{T,H_0\}\leq\sqrt{TH_0}\),
yield the claimed bound with constants depending only on \(a,b,\sigma\).
The case \(H_0\geq T\) is explicitly covered. The argument also remains valid for \(m=1\), \(\tau=1\), and degenerate confidence polytopes. There is no missing substantive boundary case.
Empirical means, thresholds, radii, confidence endpoints, and objective coefficients have polynomial encoding length in the specified inputs and observed history. Computing a threshold with a potentially large numerical value requires its binary representation, not enumeration up to that value.
Exact rational LP optimization therefore gives polynomial computation per round. The algorithm operates only on the explicitly supported types and invokes member sampling as stipulated by the task; it does not require a finite representation or enumeration of the atomless populations.
No additional clarification, missing lemma, or corrective prover round is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.