Assigning users to base stations and choosing their transmit power at the same time is a mixed discrete-continuous optimization problem, and it is NP-hard. A natural way to solve it is to write it as a graph: each user's choice is a node, and an edge joins any two users who interfere with each other. Then you run belief propagation, a message-passing algorithm in which neighbors repeatedly exchange local summaries until they agree on a joint answer. On a tree, belief propagation is exact and finishes quickly. On a graph with cycles, which a dense cellular deployment always produces, the same algorithm can oscillate, overcount evidence, or stall far from a good answer. Computing the exact answer instead costs time exponential in the graph's treewidth, a measure of how far the graph is from being a tree.
A known workaround is to cut edges until the graph becomes a tree, solve that tree exactly, and use the weights of the cut edges to bound how much was lost. Existing methods choose those cuts by a fixed rule, either a worst-case greedy score or random sampling. We propose that a reinforcement learning policy choose the cuts, one scheduling slot at a time. The policy keeps a subgraph whose treewidth stays under a cap, and exact inference runs on that subgraph. The cut edges still carry an analytical error bound, so every decision is certified no matter how good or bad the policy is. The policy is rewarded on the utility actually achieved, so it can learn which interference couplings matter for the configurations the network really visits. A worst-case rule has to protect against all configurations.
Core Claim
The worst-case "utility swing" criterion behind Bounded Approximate Decentralised Coordination using the Max-Sum Algorithm keeps the wrong edges in wireless interference graphs. That paper builds a maximum spanning tree using, as each edge's weight, the largest change one variable can cause in a neighboring factor. It then runs exact max-sum on the tree and reports an instance-specific bound. Its authors note that the swing overestimates error for factors that involve many variables. In wireless networks the realized configurations are highly concentrated: users mostly associate with nearby cells, and power levels persist from one slot to the next. An edge can therefore have a large swing that is almost never realized.
We claim a learned edge-retention policy can beat swing-greedy selection at equal treewidth and equal wall-clock budget. It can condition on channel state and on the previous slot's solution, and it can extend from trees (treewidth one) to thin junction trees (treewidth $\tau>1$). We further claim the advantage holds after the analytical bound is applied, so the gain is not bought by giving up the guarantee. To make the guarantee concrete: if $\tilde U$ is the optimal utility of the reduced problem, where dropped factors are evaluated pessimistically, and $W_{\text{drop}}$ is the summed swing of the dropped edges, then the true optimum satisfies
$$U^* \le \tilde U + W_{\text{drop}},$$
following the argument of Farinelli et al. The ratio $(\tilde U + W_{\text{drop}})/U(\hat x)$, where $U(\hat x)$ is the utility of the decision actually returned, is a per-slot certificate we report alongside performance.
This is a falsifiable claim. If greedy swing selection at the same $\tau$ matches the learned policy, the reinforcement learning component has no value. In that case the useful remaining finding is narrower: that certified thin-junction-tree decompositions beat spanning trees on these problems.
Relation to Prior Work
Three lines of work remove cycles to make message passing converge, and all three choose the structure open-loop.
Bounded Max-Sum fixes the structure greedily from worst-case swings. From Fields to Random Trees samples 5 to 10 uniform spanning trees, reweights each edge's energy by its effective resistance, runs exact belief propagation on each tree, and merges the results. Its effective-resistance step costs $O(MN^3)$, a scaling wall on dense graphs. A New Decomposition Paradigm for Graph-structured Nonlinear Programs via Message Passing partitions the graph into fixed tree clusters and reconciles cluster boundaries with block-Jacobi updates. It handles continuous variables only. These works motivate the proposal and supply its mechanism: exact inference on a reduced structure plus a bound on what was dropped. We keep that mechanism and change only how the structure is chosen.
Thin Junction Trees supplies the generalization beyond trees. It adds edges greedily while enforcing a hard treewidth cap $\tau$, which keeps exact inference at cost $O(d^{\tau+1})$ for domain size $d$. We reuse its capped-width construction but replace its likelihood-based edge score with a learned one.
The closest learned-structure work is Deep Hierarchical Communication Graph in Multi-Agent Reinforcement Learning. It lets reinforcement learning agents propose communication links and forces the resulting graph to be acyclic, so messages settle in a single pass. The proposal differs in three ways. DHCG's graph carries agent-to-agent communication in cooperative games, whereas ours is the factor graph of a resource-allocation problem. DHCG has no treewidth cap above one. DHCG also provides no bound on what removing a link costs.
Two learned-search papers constrain the design. Learning to Condition: A Neural Heuristic for Scalable MPE Inference fixes variables before exact search to reduce treewidth, and it warns that a wrong fix irreversibly excludes the optimum. Scalable Network Adaptation for Cloud-Rans: An Imitation Learning Approach imitates the pruning decisions of an exact branch-and-bound solver. Both rely on supervision from slow exact oracles.
Edge dropping differs from variable fixing in a useful way. Dropping an edge never removes a configuration from the search space; it only changes how that configuration is scored, so the true optimum stays reachable. Our reward also needs no oracle, only the realized utility.
Finally, Probabilistic Inference Based Message-Passing for Resource Constrained DCOPs shows that plain max-sum fails under tight resource constraints. Its expectation-maximization alternative converges only to local optima and does not model interference. We use its benchmarks as a check that our method transfers outside wireless problems.
Research Program
Problem setting. We build a multi-cell problem in which each user's variable is a joint choice of serving cell and a discretized transmit power level. Unary factors encode each user's own rate. Pairwise factors encode the loss in $\log(1+\text{SINR})$ that each user's interference imposes on the other. We use the 10-RRH, 15-user Cloud-RAN realizations described in the imitation-learning paper as the scale at which exact branch-and-bound can still provide optimality gaps. Larger synthetic dense deployments test scaling.
Discretizing power keeps every factor a table, so exact junction-tree inference applies directly. A follow-up variant would solve a convex power subproblem inside each clique, in the style of Optimizing AI Service Placement and Resource Allocation in Mobile Edge Intelligence Systems, which solves the continuous part in closed form once the discrete placement is fixed.
The policy. A graph network reads the interference graph's edge features and outputs an edge-retention score for each edge. Those features are path gain, swing, the previous slot's message residual, and whether either endpoint changed its assignment last slot. A deterministic step then adds edges in score order and rejects any edge that would push the treewidth estimate above $\tau$, the same greedy triangulation rule used by Thin Junction Trees. The policy can also choose $\tau$ from a small set, subject to a per-slot compute budget.
Training. Exact max-product inference runs on the resulting structure, and the decision is applied to a simulated slot. The reward is realized network utility minus a penalty proportional to inference time. Because the structure for a single slot is a one-shot decision given the current state, training is essentially a contextual bandit over edge subsets. Temporal adaptation enters through the state features, not through long-horizon credit assignment. We train with policy gradient and use the swing-greedy structure as a variance-reducing baseline action.
Closed-loop deployment. Placing the policy inside the REAL O-RAN setup (REAL: Reinforcement Learning-Enabled xApps for Experimental Closed-Loop Optimization in O-RAN with OSC RIC and srsRAN) tests whether certified decisions survive real telemetry. That setup uses a 500 ms control interval and has a messaging bottleneck that limits concurrent transmissions to three UEs. It is therefore a feasibility demonstration, not the place where the main claim is settled.
Baselines
Naive reference points. The first is max-SINR association with full power. The second is damped synchronous loopy max-product on the full graph. Together they show how much any structured inference buys.
Message-scheduling baseline. Residual Belief Propagation (Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing) updates first the messages that are changing most. It converged in 7 of 8 protein-interaction networks where the other methods failed. It is the strongest method that keeps all edges, and it tests whether stabilizing message order makes structural cuts unnecessary.
Strongest structural competitors. These are swing-greedy Bounded Max-Sum and the random-spanning-tree method with effective-resistance reweighting.
Bounded Max-Sum is the method our claim targets. On its synthetic gamma-payoff graphs it reports solutions "typically within 95% of the global optimum," with a computed approximation ratio averaging about 1.23. It solves 50-agent instances in about 800 ms.
The random-spanning-tree method, on PCI_INSTANCE_1 of the 5G cell-identity benchmark, reached an energy of about 84k, while LBP and TRBP stalled at about 372M.
We recompute both methods every slot from current channels. That gives them the same per-slot adaptivity as our policy, apart from learning.
Exact and learned-search references. We run branch-and-bound or toulbar2 with generous time limits wherever they finish, to measure optimality gaps. We also report the imitation-learned branch-and-bound pruner, which claims speedups "of over 20x" with objective loss "less than 0.6%" on same-size Cloud-RAN networks. For an end-to-end learning reference we use a PPO policy that maps channel telemetry directly to association and power. SlicePilot (Accelerating Network Slice Placement with Multi-Agent Reinforcement Learning) is the cautionary number for this family: it produced 2.42 times more QoS violations under high load than an ILP solver.
Ablation. The key ablation is swing-greedy selection at the same $\tau>1$, with the edge order taken from swing instead of from the policy. It separates the value of learning the cut from the value of allowing more width.
Fairness. Every method gets the same instances and the same per-slot wall-clock budget on the same CPU. Every tuned method gets the same hyperparameter search budget, counted in tuning trials. The learned policy's training compute is reported separately.
What counts as beating a baseline. We count it as a win when, at equal budget, the method achieves higher realized utility and a lower QoS-violation rate than per-slot swing-greedy at the same $\tau$, without a worse certified ratio. The improvement must be statistically significant across held-out channel realizations.
Why not just…?
Why not just recompute Bounded Max-Sum every slot? This is the real threat. It is cheap, it already adapts to current channels, and it carries a certificate. Our only argument against it is that worst-case swing misranks edges when realized configurations are concentrated. That argument is a hypothesis, not evidence. The same-$\tau$ greedy ablation settles it directly. If the learned policy cannot beat greedy at equal width, we will report that, and the proposal's contribution reduces to the thin-junction-tree extension.
Why not just use random spanning trees with resistance reweighting? The 84k-versus-372M result on PCI instances shows that this method is strong on locally structured graphs. However, its trees are sampled without reference to the objective, and its $O(MN^3)$ resistance computation grows quickly on dense interference graphs. We compare against it on the PCI instances, where it is strongest, and on dense HetNet graphs, where we expect its runtime to dominate. No reported result was found on Lacuna for it on joint association and power problems.
Why not just train PPO end to end? End-to-end policies are fast but produce no certificate, and the SlicePilot evidence points to rising constraint violations under load. Our PPO baseline measures this directly. If PPO matches our utility, the remaining argument for our method is the per-decision bound. We will say plainly that this is a weaker claim.
Why not just imitate an exact solver's edge choices? Labeling which edges to keep requires exact solves, and toulbar2 "often hit its 1-hour time limit" on 40-node instances in the RC-DCOP benchmarks. Supervision is therefore available only at small scale. We will train a supervised scorer on small instances and test it on large ones. That experiment shows whether oracle-free reward actually matters or whether small-scale imitation transfers well enough.
Proposed Experiments
The decisive experiment uses the Cloud-RAN-scale joint association and power instances with $\tau \in \{1,2,3\}$. It compares the learned policy against swing-greedy at matched width and matched per-slot budget. We report the realized utility gap to exact branch-and-bound, the certified ratio, and runtime.
A second test uses the dense-network scaling instances. There we track utility and certificate quality as density grows past the point where effective-resistance computation exceeds the slot budget.
Two transfer checks follow. The first runs the method on the 5G cell-identity instances against the random-spanning-tree energy of about 84k on PCI_INSTANCE_1. The second runs it on the RC-DCOP random-graph and coloring suites, where expectation-maximization reached 95–99% of optimal utility and max-sum failed to find feasible solutions in over 30% of 40-node cases. These checks ask whether the learned cut helps outside the training distribution.
A non-stationarity test trains the policy under one mobility pattern and evaluates it under another. It checks whether the features drawn from the previous slot help or cause overfitting.
Finally, a closed-loop run on the REAL testbed checks that certified decisions fit within the 500 ms control interval. Because of the three-UE limit in that setup, we treat this run only as a feasibility check.
The proposal succeeds only if the matched-width comparison favors learning. The other experiments locate where the method helps and where it does not.
References
- Bounded Approximate Decentralised Coordination using the Max-Sum Algorithm
- From Fields to Random Trees
- A New Decomposition Paradigm for Graph-structured Nonlinear Programs via Message Passing
- Thin Junction Trees
- Deep Hierarchical Communication Graph in Multi-Agent Reinforcement Learning
- Learning to Condition: A Neural Heuristic for Scalable MPE Inference
- Scalable Network Adaptation for Cloud-Rans: An Imitation Learning Approach
- Probabilistic Inference Based Message-Passing for Resource Constrained DCOPs
- Optimizing AI Service Placement and Resource Allocation in Mobile Edge Intelligence Systems
- REAL: Reinforcement Learning-Enabled xApps for Experimental Closed-Loop Optimization in O-RAN with OSC RIC and srsRAN
- Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing
- SlicePilot: Demystifying Network Slice Placement in Heterogeneous Cloud Infrastructures