Answer: Randomized polynomial-time solvable with polynomial sample complexity in the stated sampling-interface model.
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet ˜ M = l log(3/δ) λ m and K = l log(3 ˜ M/δ) log(1/(1−γ)) m . With probability 1 −δ, AUDIT is correct, it satisfies the conservative constraint (3) for all ˜ M target users, and the bounds on duration and cost from Th. 1 (using δ 3 ˜ M instead of δ) are simultaneously valid.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support \(T\) of complete user types \(t=(q_t,\nu_t,\pi_t)\), with rational masses (\mu_t)_{t\in T} summing to one, define (U_t(s)) as type \(t\)’s expected reward when shown type \(s\)’s policy. Can an adaptive audit, using reward samples from target types and source policies drawn according to \mu, with confidence \(1-\delta\), certify that the mass of types \(t\) for which \sum_{s\in T}\mu_s\mathbf{1}[U_t(s)>U_t(t)+\epsilon]>\gamma is at most \lambda, or report evidence to the contrary, while ensuring that each audited type’s average expected reward at every horizon is at least (1-\alpha)U_t(t)\)? Characterize its duration and utility-loss guarantees.
A society is given by its support: the list of the \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts supported types, not possible types. Let \(L\) be the bit length of the support identifiers, masses, and rational audit parameters.
Each stationary type \(t=(q_t,\nu_t,\pi_t)\) has a context distribution, conditional reward distributions supported on \([0,1]\), and a recommendation policy on common nonempty finite context and item sets; write \(m\) for their combined cardinality.
Types identify sampling interfaces, not numerical descriptions of unknown rewards. Showing source policy \(s\) to target \(t\) produces an independent sample via \(x\sim q_t\), \(a\sim\pi_s(\cdot\mid x)\), \(r\sim\nu_t(\cdot\mid x,a)\), with mean \(U_t(s)=\mathbb E[r]\); each interface call has unit cost.
Targets and source policies can be drawn independently with replacement according to \(\mu\). The auditor may adaptively reuse sampled source policies and may always show each target its own baseline policy.
Take \(\epsilon,\alpha\in(0,1]\), \(\gamma,\lambda\in(0,1)\), \(\delta\in(0,1/2)\), and assume \(b=\min_{t\in T}U_t(t)>0\); baseline means are unknown.
Define \(E_t=\sum_{s\in T}\mu_s\mathbf 1[U_t(s)>U_t(t)+\epsilon]\) and \(B=\sum_{t\in T}\mu_t\mathbf 1[E_t>\gamma]\).
With joint probability at least \(1-\delta\), the audit must terminate and either certify \(B\le\lambda\) or return a witnessed pair \((t,s)\) with \(U_t(s)>U_t(t)\). These alternatives may overlap.
For every audited target stream of type \(t\), with chosen sources \(s_{t,j}\), require \(\sum_{j=1}^{h}U_t(s_{t,j})\ge h(1-\alpha)U_t(t)\) at every horizon before stopping, on the same joint event.
If that stream stops at \(H_t\), its utility loss is \(C_t=H_tU_t(t)-\sum_{j=1}^{H_t}U_t(s_{t,j})\), which may be negative. Duration is the maximum stream length under parallel execution; total reward samples are counted separately.
Is this sample-access auditing problem solvable with polynomial computation and sample complexity in \(m,\tau,L,\epsilon^{-1},\gamma^{-1},\lambda^{-1},\alpha^{-1},b^{-1},\log(1/\delta)\), or is it NP-hard? What duration and utility-loss guarantees are achievable?
For a finite uniformly weighted user list, a conservative audit has population-size-independent target and source-policy counts, simultaneous duration and loss bounds, and a negative output witnessing strict pairwise envy. [Do et al.](https://arxiv.org/pdf/2104.14527v5)
No result specifically formulated for arbitrary rational type masses was verified.
The auditing problem is solvable with polynomial computation and sample complexity in the stated sampling-interface model, for arbitrary rational type masses. The proof below gives simultaneous duration, utility-loss, and correctness guarantees.
The algorithm uses population-size-independent target and source-policy counts. Its bounds do not depend on \(b^{-1}\), and baseline means need not be known. The bounds are achievable bounds; no optimality claim is made.
For \(\epsilon=1\), every \(E_t=0\), so immediate certification is valid. The construction below also handles this case.
All logarithms in the construction have base \(2\). Define
\(K=\left\lceil\lambda^{-1}\left\lceil\log_2(8/\delta)\right\rceil\right\rceil,\qquad R=\left\lceil\gamma^{-1}\left\lceil\log_2(8K/\delta)\right\rceil\right\rceil.\)
Draw \(K\) targets independently from \(\mu\), and independently draw \(R\) source policies from \(\mu\). Reuse the same source-policy list for all targets. Repeated identifiers are allowed.
Set
\(J=\left\lceil\log_2(8/\epsilon)\right\rceil,\qquad \rho_\ell=2^{-\ell}\quad(0\le\ell\le J),\qquad \eta=\rho_J,\)
\(c=\left\lceil\log_2\!\left(\frac{8K[1+R(J+1)]}{\delta}\right)\right\rceil,\qquad n_\ell=\left\lceil\frac{c}{2\rho_\ell^2}\right\rceil,\qquad N=n_J.\)
In particular,
\(\epsilon/16<\eta\le\epsilon/8,\qquad N\le128c\epsilon^{-2}+1.\)
Run one target stream for each target draw. For every stream \(i\), write \(u_i=U_{t_i}(t_i)\), and let \(H_i\) and \(C_i\) denote its duration and utility loss.
The construction guarantees, simultaneously with probability at least \(1-\delta\):
Moreover, termination and the following bounds hold deterministically in the supplied sampling-interface model:
\(D:=\max_i H_i\le RN+\max\!\left\{N,\left\lceil\frac{(1-\alpha)RN}{\alpha}\right\rceil\right\}\le N+\frac{RN}{\alpha}+1,\)
\(\text{total reward samples}\le KD.\)
Thus, with
\(c=O\!\left(\log\!\frac{KR[1+\log(1/\epsilon)]}{\delta}\right),\)
the achievable bounds are
\(D=O\!\left(\frac{Rc}{\alpha\epsilon^2}\right),\qquad \text{total reward samples}=O\!\left(\frac{KRc}{\alpha\epsilon^2}\right),\qquad C_i=O\!\left(\frac{Rc}{\epsilon}\right).\)
There are \(K\) target draws and \(R\) sampled source-policy draws, in addition to the targets’ own baseline policies.
Fix a target stream with baseline mean \(u\). Let \(p\) count baseline calls and \(e\) count calls using sampled source policies.
First make \(N\) baseline calls. Before each subsequent source-policy call, insert the minimum number of baseline calls needed to ensure
\(\alpha p\ge(1-\alpha)(e+1).\)
Then make that source-policy call and increment \(e\).
At every prefix, this schedule maintains
\(\alpha p\ge(1-\alpha)e.\)
All source means are nonnegative. Consequently, the cumulative mean utility at this prefix is at least \(pu\). The scheduling inequality gives
\(pu\ge(1-\alpha)(p+e)u.\)
This proves the required conservative constraint at every horizon, on every sample path. In particular, it does not depend on confidence intervals being correct.
After any completed source-policy call, the baseline count is exactly
\(p=\max\!\left\{N,\left\lceil\frac{(1-\alpha)e}{\alpha}\right\rceil\right\}.\)
Each source policy will receive at most \(N\) calls, so \(e\le RN\). This proves the stated duration and total-sample bounds.
The tests can use bounded-precision observations. Put \(\kappa=\eta/2\), and replace each observed reward \(r\) by
\(r^{\mathrm q}=\kappa\lfloor r/\kappa\rfloor.\)
Then \(r^{\mathrm q}\in[0,1]\) and \(0\le r-r^{\mathrm q}\le\kappa\). Only \(O(\log(1/\epsilon))\) fractional bits are retained.
For target \(t_i\), let \(\widehat u_i\) be the average of its first \(N\) quantized baseline rewards.
Process its sampled source policies in order. For a source \(s_j\), progressively collect \(n_\ell\) cumulative source rewards at stages \(\ell=0,\ldots,J\), using the conservative schedule above. Let \(\widehat v_{ij,\ell}\) be their quantized average, and define
\(a_\ell=\rho_\ell+2\eta,\)
\(L_{ij,\ell}=\widehat v_{ij,\ell}-\widehat u_i-a_\ell,\qquad V_{ij,\ell}=\widehat v_{ij,\ell}-\widehat u_i+a_\ell.\)
At each stage:
At stage \(J\),
\(V_{ij,J}-L_{ij,J}=6\eta\le3\epsilon/4.\)
Hence, if the witness condition fails, then
\(V_{ij,J}\le6\eta<\epsilon,\)
so the source is discarded. Thus every source test terminates, even if confidence intervals are incorrect.
Allow all streams to finish. If any stream recorded a witness, return one. Otherwise, certify \(B\le\lambda\).
Condition on the target and source draws. For analysis, expose in advance independent reward sequences for every stream and source-list position, including sequences that the algorithm never queries. This realizes the stipulated sampling process and permits concentration bounds despite adaptive stopping.
For independent observations \(Y_1,\ldots,Y_n\in[0,1]\) with common mean \(w\), Hoeffding’s inequality states
\(\Pr\!\left(\left|n^{-1}\sum_{h=1}^nY_h-w\right|>r\right)\le2\exp(-2nr^2).\)
Apply this to the quantized baseline average with radius \(\eta\), and to each source-stage average with radius \(\rho_\ell\). By the definitions of the sample sizes, each failure probability is at most \(2e^{-c}\).
There are at most \(K[1+R(J+1)]\) such averages. Since \(c\ge\ln(8K[1+R(J+1)]/\delta)\), their union failure probability is at most \(\delta/4\).
Let \(\mathcal A\) denote the resulting simultaneous confidence event. Quantization changes each mean by at most \(\kappa\). On \(\mathcal A\),
\(\left|\widehat v_{ij,\ell}-\widehat u_i-\bigl(U_{t_i}(s_j)-U_{t_i}(t_i)\bigr)\right|\le\rho_\ell+\eta+2\kappa=a_\ell.\)
Therefore,
\(L_{ij,\ell}\le U_{t_i}(s_j)-U_{t_i}(t_i)\le V_{ij,\ell}.\)
Two conclusions follow:
These statements hold simultaneously for all streams and all stages.
Define the bad-target set
\(G=\{t:E_t>\gamma\}.\)
Its mass is \(\mu(G)=B\). Suppose \(B>\lambda\). The probability that all \(K\) target draws miss \(G\) is
\((1-B)^K\le e^{-\lambda K}\le\delta/8.\)
For any fixed target \(t\in G\), its set of sources satisfying
\(U_t(s)>U_t(t)+\epsilon\)
has mass \(E_t>\gamma\). Hence the probability that the shared list of \(R\) independently drawn sources misses this set is at most
\((1-E_t)^R\le e^{-\gamma R}\le\delta/(8K).\)
Conditioning on all target draws and taking a union bound, the probability that some sampled bad target lacks such a sampled source is at most \(\delta/8\). Independence between the different targets’ source-hit events is unnecessary.
It follows that, when \(B>\lambda\), with probability at least \(1-\delta/4\) the sampled lists contain an improvement greater than \(\epsilon\).
On this sampling event and \(\mathcal A\), its target stream either returns an earlier valid witness or reaches that source. The source cannot be discarded and its test must terminate, so the stream returns a witness.
Thus, on a joint event of probability at least \(1-\delta/2\), every witness is valid and every certificate is valid. This argument uses the masses directly; no replication into a uniformly weighted population is required.
Fix a stream and work on \(\mathcal A\). Consider a sampled source with negative improvement. Write
\(\Delta=u-U_t(s)>0.\)
At stage \(\ell\), confidence validity gives
\(V_\ell\le-\Delta+2a_\ell=-\Delta+2\rho_\ell+4\eta.\)
Since \(4\eta\le\epsilon/2\), this source is discarded whenever
\(2\rho_\ell\le\Delta+\epsilon/2.\)
Let \(\ell_*\) be the first stage satisfying that inequality. It exists because \(\rho_J=\eta\le\epsilon/8\). Also, \(\ell_*\ge1\), since \(\Delta\le1\) and \(\epsilon\le1\). Minimality and the dyadic radii imply
\(\rho_{\ell_*}>(\Delta+\epsilon/2)/4.\)
Consequently, the number of calls to this source is at most
\(n_{\ell_*}\le\frac{8c}{(\Delta+\epsilon/2)^2}+1.\)
Its loss contribution is therefore at most
\(\Delta n_{\ell_*}\le\frac{8c\Delta}{(\Delta+\epsilon/2)^2}+\Delta\le\frac{4c}{\epsilon}+1.\)
The last inequality follows from
\((\Delta+\epsilon/2)^2\ge2\epsilon\Delta,\qquad \Delta\le1.\)
Baseline calls contribute zero loss. Sources with nonnegative improvement contribute nonpositive loss. Summing over at most \(R\) source-list positions proves
\(C_i\le R(4c/\epsilon+1).\)
This bound remains valid if the stream stops early upon finding another witness. Independently of confidence validity, the conservative constraint also gives
\(C_i\le\alpha H_i u_i.\)
Neither bound asserts that the loss is nonnegative.
All test radii and quantized observations are dyadic rationals. Sample counts and thresholds can be computed with polynomial-bit arithmetic. Each observed reward is used only through comparisons with dyadic numbers having \(O(\log(1/\epsilon))\) bits.
Weighted draws are available by premise. They can also be implemented from the rational support without expanding the population. Take a common denominator \(Q\) equal to the product of the mass denominators; its bit length is at most \(O(L)\). Sampling an integer uniformly from \(\{0,\ldots,Q-1\}\), then locating its cumulative-mass interval, gives an exact \(\mu\)-draw.
For a bounded computation budget, cap rejection sampling for each draw at
\(M=\left\lceil\log_2(2(K+R)/\delta)\right\rceil\)
attempts. Each attempt accepts with probability at least \(1/2\), so the probability that any draw exhausts its cap is at most \(\delta/2\). Perform these draws before starting streams; on exhaustion, terminate with the certificate output and count this event as failure. Successful capped draws have exactly the required distribution.
Combining this additional failure probability with Sections 4–5 yields the promised joint success probability \(1-\delta\), with bounded polynomial computation.
The population-independent sampling principle matches the uniformly weighted audit in [Do et al., Section 4.5](https://arxiv.org/html/2104.14527v5). The weighted argument and conservative bounds above are proved directly, rather than relying on an unverified arbitrary-mass extension.
⟨structured verdict parsed — rendered above⟩
Assessment: proved with one minor clarification about numerical access to sampled rewards. The probability argument, conservative schedule, termination proof, and utility-loss calculation are sound. The output resolves the assigned problem under the natural sampling-interface convention that the required finite-precision reward information is accessible in polynomial time.
The algorithm addresses the support-weighted quantities \(E_t\) and \(B\) directly. It does not replace supported types with an expanded population or treat unsupported types as inputs.
Its negative output witnesses \(U_t(s)>U_t(t)\), exactly as required. It need not witness improvement greater than \(\epsilon\). The proof correctly uses improvement greater than \(\epsilon\) only to guarantee detection when \(B>\lambda\).
Allowing a witness when \(B\le\lambda\) is consistent with the task’s overlapping alternatives.
From \(J=\lceil\log_2(8/\epsilon)\rceil\), the claimed inequalities \(\epsilon/16<\eta\le\epsilon/8\) follow, including when \(8/\epsilon\) is a power of two.
Consequently, \(N=\lceil c/(2\eta^2)\rceil\le128c\epsilon^{-2}+1\). The constant is correct.
All counts are finite and positive throughout the specified parameter ranges. The proof’s use of base-two logarithms in exponential probability bounds is valid because \(\log_2 z\ge\ln z\) for the arguments used here.
The scheduling invariant \(\alpha p\ge(1-\alpha)e\) holds initially, during inserted baseline calls, and immediately after each source call.
Every source mean is nonnegative, so cumulative mean utility is at least \(pu\). The scheduling invariant is equivalent to \(pu\ge(1-\alpha)(p+e)u\). Thus the required constraint holds at every prefix, independently of concentration events or observed reward values.
This reasoning concerns the sums of true means required by the task; it does not incorrectly substitute realized rewards.
The case \(\alpha=1\) is covered: no additional baseline calls are needed after the initial batch. Neither knowledge of \(u\) nor a lower bound on \(u\) is used.
At the final stage, \(a_J=3\eta\), hence \(V_{ij,J}-L_{ij,J}=6\eta\). If the witness condition fails, \(L_{ij,J}\le0\), which implies \(V_{ij,J}\le6\eta<\epsilon\). Therefore the discard condition holds. This establishes termination even on incorrect confidence events.
Each source-list position receives at most \(N\) calls. After a completed source call, the stated baseline count follows from inserting the minimum number of calls needed.
The resulting bound \(D\le RN+\max\{N,\lceil(1-\alpha)RN/\alpha\rceil\}\) is correct. Using the ceiling bound gives \(D\le N+RN/\alpha+1\). Total reward samples are consequently at most \(KD\).
Parallel execution and repeated target identifiers do not invalidate these bounds: the algorithm explicitly maintains a separate stream for each target draw.
The stated Hoeffding inequality applies to the pre-exposed sequences: conditional on the sampled identifiers, each sequence consists of independent bounded observations with a common mean. Deterministic quantization preserves these properties.
Pre-exposing unused observations justifies applying concentration at every prescribed stage despite adaptive stopping. The proof does not apply a fixed-sample bound directly to an uncontrolled stopping time.
Each concentration failure has probability at most \(2e^{-c}\). There are at most \(K[1+R(J+1)]\) averages, giving the claimed union bound \(\delta/4\).
The difference-estimation error bound \(\rho_\ell+\eta+2\kappa=a_\ell\) is valid. It conservatively accounts for both quantization errors.
Therefore every recorded witness is strictly valid on \(\mathcal A\), and a source with true improvement greater than \(\epsilon\) cannot be discarded.
When \(B>\lambda\), the probability of missing every bad target is at most \(e^{-\lambda K}\le\delta/8\).
Conditional on the target draws, each sampled bad target has a source-hit failure probability at most \(e^{-\gamma R}\le\delta/(8K)\). A union bound over target positions gives \(\delta/8\), despite sharing the source list.
Independence among different targets’ source-hit events is neither asserted nor needed. Independence between target draws and source draws is supplied by the task.
On the successful sampling event and \(\mathcal A\), a sampled bad target either returns an earlier valid witness or reaches a source that cannot be discarded. Deterministic test termination then forces a witness.
For \(B\le\lambda\), certification is already valid; only witness validity needs the confidence event. Thus the claimed correctness event with failure probability at most \(\delta/2\) is justified in both cases.
For a detrimental source, the bound \(V_\ell\le-\Delta+2\rho_\ell+4\eta\) follows from confidence validity.
The proposed sufficient discard condition \(2\rho_\ell\le\Delta+\epsilon/2\) is correct because \(4\eta\le\epsilon/2\).
The stage \(\ell_*\) exists. It cannot be stage zero because \(2>\Delta+\epsilon/2\), using \(\Delta\le1\) and \(\epsilon\le1\).
Minimality gives \(\rho_{\ell_*}>(\Delta+\epsilon/2)/4\), and therefore the stated call bound \(n_{\ell_*}\le8c/(\Delta+\epsilon/2)^2+1\) is valid.
The critical inequality \((\Delta+\epsilon/2)^2\ge2\epsilon\Delta\) is correct: the difference is \((\Delta-\epsilon/2)^2\). Hence each detrimental source contributes at most \(4c/\epsilon+1\).
Baseline calls have zero loss, and beneficial sources have nonpositive loss. Summing over source-list positions proves \(C_i\le R(4c/\epsilon+1)\). Early stopping can only shorten a detrimental source’s contribution.
The additional deterministic bound \(C_i\le\alpha H_i u_i\) follows directly from the conservative constraint. Negative total loss is correctly allowed.
The product denominator \(Q\) has bit length bounded by the total input length of the mass denominators. Integer interval sampling therefore avoids an exponentially expanded population.
Standard rejection sampling accepts each attempt with probability at least one half. The proposed cap gives total exhaustion probability at most \(\delta/2\).
Conditional on successful capped sampling, the draws retain the required independent distributions: acceptance depends on membership in the accepted integer range, and each accepted integer is uniform in that range.
An exhaustion certificate may be wrong, but the proof explicitly charges this event to the allowed failure probability. Combining it with the preceding \(\delta/2\) bound is valid.
Subject to the observation-access clarification below, the counts and arithmetic have polynomial complexity in the requested parameters. Independence from \(b^{-1}\) is established rather than merely asserted.
For \(\epsilon=1\), bounded rewards make every strict improvement greater than \(\epsilon\) impossible, so immediate certification is valid. The general construction also remains valid.
Equality at the thresholds is handled consistently: discard uses a non-strict inequality, whereas the required witness and the definitions of bad targets and sources use strict inequalities.
The historical population-independent sampling comparison agrees with [Do et al., Section 4.5](https://arxiv.org/html/2104.14527v5#S4.SS5). The submitted proof does not rely on that paper for its arbitrary-mass extension or its quantitative bounds.
Minor — Sections 3 and 7, access to sampled rewards.
The write-up specifies how many bits are retained, but not the computational access provided to an arbitrary real-valued observation. Computing the exact quantization \(r^{\mathrm q}=\kappa\lfloor r/\kappa\rfloor\) presumes access to suitable binary digits or comparisons with dyadic thresholds. A unit-cost sampling call alone does not explicitly specify the cost of those operations.
This is a minor model clarification under the task’s evidently intended sampling-interface interpretation, rather than a gap in the statistical argument.
Minimum clarification: state the reward-observation convention and its cost, explicitly confirming that the finite-precision information used by the stated quantizer is accessible in polynomial time. No additional mathematical argument is needed under that convention.
⟨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.