CAP-DO: Learning to warm-start game solving, cutting computation in security games

Many real-world security and inspection problems require solving a sequence of related zero-sum games—each with the same action space but different payoffs due to changing target values, costs, or inspection effectiveness. Standard Double Oracle (DO) solves large games by iteratively expanding a restricted game, but it must restart from scratch for each new context, rediscovering optimal actions through expensive full-space best responses. This inefficiency limits its use in repeated scenarios where contexts change rapidly.

CAP-DO overcomes this by learning to propose context-relevant actions. Offline, it trains separate defender and attacker rankers on previously solved game contexts. Online, these fixed rankers generate initial restricted action sets for each new context, effectively warm-starting the DO search. Crucially, the framework still relies on full-space best-response checks and a two-sided certificate for guaranteed convergence, preserving the same theoretical rigor as standard DO. In experiments on a non-additive inspection-game benchmark with up to 9,880 actions per player, CAP-DO achieved higher certification rates under fixed expansion budgets while using significantly fewer best-response calls than cold-start, trace-reuse, or heuristic warm-starts.