Answer: Polynomial-time achievable under both feedback models: full feedback \(O(\min\{H,\sqrt{H\ln\tau}\})\), partial feedback \(O(\min\{H,\sqrt{H\min\{m,\tau\}\ln\tau}\})\). Regret is zero when \(\tau=1\) or \(m=1\).
Theorem 5.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any voting rule that is a distribution over unilaterals, there exist deterministic weighting schemes with regret of O( p T ln(n)) and O( p Tn ln(n)) in the full-information and partial-information settings, respectively.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a society with finite support \(\Theta\), binary-rational masses \(\mu_\theta>0\), and each type \(\theta\) specified by a ballot trajectory \((\sigma_r^\theta)_{r=1}^H\), let round \(r\) use a voting rule \(f_r\) that is a distribution over unilaterals and loss vector \(\ell_r\). A deterministic online policy chooses weight shares \(q_r\in\Delta(\Theta)\), inducing profile \(\pi^r_\sigma=\sum_{\theta:\sigma_r^\theta=\sigma}q_r(\theta)\). Does there exist a policy whose expected regret against the best fixed type, \(\mathbb{E}[\sum_{r=1}^H f_r(\pi^r)\cdot\ell_r-\min_{\theta\in\Theta}\sum_{r=1}^H f_r(e_{\sigma_r^\theta})\cdot\ell_r]\), is sublinear in \(H\) under full and partial feedback, and what are the achievable rates as functions of \(H\) and \(\tau=|\Theta|\)?
A society is given by its support: a list of \(\tau=|\Theta|\geq1\) 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 rankings or trajectories.
There are \(H\geq1\) rounds and \(m\geq1\) alternatives \(A\). Each type has a trajectory of strict rankings \((\sigma_r^\theta)_{r=1}^H\); future rankings are unavailable to the policy. Rankings and binary-rational losses \(\ell_r\in[0,1]^m\) are fixed adversarially before play.
Each exogenous rule \(f_r\) is a known finite mixture \(f_r=\sum_{j=1}^{k_r}\alpha_{rj}g_{rj}\), where \(\alpha_{rj}\geq0\), \(\sum_j\alpha_{rj}=1\), and an anonymous unilateral is \(g_{rj}(\pi)=\sum_{\sigma\in\mathcal L(A)}\pi_\sigma e_{h_{rj}(\sigma)}\), with \(h_{rj}:\mathcal L(A)\to A\). Here \(\mathcal L(A)\) is the set of strict rankings and \(e_x\) is unit mass at \(x\). Mixture probabilities are binary rationals and the maps are supplied as circuits; the rule schedule is known initially.
Before round \(r\)'s rankings or losses are revealed, the policy deterministically chooses \(q_r\in\Delta(\Theta)\) from previous observations. These are unrestricted total weight shares: \(q_r(\theta)=\mu_\theta w_r(\theta)/\sum_\vartheta\mu_\vartheta w_r(\vartheta)\), for arbitrary nonnegative densities with positive total weight.
The induced profile is \(\pi^r_\sigma=\sum_{\theta:\sigma_r^\theta=\sigma}q_r(\theta)\), and the winner is sampled as \(a_r\sim f_r(\pi^r)\). Afterward both feedback models reveal all current rankings and the winner; full feedback reveals \(\ell_r\), whereas partial feedback reveals only \(\ell_r(a_r)\), with no internal sampling information. The policy uses no private randomness.
Expected regret is \(R_H=\mathbb E[\sum_{r=1}^H f_r(\pi^r)\cdot\ell_r-\min_{\theta\in\Theta}\sum_{r=1}^H f_r(e_{\sigma_r^\theta})\cdot\ell_r]\), with expectation over winner sampling. Let \(L\) be the total binary encoding length, including circuit descriptions; state running times in \(m,\tau,H,L\).
Can deterministic policies guarantee \(R_H=\operatorname{poly}(m,\tau)\,o(H)\) uniformly over these inputs in time polynomial in \(m,\tau,H,L\), under full and partial feedback, or is achieving such guarantees NP-hard? What regret rates in \(H,m,\tau\) are achievable under each feedback model?
For a fixed rule that is a distribution over unilaterals, the discrete model admits deterministic weighting schemes with regret \(O(\sqrt{H\ln n})\) under full feedback and \(O(\sqrt{Hn\ln n})\) under partial feedback, for \(n\) voters ([verified discrete result](https://www.cs.cmu.edu/~rnoothig/papers/voting_no_regret.pdf)). No source verified here states a result for exactly the changing-rule, winner-only feedback model defined above.
Result. Both feedback models admit deterministic policies with polynomial running time. For \(\tau\geq2\), achievable expected-regret bounds are
\(R_H=O\!\left(\min\{H,\sqrt{H\ln\tau}\}\right)\) under full feedback,
and
\(R_H=O\!\left(\min\{H,\sqrt{H\min\{m,\tau\}\ln\tau}\}\right)\) under partial feedback.
If \(\tau=1\) or \(m=1\), regret is identically zero. These guarantees hold for changing rules, use only the specified feedback, and require no private randomness. Consequently, the requested guarantees are achievable in polynomial time.
The supplied [fixed-rule paper](https://www.cs.cmu.edu/~rnoothig/papers/voting_no_regret.pdf) establishes the discrete comparison results described in the question. The proof below handles the changing-rule, winner-only model directly.
1. Reduction to losses indexed by the support. For each round and type, define the alternative distribution
\(p_{r\theta}(a)=\sum_{j=1}^{k_r}\alpha_{rj}\mathbf 1\{h_{rj}(\sigma_r^\theta)=a\}\),
and its expected loss
\(c_{r\theta}=\sum_{a\in A}p_{r\theta}(a)\ell_r(a)\).
Each \(p_{r\theta}\) is a probability distribution, and \(c_{r\theta}\in[0,1]\). Linearity of the given rules implies
\(f_r(\pi^r)(a)=\sum_{\theta\in\Theta}q_r(\theta)p_{r\theta}(a)\).
Thus the policy’s round loss is exactly \(q_r\cdot c_r\), and the comparator’s loss is \(\min_\theta\sum_r c_{r\theta}\).
These identities hold separately in every round; they do not require a fixed rule. After the current rankings are revealed, all \(p_{r\theta}\) can be computed by evaluating the supplied circuits on those rankings. No enumeration of \(\mathcal L(A)\) is needed.
The masses impose no restriction on our choices: any \(q_r\in\Delta(\Theta)\) is implemented by densities \(q_r(\theta)/\mu_\theta\), whose total weighted mass is one.
2. A deterministic policy and a general update inequality. Assume henceforth that \(H\geq2\) and \(\tau\geq2\). Let \(u\) be uniform on \(\Theta\), and set \(\gamma=1/H\).
Maintain positive weights \(z_{r\theta}\), initially \(z_{1\theta}=1\). Before seeing the current rankings or losses, choose
\(v_r(\theta)=z_{r\theta}/\sum_\vartheta z_{r\vartheta}\), and \(q_r=(1-\gamma)v_r+\gamma u\).
After feedback, construct a nonnegative loss vector \(\widehat c_r\), specified below. For a rational learning rate \(\eta\in(0,1]\), use an approximate exponential update satisfying
\(e^{-\varepsilon}e^{-\eta\widehat c_{r\theta}}\leq z_{r+1,\theta}/z_{r\theta}\leq e^\varepsilon e^{-\eta\widehat c_{r\theta}}\),
where \(\varepsilon=\eta/(8H)\). Section 5 constructs such updates using rational arithmetic in polynomial time.
Here is the update inequality we will use. For every fixed \(\theta\),
\(\displaystyle \sum_{r=1}^H\left(v_r\cdot\widehat c_r-\widehat c_{r\theta}\right) \leq \frac{\ln\tau}{\eta} +\frac{\eta}{2}\sum_{r=1}^H\sum_\vartheta v_r(\vartheta)\widehat c_{r\vartheta}^{\,2} +\frac{2H\varepsilon}{\eta}. \)
To prove it, write \(Z_r=\sum_\vartheta z_{r\vartheta}\). The upper update bound and the inequalities \(e^{-x}\leq1-x+x^2/2\) for \(x\geq0\) and \(\ln y\leq y-1\) for \(y>0\) give
\(\displaystyle \ln\frac{Z_{r+1}}{Z_r} \leq \varepsilon-\eta v_r\cdot\widehat c_r +\frac{\eta^2}{2}\sum_\vartheta v_r(\vartheta)\widehat c_{r\vartheta}^{\,2}. \)
The lower update bound, together with \(Z_1=\tau\), gives
\(\displaystyle \ln\frac{Z_{H+1}}{Z_1} \geq -\ln\tau-\eta\sum_r\widehat c_{r\theta}-H\varepsilon. \)
Summing the first inequality and comparing it with the second proves the claim. In particular, the inequality permits arbitrarily large nonnegative loss estimates.
Exploration costs at most one over the horizon: since every coordinate of \(c_r\) belongs to \([0,1]\),
\(q_r\cdot c_r-v_r\cdot c_r=\gamma(u-v_r)\cdot c_r\leq\gamma\),
and \(H\gamma=1\).
3. Full feedback. Set \(\widehat c_r=c_r\), which is computable after rankings and the loss vector are revealed. Then
\(\sum_\theta v_r(\theta)\widehat c_{r\theta}^{\,2}\leq1\).
Choose a type \(\theta^\star\) minimizing \(\sum_r c_{r\theta}\). The update inequality and the exploration bound yield
\(\displaystyle R_H\leq \frac{\ln\tau}{\eta}+\frac{\eta H}{2}+\frac54. \)
For a rational parameter choice, put \(s=\lceil\log_2\tau\rceil\), and choose \(\eta\) to be the largest power of two not exceeding \(\min\{1,\sqrt{s/H}\}\). If \(s\leq H\), this gives \(R_H=O(\sqrt{Hs})\). If \(s>H\), the universal bound \(R_H\leq H\) suffices.
Because \(s=O(\ln\tau)\) for \(\tau\geq2\), the asserted full-feedback rate follows.
4. Partial feedback: winner-only estimation. After observing the rankings, reconstruct the winner distribution
\(P_r(a)=\sum_\theta q_r(\theta)p_{r\theta}(a)\).
For the observed winner \(a_r\), define
\(\displaystyle \widehat c_{r\theta} =\frac{p_{r\theta}(a_r)\ell_r(a_r)}{P_r(a_r)}. \)
An observed winner has positive probability almost surely, so this expression is defined. It uses only the revealed rankings, winner, and winner’s loss. It does not use the sampled mixture component or any other internal sampling information.
Let \(\mathcal F_{r-1}\) denote the past observations. The rankings, rules, and losses are fixed before play, while \(q_r\) is determined by \(\mathcal F_{r-1}\). Therefore,
\(\displaystyle \mathbb E[\widehat c_{r\theta}\mid\mathcal F_{r-1}] =\sum_{a:P_r(a)>0}p_{r\theta}(a)\ell_r(a) =c_{r\theta}. \)
The last equality holds because all \(q_r(\theta)>0\): if \(P_r(a)=0\), then \(p_{r\theta}(a)=0\) for every type.
The crucial second-moment bound is
\(\displaystyle \mathbb E\!\left[\sum_\theta q_r(\theta)\widehat c_{r\theta}^{\,2}\,\middle|\,\mathcal F_{r-1}\right] = \sum_{a:P_r(a)>0} \frac{\ell_r(a)^2\sum_\theta q_r(\theta)p_{r\theta}(a)^2}{P_r(a)} \leq\min\{m,\tau\}. \)
Both bounds follow directly:
Write \(d=\min\{m,\tau\}\). Since \(q_r(\theta)\geq(1-\gamma)v_r(\theta)\),
\(\displaystyle \mathbb E\!\left[\sum_\theta v_r(\theta)\widehat c_{r\theta}^{\,2}\,\middle|\,\mathcal F_{r-1}\right] \leq\frac{d}{1-\gamma}. \)
Apply the update inequality to \(\theta^\star\). This comparator is fixed because the entire adversarial input is fixed. Taking expectations, using conditional unbiasedness, and adding the exploration cost gives
\(\displaystyle R_H \leq \frac{\ln\tau}{\eta} +\frac{\eta Hd}{2(1-\gamma)} +\frac54 \leq \frac{\ln\tau}{\eta}+\eta Hd+\frac54, \)
where the last inequality uses \(H\geq2\).
Choose \(\eta\) as the largest power of two not exceeding \(\min\{1,\sqrt{s/(Hd)}\}\). If \(s\leq Hd\), the displayed bound is \(O(\sqrt{Hds})\). If \(s>Hd\), then \(H\leq\sqrt{Hds}\), so \(R_H\leq H\) again suffices. This proves the partial-feedback rate.
The policy is deterministic: the only randomness in its subsequent weights comes from the observed winner sampling already present in the model.
5. Polynomial-time rational implementation. We now justify the numerical update requirement and its bit complexity.
Exploration ensures \(q_r(\theta)\geq1/(H\tau)\). In partial feedback,
\(\displaystyle 0\leq\widehat c_{r\theta} \leq\frac{p_{r\theta}(a_r)}{P_r(a_r)} \leq\frac1{q_r(\theta)} \leq H\tau. \)
Consequently, in either feedback model the exponential argument \(x=\eta\widehat c_{r\theta}\) belongs to \([0,K]\), where \(K=H\tau\). This bound is independent of how small the mixture probabilities are.
Choose an integer precision
\(\displaystyle B=\left\lceil2H(K+1)\right\rceil +\left\lceil\log_2(4/\varepsilon)\right\rceil+2. \)
Store every weight on the grid of multiples of \(2^{-B}\). To update a weight, first compute a rational \(t\) satisfying
\(e^{-x}\leq t\leq e^{\varepsilon/2}e^{-x}\),
and then round \(z_{r\theta}t\) downward to that grid.
Such a rational \(t\) is obtained by taking the reciprocal of a truncated Taylor series:
\(\displaystyle t=\left(\sum_{k=0}^{N}\frac{x^k}{k!}\right)^{-1}. \)
Choose an integer \(b\) with \(2^{-b}\leq\varepsilon/2\), and \(N\geq6K+b+2\). For \(n>N\), the factorial bound \(n!\geq(n/e)^n\) and \(e<3\) imply
\(x^n/n!\leq(eK/n)^n\leq2^{-n}\).
Thus the omitted tail is at most \(2^{-N}\leq2^{-b}\). Since the retained series is at least one,
\(1\leq t/e^{-x}\leq1+\varepsilon/2\leq e^{\varepsilon/2}\).
It remains to check that grid rounding preserves the required relative accuracy. Inductively, the update lower bound ensures that a weight before round \(r\) is at least \(e^{-(r-1)(K+\varepsilon)}\). Hence its unrounded next value is at least \(e^{-H(K+1)}\). By the choice of \(B\) and \(e<4\), downward rounding loses at most an \(\varepsilon/4\) fraction of that value. Since \(1-\varepsilon/4\geq e^{-\varepsilon/2}\) for \(0<\varepsilon\leq1\), the rounded update satisfies the required bounds. It also remains strictly positive, completing the induction.
For completeness, a conservative bit-operation bound can be stated explicitly. Define
\(S=L+\tau H^2+\lceil\log_2(m\tau H+2)\rceil\).
The stored weights and all loss-estimate inputs have \(O(S)\) bits. The Taylor computation uses \(N=O(S)\) terms with intermediate rational numerators and denominators of \(O(S^2)\) bits. Using elementary integer arithmetic, each update therefore takes \(O(S^5)\) bit operations.
Across all rounds, circuit evaluation takes \(O(\tau L)\) operations, and constructing the probability tables takes \(O(Hm\tau+\tau L)\) rational operations. A conservative total running-time bound is therefore
\(O\!\left((Hm\tau+\tau L)S^5\right)\).
Computing densities \(q_r(\theta)/\mu_\theta\), if required, also has polynomial bit complexity. Thus the implementation is polynomial in \(m,\tau,H,L\), including for extremely small positive masses or mixture probabilities.
For \(H=1\), any fixed distribution has regret at most one; no update is needed. The zero-regret cases \(\tau=1\) and \(m=1\) are immediate from the comparator definition.
6. The dependence on the horizon cannot generally improve. Even with \(m=\tau=2\), both feedback models have a worst-case lower bound of order \(\sqrt H\).
Take two equally massive types with fixed opposite rankings, and use the fixed unilateral that selects the top-ranked alternative. Generate independent uniform signs \(X_1,\ldots,X_H\), and set
\(\ell_r(1)=(1+X_r)/2\), and \(\ell_r(2)=(1-X_r)/2\).
Every realization is an admissible binary-rational loss sequence fixed before play. Since the current sign is independent of past observations, the policy’s expected loss in each round, averaged over these sequences, is \(1/2\). The best type’s cumulative loss is
\(\displaystyle \frac H2-\frac12\left|\sum_{r=1}^H X_r\right|. \)
Hence average expected regret is \(\mathbb E|T|/2\), where \(T=\sum_r X_r\).
To bound this explicitly, \(\mathbb E T^2=H\) and \(\mathbb E T^4=3H^2-2H\leq3H^2\). Put \(E=\{T^2\geq H/2\}\). Then
\(\displaystyle H/2 \leq\mathbb E[T^2\mathbf1_E] \leq\sqrt{\mathbb E T^4\,\Pr(E)}, \)
so \(\Pr(E)\geq1/12\). Therefore,
\(\displaystyle \mathbb E|T|/2\geq\frac{\sqrt H}{24\sqrt2}. \)
At least one fixed loss sequence attains this lower bound on expected regret. Thus the square-root dependence on \(H\) is necessary in general, although this argument does not assert optimal dependence on all other parameters.
⟨structured verdict parsed — rendered above⟩
The output resolves the task. Both regret guarantees and the polynomial-time implementation are correct under the stated input and feedback model. I found no major or minor issues requiring repair.
The definition of \(p_{r\theta}\) gives a probability distribution: its coordinates are nonnegative and sum to \(\sum_j\alpha_{rj}=1\). Consequently, \(c_{r\theta}\in[0,1]\).
Substituting the induced profile into the mixture of unilaterals gives exactly
\[
f_r(\pi^r)(a)=\sum_\theta q_r(\theta)p_{r\theta}(a).
\]
Therefore both the policy loss and the comparator agree with the support-indexed formulation.
This identity is valid separately for each rule \(f_r\), so changing rules cause no difficulty. Computing \(p_{r\theta}\) requires evaluating only the supplied circuits on the current support rankings, without enumerating all rankings.
The density construction \(w_r(\theta)=q_r(\theta)/\mu_\theta\) is valid because every mass is positive. Its total weighted mass equals one. No restriction involving the masses has been overlooked.
The policy chooses \(q_r\) from stored weights before seeing current rankings or losses. Current rankings enter only the subsequent update. This respects the information restriction.
The approximate update inequality is derived correctly. The upper bound on \(Z_{r+1}/Z_r\), the inequality \(e^{-x}\leq1-x+x^2/2\) for nonnegative \(x\), and the lower bound supplied by any fixed comparator weight give the stated result.
In particular, this calculation does not require \(\eta\widehat c_{r\theta}\leq1\). Its application to potentially large importance-weighted estimates is justified.
The approximation contribution is
\[
\frac{2H\varepsilon}{\eta}=\frac14.
\]
The exploration contribution is at most \(H\gamma=1\). Thus the later additive constant \(5/4\) is correct.
With \(\widehat c_r=c_r\), the second-moment term is at most one per round because every loss lies in \([0,1]\). Applying the update inequality to a minimizing type gives the displayed regret bound.
The power-of-two learning rate is within a factor of two of the proposed capped rate. For \(\tau\geq2\), \(s=\lceil\log_2\tau\rceil\) is comparable to \(\ln\tau\), which justifies the conversion to the asserted rate.
Combining this estimate with the unconditional upper bound \(R_H\leq H\) establishes
\[
R_H=O\!\left(\min\{H,\sqrt{H\ln\tau}\}\right).
\]
The estimator uses only current rankings, the observed winner, and its revealed loss. Reconstructing \(P_r\) after observing the rankings is permitted; it does not require that the policy knew those rankings when choosing \(q_r\).
Positive exploration ensures \(q_r(\theta)>0\) for every type. Hence \(P_r(a)=0\) implies \(p_{r\theta}(a)=0\) for every type, and the estimator is defined for every winner that can actually occur.
Conditional unbiasedness is correct. Although current rankings and losses are unavailable to the policy beforehand, they are fixed input data, and the conditional winner distribution is \(P_r\).
The two second-moment bounds are both valid:
The conversion from weights \(q_r\) to weights \(v_r\) follows from \(q_r(\theta)\geq(1-\gamma)v_r(\theta)\).
The comparator \(\theta^\star\) is fixed independently of winner sampling because the adversarial input is fixed. Thus taking expectations in the comparator inequality is legitimate. Conditional unbiasedness also applies to the past-measurable vector \(v_r\).
The resulting rate is therefore established:
\[
R_H=O\!\left(\min\{H,\sqrt{H\min\{m,\tau\}\ln\tau}\}\right).
\]
The policy remains deterministic as a function of its observations. Dependence on publicly observed winner sampling does not introduce private randomness.
The bound \(\widehat c_{r\theta}\leq H\tau\) follows correctly from exploration. It controls the exponential argument independently of small mixture probabilities.
The reciprocal Taylor construction has the stated multiplicative accuracy. For omitted indices \(n>N\), the chosen threshold ensures \(eK/n<1/2\), so the tail is bounded by \(2^{-N}\). Dividing by the retained series, which is at least one, yields the claimed relative bound.
The rounding induction is consistent:
Thus rounding preserves positivity and satisfies the required approximate update bounds.
The precision \(B\) is polynomial in the stated parameters. Stored weights have bounded numerator size as well: their upper update bounds prevent growth beyond \(e^{H\varepsilon}\). Normalization and the probability-table computations retain polynomial bit lengths.
The Taylor degree can be chosen as \(O(S)\), and the asserted \(O(S^2)\) intermediate bit lengths are consistent with powers of a rational input and factorial denominators. The conservative \(O(S^5)\) cost per update is sufficient using elementary arithmetic.
The aggregate circuit and table costs, and hence the stated total running-time bound, are polynomial in \(m,\tau,H,L\). The proof establishes bit complexity, rather than merely counting exact-real operations.
For \(\tau=1\), the policy and comparator use the same sole type. For \(m=1\), every rule outputs the sole alternative. Regret is therefore zero in both cases.
For \(H=1\), the stated bound by one handles the nondegenerate cases without requiring an update.
For fixed \(m,\tau\), both established rates are sublinear in \(H\); their coefficients are bounded by polynomials in \(m,\tau\). The estimates are uniform over the admissible trajectories, losses, masses, and circuit-described rule schedules. This answers the requested algorithmic question.
The lower-bound construction is admissible: the rankings are strict, the masses are positive binary rationals, and every realized loss sequence has binary-rational coordinates.
Independence of the current sign from past observations gives average policy loss \(1/2\) per round under either feedback model. The expression for the best type’s cumulative loss is correct.
The second and fourth moments, the Cauchy–Schwarz calculation, the probability bound \(1/12\), and the final constant \(1/(24\sqrt2)\) all check out. Averaging over finitely many loss sequences justifies the existence of a fixed sequence attaining the lower bound.
This proves necessity of square-root dependence on \(H\) in general. It does not establish optimal dependence on \(m,\tau\), and the prover explicitly preserves that distinction.
The contextual comparison is supported by Theorem 5.3 of the [cited paper](https://www.cs.cmu.edu/~rnoothig/papers/voting_no_regret.pdf). The present argument establishes its changing-rule, winner-only guarantees directly and does not depend on extending that theorem.
Actionable feedback: No repair or additional clarification is needed to verify the claimed result.
⟨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.