d4-journals-ai-2024-0035 (d4-journals-ai-2024-0035)

For each round \(t\), let a large cohort of matched seller–buyer opportunities have a finite-support rational distribution \(\mu_t\) over valuation types \((s,b)\in[0,1]^2\), fixed adversarially in advance. A learner posts a common single price \(p_t\) and receives the two acceptance bits from a uniformly sampled opportunity. For fixed \(\alpha>1\), does the minimax \(\alpha\)-regret against the best fixed price, with per-capita reward \(g_t(p)=\sum_{(s,b)}\mu_t(s,b)(b-s)\mathbf{1}\{s\le p\le b\}\), necessarily grow linearly in \(T\)?

An oblivious adversary fixes hidden societies \(\mu_1,\ldots,\mu_T\). Each society is represented by its support: a list of types \((s,b)\in([0,1]\cap\mathbb{Q})^2\) with positive binary-rational masses summing to \(1\). Let \(\tau=\max_t|\operatorname{supp}\mu_t|\) be the support size, not the number of possible types, and \(L\) the total encoding length. There is no candidate-count parameter \(m\); state any running times in \(T,\tau,L\) and other relevant parameters.
A randomized learner knows \(T\) and a fixed constant \(\alpha>1\). At round \(t\), it posts one common price \(p_t\in[0,1]\), using only its randomness and past feedback. An independent draw \((S_t,B_t)\sim\mu_t\) reveals only \((\mathbf{1}\{S_t\le p_t\},\mathbf{1}\{p_t\le B_t\})\); neither valuations, distributions, nor rewards are revealed. Equality counts as acceptance; types with \(s>b\) are allowed.
The per-capita reward is \(g_t(p)=\sum_{(s,b)\in\operatorname{supp}\mu_t}\mu_t(s,b)(b-s)\mathbf{1}\{s\le p\le b\}\). Define \(R_T^{\alpha,*}=\inf_A\sup_{\mu_{1:T}}\bigl[\max_{p\in[0,1]}\sum_{t=1}^Tg_t(p)-\alpha\,\mathbb{E}_A\sum_{t=1}^Tg_t(p_t)\bigr]\), with expectation over learner randomness and sampled feedback, and no computational restriction on \(A\). The supremum permits all finite supports and encoding lengths.

For every fixed \(\alpha>1\), is \(R_T^{\alpha,*}=\Omega(T)\), or can a learner achieve \(R_T^{\alpha,*}=o(T)\)?

For one arriving pair per round, single-price two-bit feedback has minimax \(\alpha\)-regret at least \(T/(128\alpha^3)\) for every constant \(\alpha>1\). [Source](https://arxiv.org/html/2210.06846v2)
For distributional arrivals with bounded joint densities, single-price two-bit feedback has linear ordinary regret; this concerns \(\alpha=1\) and excludes finite-support societies. [Source](https://www.jmlr.org/papers/volume25/23-1627/23-1627.pdf)
No result settling the exact finite-support rational model above was verified.

Result

For every fixed \(\alpha>1\), the minimax regret is linear. Specifically, for every positive integer \(T\),

\(\displaystyle \frac{T}{8192\alpha^3}\le R_T^{\alpha,*}\le T.\)

The lower bound already holds for stationary societies with dyadic valuations and masses, with support size \(\tau=O(\alpha^2)\).

The construction is motivated by the indistinguishability argument in [Azar–Fiat–Fusco, Theorem 4](https://arxiv.org/html/2210.06846v2#S4.SS1). The proof below directly handles the finite-support model, including equality at posted prices.

1. Constructing the societies

Fix \(\alpha>1\). Let \(K\) be the smallest power of two satisfying \(K\ge 8\alpha\). Thus,

\(\displaystyle 8\alpha\le K<16\alpha.\)

Set \(N=K^2\) and \(x_j=j/N\) for \(j\in\{0,\ldots,N\}\). Partition \([0,1]\) into \(K\) closed blocks,

\(\displaystyle J_i=[x_{iK},x_{(i+1)K}],\qquad i\in\{0,\ldots,K-1\}.\)

Each block has length \(1/K\).

For each \(i\), define a society \(\mu^{(i)}\) containing the following types, each with mass \(1/N\):

• One long-interval type \((x_{iK},x_{(i+1)K})\).
• The short-interval types \((x_j,x_{j+1})\) for all \(j\in\{0,\ldots,N-1\}\) outside \(\{iK,\ldots,(i+1)K-1\}\).
• The point types \((x_j,x_j)\) for \(j\in\{iK+1,\ldots,(i+1)K-1\}\).

There are exactly \(1+(N-K)+(K-1)=N\) distinct types. Their masses are positive and sum to one. Since \(N\) is a power of two, all valuations and masses are dyadic rationals. Every type satisfies \(s\le b\).

Write \(g^{(i)}\) for the reward function of \(\mu^{(i)}\). Our adversarial instances are stationary: \(\mu_t=\mu^{(i)}\) for every round.

2. Exact feedback indistinguishability

Claim. For every price \(p\in[0,1]\), the two-bit feedback distribution is identical under all \(K\) societies, including when \(p\) equals a valuation.

First, all societies have the same seller marginal: each of \(x_0,\ldots,x_{N-1}\) has mass \(1/N\). Indeed, inside the selected block, the long type supplies seller value \(x_{iK}\), and the point types supply the remaining seller values of that block.

Likewise, all societies have the same buyer marginal: each of \(x_1,\ldots,x_N\) has mass \(1/N\). Inside the selected block, the long type supplies buyer value \(x_{(i+1)K}\), and the point types supply the remaining buyer values.

To see why these marginals determine the joint feedback, define

\(\displaystyle a(p)=\Pr(S\le p),\qquad c(p)=\Pr(p\le B).\)

Because every type has \(S\le B\), the feedback \((0,0)\) is impossible: it would require \(S>p>B\). Consequently,

\(\displaystyle \Pr((1,1))=a(p)+c(p)-1,\quad \Pr((1,0))=1-c(p),\quad \Pr((0,1))=1-a(p),\quad \Pr((0,0))=0. \)

The marginals \(a(p)\) and \(c(p)\) are common to all societies, so the entire feedback law is common. These identities use exactly the stipulated weak acceptance inequalities; no grid prices need to be excluded.

It follows that, for any randomized learner, the distribution of its price \(p_t\) is independent of which society \(\mu^{(i)}\) is used. Here is the induction: the initial internal randomness has the same law in every instance; given a common law of the learner’s state and past feedback, its next price has a common law; conditional on that price and history, the next independently sampled feedback has the common law just established. Thus the learner’s updated state and history also have a common law.

Denote the common distribution of \(p_t\) by \(\nu_t\).

3. Benchmark and learner reward bounds

Benchmark bound. In society \(\mu^{(i)}\), posting the midpoint of \(J_i\) trades with the long type. Its mass is \(1/N\), and its gain is \(1/K\). Therefore,

\(\displaystyle \max_{p\in[0,1]}g^{(i)}(p)\ge\frac{1}{NK}=\frac{1}{K^3}.\)

Since the instance is stationary,

\(\displaystyle \max_p\sum_{t=1}^T g_t(p)\ge\frac{T}{K^3}.\)

Average learner reward bound. Define

\(\displaystyle \overline g(p)=\frac1K\sum_{i=0}^{K-1}g^{(i)}(p).\)

We claim that, for every price,

\(\displaystyle \overline g(p)\le\frac{4}{K^4}.\)

For the long types, a price belongs to at most two closed blocks \(J_i\). Each corresponding long type contributes \((1/N)(1/K)\). Averaging over societies gives a contribution at most

\(\displaystyle \frac1K\cdot 2\cdot\frac1N\cdot\frac1K=\frac{2}{K^4}.\)

For the short types, a price belongs to at most two elementary intervals \([x_j,x_{j+1}]\). Each short type has mass \(1/N\) and gain \(1/N\). Hence their contribution in each society, and therefore their average contribution, is at most

\(\displaystyle \frac{2}{N^2}=\frac{2}{K^4}.\)

Point types have zero gain. Adding the contributions proves the claim. Counting two closed intervals explicitly covers equality at their shared endpoint.

Using the common price distributions \(\nu_t\), we obtain

\(\displaystyle \frac1K\sum_{i=0}^{K-1} \mathbb E_i\!\left[\sum_{t=1}^T g^{(i)}(p_t)\right] = \sum_{t=1}^T\int_{[0,1]}\overline g(p)\,\nu_t(dp) \le\frac{4T}{K^4}. \)

Here \(\mathbb E_i\) includes both learner randomness and sampled feedback under the stationary society \(\mu^{(i)}\).

4. Minimax conclusion

Fix any learner \(A\). Averaging its regret over the \(K\) stationary instances gives

\(\displaystyle \frac1K\sum_{i=0}^{K-1} \left[ T\max_p g^{(i)}(p) -\alpha\,\mathbb E_i\sum_{t=1}^Tg^{(i)}(p_t) \right] \ge \frac{T}{K^3}-\frac{4\alpha T}{K^4}. \)

Since \(K\ge8\alpha\), the right-hand side is at least \(T/(2K^3)\). At least one fixed society therefore gives learner \(A\) regret at least this amount. That society can be selected before play, so the adversary is oblivious.

This argument applies to every learner, without computational restrictions. Taking the infimum over learners and using \(K<16\alpha\) yields

\(\displaystyle R_T^{\alpha,*}\ge\frac{T}{2K^3}\ge\frac{T}{8192\alpha^3}.\)

For the upper bound, every reward satisfies \(0\le g_t(p)\le1\). Thus the benchmark is at most \(T\), while the learner’s reward is nonnegative, giving \(R_T^{\alpha,*}\le T\).

The construction has \(\tau=K^2=O(\alpha^2)\). With each round’s support listed explicitly, its total encoding length is \(L=O(T\tau\log(\tau+1))\). Thus the lower bound requires neither growing support size for fixed \(\alpha\) nor unbounded numerical precision.

⟨structured verdict parsed — rendered above⟩

The prover’s argument is correct and resolves the stated finite-support rational model. I found no major or minor mathematical issues. It establishes the claimed bounds for every positive integer \(T\) and every fixed \(\alpha>1\).

1. Construction and admissibility

The smallest power of two \(K\) satisfying \(K\ge 8\alpha\) obeys \(8\alpha\le K<16\alpha\). Consequently, \(N=K^2\) is also a power of two, and all valuations \(x_j=j/N\) and masses \(1/N\) are dyadic rationals.

For each society, the three groups of types are distinct:

• The long type has interval length \(1/K\).
• The short types have interval length \(1/N\) and lie outside the selected block.
• The point types have interval length zero and lie strictly inside the selected block.

Their total number is \(1+(N-K)+(K-1)=N\), so the positive masses sum to one. Every society is admissible, with support size exactly \(\tau=N\). Restricting the construction to types satisfying \(s\le b\) is permitted even though the task allows additional types with \(s>b\).

2. Feedback indistinguishability

The seller-marginal calculation is correct. Outside the selected block, the short types supply each corresponding seller grid point once. Inside it, the long type supplies the left endpoint and the point types supply all remaining seller grid points. Thus every society has seller mass \(1/N\) at each of \(x_0,\ldots,x_{N-1}\).

The buyer-marginal calculation is also correct: the long type supplies the selected block’s right endpoint, while the point types supply its interior grid points. Every society has buyer mass \(1/N\) at each of \(x_1,\ldots,x_N\).

For this construction, feedback \((0,0)\) would require \(S>p>B\), contradicting \(S\le B\). Therefore the two acceptance events have union of probability one. The displayed identities for all four feedback probabilities follow correctly from their marginal probabilities.

This reasoning remains valid at every grid point and at \(p=0,1\). Point types produce \((1,1)\) at their valuation, and the weak acceptance inequalities are respected throughout.

The adaptive indistinguishability induction is valid. Given the price and past history, the independent next draw produces the same feedback law in every society. Accordingly, any fixed randomized learner has the same price distribution \(\nu_t\) in every instance. No assumption that prices lie on the grid is used.

3. Benchmark bound

The midpoint of \(J_i\) is accepted by the long type. Its contribution is
\[ \frac{1}{N}\frac{1}{K}=\frac{1}{K^3}. \]
All other contributions are nonnegative. Hence the benchmark lower bound \(T/K^3\) follows for the stationary instance.

The use of a maximum is legitimate: these finite-support reward functions attain their maxima. Equality at interval endpoints does not undermine the bound.

4. Average learner reward bound

The interval counts and constants are correct.

A price lies in at most two closed blocks. Averaging the corresponding long-type contributions over the \(K\) societies therefore gives at most \(2/K^4\).

A price lies in at most two closed elementary intervals. In each society, each present short type contributes \(1/N^2\), so the short-type contribution is at most \(2/N^2=2/K^4\). This bound also bounds its average across societies.

Point types contribute zero. Thus the claimed uniform inequality
\[ \overline g(p)\le \frac{4}{K^4} \]
holds, including at shared endpoints.

The subsequent expectation identity correctly uses the common distributions \(\nu_t\). Interchanging the finite sums and integrals is justified because the rewards are bounded measurable functions. The average expected cumulative learner reward is therefore at most \(4T/K^4\).

5. Minimax conclusion and constants

For every learner, averaging the instance-specific regrets gives
\[ \frac{T}{K^3}-\frac{4\alpha T}{K^4} = \frac{T}{K^3}\left(1-\frac{4\alpha}{K}\right) \ge \frac{T}{2K^3}. \]
The last inequality follows from \(K\ge8\alpha\).

At least one of the finitely many stationary societies attains this average lower bound. Its selection may depend on the learner’s strategy, but does not depend on realized randomness or feedback. This is consistent with an oblivious adversary and with the order of quantifiers in the minimax definition.

Since the lower bound holds for every learner, taking the infimum is valid. The constant calculation is correct:
\[ K<16\alpha \quad\Longrightarrow\quad \frac{T}{2K^3}\ge\frac{T}{8192\alpha^3}. \]

The upper bound is correct even for the broader task allowing \(s>b\): such types never satisfy \(s\le p\le b\), while every trading type contributes a gain between zero and one. Thus \(0\le g_t(p)\le1\), and every learner’s regret is at most \(T\).

6. Scope and remaining clarification

The support bound \(\tau=K^2=O(\alpha^2)\) and explicit-list encoding bound \(L=O(T\tau\log(\tau+1))\) are consistent with the construction. For fixed \(\alpha\), the lower bound requires neither increasing support size nor increasing precision as \(T\) grows. No candidate-count parameter or algorithmic running-time claim is introduced.

The [cited paper](https://arxiv.org/html/2210.06846v2#S4.SS1) serves only as motivation; the proof does not invoke its theorem to transfer a result between models.

No additional mathematical clarification is needed. The result settles the regret question, but does not classify computational complexity; the required complexity-status field is therefore marked “unresolved.”

⟨structured verdict parsed — rendered above⟩