💻 computer science

Learning Ordinal Response Policies in Rank-Based Stochastic Prize-Collecting Games

This paper introduces Stochastic Prize-Collecting Orienteering Games (SPCOG) to model competitive multi-agent routing, proposing the Ordinal Rank (OR) concept and the Fictitious Ordinal Response Learning (FORL) algorithm to demonstrate that policies conditioned on local ordinal information outperform global-rank approaches in terms of performance and generalization.

Original authors: Malintha Fernando, Petter Ögren, Silun Zhang

Published 2026-06-11

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Malintha Fernando, Petter Ögren, Silun Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A Game of "Grab the Bag"

Imagine a city where there are many bags of money scattered around. In a traditional team scenario (like a delivery company), all the drivers work together to grab as many bags as possible to help the company win. They coordinate perfectly so no one gets in each other's way.

But in the real world, drivers often work for themselves. They are self-interested. They want to grab the biggest bag for themselves, even if it means blocking someone else. This paper introduces a new way to plan routes for these selfish drivers, called SPCOG (Stochastic Prize-Collecting Orienteering Games).

The main problem is: How do you teach a group of selfish robots to move efficiently when they are competing for the same rewards, and the environment is unpredictable?

The Problem with "Global" Thinking

The researchers found that if you tell a robot, "You are the 5th most important robot in the whole city," it gets confused. The city is too big, and the robot can't see everything. It's like trying to navigate a crowded party by only knowing your name on a guest list, without knowing who is standing right next to you.

The Solution: "Ordinal Rank" (The Local VIP List)

The paper proposes a clever shortcut called Ordinal Rank (OR).

Instead of worrying about the whole city, a robot only cares about the immediate neighborhood it can reach in one step.

The Analogy: Imagine you are at a buffet. You don't need to know the seating chart of the entire restaurant. You only need to know: "Am I the first person in line at this specific food station? Or am I the second? Or the third?"
How it works: The robot looks at its immediate neighbors. If it is the "highest rank" (senior) among them, it grabs the best prize. If it is the "lowest rank" (junior), it knows it has to settle for the second-best prize because the senior robot will take the first one.

The paper claims that this "Local VIP List" is a much better way to teach robots than giving them a "Global VIP List" (knowing their rank among everyone in the world).

The Learning Algorithm: "Fictitious Ordinal Response" (FORL)

To teach the robots this behavior, the authors created a training method called FORL. Think of this as a very organized, turn-based rehearsal.

The Bootstrapping Phase: First, the "Boss" robot (Rank #1) learns how to play the game alone against random noise. Once the Boss is confident, it shares its "brain" with everyone else.
The Fictitious Play Phase: Then, the robots take turns learning.
- Robot #2 learns how to play against the Boss's fixed strategy.
- Robot #3 learns how to play against the Boss and Robot #2's fixed strategies.
- And so on.
The Entropy Rule: The training uses a "confidence meter" (entropy). If a robot is guessing wildly (low confidence), it keeps training. Once it becomes very confident in its moves (high confidence), it stops learning that specific part and moves on.

This method ensures that the robots eventually find a stable state where no one wants to change their strategy because they are doing the best they can given what the others are doing.

What Did They Find?

The researchers tested this on real road maps (like Stockholm and Manhattan) with simulated traffic and prizes.

Better than Global Knowledge: Robots trained with the "Local VIP List" (Ordinal Rank) performed much better than robots trained with the "Global List." They were faster to learn and made fewer mistakes.
Scaling Up: When they added more and more robots to the game (up to 25), the "Local VIP List" method kept working smoothly. The "Global List" method fell apart and became chaotic as the group got bigger.
Near-Perfect Results: Even though the robots were selfish and competing, they managed to collect about 95% of the total money that a perfectly cooperative team (who shared all secrets) would have collected.

The Bottom Line

This paper shows that in a chaotic, competitive world, you don't need to know everything about the whole system to make good decisions. You just need to know your local rank among the people immediately around you. By teaching robots to focus on their immediate neighbors rather than the whole world, they can learn to compete efficiently and reach a stable, high-performing outcome.

Technical Summary: Learning Ordinal Response Policies in Rank-Based Stochastic Prize-Collecting Games

1. Problem Definition

The paper addresses the limitations of the Team Orienteering Problem (TOP) in multi-agent systems. While TOP provides a unified framework for cooperative routing (e.g., last-mile delivery, surveillance) where agents maximize a collective utility under travel budgets, it fails to model scenarios involving self-interested agents competing in resource-scarce environments. In such settings, agents (e.g., competing delivery fleets or crowd-sourced drivers) prioritize individual rewards over collective gain, and their interactions are governed by stochastic transitions and energy constraints.

To bridge this gap, the authors propose the Stochastic Prize-Collecting Orienteering Game (SPCOG). In an SPCOG:

Agents operate on a weighted graph with stochastic prize distributions at nodes.
Agents have individual travel budgets and aim to maximize their own cumulative rewards.
Conflict Resolution: When multiple agents visit the same node simultaneously, a rank-based rule applies: the agent with the highest global rank (lowest index) claims the prize entirely; others receive zero.
Objective: Find convergent policies for independent agents to maximize individual rewards, acknowledging that the total team reward may be lower than the cooperative TOP optimum due to competition.

2. Methodology

Theoretical Analysis of Equilibria
The authors first analyze the existence of a Pure Nash Equilibrium (PNE) in SPCOGs:

Complete Graphs: They prove that for complete graphs, a unique PNE exists under rank-based conflict resolution. In this equilibrium, the $i$ -th ranked agent selects the $i$ -th largest available prize. The total reward in this PNE coincides with the optimal solution of an equivalent cooperative TOP.
Star Graphs: A similar unique PNE exists where agents move to the $i$ -th largest prize in alternating stages.
Arbitrary Graphs: The paper demonstrates via counter-example (a specific two-agent scenario) that a PNE does not necessarily exist for arbitrary graph structures when agents move simultaneously, highlighting the complexity of solving these games compared to Stackelberg (leader-follower) formulations.

Ordinal Rank (OR) Concept
To address the challenge of partial observability and the exponential state space in general graphs, the authors introduce Ordinal Rank (OR):

Immediate Opponents: Agents are grouped into "localized stage games" based on a "separating graph" where edges connect agents with overlapping reachable sets.
Definition: An agent's OR is defined as $1 +$ the number of agents with a higher global rank (lower index) within its immediate neighborhood (connected component).
Significance: OR summarizes the most influential local competition. The authors hypothesize that conditioning policies on OR, rather than global state or global rank, acts as a strong inductive bias, allowing agents to learn best responses to immediate opponents without requiring global information.

Fictitious Ordinal Response Learning (FORL)
The authors propose FORL, an entropy-regulated learning algorithm designed for independent multi-agent reinforcement learning (MARL):

Sequential Updates: Agents update their policies sequentially based on their rank. Higher-ranked agents update first, assuming lower-ranked agents follow random or stationary policies.
Bootstrapping: The highest-ranked agent learns first to solve the underlying stochastic single-agent problem. Once its policy reaches a confidence threshold (measured by entropy), its parameters are shared with others.
Fictitious Play: Subsequent agents update their policies by playing against the "stationary" policies of higher-ranked agents.
Entropy Regulation: The algorithm uses a decaying entropy threshold ( $H_{stop}$ ) to ensure convergence. If a PNE exists, the algorithm converges to a pure strategy (entropy $\to$ 0); otherwise, it provides confidence bounds on the quality of the mixed-strategy policy.
Policy Architecture: Policies are modeled using a Transformer-based architecture (TRXL-I) and are conditioned on local observations augmented with the OR. Action masking is used to enforce graph constraints.

3. Key Contributions

SPCOG Formulation: Introduction of a game-theoretic variant of the TOP for self-interested agents in stochastic, energy-constrained environments.
Theoretical Guarantees: Proof of a unique PNE on complete and star graphs that aligns with the optimal TOP solution, and a counter-example showing the non-existence of PNEs on arbitrary graphs.
Ordinal Rank (OR): Proposal of OR as a concise, local representation of an agent's competitive standing, which serves as a strong inductive bias for learning.
FORL Algorithm: Development of an entropy-regulated, fictitious-play-inspired algorithm that yields convergent policies in independent learning settings.
Empirical Validation: Demonstration that OR-conditioned policies outperform global-rank conditioned policies in terms of generalizability, scalability, and training efficiency.

4. Experimental Results

Experiments were conducted on real-world road networks (Stockholm and Manhattan) with static and dynamic prize distributions.

Performance vs. TOP: In complete graphs, OR-conditioned policies achieved 95% of the optimal TOP reward. In incomplete graphs, the worst-case equilibrium achieved 87% of the optimal solution.
Generalizability: Policies trained with FORL and OR conditioning demonstrated superior "zero-shot" transfer capabilities to imbalanced, demand-driven prize distributions compared to Independent Policy Learning (IPL) and parameter-sharing methods conditioned on global state.
Scalability: When scaling to teams of up to 25 agents, policies conditioned on OR (PS-OR) showed linear scaling in total reward with low variance. In contrast, policies conditioned on global rank (PS-GR) exhibited sublinear gains and significantly higher variance.
Efficiency: The FORL method required 1.56x to 2.2x less training time to reach comparable reward profiles compared to standard parameter-sharing and independent learning baselines.

5. Significance and Claims

The paper claims that the Ordinal Rank concept effectively decouples the need for global state information in multi-agent routing games. By focusing on the local "immediate opponents" and their relative ranks, agents can learn robust strategies that generalize well to larger team sizes and unseen environments.

The authors assert that FORL provides a practical mechanism for obtaining convergent policies in competitive, stochastic routing games where traditional cooperative assumptions fail. The work suggests that in rank-based conflict scenarios, local information conditioned on ordinal position is a more effective learning signal than global state or global rank, offering a scalable solution for heterogeneous, self-interested robotic fleets.