d4-conf-atal-2020-0270 (d4-conf-atal-2020-0270)

Given a finite support \(G\) of game types with masses \(\mu_g\), action sets \(A_g\), horizon \(T\), and \(N\) dyads distributed across types, but unknown reward laws \(P_{g,a}\), characterize the minimax population-average individual-rational regret. Each round, allocate fractions \(x_{g,a,t}\) of type \(g\) to joint actions \(a\), with \(\sum_{a\in A_g}x_{g,a,t}=\mu_g\); pooled feedback consists of the corresponding finite-\(N\) dyad observations. Determine the regret rate in \(N,T,\mu\), and the action-set sizes, and give a matching algorithm and lower bound.

A society is given by its support: a list \(G\) of \(\tau\) game types with positive binary-rational masses \(\mu_g\), where \(\sum_g\mu_g=1\); \(\tau\) counts supported types, not possible types. Let \(L\) be the input bit length.
Type \(g\) has joint-action set \(A_g=A_g^1\times A_g^2\), with \(|A_g^i|\ge2\); write \(K_g=|A_g|\) and \(m=\max_gK_g\). There are \(N\) persistent dyads, exactly \(n_g=N\mu_g\in\mathbb Z_{>0}\) of each type, and a known integer horizon \(T\ge m\).
Playing \(a\) in type \(g\) produces a reward pair from an unknown fixed law \(P_{g,a}\) on \([0,1]^2\), with mean \(r_g(a)\); draws are independent across dyads and rounds conditional on their actions, while the two rewards within a pair may be dependent. No relationship between laws of different types is assumed.
Let \(s_g^i\) be player \(i\)'s maximin value in the mean-payoff game. The benchmark \(v_g\) is the egalitarian bargaining value: among \(v\in\operatorname{conv}\{r_g(a):a\in A_g\}\), lexicographically maximize \((\min_i(v^i-s_g^i),\max_i(v^i-s_g^i))\).
At round \(t\), a controller using only completed rounds chooses a randomized assignment of joint actions with conditional expected counts \(Nx_{g,a,t}\), where \(x_{g,a,t}\ge0\) and \(\sum_a x_{g,a,t}=\mu_g\). Each dyad plays once; all labeled actions and reward pairs are pooled after the round. Thus allocations are divisible in expectation, but feedback remains finite and arrives in batches.
For dyad \(d\) of type \(g(d)\), define population-average individual-rational regret by \(R_{N,T}=N^{-1}\sum_{d=1}^N\max_{i\in\{1,2\}}\{Tv_{g(d)}^i-\sum_{t=1}^T r_{d,t}^i\}\), without taking positive parts; define \(\mathcal R^*=\inf_\Lambda\sup_{(P_{g,a})}\mathbb E_\Lambda R_{N,T}\).

What is the minimax order of \(\mathcal R^*\) as a function of \(N,T,\mu\), and the action-set sizes, with matching algorithmic upper and lower bounds? State algorithm running times in \(m,\tau,L,N,T\).

For a single dyad with \(K\) joint actions and \(T\ge K\), the established lower bound is \(\Omega(K^{1/3}T^{2/3})\); UCRG has a high-probability upper bound \(\widetilde O(K^{1/3}T^{2/3})\). [Source](https://ifaamas.org/Proceedings/aamas2020/pdfs/p1395.pdf)
No result settling the specified population model was located.

1. Status and proved bounds

The general minimax order remains partially resolved. The population bounds in the notes can be proved rigorously, including the variance correction. In addition, I prove that the logarithmic gap cannot be removed within the class of controllers that fix their exploration schedule in advance and then commit: for one dyad playing a $2\times2$ game, that restricted class has minimax regret
$$ \Theta\!\left(T^{2/3}(\log T)^{1/3}\right). $$
This restriction matters: the result does not give a logarithmic lower bound for fully adaptive controllers.

Write
$$ n_g=N\mu_g, \qquad B_g=\left(\frac{K_gT^2}{n_g}\right)^{1/3}, $$
and define
$$ W=\sqrt T+\sum_{g\in G}\mu_gB_g =\sqrt T+\frac{T^{2/3}}{N^{1/3}} \sum_{g\in G}K_g^{1/3}\mu_g^{2/3}. $$

There are universal constants $c,C>0$ such that
$$ cW\le \mathcal R^* \le C\sum_{g\in G}\mu_g \min\left\{ T,\, \sqrt T+ \left(\frac{K_gT^2\ell_g}{n_g}\right)^{1/3} \right\}, \qquad \ell_g=\left\lceil\log_2(4K_gT)\right\rceil. $$

Thus the unrestricted population minimax regret is determined up to a factor of order $(\log(4mT))^{1/3}$. The cited single-dyad results provide the corresponding starting point, but do not settle this population model. [Tossou et al., *A Novel Individually Rational Objective In Multi-Agent Multi-Armed Bandits*](https://ifaamas.org/Proceedings/aamas2020/pdfs/p1395.pdf)

All population bounds below are proved directly.

2. Geometry and stability of the benchmark

Fix a type and suppress its subscript. Let
$$ C=\operatorname{conv}\{r(a):a\in A\}, \qquad w(p)=\sum_a p_a r(a), \qquad p\in\Delta_A, $$
where $\Delta_A$ is the simplex of distributions over joint actions. Write
$$ z=\max_{p\in\Delta_A}\min_i\{w^i(p)-s^i\}. $$

The benchmark exists: first maximize the continuous minimum-advantage objective over the compact simplex, and then maximize the continuous maximum-advantage objective over the resulting compact set.

A geometric property

Suppose the benchmark has unequal advantages, with
$$ v^1-s^1=z<v^2-s^2. $$
Then every $u\in C$ satisfies $u^1\le v^1$.

Indeed, if $u^1>v^1$, then for sufficiently small $\lambda>0$, the payoff
$$ (1-\lambda)v+\lambda u $$
has both advantages strictly greater than $z$. Its first advantage increases strictly, and its second remains above $z$ by continuity. This contradicts the definition of $z$.

This property also implies uniqueness of the benchmark payoff. In the unequal-advantage case, its lower-advantage coordinate is fixed at the maximum feasible value, and its other coordinate is fixed by secondary optimality. In the equal-advantage case, both coordinates are fixed by $s$ and $z$.

Stability lemma with relaxed constraints

Suppose estimated means satisfy
$$ \max_{a,i}|\widehat r^i(a)-r^i(a)|\le\eta. $$
Let $\widehat s^i$ be the maximin values of the estimated game, and put
$$ \widehat w(p)=\sum_a p_a\widehat r(a), \qquad \widehat z= \max_{p\in\Delta_A} \min_i\{\widehat w^i(p)-\widehat s^i\}. $$
Choose $\widehat p$ to maximize $\widehat w^1(p)+\widehat w^2(p)$ subject to
$$ \widehat w^i(p)-\widehat s^i\ge\widehat z-4\eta, \qquad i=1,2. $$

Then
$$ w^i(\widehat p)\ge v^i-8\eta, \qquad i=1,2. $$

Proof. Uniform perturbation by at most $\eta$ changes every mixed-strategy payoff by at most $\eta$. Taking minima and maxima preserves this bound, so
$$ |\widehat s^i-s^i|\le\eta. $$
Consequently, every policy’s estimated advantage differs from its true advantage by at most $2\eta$, and
$$ |\widehat z-z|\le2\eta. $$

A policy attaining $v$ is feasible for the relaxed estimated problem: its estimated advantages are at least $z-2\eta\ge\widehat z-4\eta$. Hence the relaxed feasible set is nonempty.

Feasibility of $\widehat p$ gives
$$ w^i(\widehat p)-s^i\ge z-8\eta. $$
Its total-payoff optimality, compared with a policy attaining $v$, gives
$$ w^1(\widehat p)+w^2(\widehat p) \ge v^1+v^2-4\eta. $$

If both benchmark advantages equal $z$, the coordinatewise conclusion follows from the first inequality. Otherwise, exchange the players if necessary so that $v^1-s^1=z<v^2-s^2$. The geometric property gives $w^1(\widehat p)\le v^1$, and therefore the total-payoff inequality implies
$$ w^2(\widehat p)\ge v^2-4\eta. $$
The first coordinate is at least $v^1-8\eta$. This proves the lemma. $\square$

3. A feasible population algorithm and its upper bound

Run the following procedure independently for each supported type. Fix a type with $n$ dyads and $K$ joint actions. Define
$$ \ell=\left\lceil\log_2(4KT)\right\rceil, \qquad q=\left\lceil \left(\frac{n^2T^2\ell}{K^2}\right)^{1/3} \right\rceil, \qquad h=\left\lceil\frac{Kq}{n}\right\rceil. $$

If $h>T$, play any fixed action throughout. Otherwise:

• During the first $h$ rounds, use a predetermined assignment of actions that designates exactly $q$ samples of each joint action. Fill unused dyad-round slots arbitrarily.
• After round $h$, compute empirical means from the designated samples.
• Solve the relaxed bargaining problem from Section 2.
• In every remaining round, independently sample $\widehat p$ for every dyad.

The exploration schedule exists because $nh\ge Kq$. It uses no observations from the current round. During exploitation, the conditional expected count of action $a$ is $n\widehat p_a$, so the required allocation is
$$ x_{g,a,t}=\mu_g\widehat p_a. $$
Thus the algorithm respects both the batching and allocation requirements.

Estimation

For finite computation, quantize each reward downward to mesh $2^{-b}$, where
$$ b=\left\lceil\log_2(16T)\right\rceil, \qquad \rho=2^{-b}\le\frac1{16T}. $$
This changes each sample by at most $\rho$.

Coordinatewise Hoeffding inequalities and a union bound over the $2K$ coordinates give
$$ \Pr\left( \max_{a,i}|\widehat r^i(a)-r^i(a)| > \sqrt{\frac{\ell}{2q}}+\rho \right) \le4K e^{-\ell}\le\frac1T. $$
Here $\ell\ge\ln(4KT)$. Dependence between the two rewards within a pair does not affect the coordinatewise inequalities.

Choose a rational tolerance satisfying
$$ \sqrt{\frac{\ell}{2q}}+\rho \le\eta \le2\left(\sqrt{\frac{\ell}{2q}}+\rho\right). $$
A dyadic approximation supplies such a tolerance.

Individual fluctuations: corrected variance argument

Condition on the exploration history, which fixes $\widehat p$. Write $S=T-h$ and, for one dyad, let $X_t=(X_t^1,X_t^2)$ denote its exploitation reward pair. Define
$$ U_i=\sum_{t=h+1}^T\bigl(w^i(\widehat p)-X_t^i\bigr). $$
The exploitation reward pairs are independent across rounds, and $\mathbb E U_i=0$ under this conditioning.

The relevant variance concerns the coordinate difference. Since
$$ X_t^1-X_t^2\in[-1,1], $$
we have
$$ \operatorname{Var}(X_t^1-X_t^2) \le \mathbb E(X_t^1-X_t^2)^2\le1, $$
regardless of dependence within the reward pair. Independence across rounds therefore gives
$$ \mathbb E(U_1-U_2)^2\le S. $$
Using the identity
$$ \max(U_1,U_2)=\frac{U_1+U_2+|U_1-U_2|}{2} $$
and Cauchy–Schwarz yields
$$ \mathbb E\max(U_1,U_2)\le\frac{\sqrt S}{2}. $$

Regret accounting

On the estimation event, the stability lemma bounds both exploitation mean deficits by $8\eta$. Exploration contributes at most $h$ to either player’s deficit, because rewards and benchmark coordinates belong to $[0,1]$.

On the exceptional event, regret is pathwise at most $T$. Its probability is at most $1/T$. Consequently, the expected average regret of this type satisfies
$$ \mathbb E R_{\mathrm{type}} \le h+8T\eta+\frac{\sqrt T}{2}+1. $$

Put
$$ B=\left(\frac{KT^2\ell}{n}\right)^{1/3}. $$
The unrounded quantity defining $q$ is at least $1$, because $T\ge K$ and $n\ge1$. Hence
$$ h\le2B+1, \qquad T\sqrt{\frac{\ell}{2q}}\le\frac B{\sqrt2}. $$
The quantization contribution satisfies $T\rho\le1/16$. Thus
$$ \mathbb E R_{\mathrm{type}}\le C(\sqrt T+B). $$

If $h>T$, then $T<2B+1$. Since $K\ge4$ and $T\ge K$, this implies $B>3T/8$, so the fallback policy also satisfies this bound.

Every policy has pathwise regret at most $T$. Enlarging the universal constant if necessary gives
$$ \mathbb E R_{\mathrm{type}} \le C\min\left\{ T,\, \sqrt T+\left(\frac{KT^2\ell}{n}\right)^{1/3} \right\}. $$
Finally,
$$ R_{N,T}=\sum_g\mu_gR_g, $$
where $R_g$ is the average regret within type $g$. Taking expectations and summing proves the population upper bound.

4. Expected regret is nonnegative

This fact is needed because regret is defined without positive parts.

Fix an environment, a controller, and a dyad. Conditional mean rewards equal the means of its assigned actions. Therefore its expected time-average payoff is some $u\in C$.

The payoff $u$ cannot strictly exceed $v$ in both coordinates: that would strictly increase the minimum advantage above $z$. Hence
$$ \max_i(v^i-u^i)\ge0. $$
Jensen’s inequality for the convex maximum function gives
$$ \mathbb E\max_i\left\{Tv^i-\sum_{t=1}^T X_t^i\right\} \ge T\max_i(v^i-u^i)\ge0. $$

Thus expected regret is nonnegative for each dyad, each type, and every fixed environment. No pathwise nonnegativity is asserted.

5. Learning lower bound for one type

Fix an arbitrary permitted rectangular action set with $K$ joint actions and $n$ dyads. Let
$$ M=nT, \qquad H=K-1, \qquad \varepsilon=\frac1{16}\left(\frac HM\right)^{1/3}. $$
Because $M\ge K$, we have $0<\varepsilon\le1/16$.

Choose one distinguished action $a_0$. In the null environment, set
$$ r_0(a_0)=(1/2,1), \qquad r_0(a)=(1/2,1/2)\quad(a\ne a_0). $$
For every $j\ne a_0$, define an alternative differing only at $j$, with
$$ r_j(j)=(1/2+\varepsilon,1/2+\varepsilon). $$
Use independent Bernoulli coordinates with these means; a coordinate of mean $1$ is deterministic.

Benchmarks

In the null environment, both maximin values are $1/2$. For player $1$, this follows because its payoff is constantly $1/2$. For player $2$, all payoffs are at least $1/2$, and an opposing row different from the row of $a_0$ caps its guarantee at $1/2$. Such a row exists by the action-set hypotheses.

All null payoffs have first coordinate $1/2$, so secondary optimality gives
$$ v_0=(1/2,1). $$

In alternative $j$, player $1$ still has maximin value $1/2$: all payoffs are at least $1/2$, while an opposing column different from the column of $j$ makes every first-player payoff exactly $1/2$.

Write player $2$’s maximin value as $1/2+d$. All its payoffs are at least $1/2$, and a row different from the row of $a_0$ contains only payoffs at most $1/2+\varepsilon$. Therefore
$$ 0\le d\le\varepsilon. $$
The policy assigning mass $2d$ to $a_0$ and $1-2d$ to $j$ has both advantages equal to
$$ (1-2d)\varepsilon. $$
Thus the alternative’s optimal minimum advantage is at least $(1-2\varepsilon)\varepsilon$, giving
$$ v_j^1\ge\frac12+\frac34\varepsilon. $$

Information comparison, including batched feedback

Let $Q_j$ be the total number of plays of action $j$, and put
$$ D_0=\mathbb E_0\sum_{j\ne a_0}Q_j. $$
Under the null, the expected type-average regret is at least the second-player deficit:
$$ \mathbb E_0R_{\mathrm{type}}\ge\frac{D_0}{2n}. $$

Let $\mathbb P_0,\mathbb P_j$ be the complete transcript laws. The conditional assignment kernel is the same under both environments. Conditional on assignments, reward laws factor across dyads within each round. The relative-entropy chain rule therefore applies to these batches, and only rewards from action $j$ contribute.

For one reward pair at $j$, the divergence from null to alternative is
$$ -\ln(1-4\varepsilon^2)\le8\varepsilon^2. $$
Consequently,
$$ D_{\mathrm{KL}}(\mathbb P_0\Vert\mathbb P_j) \le8\varepsilon^2\mathbb E_0Q_j. $$

Pinsker’s inequality, together with $0\le Q_j\le M$, yields
$$ \mathbb E_jQ_j \le\mathbb E_0Q_j+ 2M\varepsilon\sqrt{\mathbb E_0Q_j}. $$
Averaging over alternatives and using concavity of the square root gives
$$ \frac1H\sum_j\mathbb E_jQ_j \le \frac{D_0}{H} +2M\varepsilon\sqrt{\frac{D_0}{H}}. $$

A fixed prior

Give the null probability $1/2$ and every alternative probability $1/(2H)$.

If $D_0\ge\varepsilon M$, the null contribution to Bayes regret is at least $\varepsilon M/(4n)$. The alternative contributions are nonnegative by Section 4.

Otherwise, $D_0<\varepsilon M$. Since $\varepsilon\le1/16$ and $H\ge1$,
$$ \frac{D_0}{H}\le\frac M{16}. $$
Also,
$$ 2\varepsilon\sqrt{\frac{D_0}{H}} \le2\sqrt{\frac{\varepsilon^3M}{H}} =\frac1{32}. $$
Hence
$$ \frac1H\sum_j\mathbb E_jQ_j\le\frac{3M}{32}. $$

In alternative $j$, the first-player deficit gives
$$ \mathbb E_jR_{\mathrm{type}} \ge \frac{\varepsilon}{n} \left(\frac{3M}{4}-\mathbb E_jQ_j\right). $$
The alternatives’ combined prior contribution is therefore at least
$$ \frac{\varepsilon M}{2n} \left(\frac34-\frac3{32}\right) >\frac{\varepsilon M}{4n}. $$

Both cases give Bayes regret at least $\varepsilon M/(4n)$. Since $H=K-1\ge3K/4$,
$$ \inf_\Lambda\sup_P\mathbb E R_{\mathrm{type}} \ge c\left(\frac{KT^2}{n}\right)^{1/3}. $$

6. Direct sum and individual-noise lower bounds

Direct sum over supported types

Take the product of the priors from Section 5, one for every supported type.

For a given type, condition on fixed environments for all other types. In the null-versus-alternative comparison for the chosen type, the other reward kernels are identical. Although their observations can influence subsequent assignments, they contribute zero relative entropy. The same conditional assignment kernels and the same batch chain-rule calculation remain valid.

The one-type Bayes lower bound therefore holds conditionally on every choice of the other environments. Integrating and summing the type contributions gives
$$ \mathcal R^* \ge c\sum_g\mu_g \left(\frac{K_gT^2}{n_g}\right)^{1/3}. $$
This argument permits arbitrary coordination between types and dyads.

Unavoidable individual noise

For every type and every action, use the action-independent law
$$ (X^1,X^2)=(B,1-B), \qquad B\sim\operatorname{Bernoulli}(1/2). $$
Every mean payoff and benchmark is $(1/2,1/2)$. A dyad’s regret is exactly
$$ \left|\sum_{t=1}^T(B_t-1/2)\right|. $$

Let $Z=\sum_{t=1}^T(2B_t-1)$. Independence gives
$$ \mathbb EZ^2=T, \qquad \mathbb EZ^4=T+6\binom T2=3T^2-2T\le3T^2. $$
Paley–Zygmund applied to $Z^2$ implies
$$ \Pr(Z^2\ge T/2)\ge\frac1{12}. $$
Therefore
$$ \mathbb E|Z|/2\ge\frac{\sqrt T}{24\sqrt2}. $$

Population averaging preserves this expectation, so
$$ \mathcal R^*\ge c\sqrt T. $$
Combining the two lower bounds using $\max\{a,b\}\ge(a+b)/2$ proves $\mathcal R^*\ge cW$.

7. New result: fixed exploration followed by commitment requires a logarithm

This section identifies a limitation of the upper-bound algorithm’s architecture.

Restricted controller class

Consider one type with $n$ dyads. Before receiving any rewards, the controller selects its exploration length and complete exploration assignment schedule, possibly using randomness independent of the rewards. After exploration, subsequent assignments may depend on the exploration observations and fresh randomness, but must ignore all subsequent rewards.

Call this class $\mathsf{ETC}$. The algorithm in Section 3 belongs to it. The unrestricted controller class is larger.

An implicit lower bound

For any controller in $\mathsf{ETC}$, write
$$ r=\sup_P\mathbb E R_{\mathrm{type}}. $$
If $r\le T/1024$, then
$$ r^3\ge \frac{(K-1)T^2}{8192n} \ln\left(\frac{T}{4r}\right). $$

Proof. Section 6 ensures $r>0$. Use the family from Section 5, now with
$$ \varepsilon=\frac{8r}{T}\le\frac1{128}. $$
All benchmark calculations remain valid.

Let $Q_j$ again count all plays of alternative action $j$. The null regret bound gives
$$ D_0=\mathbb E_0\sum_{j\ne a_0}Q_j\le2nr. $$
For every alternative,
$$ r\ge \frac{\varepsilon}{n} \left(\frac{3nT}{4}-\mathbb E_jQ_j\right). $$
Since $nr/\varepsilon=nT/8$, this implies
$$ \mathbb E_jQ_j\ge\frac{5nT}{8}. $$

Set $M=nT$ and define the event
$$ E_j=\{Q_j\ge M/2\}. $$
Because $Q_j\le M$,
$$ \mathbb E_jQ_j \le\frac M2+\frac M2\Pr_j(E_j). $$
Thus
$$ \Pr_j(E_j)\ge\frac14. $$
Under the null, Markov’s inequality gives
$$ \Pr_0(E_j) \le\frac{2\mathbb E_0Q_j}{M} \le\frac{4r}{T}. $$

Now retain only the controller’s initial random choices, its exploration observations, and its complete subsequent action sequence. Subsequent reward observations are excluded. Because the controller ignores those rewards, the post-exploration action sequence is produced by a common stochastic kernel from the retained exploration information.

Let $e_j$ be the expected number of exploration plays of $j$. The exploration design is independent of rewards, so $e_j$ is the same under the null and every alternative.

For a Bernoulli coordinate,
$$ D_{\mathrm{KL}}\!\left( \operatorname{Bernoulli}(1/2+\varepsilon) \Vert \operatorname{Bernoulli}(1/2) \right) \le4\varepsilon^2. $$
Indeed, relative entropy is at most the chi-squared divergence, which here equals $4\varepsilon^2$. The two independent coordinates give a pair divergence at most $8\varepsilon^2$.

The chain rule for exploration observations and data processing for subsequent actions therefore bound the retained transcript divergence, in the alternative-to-null direction, by
$$ 8\varepsilon^2e_j. $$

The event $E_j$ is measurable from that transcript. Write
$$ p_j=\Pr_j(E_j), \qquad \alpha_j=\Pr_0(E_j). $$
Data processing to this binary event gives
$$ 8\varepsilon^2e_j \ge d(p_j\Vert\alpha_j), $$
where $d$ denotes Bernoulli relative entropy. The elementary entropy bound
$$ d(p\Vert\alpha)\ge p\ln(1/\alpha)-\ln2 $$
implies
$$ 8\varepsilon^2e_j \ge \frac14\ln\left(\frac{T}{4r}\right)-\ln2. $$
Since $r\le T/1024$, the logarithm is at least $8\ln2$, and hence
$$ e_j\ge \frac1{64\varepsilon^2} \ln\left(\frac{T}{4r}\right). $$

Summing over the $H=K-1$ alternatives, and observing that exploration plays are included among all null non-$a_0$ plays, yields
$$ 2nr\ge D_0\ge\sum_j e_j \ge \frac{H}{64\varepsilon^2} \ln\left(\frac{T}{4r}\right). $$
Substituting $\varepsilon=8r/T$ proves
$$ r^3\ge \frac{HT^2}{8192n} \ln\left(\frac{T}{4r}\right). $$
$\square$

Matching restricted rate for a single $2\times2$ game

Let $n=1$ and $K=4$. For every $\mathsf{ETC}$ controller, the preceding inequality implies, for all sufficiently large $T$,
$$ r\ge cT^{2/3}(\ln T)^{1/3}. $$

To check this implication, split into two cases. If $r\ge T^{3/4}$, the asserted bound follows because
$$ \frac{T^{3/4}}{T^{2/3}(\ln T)^{1/3}} =\frac{T^{1/12}}{(\ln T)^{1/3}} \longrightarrow\infty. $$
If $r<T^{3/4}$, then for sufficiently large $T$, we have $r\le T/1024$ and
$$ \ln\left(\frac{T}{4r}\right) \ge\frac14\ln T-\ln4 \ge\frac18\ln T. $$
The implicit lower bound then gives the asserted rate.

Section 3 supplies an $\mathsf{ETC}$ upper bound of the same order when $n=1$ and $K=4$. Therefore
$$ \inf_{\Lambda\in\mathsf{ETC}}\sup_P \mathbb E R_{1,T} = \Theta\!\left(T^{2/3}(\ln T)^{1/3}\right). $$

The divergence argument uses the fact that exploitation rewards are ignored. For a fully adaptive controller, those rewards may affect subsequent action counts; the retained-transcript argument above no longer applies. Consequently, this theorem does not close the unrestricted minimax gap.

8. Computation and an exactly resolved population regime

Running time

For each supported type, the upper-bound algorithm solves four rational linear programs:

• two programs computing the players’ maximin values;
• one computing $\widehat z$;
• one maximizing total payoff under the relaxed constraints.

Each has $O(m)$ variables and constraints. Quantized empirical means have bit length $O(\log(NT))$. Exact rational linear-programming solutions and the subsequent coefficients have encoding lengths polynomial in $m$ and $L+\log(NT)$.

Processing observations and generating assignments requires $O(NT)$ operations, apart from arithmetic and sampling. Rational categorical sampling can be implemented with expected polynomial bit cost. A conservative expected bit-operation bound is
$$ (NT+\tau)\operatorname{poly}\!\left(m,L+\log(NT)\right) +NT\,C_{\mathrm{quant}}(b), \qquad b=\left\lceil\log_2(16T)\right\rceil, $$
where $C_{\mathrm{quant}}(b)$ is the cost of obtaining one $b$-bit quantization of a reward pair.

If the observation interface returns that quantization in $O(b)$ bit operations, the last term is absorbed into the displayed polynomial bound. If rewards arrive as explicitly encoded rationals, their reading and quantization costs must instead be included. For arbitrary real observations with no specified access model, an unconditional bit-running-time statement is not defined; the mathematical regret bound does not require such a representation assumption.

A regime with matching unrestricted bounds

If every supported type satisfies
$$ n_g\ge K_g\sqrt T\,\ell_g, $$
then
$$ \left(\frac{K_gT^2\ell_g}{n_g}\right)^{1/3} \le\sqrt T. $$
The population upper bound is therefore $O(\sqrt T)$, while Section 6 gives the matching lower bound. Hence, in this regime,
$$ \mathcal R^*=\Theta(\sqrt T). $$

9. Remaining open point

For general populations, the proved unrestricted bounds still differ by a logarithmic factor. The new restricted-class theorem shows that simply sharpening the analysis of fixed exploration followed by commitment cannot remove that factor, even with four joint actions and one dyad.

What remains is either an adaptive algorithm attaining $O(W)$, or a stronger lower bound applicable to all admissible controllers.

⟨structured verdict parsed — rendered above⟩

Overall assessment

The output establishes substantial, rigorous partial results, but does not resolve the general minimax order requested in USER_TASK. I found no false central step in the population bounds or the restricted-controller theorem.

The established unrestricted bounds are
$$ c\left[ \sqrt T+ \sum_g\mu_g\left(\frac{K_gT^2}{n_g}\right)^{1/3} \right] \le \mathcal R^* \le C\sum_g\mu_g \min\left\{ T,\, \sqrt T+ \left(\frac{K_gT^2\ell_g}{n_g}\right)^{1/3} \right\}. $$
These leave a logarithmic gap in general. The prover explicitly acknowledges that gap and correctly limits its logarithmic lower bound to the restricted exploration-then-commit class.

Step-by-step verification

1. Definitions and scope

The substitutions
$$ n_g=N\mu_g, \qquad \sum_g\mu_g \left(\frac{K_gT^2}{n_g}\right)^{1/3} = \frac{T^{2/3}}{N^{1/3}} \sum_g K_g^{1/3}\mu_g^{2/3} $$
are correct.

The action-set assumptions imply $K_g\ge4$, and the horizon assumption gives $T\ge K_g$. These restrictions are used correctly in the rounding estimates and lower-bound constructions.

The introductory claim that the general problem is only partially resolved accurately describes the results that follow. The cited [single-dyad paper](https://ifaamas.org/Proceedings/aamas2020/pdfs/p1395.pdf) provides background; the population arguments do not depend on transferring its theorem to this model.

2. Benchmark geometry and stability

Existence. Both optimization stages operate on nonempty compact sets with continuous objectives. This establishes existence.

Geometric property. If the first benchmark advantage equals $z$ and the second strictly exceeds $z$, the proposed sufficiently small convex perturbation toward a point with larger first payoff raises both advantages above $z$. The contradiction is valid.

Uniqueness. The geometric property and secondary optimality justify uniqueness. The discussion is compressed, but the assertion that the smaller-advantage coordinate reaches its global feasible maximum also excludes another benchmark with the opposite ordering of advantages. No additional mathematical lemma is needed.

Perturbation estimates. Uniform coordinatewise error at most $\eta$ implies
$$ |\widehat s^i-s^i|\le\eta, \qquad |\widehat z-z|\le2\eta. $$
The maximin estimate applies to arbitrary mixed strategies because their payoffs are convex combinations of matrix entries. Taking extrema preserves the uniform error bound.

Relaxed feasibility. A policy attaining $v$ has estimated advantages at least $z-2\eta$, which is at least $\widehat z-4\eta$. Thus the comparison policy is feasible.

Coordinatewise guarantee. The constants are correct:

• Estimated feasibility gives true advantages at least $z-8\eta$.
• Estimated total-payoff optimality gives true total payoff at least $v^1+v^2-4\eta$.
• In the unequal-advantage case, the geometric property supplies the upper bound on the smaller-advantage coordinate needed to bound the other coordinate.

Consequently, the stated guarantee
$$ w^i(\widehat p)\ge v^i-8\eta $$
is justified for both players.

3. Population algorithm and upper bound

Feasibility under batching. The inequality $nh\ge Kq$ supplies enough dyad-round slots for the designated samples. A predetermined assignment uses no incomplete-round observations. Exploitation has the required conditional expected counts. Persistent dyads introduce no obstruction.

Concentration. The designated samples are independent samples from their respective fixed action laws. Coordinatewise Hoeffding bounds remain applicable despite dependence within each reward pair.

Downward quantization contributes bias at most $\rho$. The displayed union bound is correct:
$$ 4K e^{-\ell}\le\frac1T, $$
because the chosen base-two logarithm satisfies $\ell\ge\ln(4KT)$.

Individual fluctuations. Conditioning on the exploration history fixes $\widehat p$. Independent action sampling and fresh reward draws make the exploitation pairs independent across rounds under that conditioning.

The relevant difference satisfies
$$ X_t^1-X_t^2\in[-1,1], $$
so its variance is at most $1$. Therefore
$$ \mathbb E(U_1-U_2)^2\le S. $$
The maximum identity and Cauchy–Schwarz correctly yield
$$ \mathbb E\max(U_1,U_2)\le\frac{\sqrt S}{2}. $$
This calculation does not assume independence of the two coordinates.

Regret accounting. Exploration contributes at most $h$ to each coordinate’s deficit. On successful estimation, exploitation contributes at most $8T\eta$ plus the fluctuation term. On failure, the pathwise upper bound $T$ and failure probability at most $1/T$ justify the additive $1$.

The argument requires only a pathwise upper bound on regret, so potentially negative realized regret causes no problem.

Rounding and fallback. The unrounded sample count is at least $1$. The bounds
$$ h\le2B+1, \qquad T\sqrt{\frac{\ell}{2q}}\le\frac B{\sqrt2} $$
are correct. Also, $T\rho\le1/16$.

If $h>T$, the deduction $B>3T/8$ follows from $T\ge4$. Thus the fallback is covered by the asserted upper bound.

Finally, population averaging gives exactly
$$ R_{N,T}=\sum_g\mu_gR_g. $$
The displayed population upper bound follows.

4. Nonnegativity of expected regret

The expected time-average payoff of each dyad belongs to the corresponding convex hull, even under adaptive action selection.

A feasible payoff strictly exceeding $v$ in both coordinates would improve the primary bargaining objective. Hence at least one expected benchmark deficit is nonnegative. Jensen’s inequality for the maximum then gives nonnegative expected regret.

This establishes precisely the expected nonnegativity needed later. It does not improperly assert pathwise nonnegativity.

5. One-type learning lower bound

Admissible environments. All proposed Bernoulli means lie in $[0,1]$. Since $M\ge K$,
$$ 0<\varepsilon\le\frac1{16}. $$
The construction works for every permitted rectangular action set.

Maximin calculations. The alternate row and column used to bound the guarantees exist because each player has at least two actions. The claimed null maximin values and alternative first-player maximin value are correct. The bounds
$$ 0\le d\le\varepsilon $$
also follow as stated.

Alternative benchmark. The proposed mixture has valid probabilities and equal advantages $(1-2d)\varepsilon$. The resulting bound
$$ v_j^1\ge\frac12+\frac34\varepsilon $$
is conservative and correct.

Batchwise information comparison. Conditional assignment kernels agree across environments. Conditional reward laws factor across dyads, and only samples from action $j$ differ. The relative-entropy chain rule therefore applies despite batching and adaptive assignments.

For one reward pair, the divergence is
$$ -\ln(1-4\varepsilon^2)\le8\varepsilon^2. $$
Pinsker’s inequality with the bounded statistic $Q_j\in[0,M]$ gives the stated expectation comparison.

Prior calculation. Both branches are valid. In the small-$D_0$ branch,
$$ 2\sqrt{\frac{\varepsilon^3M}{H}}=\frac1{32}, $$
and the average alternative action count is at most $3M/32$. The prior weights and regret constants are accounted for correctly.

The fixed-prior argument proves the claimed one-type lower bound.

6. Direct sum and individual noise

Direct sum. Conditioning on the other types’ environments leaves their conditional reward kernels identical in the chosen null-versus-alternative comparison. Their observations may influence assignments, but contribute no additional divergence. The one-type argument remains valid for controllers coordinating all types.

Integrating over the product prior and summing weighted type regrets is justified.

Individual-noise lower bound. The action-independent complementary Bernoulli law has the claimed benchmark. Each dyad’s regret equals the absolute centered Bernoulli sum.

The second and fourth moments are correct:
$$ \mathbb EZ^2=T, \qquad \mathbb EZ^4=3T^2-2T. $$
Paley–Zygmund applies to the nonnegative variable $Z^2$ with finite second moment and gives the stated probability and expectation bounds.

Population averaging preserves the expectation, so the noise lower bound remains of order $\sqrt T$, regardless of $N$.

Combining the two separate worst-case lower bounds using their maximum is valid; the environments need not simultaneously realize both contributions.

7. Restricted exploration-then-commit theorem

The restriction is defined sufficiently precisely: exploration design is independent of rewards, and exploitation ignores subsequent rewards.

The proof correctly distinguishes:

• Total action counts, used to define $E_j$.
• Exploration counts, which determine the retained transcript’s information.

The null bound, alternative expected-count bound, and event probability estimates are correct.

The alternative-to-null Bernoulli divergence is at most $4\varepsilon^2$ per coordinate. Retaining the initial random choices and exploration observations permits the subsequent action sequence to be represented by a common stochastic kernel. Thus the divergence bound depends only on $e_j$.

The binary relative-entropy estimate is valid. Under $r\le T/1024$, its entropy subtraction leaves the stated constant, and substitution of $\varepsilon=8r/T$ gives
$$ r^3\ge \frac{(K-1)T^2}{8192n} \ln\left(\frac{T}{4r}\right). $$

The two-case asymptotic argument for $n=1$ and $K=4$ correctly proves the matching restricted rate.

Scope limitation: This theorem supplies no logarithmic lower bound for unrestricted adaptive controllers. The prover correctly states that limitation.

8. Running time and resolved regime

The four optimization problems have polynomial size. Quantization and rational tolerance selection keep their coefficient lengths polynomially bounded. The stated expected running time is appropriately conditional on the reward-access model.

For arbitrary real observations, the original task does not specify a bit-access interface. The prover correctly identifies that an unconditional bit-operation bound is therefore undefined; this qualification is not a mathematical defect.

Under
$$ n_g\ge K_g\sqrt T\,\ell_g $$
for every supported type, the upper learning term is at most $\sqrt T$. Together with the noise lower bound, this establishes the claimed unrestricted rate
$$ \mathcal R^*=\Theta(\sqrt T) $$
in that regime.

Issue and actionable feedback

Major — the general target remains unresolved. Sections 1 and 9 leave a logarithmic separation between the unrestricted upper and lower bounds. The restricted-controller result and the resolved high-population regime do not provide matching bounds for all admissible inputs.

Required completion: Supply an unrestricted result that closes that separation, with its applicable parameter ranges and algorithmic running time. Further clarification of the existing calculations alone cannot complete the task.

No additional blocking mathematical error was found in the arguments presented.

⟨structured verdict parsed — rendered above⟩