Ranked Prioritization of Groups in Combinatorial Bandit Allocation

Lily Xu, Arpita Biswas, Fei Fang, Milind Tambe

Abstract

This paper introduces a novel combinatorial multi-armed bandit (CMAB) framework designed to balance total reward maximization with the prioritization of specific groups based on ordinal rankings. In the context of wildlife conservation, this allows patrol planners to prioritize endangered species even when they reside in areas with lower overall poaching activity. By reformulating a complex ranking objective into a weighted linear sum, the authors developed RankedCUCB, an algorithm that achieves sub-linear regret and improves outcomes for endangered wildlife by up to 38% compared to standard approaches.

The Challenge: Beyond Total Reward Maximization

In wildlife conservation, ranger patrols are the primary defense against poaching. Planners typically use combinatorial bandits to allocate limited patrol hours across various locations. However, standard bandit algorithms often aim solely to maximize the total number of snares found (the reward).

This creates a "blind spot": if a patrol planner only targets high snare counts, they may inadvertently neglect regions where the most vulnerable species (like elephants) live, simply because those areas have lower total animal densities—and thus fewer total snares—than regions teeming with common species like wild pigs. Existing fairness models in bandit literature often fail to address the complex combinatorial allocations required for spatial patrolling.

Methodology

The authors propose a framework for Ranked Prioritization that moves beyond simple reward maximization.

  1. The Objective Function: They define a prioritization metric $\mathcal{P}(\beta)$ that measures how well an allocation aligns with a pre-defined ranking of species importance (e.g., Critically Endangered > Least Concern). Unlike traditional ranking coefficients, this metric is continuous and differentiable, making it suitable for optimization.
  2. Linear Reformulation: A key mathematical insight is the proof that the combined objective—balancing total reward and ranked prioritization—can be re-expressed as a weighted linear sum of the rewards at each location. This allows the problem to be solved efficiently using an Integer Linear Program (LP).
  3. RankedCUCB Algorithm: Building on the LIZARD algorithm, RankedCUCB uses Upper Confidence Bounds (UCB) to handle uncertainty. It incorporates Lipschitz continuity and monotonicity assumptions to speed up learning in spatial environments.
  4. Decaying Prioritization: To account for noisy early-round estimates, the algorithm uses a decaying parameter ($\epsilon_t$) to focus on pure reward maximization initially, gradually increasing the weight of prioritization as confidence in the species-location data grows.

Experimental Setup

The approach was evaluated using two primary sources:

  • Srepok Wildlife Sanctuary (Cambodia): Real-world data involving four species groups: elephants (Critically Endangered), banteng (Endangered), muntjac (Least Concern), and wild pigs (Least Concern).
  • Synthetic Dataset: A controlled environment with 5 groups across 25 locations to test robustness.
Spatial distribution of species groups and poaching risk in the Srepok Wildlife Sanctuary.

Key Results and Insights

The Pareto Frontier

The authors visualize a Pareto Frontier, showing the explicit tradeoff between total reward (snares found) and prioritization (protecting the right species). The results indicate that the curve is often steep: planners can achieve a massive gain in prioritization while sacrificing less than 10% of the total reward.

Performance Gains

RankedCUCB showed up to a 38% improvement in outcomes for endangered species compared to priority-blind baselines like LIZARD. It consistently outperformed "NaiveRank" approaches, which prioritize targets independently and ignore group-wide patterns.

Performance comparison across SREPOK and Synthetic datasets, illustrating the Pareto Frontier and regret convergence.

Theoretical Guarantees

The authors proved that RankedCUCB achieves asymptotic no-regret, meaning that over time, the algorithm's performance converges to the best possible fixed allocation strategy.

Conclusion and Future Work

This research demonstrates that "fairness" in conservation is not about equal treatment, but about equitable protection based on vulnerability. While the current model assumes known species distributions and disjoint groups, it provides a powerful foundation for resource allocation in high-stakes environments. Future work may explore overlapping species groups and non-linear conservation goals, such as maintaining minimum population thresholds to prevent ecological collapse.

Summary updated

BibTeX
@inproceedings{xu2022ranked,
  author = {Lily Xu and Arpita Biswas and Fei Fang and Milind Tambe},
  title = {{Ranked Prioritization of Groups in Combinatorial Bandit Allocation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/723},
}
Figure