Fair Lotteries over Beamforming Configurations

When a base station shares a wireless channel among users whose channels differ greatly in quality, any single fixed configuration forces a trade-off. Here a configuration means which users to serve, in what order to decode them, and how to set the antenna weights and the reflecting-surface phases. Serving the strong users starves the weak ones. Protecting the weakest user (max-min fairness) points all the energy at one bad channel and wastes capacity. The ex-ante fairness literature offers a way out. Instead of committing to one outcome, the system commits to a lottery: a probability distribution over outcomes, chosen so that every participant's expected utility is fair before the coin is flipped. That literature, however, works almost entirely with combinatorial objects whose values are well behaved: item assignments, seed sets, submodular valuations. Wireless configurations are neither. They mix discrete choices (user subsets, decoding orders, 1-bit surface phase patterns) with continuous vectors (beamformers), and user rates depend on those choices through non-convex interference.

This note proposes a stochastic mixed discrete-continuous policy whose randomness is the fairness lottery. It is trained to maximize a concave function of per-user expected rates, and its structure follows from a simple geometric fact: a fair lottery over $K$ users never needs more than $K+1$ distinct configurations. The model-based version of this idea turns any existing weighted-sum-rate solver into a fair-lottery solver. The learned version amortizes that solver so it runs within a channel coherence interval. A separate rounding step makes the lottery fair not only in expectation but also in what users actually receive over a finite frame.

Core Claim

The obstacle that looks hardest at this intersection is how to decompose a fair fractional solution into realizable outcomes when the outcomes include continuous beamformers on a non-convex manifold. The research file frames this as a gap because Birkhoff–von Neumann and bihierarchy decompositions only handle discrete matrices. Our claim is that this decomposition problem should be sidestepped rather than solved.

For a fixed channel state $H$, each deterministic configuration $a=(d,x)$ gives a rate vector $R(a;H)\in\mathbb{R}^K$, where $d$ is the discrete part and $x$ the continuous beamformer. The expected rate vector of any lottery lies in the convex hull of the set of achievable rate vectors. By Carathéodory's theorem, every point of that hull is a mixture of at most $K+1$ achievable points. The ex-ante fair problem is therefore exactly

$$\max_{p\in\Delta_{K+1},\;a_1,\dots,a_{K+1}} \; g\Big(\textstyle\sum_{j} p_j R_1(a_j;H),\;\dots,\;\sum_j p_j R_K(a_j;H)\Big),$$

where $g$ is a concave aggregator such as the minimum, the sum of logs (Nash social welfare), or a $p$-norm, and $p$ holds the mixture weights. The lottery is built directly as a short list of hybrid configurations. Nothing continuous ever has to be decomposed.

This problem can be solved by a Frank–Wolfe loop (repeatedly linearize the objective and move toward the best point under that linearization). At the current expected rates $\mu$, set per-user weights $\lambda_k=\partial g/\partial\mu_k$. The best new support point is then the solution of a weighted sum-rate problem with weights $\lambda$. That is precisely the problem that alternating optimization and block minorization-maximization already solve well. Submodularity, which the guarantees in Greedily Maximizing Ex-Ante Fairness require, is replaced by access to a weighted-sum-rate oracle. Interference-coupled rates are not submodular, but they do admit such an oracle.

Research Program

The first component is the model-based lottery solver and its analysis. The oracle is the multi-user weighted-sum-rate solver of Zhang and Zhao's block minorization-maximization method, which updates beamformer and surface phases by maximizing lower-bounding surrogates. For discrete phases we use the outer-approximation mixed-integer approach of Di et al.. For NOMA decoding orders we use alternating optimization with sequential rank-one relaxation from Mu et al.. All three papers supply method, and none of them randomizes.

We aim to prove the following. If the oracle returns a configuration within a factor $\alpha$ of the best weighted sum rate, a situation that local solvers make realistic, then after $t$ Frank–Wolfe steps the lottery reaches the optimum of $g$ over the $\alpha$-shrunken rate region, up to an $O(1/t)$ error. This extends the continuous-greedy setting of Greedily Maximizing Ex-Ante Fairness from exact combinatorial oracles to approximate non-convex ones. A final re-optimization of the weights over the collected configurations then prunes the support to $K+1$ points.

The second component is a learned mixture policy for low-latency deployment. The model-based loop calls an iterative solver many times per channel realization. The research file identifies this cost as the binding constraint on alternating-optimization methods within coherence times. We therefore train a network with a shared trunk that reads the channel estimate and outputs $K+1$ slots. Each slot contains a categorical head over discrete choices (scheduled subset, decoding order, 1- or 2-bit phase pattern) and a continuous head for the beamformer. The continuous head is conditioned on the sampled discrete choice, following the prompt-conditioning design of Sun et al., so no parameters are spent on inactive options. A final softmax gives the mixture weights.

The training objective is a concave function of expectations, not an expectation of a reward, so ordinary policy gradients do not apply directly. Instead, we estimate $\mu$ from a batch of samples at the same channel state, compute $\lambda=\nabla g(\mu)$, and apply a hybrid policy gradient to the weighted sum $\sum_k\lambda_k R_k$. This is the same linearization that drives Frank–Wolfe. At deployment the policy is sampled, not replaced by its most likely action. Standard practice in hybrid RL, as in Wang et al. and LAPP, treats policy randomness as exploration to be removed. Here the randomness is the product being delivered.

The third component is ex-post realization over a frame. A lottery that is fair in expectation can still be unlucky in any given frame of $T$ slots. When the channel is roughly static over the frame, we replace independent sampling with deterministic stratified rounding of $Tp_j$, so that each configuration is used within one slot of its target count. Every user's realized rate then lies within one slot's worth of its ex-ante share. This is the analogue of envy-freeness up to one good that Recursive Probabilistic Serial and Halpern et al. obtain for items. When the channel changes within the frame, we carry forward a deficit vector across slots and test whether this preserves the bound empirically. The impossibility results in the best-of-both-worlds paper warn that ex-post Pareto optimality cannot also be demanded, so we do not claim it.

Baselines

The naive reference point is a deterministic sum-rate configuration from block minorization-maximization in each slot. It shows how badly unfair the unconstrained optimum is.

The first strong existing competitor is deterministic max-min alternating optimization, the classical fairness answer in the IRS–NOMA line of Mu et al.. It targets the same fairness goal without randomization. The research file argues that it sacrifices a large amount of sum rate, but it reports no max-min rate figure. We find no reported result on Lacuna for max-min or Nash-welfare rates in RIS-assisted MISO, so all fairness numbers will be produced by us under shared channel draws. Our lottery beats this baseline if it achieves a higher expected minimum rate, or an equal minimum rate with higher sum rate, on the same channels.

The strongest competitor is proportional-fair scheduling with a per-slot weighted-sum-rate solver. At each slot it sets $\lambda_k$ to the inverse of each user's running average rate and solves one weighted-sum-rate problem with the same block minorization-maximization oracle. It is the strongest because it is also a gradient method on a concave utility of average rates, and with long horizons and i.i.d. fading it converges to the same utility-optimal point. It receives the same oracle, the same per-slot compute budget, and the same channel traces. Beating it means higher Nash welfare and a smaller worst-user shortfall at short frame lengths ($T\le 20$ slots), together with matching performance at long $T$.

For the learned policy, the strongest hybrid-RL competitor is CHPO. Its switching rule alternates between reward and cost updates. We run it with a sum-rate reward and a minimum-rate threshold as its cost. On its own Parking benchmark CHPO reported an episodic reward of 37.63 against 20.01 for the Lagrangian baseline HPPO-Lag. That domain is different, so the figure only sets expectations about stability. We also include a discretized deep Q-network in the style of Gao et al.. All learned methods receive the same number of environment samples and the same hyperparameter-search budget.

Two ablations isolate the key ingredient. The first uses the same network with a single slot, trained on the same concave objective but deployed deterministically. This removes the lottery while keeping everything else. The second is a proportional-fair policy that uses our learned network as a fast weighted-sum-rate oracle, conditioned on $\lambda$. It isolates whether the explicit $(K+1)$-slot mixture adds anything beyond fast amortized solving.

Why not just…?

Why not just run proportional-fair scheduling, which already time-shares configurations? This is the real threat. Over many slots of stationary fading, proportional fairness implicitly traces the same convex hull. Our proposal differs in three testable ways. The lottery is fair at every slot rather than only asymptotically. It needs no running averages, so newly arriving users are not disadvantaged by their history. And the rounding step bounds the realized unfairness over a finite frame. If our frame-length sweep shows proportional fairness matching the lottery at $T=10$ as well as at $T=1000$, the model-based component adds nothing, and the contribution narrows to the ex-post bound and amortization.

Why not just use deterministic max-min optimization? Mixing configurations can reach expected-rate vectors that no single configuration achieves. Whether that gain is large in practice for realistic channel asymmetry is an empirical question. We measure it directly as the gap between the lottery and max-min, sweeping how far apart the users' path losses are.

Why not just add a fairness penalty to a standard hybrid RL reward? A per-slot reward such as the sum of log instantaneous rates is an expectation of a concave function. That is not a concave function of expected rates, and it is maximized by a deterministic policy that never randomizes. The single-slot ablation tests this directly. Lagrangian variants also face the instability that the CHPO study documents.

Why learn anything, instead of running the Frank–Wolfe lottery solver every block? If the channel stays fixed long enough, one should run the solver. The learned policy is justified only where wall-clock latency exceeds the coherence time. We therefore report both methods against measured coherence budgets and state where the crossover occurs.

Proposed Experiments

The primary testbed is downlink multi-user MISO with a reflecting surface under Rician fading at 5.9 GHz, following the setups of Mu et al. and Di et al.. We use 4 to 8 users, 16 to 64 surface elements, and continuous, 1-bit, 2-bit, and 3-bit phases. The 3-bit setting matters because both papers report near-continuous performance there, which makes it a natural control. For users placed asymmetrically, NOMA decoding order becomes an additional discrete variable. A secondary testbed is the 3GPP TR 36.885 Manhattan device-to-device setting of Wang et al., with 10 resource blocks and channel-plus-power hybrid actions. It tests whether the approach transfers beyond reflecting surfaces.

The metrics are ex-ante Nash welfare, ex-ante minimum expected rate, and sum rate. We also measure realized worst-user shortfall relative to the ex-ante share over frames of $T\in\{5,10,20,100,1000\}$ slots, and wall-clock time per decision.

Three checks decide the proposal. First, at moderate-to-severe channel asymmetry, the Frank–Wolfe lottery must beat deterministic max-min on Nash welfare at matched minimum rate. This verifies that the convex-hull gain exists in these physics. Second, at $T\le 20$, the rounded lottery must show smaller realized shortfall than proportional fairness with the same oracle. This verifies that the proposal is not just re-derived time-sharing. Third, the learned mixture policy must come within a few percent of the model-based lottery's Nash welfare at a small fraction of its latency, and it must beat the single-slot and proportional-fair-with-learned-oracle ablations. This verifies that the mixture structure, not just amortization, carries the gain. We also measure the oracle quality $\alpha$ empirically, by comparing to exhaustive search on small instances, to test whether the predicted shrinkage of the region matches what is observed.