An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret (aaai23-25985)

Given a finite set of reward types Θ, rational masses ν, K arms, horizon H, and unknown bounded type-arm reward laws, a learner chooses one common arm per round and observes the aggregate reward of every positive-mass type; compute adaptive policies with polynomial-time implementation and determine a high-probability bound for per-capita regret relative to the ν-weighted Nash-welfare-optimal policy.

A society is given by its support: a list \(\Theta\) of \(\tau\geq1\) types with positive binary-rational masses \(\nu_\theta\), normalized by \(\sum_\theta\nu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types; there are \(m=K\geq1\) arms and \(H\geq1\) rounds.
Each arm has an unknown stationary joint reward law on \([0,1]^\Theta\), with type means \(\mu_{\theta,a}\); successive pulls give independent samples, while coordinates within a sample may be dependent.
At round \(t\), using only previous observations, the learner selects \(\pi_t\in\Delta_K\), samples one common arm \(a_t\sim\pi_t\), and observes each type's aggregate \(Y_{\theta,t}=\nu_\theta X_{\theta,a_t,t}\).
Define \(W_\nu(\pi,\mu)=\prod_{\theta\in\Theta}(\sum_a\pi_a\mu_{\theta,a})^{\nu_\theta}\), with value zero if any factor vanishes, and \(\pi^\star\in\arg\max_{\pi\in\Delta_K}W_\nu(\pi,\mu)\). Per-capita cumulative regret is \(R_H=\sum_{t=1}^H[W_\nu(\pi^\star,\mu)-W_\nu(\pi_t,\mu)]\).
For \(\delta\in(0,1)\), let \(B^\star(K,H,\nu,\delta)=\inf_A\inf\{b\geq0:\sup_D\Pr_{A,D}(R_H>b)\leq\delta\}\), where \(A\) ranges over learners without computational restrictions and \(D\) over the reward laws above.
Use binary-rational reward observations; \(L\) denotes the input bit length plus the largest observation encoding length. Polynomial implementation means time per round polynomial in \(m,\tau,L,\log H,\log(1/\delta)\).

What is the minimax high-probability regret \(B^\star(K,H,\nu,\delta)\), and can it be attained up to logarithmic factors and additive \(1\) with polynomial-time implementation, or is attaining that guarantee NP-hard?

For discrete agents and unnormalized Nash-product regret, an efficient algorithm achieves \(\widetilde O(\sqrt{NKH}+NK)\) with probability \(1-\delta\). [Jones–Nguyen–Nguyen](https://arxiv.org/abs/2209.11817)
For equal masses \(\nu_\theta=1/\tau\), geometric-mean expected regret has upper bound \(\widetilde O(K^{2/\tau}H^{(\tau-1)/\tau}+K)\) and a matching horizon exponent in the stated lower-bound regime; this does not settle arbitrary rational masses and minimax high-probability regret. [Zhang–Vuong–Luo](https://arxiv.org/html/2405.20678v1)

Status and proved results

The full joint characterization in $K,H,\nu,\delta$ remains partial. The results below establish polynomial-time attainment of the minimax rate up to logarithmic factors and additive $1$ for $0<\delta<1/4$, extend the lower bounds to every $\delta<1$, and characterize exactly when the minimax quantile is zero.

Assume first that $K\geq2$. Define
$$ q=\min\{1,K/H\},\qquad \beta_S=\sum_{\theta\in S}\nu_\theta, $$
and
$$ \mathcal F = H\max\left\{ \sqrt q,\ \max_{\varnothing\neq S\subseteq\Theta}\beta_Sq^{\beta_S} \right\}, \qquad \Lambda=\log\left(\frac{8\tau KH}{\delta}\right). $$
For the confidence-dependent lower bound, put
$$ s=1-\delta,\qquad \lambda=\max\left\{0,1-\frac1{Ks}\right\}. $$

There are universal constants $c,C>0$ such that, for every $\delta\in(0,1)$,
$$ \begin{aligned} cH\max\left\{ s\lambda^2\sqrt q,\ \max_{\varnothing\neq S\subsetneq\Theta} \beta_S(1-\beta_S)s^{\beta_S+2}q^{\beta_S} \right\} &\leq B^\star(K,H,\nu,\delta)\\ &\leq \min\{H,C\Lambda^2\mathcal F+1\}. \end{aligned} $$
An empty maximum over proper subsets is interpreted as zero. The upper bound has an implementation whose time per round is polynomial in $K,\tau,L,\log H,\log(1/\delta)$.

In particular, for $0<\delta<1/4$,
$$ c\mathcal F \leq B^\star(K,H,\nu,\delta) \leq \min\{H,C\Lambda^2\mathcal F+1\}. $$

The exact zero-quantile characterization is
$$ B^\star(K,H,\nu,\delta)=0 \quad\Longleftrightarrow\quad K=1 \ \text{or}\ \left(\tau=1\ \text{and}\ \delta\geq1-\frac1K\right). $$

The larger-$\delta$ regime cannot have the same uniform mass dependence as the high-confidence regime. Section 8 gives an explicit two-type example demonstrating this.

1. A continuity inequality adapted to Bernstein bounds

For positive weights $w_i$ satisfying
$$ \sum_iw_i\leq1, $$
define
$$ F_w(x)=\prod_i x_i^{w_i}, \qquad \alpha=\min\left\{\frac12,\min_iw_i\right\}. $$

Lemma. Suppose $x,y\in[0,1]^I$, $x\leq y$ coordinatewise, and
$$ y_i-x_i\leq8\sqrt{zx_i}+25z $$
for every $i$, where $z\geq0$. Then
$$ F_w(y)-F_w(x)\leq40z^\alpha. $$

Proof. On the positive orthant,
$$ h^\top\nabla^2F_w(x)h = F_w(x)\left[ \left(\sum_iw_i\frac{h_i}{x_i}\right)^2 - \sum_iw_i\left(\frac{h_i}{x_i}\right)^2 \right]. $$
Weighted Cauchy–Schwarz bounds the squared sum by
$$ \left(\sum_iw_i\right) \sum_iw_i\left(\frac{h_i}{x_i}\right)^2. $$
Thus the Hessian is negative semidefinite. Continuity extends concavity to the boundary.

The cases $z=0$ and $z\geq1$ follow immediately from the hypothesis and $0\leq F_w\leq1$. Suppose $0<z<1$. Let
$$ m=\min_i x_i, $$
and choose $j$ with $x_j=m$.

If $m\leq z$, then $y_j\leq34z$. When $34z<1$,
$$ F_w(y)\leq y_j^{w_j} \leq(34z)^\alpha \leq\sqrt{34}\,z^\alpha. $$
When $34z\geq1$, the same bound follows from
$$ F_w(y)\leq1\leq(34z)^\alpha. $$

If $m>z$, the tangent inequality for concavity gives
$$ \begin{aligned} F_w(y)-F_w(x) &\leq F_w(x)\sum_iw_i\frac{y_i-x_i}{x_i}\\ &\leq33\sqrt z\,F_w(x)\sum_i\frac{w_i}{\sqrt{x_i}}. \end{aligned} $$
Here $z/x_i\leq\sqrt{z/x_i}$. Also,
$$ \sum_i\frac{w_i}{\sqrt{x_i}}\leq\frac1{\sqrt m}, \qquad F_w(x)\leq m^{w_j}\leq m^\alpha. $$
Therefore
$$ F_w(y)-F_w(x) \leq33\sqrt z\,m^{\alpha-1/2} \leq33z^\alpha, $$
because $m>z$ and $\alpha\leq1/2$. This proves the lemma.

2. Confidence bounds and adaptive sampling

Because $\nu_\theta>0$, the learner recovers each individual reward exactly:
$$ X_{\theta,a_t,t}=\frac{Y_{\theta,t}}{\nu_\theta}. $$
Dependence between coordinates within a reward vector does not prevent marginal concentration inequalities.

For bounded-size empirical statistics, round each recovered reward upwards to a dyadic grid of mesh
$$ \eta=2^{-\lceil\log_2H\rceil}\leq\frac1H. $$
If $\mu'_{\theta,a}$ is its rounded mean, then
$$ \mu_{\theta,a}\leq\mu'_{\theta,a}\leq\mu_{\theta,a}+\eta. $$
Rounded observations remain in $[0,1]$ and remain independent across successive pulls.

Let
$$ b=\left\lceil\log_2\left(\frac{4\tau KH}{\delta}\right)\right\rceil. $$
For $n\geq1$, let $\widehat\mu_{\theta,a,n}$ denote the rounded empirical mean after $n$ pulls. A bounded random variable in $[0,1]$ with mean $u$ has variance at most $u$. Bernstein’s inequality consequently gives
$$ \Pr\left( \left|\widehat\mu_{\theta,a,n}-\mu'_{\theta,a}\right| > \sqrt{\frac{2\mu'_{\theta,a}b}{n}}+\frac bn \right) \leq2e^{-b}. $$
A union bound over $\theta,a,n$ with $n\leq H$ shows that these inequalities hold simultaneously with probability at least $1-\delta/2$. They concern the fixed sample stream of each arm, so adaptive selection of which stream to observe causes no difficulty.

For a pulled arm, use
$$ U_{\theta,a} = \min\left\{ 1,\ \widehat\mu_{\theta,a,n} +4\sqrt{\widehat\mu_{\theta,a,n}b/n} +8b/n \right\}. $$
Approximate the square root upwards with error at most $b/(4n)$. For an unpulled arm set $U_{\theta,a}=1$.

On the simultaneous concentration event, with $d_a=\max\{1,n_a\}$,
$$ \mu'_{\theta,a}\leq U_{\theta,a} \leq \mu'_{\theta,a} + 8\sqrt{\frac{\mu'_{\theta,a}b}{d_a}} + \frac{16b}{d_a}. $$

To verify the constants, write $h=\widehat\mu_{\theta,a,n}$, $u=\mu'_{\theta,a}$ and $v=b/n$. The concentration event implies
$$ |h-u|\leq\sqrt{2uv}+v. $$
Since $\sqrt{2uv}\leq u/2+v$, it follows that $u\leq2h+4v$, and hence
$$ u-h\leq2\sqrt{hv}+4v. $$
This proves optimism. Also $h\leq2u+2v$, so the upper-estimate error, including the upwards square-root approximation, is at most
$$ 8\sqrt{uv}+16v. $$
Clipping at $1$ preserves optimism. The unpulled case follows from $b\geq1$.

At round $t$, define
$$ z_t=\sum_a\frac{\pi_{t,a}}{\max\{1,n_{t,a}\}}, \qquad \rho_t=bz_t, $$
and
$$ x_{\theta,t}=\sum_a\pi_{t,a}\mu_{\theta,a}, \qquad y_{\theta,t}=\sum_a\pi_{t,a}U_{\theta,a}. $$
Weighted Cauchy–Schwarz gives
$$ y_{\theta,t}-x_{\theta,t} \leq \eta+8\sqrt{\rho_t(x_{\theta,t}+\eta)}+16\rho_t. $$
Every denominator in $z_t$ is at most $H$, so $\eta\leq1/H\leq\rho_t$. Consequently,
$$ y_{\theta,t}-x_{\theta,t} \leq8\sqrt{\rho_tx_{\theta,t}}+25\rho_t. $$

We next control the predictable sampling quantities $z_t$. Set
$$ Z_t=\frac1{\max\{1,n_{t,a_t}\}}, \qquad c_0=1-e^{-1}. $$
Conditional on the selected policy, $\mathbb E[Z_t]=z_t$. Since
$$ e^{-u}\leq1-c_0u\qquad(0\leq u\leq1), $$
the process
$$ \exp\left(c_0\sum_{t\leq h}z_t-\sum_{t\leq h}Z_t\right) $$
is a nonnegative supermartingale starting at $1$. Markov’s inequality therefore gives, with probability at least $1-\delta/2$,
$$ c_0\sum_{t=1}^Hz_t \leq \sum_{t=1}^HZ_t+\log(2/\delta). $$
An arm pulled $n\geq1$ times contributes
$$ 1+\sum_{j=1}^{n-1}\frac1j\leq2+\log H. $$
Thus, on an event of probability at least $1-\delta$ encompassing both estimates,
$$ \sum_{t=1}^H\rho_t\leq Q, \qquad Q=\frac b{c_0}\left[K(2+\log H)+\log(2/\delta)\right]. $$
For a universal constant $C_0$,
$$ Q\leq C_0K\Lambda^2. $$

3. Optimism after discarding a small total mass

Let $J\subseteq\Theta$ be discarded types, and suppose $G=\Theta\setminus J$ is nonempty. Write
$$ \beta=\sum_{\theta\in J}\nu_\theta, \qquad \alpha_G=\min\left\{\frac12,\min_{\theta\in G}\nu_\theta\right\}, $$
and define the retained objective without renormalizing its exponents:
$$ F_G(\pi,\mu) = \prod_{\theta\in G} \left(\sum_a\pi_a\mu_{\theta,a}\right)^{\nu_\theta}. $$

Set
$$ \gamma=\varepsilon=\frac1{2H}, \qquad \mathcal P_\gamma = \{\pi\in\Delta_K:\pi_a\geq\gamma/K\text{ for every }a\}. $$
At each round compute a dyadic policy satisfying
$$ \pi_{t,a}\geq\frac{\gamma}{2K}, $$
and
$$ F_G(\pi_t,U_t) \geq \max_{\pi\in\mathcal P_\gamma}F_G(\pi,U_t)-\varepsilon. $$
Section 5 establishes the polynomial-time implementation, including exact feasibility.

Mixing any policy with the uniform policy at weight $\gamma$ preserves every retained utility by a factor at least $1-\gamma$. The retained exponent sum is at most $1$, so restricting to $\mathcal P_\gamma$ costs at most $\gamma$ in objective value.

Optimism and the continuity lemma now imply
$$ \max_{\pi\in\Delta_K}F_G(\pi,\mu)-F_G(\pi_t,\mu) \leq\gamma+\varepsilon+40\rho_t^{\alpha_G}. $$

For each type, put $M_\theta=\max_a\mu_{\theta,a}$. If some $M_\theta=0$, the original welfare and regret are identically zero. Otherwise define
$$ C_J=\prod_{\theta\in J}M_\theta^{\nu_\theta}. $$
Every implemented policy gives each discarded type utility at least $\gamma M_\theta/(2K)$. Therefore
$$ W_\nu(\pi^\star,\mu) \leq C_J\max_\pi F_G(\pi,\mu), $$
whereas
$$ W_\nu(\pi_t,\mu) \geq C_J\left(\frac{\gamma}{2K}\right)^\beta F_G(\pi_t,\mu). $$
Using $C_J\leq1$, $F_G\leq1$, and $1-e^{-u}\leq u$, we obtain
$$ \begin{aligned} W_\nu(\pi^\star,\mu)-W_\nu(\pi_t,\mu) &\leq \max_\pi F_G(\pi,\mu)-F_G(\pi_t,\mu) +\beta\log(4KH). \end{aligned} $$

Since $u\mapsto u^{\alpha_G}$ is concave,
$$ \sum_{t=1}^H\rho_t^{\alpha_G} \leq H^{1-\alpha_G}Q^{\alpha_G}. $$
It follows that, with probability at least $1-\delta$,
$$ R_H \leq 40H^{1-\alpha_G}Q^{\alpha_G} +\beta H\log(4KH)+1. $$

4. Selecting discarded types without subset optimization

If $q\geq1/2$, use any policy. Then
$$ R_H\leq H\leq\sqrt2\,\mathcal F. $$
Suppose $q<1/2$. Compute
$$ d=1+\left\lceil\log_2(1/q)\right\rceil, \qquad r=\frac1d, $$
and discard exactly the types satisfying $\nu_\theta<r$. Let $\beta$ be their total mass.

If $\beta\geq r$, accumulate discarded types until their total mass first reaches $r$. Each increment is smaller than $r$, so this gives a subset $S$ satisfying
$$ r\leq\beta_S<2r. $$
Since $\log(1/q)/d<1$,
$$ q^{2r}\geq e^{-2}. $$
Consequently,
$$ \mathcal F\geq H\beta_Sq^{\beta_S}\geq e^{-2}Hr. $$
Any policy then satisfies $R_H\leq e^2d\,\mathcal F$.

If $\beta<r$, the retained set is nonempty, and $\alpha_G\geq r$. Using the estimate on $Q$ from Section 2,
$$ R_H \leq C_1\Lambda Hq^{\alpha_G} +\beta H\log(4KH)+1. $$
If $\alpha_G=1/2$, the ordinary-bandit term in $\mathcal F$ gives
$$ Hq^{\alpha_G}\leq\mathcal F. $$
Otherwise a retained singleton of mass $\alpha_G$ gives
$$ \mathcal F\geq H\alpha_Gq^{\alpha_G}, $$
so in either case
$$ Hq^{\alpha_G}\leq d\,\mathcal F. $$
When $\beta>0$, the discarded set itself gives
$$ \mathcal F\geq H\beta q^\beta\geq e^{-1}\beta H, $$
because $\beta<r$. The required bound is immediate when $\beta=0$.

Finally, $d=O(\Lambda)$ and $\log(4KH)\leq\Lambda$. Thus
$$ R_H\leq C\Lambda^2\mathcal F+1 $$
with probability at least $1-\delta$. Combining this with the deterministic bound $R_H\leq H$ proves the claimed upper bound.

The algorithm uses only comparisons between individual rational masses and $1/d$. It never computes the subset maximum defining $\mathcal F$.

5. Polynomial implementation with exact feasibility

All confidence entries are rational and satisfy
$$ \frac1H\leq U_{\theta,a}\leq1. $$
Indeed, an unpulled entry equals $1$; a pulled entry has an added term at least $8b/n\geq8/H$ before clipping.

For a fixed retained set, maximize
$$ g(\pi)= \sum_{\theta\in G}\nu_\theta \log\left(\sum_a\pi_aU_{\theta,a}\right). $$
It is concave, and maximizing it is equivalent to maximizing $F_G=e^g$. On the simplex,
$$ -\log H\leq g(\pi)\leq0, $$
and
$$ 0\leq \frac{\partial g}{\partial\pi_a} = \sum_{\theta\in G} \frac{\nu_\theta U_{\theta,a}} {\sum_b\pi_bU_{\theta,b}} \leq H. $$
Thus $g$ is $H$-Lipschitz in the $\ell_1$ norm on the simplex.

5.1 The precise weak-optimization guarantee

We use the following consequence of Theorem 3.1 of Grötschel–Lovász–Schrijver, with weak optimization defined in Section 1: for a compact convex body with an explicitly known interior ball, outer ball, and polynomial-time weak separation, linear weak optimization returns a rational point $y$ such that
$$ \operatorname{dist}(y,Q)\leq\xi, \qquad c^\top y\geq\max_{z\in Q}c^\top z-\xi. $$
Its running time is polynomial in the input lengths and $\log(1/\xi)$, including the encoding lengths of the ball parameters. This guarantee allows approximate feasibility; we repair it explicitly below. [Grötschel–Lovász–Schrijver, Theorem 3.1](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1981a.pdf).

Write
$$ p(x)=(x_1,\ldots,x_{K-1},1-\textstyle\sum_{i<K}x_i), $$
and let
$$ B=2+\lceil\log_2H\rceil. $$
Apply weak optimization to the compact convex hypograph
$$ Q= \left\{ (x,v): p(x)\in\mathcal P_\gamma,\ -B\leq v\leq g(p(x)) \right\}, $$
with objective $c^\top(x,v)=v$.

A known interior-ball center is
$$ x_i=\frac1K,\qquad v=-B+1, $$
with radius $1/(8K^2)$. To check this, a perturbation of $x$ within this radius changes the last probability coordinate by at most $K/(8K^2)$, while the distance from the uniform policy to each probability floor is at least $1/(2K)$. Also,
$$ g(p)\geq-\log H\geq-B+2, $$
so the vertical coordinate has adequate slack. An outer-ball radius $B+K+3$ suffices.

The weak separation oracle first checks the rational linear constraints. At a feasible $p(x)$, evaluate $g(p(x))$ to error at most one quarter of the oracle tolerance. A point lying at most that tolerance above the graph is certified as approximately feasible. Otherwise concavity supplies a separating hyperplane using the rational gradient of $g(p(x))$. Rational normalization, or sufficiently accurate normalization with the tolerance budget, gives the required weak separator.

Logarithms are polynomial-time evaluable to the necessary binary precision. For example, after dyadic range reduction to $u\in[1,2)$,
$$ \log u = 2\sum_{j=0}^{\infty} \frac{z^{2j+1}}{2j+1}, \qquad z=\frac{u-1}{u+1}\in[0,1/3). $$
The tail decreases geometrically. Rational gradients are computed exactly. Hence all oracle hypotheses hold.

5.2 Repairing the returned policy

Choose
$$ \xi=\frac{\varepsilon}{4+16HK^2}. $$
Let $(x,v)$ be the weak-optimization output. There exists $(x',v')\in Q$ at distance at most $\xi$. Put
$$ p=p(x),\qquad p'=p(x'). $$
Then
$$ \sum_ap_a=1,\qquad p_a\geq\frac{\gamma}{K}-K\xi, \qquad \|p-p'\|_1\leq2K\xi. $$
Also,
$$ g(p')\geq v'\geq v-\xi\geq\max_{\mathcal P_\gamma}g-2\xi. $$

Let $u$ be the uniform policy and define
$$ e=K\xi,\qquad a=\frac{1-\gamma}{K}, \qquad \ell=\frac{e}{a+e}, \qquad \widetilde\pi=(1-\ell)p+\ell u. $$
For every coordinate,
$$ \widetilde\pi_a \geq (1-\ell)\left(\frac{\gamma}{K}-e\right) +\ell\left(\frac{\gamma}{K}+a\right) =\frac{\gamma}{K}. $$
Thus $\widetilde\pi$ is exactly feasible.

Since $a\geq1/(2K)$, we have $\ell\leq2K^2\xi$. Our choice of $\xi$ also ensures $\|u-p\|_1\leq3$, and therefore
$$ \|\widetilde\pi-p'\|_1 \leq2K\xi+3\ell \leq8K^2\xi. $$
The Lipschitz bound yields
$$ g(\widetilde\pi) \geq \max_{\mathcal P_\gamma}g-(2+8HK^2)\xi = \max_{\mathcal P_\gamma}g-\frac{\varepsilon}{2}. $$
Because $F_G=e^g\leq1$, this entails product-objective error at most $\varepsilon/2$.

Finally, round $\widetilde\pi$ to a dyadic simplex policy with denominator $D$, where $D$ is a power of two satisfying
$$ D\geq \max\left\{\frac{2HK}{\varepsilon},\frac{2K}{\gamma}\right\}. $$
Rounding down all coordinates and distributing the remaining units gives coordinate error at most $1/D$. It preserves the floor $\gamma/(2K)$.

On the simplex, every partial derivative of $F_G$ is at most $H$. Thus rounding changes its value by at most
$$ \frac{HK}{D}\leq\frac{\varepsilon}{2}. $$
This establishes the policy guarantee used in Section 3.

Dyadic policies can be sampled with exactly $\log_2D$ random bits. The empirical statistics, confidence bounds, optimization output, and rounding precision all have polynomial encoding length. The running time depends on rational mass denominators through their bit lengths, never through their numerical values.

6. Lower bounds throughout the confidence range

All constructions below use binary individual rewards. Their aggregate observations are therefore binary rational because the masses are binary rational.

6.1 The ordinary-bandit contribution

Suppose $\lambda>0$, equivalently $\delta<1-1/K$. Give every type the same Bernoulli reward. Then
$$ W_\nu(\pi,\mu)=\sum_a\pi_a\mu_a. $$

Under a reference environment $D_0$, every arm has mean $1/2$. Define
$$ S_j=\sum_{t=1}^H\pi_{t,j}. $$
Since $\sum_jS_j=H$, some $j$ satisfies
$$ \mathbb E_0S_j\leq\frac HK. $$
Let
$$ a=1-\frac{\lambda}{2}. $$
Markov’s inequality gives
$$ \Pr_0(S_j\leq aH) \geq1-\frac1{Ka} = \delta+\frac{s\lambda}{2-\lambda}. $$

In environment $D_j$, raise only arm $j$’s mean by
$$ \epsilon=\frac{s\lambda}{32}\sqrt q. $$
The adaptive likelihood chain rule gives
$$ \operatorname{KL}(P_0\Vert P_j) = \mathbb E_0N_j\, \operatorname{kl}(1/2,1/2+\epsilon). $$
Here $\mathbb E_0N_j=\mathbb E_0S_j$. Since $\epsilon\leq1/32$,
$$ \operatorname{kl}(1/2,1/2+\epsilon) = -\frac12\log(1-4\epsilon^2) \leq3\epsilon^2. $$
Consequently,
$$ \operatorname{KL}(P_0\Vert P_j) \leq\frac{3s^2\lambda^2}{1024}. $$
Pinsker’s inequality gives total variation distance smaller than $s\lambda/8$. The event $S_j\leq aH$ therefore has probability strictly greater than $\delta$ under $D_j$.

On that event,
$$ R_H=\epsilon(H-S_j) \geq \frac{s\lambda^2}{64}H\sqrt q. $$
Every smaller regret threshold fails the minimax probability requirement. Hence
$$ B^\star\geq\frac{s\lambda^2}{64}H\sqrt q. $$

6.2 A hidden rare arm with an unknown optimal mixture

Fix a nonempty proper subset $S$ of types, and write
$$ \beta=\beta_S\in(0,1). $$
Put
$$ q'=\min\{1,(K-1)/H\}, \qquad \epsilon=\frac{s q'}4. $$

In a reference environment, all types in $S$ receive a common Bernoulli reward of mean $\epsilon$ from arm $1$, and zero from every other arm. All types outside $S$ receive a common Bernoulli reward of mean $1-\beta$ from arm $1$, and deterministic reward $1$ from every other arm. The two groups may be sampled independently.

Choose $j\in\{2,\ldots,K\}$ with
$$ \mathbb E_0N_j\leq\frac{H}{K-1}. $$

For a parameter $z\in[1/4,3/4]$, define
$$ a_z=\frac{1-z}{2-\beta-z}. $$
In the alternative environment $D_{j,z}$, change only the reward of group $S$ on arm $j$: it becomes a common Bernoulli reward of mean $\epsilon a_z$.

Couple the reference and alternative histories using the same learner randomness and all unchanged reward samples. Histories can first diverge only when arm $j$ produces a positive group-$S$ reward. Thus their total variation distance is at most
$$ \epsilon a_z\,\mathbb E_0N_j \leq \frac{\epsilon H}{K-1} \leq\frac s4. $$

For a policy, write $p=\pi_1$. Its first-group utility is
$$ \epsilon(p+a_z\pi_j) \leq\epsilon(a_z+(1-a_z)p), $$
and its second-group utility is $1-\beta p$. Define
$$ f_z(p) = (a_z+(1-a_z)p)^\beta(1-\beta p)^{1-\beta}. $$
The policy using probability $z$ on arm $1$ and $1-z$ on arm $j$ attains $\epsilon^\beta f_z(z)$.

We now verify that $z$ is the unique maximizer and quantify the loss away from it. Differentiating the logarithm,
$$ \frac{f_z'(p)}{f_z(p)} = \frac{\beta(1-a_z)}{a_z+(1-a_z)p} - \frac{(1-\beta)\beta}{1-\beta p}. $$
Substitution of $p=z$ gives zero. Moreover,
$$ f_z''(p) = -\beta(1-\beta)f_z(p) \left( \frac{1-a_z}{a_z+(1-a_z)p} + \frac{\beta}{1-\beta p} \right)^2. $$

For all admissible $z,p$,
$$ a_z\geq\frac15, \qquad 1-a_z\geq\frac{1-\beta}{2}. $$
Also,
$$ f_z(p)\geq a_z^\beta(1-\beta)^{1-\beta}\geq\frac1{10}. $$
For the last inequality, $t^t\geq e^{-1/e}>1/2$ for $t\in(0,1)$, as follows by minimizing $t\log t$. Both utility factors are at most $1$, so the expression in parentheses is at least
$$ 1-a_z+\beta\geq\frac12. $$
Therefore
$$ f_z''(p)\leq-\frac{\beta(1-\beta)}{40}. $$
Integrating this inequality from the stationary point $z$ proves
$$ f_z(z)-f_z(p) \geq \frac{\beta(1-\beta)}{80}(p-z)^2. $$
In particular, $z$ is the unique maximizer.

Let
$$ \bar p=\frac1H\sum_{t=1}^H\pi_{t,1}. $$
Concavity of $f_z$ and the preceding welfare bound give, on every alternative history,
$$ R_H \geq \frac{\beta(1-\beta)}{80} H\epsilon^\beta(\bar p-z)^2. $$

Set $r=s/16$. Under the reference law, average over $z$ uniformly in $[1/4,3/4]$. For every fixed value of $\bar p$, the set of parameters within distance $r$ has length at most $2r$. Hence
$$ \frac1{1/2} \int_{1/4}^{3/4} \Pr_0(|\bar p-z|\leq r)\,dz \leq4r=\frac s4. $$
There is consequently a parameter $z$ for which the reference probability is at most $s/4$.

For this parameter, let
$$ b_\beta = \frac{\beta(1-\beta)}{80}H\epsilon^\beta r^2. $$
The event $R_H\leq b_\beta$ implies $|\bar p-z|\leq r$. Transferring this event through the coupling yields
$$ \Pr_{j,z}(R_H\leq b_\beta)\leq\frac s2<s. $$
Thus its complementary probability exceeds $\delta$.

Finally, $q'\geq q/2$, so $\epsilon\geq sq/8$. It follows that
$$ B^\star \geq b_\beta \geq \frac1{163840} \beta(1-\beta)s^{\beta+2}Hq^\beta. $$
This proves the proper-subset lower bound for every $\delta<1$.

6.3 Recovering the high-confidence characterization

When $\delta<1/4$,
$$ s>\frac34,\qquad \lambda\geq\frac13. $$
Thus the ordinary-bandit lower bound is a universal constant times $H\sqrt q$.

For every subset mass $\beta\leq1/2$, the rare-mixture lower bound is a universal constant times $\beta Hq^\beta$, because
$$ 1-\beta\geq\frac12, \qquad s^{\beta+2}\geq(3/4)^3. $$
A subset with $\beta>1/2$ contributes at most $H\sqrt q$ to $\mathcal F$. The full subset, of mass $1$, also contributes at most $H\sqrt q$.

Taking the largest contribution proves $B^\star\geq c\mathcal F$.

7. Exact zero quantiles and a one-round formula

If $K=1$, there is only one policy, so regret is zero.

Suppose $K\geq2$ and $\tau=1$. Choose one uniformly random arm and use it throughout. Every environment has at least one optimal arm, so this learner has zero regret with probability at least $1/K$. Therefore
$$ B^\star=0 \qquad\text{if}\qquad \delta\geq1-\frac1K. $$
For smaller $\delta$, the ordinary-bandit lower bound is strictly positive.

If $\tau\geq2$, a nonempty proper subset exists and has mass strictly between zero and one. The rare-mixture lower bound is then strictly positive for every $\delta<1$. This proves the zero-quantile characterization stated at the outset.

There is also an exact formula for one type and one round:
$$ B^\star(K,1,(1),\delta) = 1-\frac1{\lceil K(1-\delta)\rceil}. $$

Proof. Put $n=\lceil K(1-\delta)\rceil$. Choose a uniformly random subset of $n$ arms and assign probability $1/n$ to each of them. Any fixed optimal arm belongs to this subset with probability $n/K\geq1-\delta$. On that event, regret is at most $1-1/n$, since rewards lie in $[0,1]$.

For the converse, consider the $K$ environments in which exactly one arm has deterministic reward $1$ and all others have reward zero. If a learner guarantees threshold $b$, its first policy must satisfy
$$ \Pr(\pi_j\geq1-b)\geq1-\delta $$
for every $j$. If $b<1-1/n$, each policy has at most $n-1$ coordinates satisfying $\pi_j\geq1-b$. Summing their probabilities would give
$$ K(1-\delta)\leq n-1, $$
contrary to the definition of $n$. For $n=1$, the lower bound is simply nonnegativity.

8. Why the uniform rate changes at larger $\delta$

Let $\theta_0$ have largest mass, and put
$$ \beta=1-\nu_{\theta_0}. $$
Suppose $\tau\geq2$. Choose a uniformly random arm $j$ and use the fixed policy
$$ \pi=(1-\beta)e_j+\beta u, $$
where $u$ is uniform.

With probability at least $1/K$, arm $j$ maximizes the utility of type $\theta_0$. On this event, if $M_\theta=\max_a\mu_{\theta,a}$, then
$$ W_\nu(\pi^\star,\mu) \leq M_{\theta_0}^{1-\beta} \prod_{\theta\neq\theta_0}M_\theta^{\nu_\theta}, $$
whereas
$$ W_\nu(\pi,\mu) \geq (1-\beta)^{1-\beta} \left(\frac{\beta}{K}\right)^\beta M_{\theta_0}^{1-\beta} \prod_{\theta\neq\theta_0}M_\theta^{\nu_\theta}. $$
If any $M_\theta=0$, regret is zero; otherwise the displayed inequalities apply directly.

Define binary entropy using natural logarithms:
$$ h(\beta)=-\beta\log\beta-(1-\beta)\log(1-\beta). $$
For $\delta\geq1-1/K$, the guessing strategy proves
$$ B^\star \leq H\left[1-e^{-h(\beta)-\beta\log K}\right] \leq H[h(\beta)+\beta\log K]. $$

For example, take
$$ K=2,\qquad \delta=\frac12,\qquad \nu=(H^{-2},1-H^{-2}), $$
with $H$ a power of two, so the masses are binary rational. Since
$$ h(\beta)\leq\beta\log(1/\beta)+\beta, $$
the preceding bound gives
$$ B^\star \leq \frac{2\log H+1+\log2}{H}. $$
But
$$ \mathcal F\geq\sqrt{2H}. $$
Thus $\mathcal F$ cannot characterize the minimax quantile uniformly over masses at $\delta=1/2$, even up to logarithmic factors.

A further statistical comparison identifies a useful scale in this regime. Define
$$ \Psi=\max_{\varnothing\neq S\subsetneq\Theta} \beta_S(1-\beta_S)q^{\beta_S}. $$
For $\tau\geq2$ and $\delta\geq1-1/K$,
$$ c(1-\delta)^3H\Psi \leq B^\star \leq C\Lambda^2H\Psi+1. $$

The lower bound follows from Section 6 because $s^{\beta+2}\geq s^3$. Here is a proof of the upper comparison.

First,
$$ \frac{\mathcal F}{H}\leq\max\{\sqrt q,2\Psi\}. $$
Indeed, masses above $1/2$ contribute at most $\sqrt q$, and for masses at most $1/2$ the factor $1-\beta_S$ is at least $1/2$.

Let $\rho=1-\max_\theta\nu_\theta$. If $\rho\geq1/4$, there is a subset of mass in $[1/4,1/2]$. If the largest mass is at least $1/2$, use its complement. Otherwise accumulate types until their total first reaches $1/4$; that total is below $3/4$, and either it or its complement has the required mass. Consequently,
$$ \Psi\geq\frac3{16}\sqrt q, $$
and the $\mathcal F$ upper bound suffices.

Suppose $\rho<1/4$, and put $T=\log(1/q)$. If $\rho T\leq2$, then
$$ \Psi\geq\rho(1-\rho)q^\rho \geq\frac34e^{-2}\rho. $$
Guessing an arm maximizing the largest-mass type and mixing it with the uniform policy at weight $\gamma=1/(2H)$ gives, on the successful guess,
$$ R_H\leq\frac12+\rho H\log(2KH). $$
Its success probability is at least $1/K$, which suffices in the stated confidence regime.

If $\rho T\geq1$, then
$$ \frac{\Psi}{\sqrt q} \geq \frac34\rho e^{(1/2-\rho)/\rho} \geq\frac{3e}{16}>\frac12. $$
The middle inequality follows because $\rho e^{1/(2\rho)-1}$ decreases on $(0,1/4]$. Again the $\mathcal F$ upper bound suffices. These two cases cover all possibilities.

This comparison leaves a factor polynomial in $1/(1-\delta)$ between the lower and upper bounds, rather than a logarithmic factor. It therefore does not settle the requested joint confidence dependence.

9. Fixed-mass rates and the remaining question

For every fixed mass vector with $\tau\geq2$, put
$$ \alpha=\min_\theta\nu_\theta\leq\frac12. $$
The singleton of mass $\alpha$ in Section 6 gives, for every fixed $\delta<1$,
$$ B^\star\geq c_{\nu,\delta}Hq^\alpha. $$
Conversely, every nonempty subset has mass at least $\alpha$, so
$$ \mathcal F\leq Hq^\alpha. $$
Hence, with constants allowed to depend on $\nu,\delta$,
$$ B^\star(K,H,\nu,\delta) = \widetilde\Theta(Hq^\alpha). $$
In particular, for $H\geq K$,
$$ B^\star = \widetilde\Theta(K^\alpha H^{1-\alpha}). $$
The polynomial algorithm above attains this fixed-mass rate throughout $\delta<1$.

For arbitrary rational masses treated as part of the input, the stronger uniform conclusion is proved for $0<\delta<1/4$: the minimax scale is $\mathcal F$ up to logarithmic factors and additive $1$, and attaining that guarantee admits a polynomial-time implementation. No computational hardness assumption is needed for this result.

What remains unresolved is a characterization with uniform constants and only logarithmic losses across the full joint parameter range, especially near $\delta=1-1/K$ and as $\delta$ approaches $1$. Consequently, the polynomial-attainment versus hardness question for that full guarantee also remains open here.

⟨structured verdict parsed — rendered above⟩

Verification report

Overall assessment: partial, with substantial valid progress. The statistical arguments support the stated bounds, the characterization for $0<\delta<1/4$, and the exact zero-quantile result. I found no false central step. The polynomial implementation is sound in substance, with a minor clarification needed in the weak-separation oracle.

The output does not resolve the full USER_TASK: it leaves the uniform joint confidence dependence, and attainment of the corresponding full-range minimax guarantee, unresolved. It explicitly acknowledges this limitation.

1. Scope and quantifiers

The initial restriction $K\geq2$ is necessary for the displayed positive lower bounds. Section 7 correctly handles $K=1$ separately.

The bounds are uniform over admissible reward laws. Recovering individual observations by dividing by positive masses is legitimate, and the lower-bound constructions use admissible observations. Bernoulli probabilities need not themselves be binary rational: the task restricts observation encodings, and these constructions produce individual observations in $\{0,1\}$.

For each learner, the lower bounds select an environment after examining its reference-law behavior. This is consistent with the supremum over environments in the definition of $B^\star$.

Major issue — incomplete target coverage. The full-range lower and upper bounds do not establish minimax attainment with only logarithmic losses uniformly in all parameters. In particular, the larger-confidence comparison leaves a factor polynomial in $1/(1-\delta)$. No hardness result resolves the remaining computational question.

Minimum additional work: establish the missing uniform confidence dependence and attainment guarantee, or an applicable hardness result. This requires additional mathematics, not an expositional clarification.

2. Continuity lemma

The Hessian identity is correct. Weighted Cauchy–Schwarz proves concavity under the stated exponent-sum condition, and continuity extends it to boundary points.

Both cases in the modulus argument check out:

• When $m\leq z$, the hypothesis gives $y_j\leq34z$. The comparisons involving $w_j\geq\alpha$ and $\alpha\leq1/2$ have the correct directions, including the case $34z\geq1$.
• When $m>z$, all coordinates are positive, so the tangent inequality applies. The bounds using $F_w(x)\leq m^\alpha$ and $m^{\alpha-1/2}\leq z^{\alpha-1/2}$ are valid.

The constant $40$ covers the displayed estimates. The lemma is valid for the finite, nonempty index sets used later.

3. Confidence bounds and adaptive sampling

The observation recovery and upward dyadic rounding are valid. The rounding grid includes $1$, so rounded observations remain in $[0,1]$.

The Bernstein bound follows from the variance bound for a bounded random variable with mean $u$. The use of a base-two logarithm for $b$ is conservative; the union bound gives the claimed failure probability.

The optimism and upper-error constants remain valid after the specified upward square-root approximation. Clipping preserves optimism, and the unpulled-arm convention satisfies the stated inequalities.

The mixture calculation correctly applies weighted Cauchy–Schwarz. The absorption of rounding error into $25\rho_t$ is valid because $\eta\leq\rho_t$.

The sampling-process argument also checks out:

• Conditioned on the chosen policy, the conditional mean of $Z_t$ is $z_t$.
• The exponential process is a nonnegative supermartingale.
• The harmonic contribution of each arm is bounded by $2+\log H$.
• The resulting estimate $Q\leq C_0K\Lambda^2$ holds throughout the stated parameter range.

Using fixed arm sample streams correctly handles adaptive observation times. Dependence among coordinates within a sample does not invalidate these marginal bounds.

4. Discarded types and the upper regret bound

The retained objective keeps the original exponents, whose sum is at most $1$; thus the continuity lemma applies without renormalization.

The restriction to $\mathcal P_\gamma$ costs at most $\gamma$. The implemented policy need only satisfy the weaker floor stated in Section 3, because its objective guarantee is separately compared with the optimum over $\mathcal P_\gamma$.

The discarded-type argument is correct. The separate treatment of a type with $M_\theta=0$ handles the degenerate welfare case. Otherwise, the policy floor supplies the stated utility lower bounds, and the logarithmic discarded-mass penalty follows.

The concavity bound for the sum of $\rho_t^{\alpha_G}$ is valid. With $\gamma=\varepsilon=1/(2H)$, the optimization and restriction losses sum to the additive $1$ claimed.

The threshold selection in Section 4 is also correct:

• In the large-$q$ regime, the deterministic regret bound suffices.
• If discarded mass reaches $r$, the accumulated subset has mass in $[r,2r)$.
• If discarded mass is below $r$, the retained set is nonempty and $\alpha_G\geq r$.
• The singleton and discarded-subset comparisons correctly bound the two regret contributions by logarithmic multiples of $\mathcal F$.

The algorithm does not need to compute the subset maximum defining $\mathcal F$.

5. Polynomial implementation

The lower bound on confidence entries ensures that every logarithm argument is at least $1/H$. Consequently, the bounds on $g$, its derivatives, and its Lipschitz constant are correct.

The cited weak-optimization guarantee matches the weak optimization definition in Section 1 of the referenced paper: it permits approximate feasibility and compares the objective with the maximum over the entire body. The application therefore does not incorrectly assume exact feasibility. The explicit interior and outer balls satisfy the required geometric conditions. [Grötschel–Lovász–Schrijver, Sections 1 and 3](https://www.ufsj.edu.br/portal2-repositorio/File/nepomuceno/elip.pdf).

The logarithm evaluation argument provides polynomial dependence on precision. Exact rational gradients also have polynomial encoding length.

Minor issue — oracle tolerance specification. The write-up does not explicitly state the decision thresholds used with the approximate evaluation of $g$, or the normalized weak-separation inequality returned after rational normalization. An evaluation error of one quarter of the tolerance does not, by itself, specify a valid acceptance rule.

Minimum clarification: state the acceptance threshold and the returned separator inequality, accounting for evaluation and normalization errors within the oracle tolerance. This is routine precision bookkeeping and does not require new mathematics.

The feasibility repair in Section 5.2 checks out. The affine-coordinate error, uniform mixing coefficient, policy-distance bound, and resulting objective error all have valid constants.

The final dyadic rounding also gives the claimed guarantee when remaining units are assigned to distinct coordinates, as in standard simplex rounding. It preserves the weaker floor and yields bounded-time exact sampling. Encoding lengths depend polynomially on mass bit lengths rather than numerical denominators.

Thus the polynomial implementation claim is supported in substance.

6. Ordinary-bandit lower bound

Giving every type the same reward reduces welfare exactly to the linear bandit objective.

The reference-arm selection, Markov bound, and identity involving $s$ and $\lambda$ are correct. The adaptive likelihood calculation is valid for these Bernoulli environments.

The relative-entropy bound and Pinsker constant leave sufficient probability margin: the transferred event has probability strictly greater than $\delta$. On that event, the stated regret lower bound follows.

The quantile argument correctly considers every threshold strictly smaller than the displayed regret level. This establishes the lower bound despite the strict inequality in the definition of the failure event.

7. Rare-arm mixture lower bound

This construction is valid and addresses nonlinear welfare rather than merely reproducing the ordinary-bandit lower bound.

The coupling bound correctly uses the expected reference pull count. The first-group policy utility bound and the exact second-group utility are correct.

The calculations establishing the maximizer check out:

• Substitution of $a_z$ gives $f_z'(z)=0$.
• The second-derivative identity is correct.
• The uniform lower bounds on $a_z$, $f_z$, and the squared expression imply the stated curvature bound.
• The quadratic loss estimate follows from that curvature bound.

The passage to $\bar p$ uses concavity correctly. Parameter averaging supplies a suitable $z$, and the coupling transfers the small-regret probability with the required strict margin.

The final numerical constant is valid: the factors from the curvature bound, $r^2$, and the estimate on $\epsilon^\beta$ produce the denominator $163840$.

The lower bound holds uniformly for every nonempty proper subset and every $\delta<1$.

8. High-confidence and zero-quantile conclusions

For $0<\delta<1/4$, the bounds on $s$ and $\lambda$ supply universal constants.

Proper subsets of mass at most $1/2$ receive the required rare-mixture lower bound. Subsets of larger mass, including the full subset, are dominated by the ordinary-bandit contribution. Therefore the stated lower bound by $c\mathcal F$ follows.

The zero-quantile characterization is correct:

• For $K=1$, regret is identically zero.
• For one type, guessing an optimal arm has success probability at least $1/K$.
• Below that confidence threshold, the ordinary-bandit lower bound is positive.
• With at least two positive-mass types, the proper-subset lower bound is positive for every $\delta<1$.

The one-type, one-round formula is also correct. Its converse uses the strict threshold properly, and the case where the ceiling equals $1$ is explicitly handled.

9. Larger-confidence comparison and fixed-mass rates

The guessing strategy and entropy bound are valid. They demonstrate that $\mathcal F$ cannot uniformly describe the larger-confidence minimax quantile over input-dependent masses.

Minor issue — inadmissible example endpoint. The example permits $H$ to be any power of two, which includes $H=1$. At that endpoint, the second mass is zero, violating the task’s positive-mass assumption. The displayed comparison with $\sqrt{2H}$ also requires $H\geq2$.

Minimum clarification: restrict the example to powers of two with $H\geq2$.

The subsequent $\Psi$ comparison is mathematically consistent. The subset-existence argument, dominant-mass cases, and exponential comparison have the correct ranges and constants. The overlapping case conditions cover all possibilities.

Section 9 correctly derives the fixed-mass rate, with constants allowed to depend on $\nu$ and $\delta$. This does not supply the uniform input-dependent characterization requested by the task, and the output appropriately distinguishes those claims.

Final adjudication

The output contains genuine, substantial progress: valid statistical upper and lower bounds, a high-confidence minimax characterization up to logarithmic factors, a polynomial implementation in substance, and exact zero-quantile and one-round results.

The full assignment remains unresolved. The appropriate status is partial, rather than refuted. The identified implementation and example issues are minor; the missing uniform confidence characterization is the substantive blocker.

⟨structured verdict parsed — rendered above⟩