Ranked Prioritization of Groups in Combinatorial Bandit Allocation

Lily Xu, Arpita Biswas, Fei Fang, Milind Tambe

TL;DR

Standard combinatorial bandit algorithms optimize for total reward, but in wildlife conservation, finding the most poacher snares shouldn't come at the expense of ignoring critically endangered species. This paper introduces RankedCUCB, a novel bandit algorithm that balances reward maximization with ranked group prioritization. Tested on real-world anti-poaching data, it improves conservation outcomes for endangered species by up to 38% while maintaining theoretical no-regret guarantees.

What Problem Does This Paper Address?

Ranger patrols are a vital line of defense against illegal poaching in protected wildlife areas. To deploy limited ranger resources efficiently, conservationists often use multi-armed bandit (MAB) frameworks—specifically combinatorial bandits—to learn which locations yield the highest probability of detecting poacher snares.

However, traditional algorithms have a major blind spot: they treat all rewards equally. In the wild, different locations are home to different species in varying proportions. If an algorithm only maximizes the total number of snares found, it naturally prioritizes areas with high densities of abundant species (like wild pigs or muntjacs), because that is where poachers place the most snares. Unfortunately, this leaves rarer, critically endangered species (like elephants) severely unprotected if they happen to live in lower-risk or different areas.

Figure 1: Animal density distributions and poaching risk (expected number of snares) across a 10 × 10 km region in Srepok Wildlife Sanctuary, Cambodia. The distribution of the species of greatest conservation concern, the elephant, differs from that of other ani- mals and overall poaching risk.

As shown in Figure 1, the spatial distribution of elephants in Cambodia's Srepok Wildlife Sanctuary does not align with the overall poaching risk map. This paper addresses this gap by introducing a way to mathematically prioritize vulnerable groups within a combinatorial bandit framework.

Methods

The authors formulate the problem as a combinatorial bandit allocation with $N$ locations and $G$ groups (species), where an ordinal priority ranking of the groups is known (e.g., from the IUCN Red List).

The core technical contributions include:

  1. A Continuous Prioritization Metric: Instead of using standard ranking correlation coefficients like Kendall's tau—which are discontinuous and difficult to optimize—the authors construct a smooth, differentiable function, $\mathcal{P}(\vec{\beta})$, that quantifies how well a patrol allocation aligns with the desired species priority ranking.
  2. Linear Reformulation: The authors prove that the combined objective—balancing total reward and ranked prioritization using a tuning parameter $\lambda$—can be re-expressed as a weighted linear sum of the rewards at individual locations. This decomposability is a massive win because it allows the optimal action to be found efficiently using an Integer Linear Program (ILP).
  3. The RankedCUCB Algorithm: To handle the exploration-exploitation tradeoff, the algorithm uses an Upper Confidence Bound (UCB) approach. Crucially, it incorporates a decaying parameter ($\epsilon_t \sim t^{-1/3}$) to discount the weight of the prioritization metric in early rounds. This prevents the algorithm from making bad, aggressive prioritization decisions when its underlying reward estimates are still highly uncertain.

Datasets

The algorithm was evaluated on two datasets:

  • Srepok Wildlife Sanctuary Dataset: Real-world species density and poaching data from Cambodia, featuring 4 groups ranked by endangerment level: elephants (critically endangered), banteng (endangered), muntjac (least concern, decreasing), and wild pig (least concern), distributed across 25 locations.
  • Synthetic Dataset: A broader benchmark featuring 5 groups randomly distributed across locations to test the algorithm's scalability and robustness.

Key Insights and Ideas

  • The Danger of Pure Reward Maximization: The paper highlights that standard reward-maximizing algorithms (like LIZARD) can actually perform worse than random when it comes to protecting prioritized species. By blindly chasing the highest snare counts, they over-allocate resources to common-species zones.
  • Information-Aware Prioritization: You cannot enforce fair or ranked prioritization if your data is garbage. By using a decaying epsilon strategy, RankedCUCB elegantly prioritizes pure exploration/learning early on and gradually enforces strict species prioritization as its confidence in the environment increases.
  • Algorithmic Efficiency: Reducing a complex, multi-group ranking objective down to a decomposable linear program means this approach doesn't sacrifice computational feasibility for ethical alignment.

Key Results

  • Endangered Species Protection: RankedCUCB achieved up to a 38% improvement in conservation outcomes for endangered species compared to traditional approaches.
  • Pareto Frontier Efficiency: As visualized in Figure 2 (right), RankedCUCB effectively maps out the Pareto frontier between reward and prioritization. It allows managers to strategically sacrifice a tiny fraction of total reward (less than 10%) to achieve a massive, two-fold increase in prioritization accuracy.
  • Theoretical Guarantees: The authors prove that RankedCUCB achieves sub-linear cumulative regret, meaning that over time, its performance asymptotically approaches the optimal strategy in hindsight.
Figure 2: The performance of each approach. LEFT evaluates the objective with tuning parameter λ = 0.3 and λ = 0.8. Our approach, RankedCUCB, performs significantly better than baselines. CENTER evaluates reward and prioritization (at λ = 0.8), the two components of the combined objective. The reward-maximizing LIZARD algorithm rapidly maximizes reward but performs worse than random in terms of rank order. RIGHT visualizes the Pareto frontier trading off the two components of our objective. Labels represent different values of λ ∈{0.1, 0.2, . . . , 1.0}. Each point plots the reward and ranked prioritization as the average of the final 10 timesteps. All results are averaged over 30 random seeds and smoothed with an exponential moving average.

Limitations and Future Work

While highly effective, the model operates under a few simplifying assumptions:

  • Coarse Ordinal Rankings: The model relies on simple ordinal rankings ($1, 2, \dots, G$). While the authors show how to extend this to weighted rankings, obtaining exact weights from domain experts can be challenging.
  • Uniform Benefit Assumption: The framework assumes that a patrol at a specific location benefits all species present there equally. In reality, poachers might use specific snare types that target certain species over others.

The authors note that this framework is highly generalizable and can easily be adapted to other critical resource-allocation domains facing similar group-fairness challenges, such as preventing illegal logging, managing overfishing, or distributing healthcare resources.

Summary updated

Abstract

Preventing poaching through ranger patrols protects endangered wildlife, directly contributing to the UN Sustainable Development Goal 15 of life on land. Combinatorial bandits have been used to allocate limited patrol resources, but existing approaches overlook the fact that each location is home to multiple species in varying proportions, so a patrol benefits each species to differing degrees. When some species are more vulnerable, we ought to offer more protection to these animals; unfortunately, existing combinatorial bandit approaches do not offer a way to prioritize important species. To bridge this gap, (1) We propose a novel combinatorial bandit objective that trades off between reward maximization and also accounts for prioritization over species, which we call ranked prioritization. We show this objective can be expressed as a weighted linear sum of Lipschitz-continuous reward functions. (2) We provide RankedCUCB, an algorithm to select combinatorial actions that optimize our prioritization-based objective, and prove that it achieves asymptotic no-regret. (3) We demonstrate empirically that RankedCUCB leads to up to 38% improvement in outcomes for endangered species using real-world wildlife conservation data. Along with adapting to other challenges such as preventing illegal logging and overfishing, our no-regret algorithm addresses the general combinatorial bandit problem with a weighted linear objective.
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