Minimax Optimistic Planning for Continuous-Action Noncooperative Sequential Control

We consider problems in which two competing agents influence in turn a dynamical system using continuous, scalar actions. One agent seeks to maximize an infinite-horizon value, while the other aims to minimize it, leading to a sequential noncooperative game. To search for the minimax-optimal solution, we introduce Minimax Optimistic Planning for Continuous actions (MOPC), an algorithm that iteratively refines the most promising regions of the space of action sequences. Our analysis shows that MOPC provides computable bounds on the solution quality, and that these bounds converge as computation grows at rates driven by a measure of problem complexity. We show how to pose in our framework – and thereby near-optimally solve – a class of problems in which opinions in a social network are influenced by two competing marketers. In experiments on such problems, MOPC outperforms uniform allocation over time.