Agent Utilities over Generalized Voronoi Regions and their Gradients

Andre N. Costa; Petter Ögren; Carlos H. C. Ribeiro

cs.ROJun 16, 2026

Agent Utilities over Generalized Voronoi Regions and their Gradients

Authors: Andre N. Costa, Petter Ögren, Carlos H. C. Ribeiro

Abstract

In this paper, we generalize the concept of Voronoi regions, define agent utility as the integral of a utility density over the corresponding Voronoi region, derive gradients of the utility, and illustrate the approach in a two-team example from soccer. The generalization of Voronoi regions is in the form of so-called Cost-Induced Voronoi (CIV) regions, where the agent state space may differ from the space being partitioned. One example of such regions is when the cost is given by the optimal solution of an LQR control problem. Then the agent states include position as well as velocity, while the partitioned space only includes positions. The agent utility is defined by integrating some utility density over the CIV region of the agent. This utility density might be the probability density of some beneficial event, such as receiving a pass in soccer. The utility is then the overall probability of receiving a pass and the gradient represents a way to improve that probability. We show how this utility gradient can be computed using the Reynolds Transport Theorem from fluid mechanics, and that this approach achieves similar accuracy while reducing computation time by about an order of magnitude compared to a baseline finite-difference approximation.

Explore similar work

Jun 20, 2026cs.LG

Drowning in Routine: Signal Dilution in Multi-Turn Agent Training

Multi-turn agents interleave consequential decisions with routine execution: some actions change the downstream return distribution, while others are necessary but reward-equivalent. The cost of trajectory-level credit assignment, often attributed to long horizons, is in fact governed by decision density

ρ

: the fraction of turns whose actions affect the return. When decision density is low, routine turns create signal dilution: they add gradient variance to trajectory-level estimators such as GRPO without adding expected signal. Under explicit assumptions, the resulting turn-level to trajectory-level signal-to-noise ratio scales as

ρ^{-1/2}

, provided critic error remains controlled. The same analysis identifies the complementary regime: at high decision density, trajectory-level methods can remain competitive while avoiding the cost of a critic. In a controlled environment where

ρ

is exactly tunable, the predicted scaling is recovered with

R^2 = 0.999

, and the training-step gap widens significantly as

ρ\to 0

Yann Pernot, Vi Retault

Topic pending

Ask PDF

Jul 10, 2026math.OC

Control Laguerre Tessellation: Semi-discrete Optimal Transport Over Control Systems

We study the optimal transport of optimally controlled agents from a compactly supported absolutely continuous source to a discrete target measure. The ground cost for the transport is induced by the optimal cost of the agents' motion. When this ground cost satisfies the twist condition, the optimal transport map is given almost everywhere in terms of a Laguerre tessellation of the state space. We refer to this control-theoretic generalization of Laguerre tessellation as Control Laguerre Tessellation (CLT), and illustrate it for two ground costs induced by linear controlled agents with minimum energy and minimum time objectives.

Ripon C. Sarker, Abhishek Halder

Optimal Transport Optimal Control Feedback Linearization Lagrangian Methods Polygons

Ask PDF

May 8, 2026cs.LG

The Reciprocity Gradient

Communication is fundamental to sustaining reciprocity and cooperation in strategic interactions. We identify and formulate the influence attribution problem as the central optimization difficulty inherent in such dynamics for a learning agent: any action or signal the agent emits reshapes the reputations of many third parties along combinatorially branching paths before feeding back into its own future rewards, forcing the agent to account for all of these indirect channels at once when choosing every action. To address this, we introduce the reciprocity gradient, which explicitly backpropagates reward gradients through private estimators of opponents' policies trained from public observations. The gradient flows through the reputation chain itself analytically, rather than being estimated from sampled returns. It jointly optimizes actions and evaluative signals without intrinsic rewards or reward shaping. Empirically, the method recovers near-optimal context-sensitive policies, while sample-based baselines collapse into constant-output policies.

Yue Lin, Pascal Poupart, Shuhui Zhu +5

Policy Gradient Reputation Collective Behaviors

Ask PDF