Answer: \(\mathrm{NP}\)-hard, already for \(\tau=d=T=1\) and \(k=2\), on instances satisfying all promises and conditional regret assumptions.
Theorem 2 — class: algorithmic
Given a finite support of customer cohorts with binary-rational masses \(\mu_\theta\), a shared feasible product space and feature map, a context stream for each cohort, and typewise choice fractions, can one compute cohort query sets and Choice Perceptron updates in polynomial time while attaining the mass-weighted expected average-regret guarantee?
A society is given by its support: the list of the \(\tau\) types with positive binary-rational masses \(\mu_\theta\), normalized by \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
The shared product space \(Y\) is a nonempty bounded set described by rational mixed-integer linear constraints on \(m\) attributes. Each cohort supplies a context stream \((x_{\theta t})_{t=1}^T\); the supplied feature map \(\phi(x,\cdot):Y\to\mathbb R^d\) is rational affine for each context, with \(\|\phi(x,y)\|_2\le R\). True utilities are \(u_\theta^*(x,y)=\langle w_\theta^*,\phi(x,y)\rangle\), with fixed unknown \(w_\theta^*\in\mathbb R^d\), allowing either sign.
Maintain separate estimates \(w_{\theta1}=0\), with constant positive rational step size \(\eta\) and query size \(k\ge2\). Write \(v_{\theta t}(y)=\phi(x_{\theta t},y)\) and \(u_{\theta t}(y)=\langle w_{\theta t},v_{\theta t}(y)\rangle\).
At each round compute an exact maximizing tuple \((y_1,\ldots,y_k)\in Y^k\) for \(t^{-1}\sum_{i=2}^k\|v_{\theta t}(y_1)-v_{\theta t}(y_i)\|_1+(1-t^{-1})\sum_{i=2}^k u_{\theta t}(y_i)\), subject to \(y_1\in\arg\max_{y\in Y}u_{\theta t}(y)\) and pairwise distinct feature vectors. Promise that these constrained maxima exist at every round; any rational maximizing tuple is allowed, with ties resolved deterministically. Set \(Q_{\theta t}=\{y_1,\ldots,y_k\}\).
After issuing the query, receive exact binary-rational choice fractions \(p_{\theta t}(y)\ge0\), summing to one on \(Q_{\theta t}\). They satisfy \(p_{\theta t}(y)\ge p_{\theta t}(z)\iff u_\theta^*(x_{\theta t},y)\ge u_\theta^*(x_{\theta t},z)\). Update \(w_{\theta,t+1}=w_{\theta t}+\eta D_{\theta t}\), where \(D_{\theta t}=\frac{k}{k-1}\sum_{y\in Q_{\theta t}}p_{\theta t}(y)v_{\theta t}(y)-\frac1{k-1}\sum_{y\in Q_{\theta t}}v_{\theta t}(y)\).
Define \(r_{\theta t}=\max_{y\in Y}u_\theta^*(x_{\theta t},y)-\max_{y\in Q_{\theta t}}u_\theta^*(x_{\theta t},y)\), \(h_{\theta t}=\max_{y\in Y}u_\theta^*(x_{\theta t},y)-\min_{y\in Q_{\theta t}}u_\theta^*(x_{\theta t},y)\), and \(M_\theta=\sum_{t=1}^T\mathbf1[\langle w_\theta^*,D_{\theta t}\rangle=0]\).
The guarantee is conditional on constants \(\alpha_\theta\in(0,1]\) and \(\beta_\theta\in\mathbb R\) satisfying \(\langle w_\theta^*,D_{\theta t}\rangle\ge\alpha_\theta h_{\theta t}-2\alpha_\theta R\|w_\theta^*\|_2\mathbf1[\langle w_\theta^*,D_{\theta t}\rangle=0]\) at every round and \(T^{-1}\sum_t\langle w_{\theta t},D_{\theta t}\rangle\le\beta_\theta\), with \(2\beta_\theta/\eta+4R^2\ge0\).
The required mass-weighted expected average-regret bound is \(\mathbb E[T^{-1}\sum_{t,\theta}\mu_\theta r_{\theta t}]\le\sum_\theta\mu_\theta\bigl(\frac{\|w_\theta^*\|_2\sqrt{2\beta_\theta/\eta+4R^2}}{\alpha_\theta\sqrt T}+\frac{2R\|w_\theta^*\|_2M_\theta}{T}\bigr)\). Exact cohort fractions and deterministic tie choices make this trajectory deterministic.
Can these cohort queries and Choice Perceptron updates be computed while attaining the stated conditional regret bound in time polynomial in \(m,\tau,d,k,T,L\), or is this computational problem NP-hard? Here \(L\) is the total bit length of the supplied constraints, feature maps, contexts, numerical parameters, masses, and received fractions; response generation is external.
For an individual user with sampled choice feedback, Choice Perceptron has the corresponding conditional expected-regret bound; this is not a polynomial-time query-selection theorem. Exact query selection is formulated using mixed-integer optimization ([source](https://arxiv.org/pdf/1711.07875)).
No result settling this exact cohort formulation was located.
The computational problem is \(\mathrm{NP}\)-hard, already for \(\tau=d=T=1\) and \(k=2\). The hardness persists on instances satisfying every stated promise and both conditional regret assumptions.
The stated regret bound nevertheless holds for the exact-fraction updates. Thus the statistical guarantee and the difficulty of exact query selection are compatible.
Let \(F\) be a Boolean formula in conjunctive normal form with three literals per clause, on variables \(a_1,\ldots,a_n\). We use the standard fact that deciding satisfiability of such formulas is \(\mathrm{NP}\)-complete.
For a literal \(\ell\), define its affine truth indicator by
\(\lambda_{a_i}(a)=a_i,\qquad \lambda_{\neg a_i}(a)=1-a_i.\)
Construct products \(y=(a,z,s)\), with \(m=n+2\) attributes, and define \(Y\) by the rational mixed-integer linear constraints
\(a_i\in\{0,1\},\qquad z\in\{0,1\},\qquad s\in\mathbb Z,\qquad 0\le s\le2,\qquad s\le1+z,\)
together with, for every clause \(C\) of \(F\),
\(\displaystyle \sum_{\ell\in C}\lambda_\ell(a)\ge z.\)
Take one cohort of mass \(\mu_1=1\), one constant context, and
\(\tau=d=T=1,\qquad k=2,\qquad \eta=1,\qquad \phi(x,(a,z,s))=\frac{s}{2},\qquad R=1.\)
This construction has encoding length polynomial in the length of \(F\).
For every Boolean assignment \(a\), choosing \(z=0\) makes every clause constraint hold, because each literal indicator is nonnegative. Both \(s=0\) and \(s=1\) are then feasible. Consequently, \(Y\) is nonempty and contains two distinct feature vectors.
The set \(Y\) is finite and bounded, and all its products have integer coordinates. Hence every constrained query maximum exists and has a rational maximizing tuple. Also,
\(\displaystyle |\phi(x,y)|=\frac{s}{2}\le1=R.\)
Finally, a product with \(s=2\) exists if and only if \(F\) is satisfiable:
Thus the attainable feature set is precisely
\(\displaystyle \phi(x,Y)= \begin{cases} \{0,\frac12\},&F\text{ is unsatisfiable},\\ \{0,\frac12,1\},&F\text{ is satisfiable}. \end{cases}\)
At the first round, \(w_{11}=0\), so every product maximizes the estimated utility. With \(T=1\) and \(k=2\), the query objective reduces to
\(\displaystyle |\phi(x,y_1)-\phi(x,y_2)|.\)
Its maximum is therefore
\(\displaystyle \begin{cases} \frac12,&F\text{ is unsatisfiable},\\ 1,&F\text{ is satisfiable}. \end{cases}\)
Every maximizing tuple uses the smallest and largest attainable features. Hence, regardless of deterministic tie resolution,
\(\displaystyle F\text{ is satisfiable}\quad\Longleftrightarrow\quad \max\{s(y_1),s(y_2)\}=2.\)
A polynomial-time algorithm returning the required exact query would therefore decide satisfiability in polynomial time. This proves \(\mathrm{NP}\)-hardness of query selection, and consequently of the requested combined computation.
The hardness does not rely on violating the feedback model or the conditions attached to the guarantee.
Choose the fixed, nonzero true weight \(w_1^*=1\). For the issued pair, let \(y^+\) have the larger feature and \(y^-\) the smaller feature. Supply the exact binary-rational fractions
\(p_{11}(y^+)=1,\qquad p_{11}(y^-)=0.\)
Since the features are distinct and true utility equals the feature, these fractions satisfy the stipulated ordering equivalence. Generating them only requires comparing the returned coordinates.
Write
\(\delta=\phi(x,y^+)-\phi(x,y^-)\in\{\frac12,1\}.\)
For \(k=2\), the update gives
\(\displaystyle D_{11} =2\phi(x,y^+)-\phi(x,y^+)-\phi(x,y^-) =\delta.\)
Because an exact maximizing pair contains both extreme features,
\(\langle w_1^*,D_{11}\rangle=\delta,\qquad h_{11}=\delta,\qquad r_{11}=0,\qquad M_1=0.\)
Take \(\alpha_1=1\) and \(\beta_1=0\). The first conditional inequality holds with equality. The second holds because
\(\langle w_{11},D_{11}\rangle=0=\beta_1.\)
The remaining numerical condition also holds:
\(2\beta_1/\eta+4R^2=4\ge0.\)
Thus every instance produced by the reduction satisfies all promises, with fixed conditional constants and a nonzero true utility weight. The first query already reveals satisfiability before any response is needed.
Fix a cohort and suppress its index. Write \(v_{ti}=v_t(y_i)\) and \(p_{ti}=p_t(y_i)\).
The update can be rewritten as
\(\displaystyle D_t=\sum_{i=1}^k p_{ti} \left(v_{ti}-\frac1{k-1}\sum_{j\ne i}v_{tj}\right). \)
Each vector in parentheses has norm at most \(2R\): the first term has norm at most \(R\), and the second is an average of vectors of norm at most \(R\). Since the fractions are nonnegative and sum to one, the triangle inequality yields
\(\|D_t\|_2\le2R.\)
Expanding \(w_{t+1}=w_t+\eta D_t\) gives
\(\displaystyle \|w_{t+1}\|_2^2 =\|w_t\|_2^2+2\eta\langle w_t,D_t\rangle+\eta^2\|D_t\|_2^2. \)
Summing over rounds, using \(w_1=0\), the update norm bound, and the assumed average bound on \(\langle w_t,D_t\rangle\), gives
\(\displaystyle \|w_{T+1}\|_2^2 \le2\eta\beta T+4\eta^2R^2T =\eta^2T\left(\frac{2\beta}{\eta}+4R^2\right). \)
The assumed nonnegativity of the expression in parentheses therefore implies
\(\displaystyle \|w_{T+1}\|_2 \le\eta\sqrt T\sqrt{\frac{2\beta}{\eta}+4R^2}. \)
By their definitions, \(0\le r_t\le h_t\). Summing the assumed conditional informativeness inequality therefore gives
\(\displaystyle \alpha\sum_{t=1}^T r_t \le\sum_{t=1}^T\langle w^*,D_t\rangle +2\alpha R\|w^*\|_2M. \)
The update recurrence and \(w_1=0\) imply
\(\displaystyle \sum_{t=1}^T\langle w^*,D_t\rangle =\frac{\langle w^*,w_{T+1}\rangle}{\eta} \le\frac{\|w^*\|_2\|w_{T+1}\|_2}{\eta}, \)
where the last inequality is Cauchy–Schwarz. Substituting the norm bound and dividing by \(\alpha T\) yields
\(\displaystyle \frac1T\sum_{t=1}^T r_t \le \frac{\|w^*\|_2\sqrt{2\beta/\eta+4R^2}}{\alpha\sqrt T} +\frac{2R\|w^*\|_2M}{T}. \)
Apply this argument separately to each cohort, multiply by its nonnegative mass, and sum. This proves
\(\displaystyle \frac1T\sum_{t,\theta}\mu_\theta r_{\theta t} \le \sum_\theta\mu_\theta \left( \frac{\|w_\theta^*\|_2\sqrt{2\beta_\theta/\eta+4R^2}}{\alpha_\theta\sqrt T} +\frac{2R\|w_\theta^*\|_2M_\theta}{T} \right). \)
The trajectory is deterministic under the stated feedback and tie choices, so taking the indicated expectation leaves this inequality unchanged.
Given encoded rational query tuples and fractions, the updates require only rational arithmetic and are computable in polynomial time in those encoding lengths. The obstacle is obtaining the exact maximizing queries: the reduction proves hardness even when all returned coordinates have constant bit length.
The cited [Choice Perceptron paper](https://arxiv.org/pdf/1711.07875) formulates query selection through mixed-integer optimization. The reduction above independently establishes hardness for this precise cohort formulation.
Therefore, the conditional regret bound is valid, but computing the prescribed trajectory is \(\mathrm{NP}\)-hard. A general polynomial-time algorithm in \(m,\tau,d,k,T,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output resolves the task correctly. Its reduction establishes that computing the prescribed exact queries is \(\mathrm{NP}\)-hard, even with \(\tau=d=T=1\) and \(k=2\), while satisfying all promises and conditional regret assumptions. The separate derivation of the stated regret bound is also valid.
No major or minor issues were found. No additional clarification is required.
The cited standard theorem—that satisfiability of Boolean CNF formulas with three literals per clause is \(\mathrm{NP}\)-complete—is stated sufficiently precisely. The source formulas have exactly the form required by the construction.
The literal indicators correctly encode truth values for Boolean assignments. Every constructed constraint is rational and linear, with the integrality restrictions explicitly stated. The construction uses \(m=n+2\) attributes, one constraint per clause, and coefficients of constant bit length. Its encoding length is therefore polynomial in the formula length.
The chosen support, mass, dimensions, step size, feature map, and radius meet the task’s requirements:
Assessment: Correct.
When \(z=0\), every clause constraint holds because its literal indicators are nonnegative. For any Boolean assignment, both \(s=0\) and \(s=1\) are feasible. Thus the domain is nonempty and admits a pair with distinct features, regardless of satisfiability.
All coordinates are bounded integers, so \(Y\) is finite. Consequently, the feasible query set is finite and nonempty, and a rational maximizing tuple exists. Since \(T=1\), this verifies the query-existence promise at every required round.
The asserted characterization of \(s=2\) is exact:
Together with the always-feasible values \(s=0,1\), this establishes precisely the two feature sets stated by the prover.
Assessment: Correct; the reduction satisfies the promises on both satisfiable and unsatisfiable inputs.
At the first round, the estimate is zero. Therefore every feasible product satisfies the requirement that \(y_1\) maximize estimated utility.
At \(t=1\), the estimated-utility term has coefficient zero. With scalar features and \(k=2\), the remaining objective is exactly the absolute feature difference.
For either stated feature set, every maximizing pair contains the minimum and maximum attainable features. Hence the returned pair contains a product with \(s=2\) exactly when the formula is satisfiable. This conclusion holds for every maximizing tuple and therefore does not depend on the deterministic tie rule.
Reading the returned coordinates decides satisfiability in polynomial time. The reduction establishes hardness of the required search computation: a polynomial-time exact-query algorithm would yield a polynomial-time satisfiability algorithm. A solver for the combined query-and-update task must also produce this first query.
Assessment: Correct. The argument establishes \(\mathrm{NP}\)-hardness, without claiming membership in \(\mathrm{NP}\) or \(\mathrm{NP}\)-completeness.
The chosen true weight \(w_1^*=1\) is permitted by the task. The task allows either sign; a hardness reduction may use a positive weight.
Distinct scalar features give strictly ordered true utilities. Assigning fraction one to the larger feature and zero to the smaller feature satisfies the ordering equivalence in both directions. These fractions are binary-rational, nonnegative, and sum to one. They can be supplied by comparing the returned coordinates, without solving another satisfiability problem.
The update calculation is correct: for \(k=2\), the update equals the feature difference \(\delta\). Since the maximizing query contains both extremes:
With \(\alpha_1=1\), the first conditional inequality holds with equality. With \(\beta_1=0\), the second holds because the initial estimate is zero. The numerical nonnegativity condition evaluates to \(4\ge0\).
Assessment: Correct. Hardness holds within the conditional regime, with fixed constants and nonzero true weight.
Update identity and norm. Expanding the weighted expression for \(D_t\) reproduces the prescribed update: each feature has coefficient \((kp_{ti}-1)/(k-1)\). Each parenthesized vector has norm at most \(2R\), and the fractions form a convex combination. Thus \(\|D_t\|_2\le2R\) is valid for every \(k\ge2\).
Estimate norm. The squared-norm recurrence is exact. Summing telescopes from \(w_1=0\). Applying the assumed bound on the sum of estimated alignments and the update-norm bound gives precisely the stated coefficient \(2\beta/\eta+4R^2\). Its assumed nonnegativity justifies taking the square root, including the zero case.
Conversion to regret. The relation \(0\le r_t\le h_t\) follows directly from the definitions and \(Q_t\subseteq Y\). Summing the conditional informativeness inequality therefore gives the displayed regret inequality with the correct correction term involving \(M\).
Alignment bound. The recurrence gives the stated telescoping identity for cumulative true alignment. Cauchy–Schwarz applies to the real vectors without any restriction on the signs of the true weights. Substitution and division by positive \(\alpha T\) produce exactly the required constants.
Aggregation and expectation. Multiplication by nonnegative cohort masses preserves each inequality. Summing yields the required mass-weighted bound. Under the task’s deterministic-trajectory premise, expectation leaves this bound unchanged.
The argument also covers zero true weights and negative values of \(\beta\) satisfying the stipulated nonnegativity condition.
Assessment: Correct throughout.
The claim about updates is appropriately restricted to polynomial time in the encoding lengths of supplied rational tuples and fractions. Rational affine evaluation and rational arithmetic support that claim. The prover does not use it to assert a polynomial bound on obtaining general optimizing tuples.
In the reduction, every returned coordinate has constant bit length and each tuple has polynomial total encoding length. Thus excessive output length cannot explain the established hardness.
The paper’s statement that query selection can be formulated as mixed-integer linear optimization supports the prover’s contextual citation. The hardness proof itself is independent of that source. [Choice Perceptron paper, page 5](https://arxiv.org/pdf/1711.07875)
The conclusion answers the prescribed exact computation. It does not claim hardness of every possible procedure attaining the same regret bound.
None. The reduction and regret derivation stand as written.
⟨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.