Discretization of Continuous Action Spaces in Extensive-Form Games

Extensive-form games are a powerful tool for modeling a large range of multiagent scenarios. However, most solution algorithms require discrete, finite games. In contrast, many real-world domains require modeling with continuous action spaces. This is usually handled by heuristically discretizing the continuous action space without solution quality bounds. In this paper we address this issue. Leveraging recent results on abstraction solution quality, we develop the first framework for providing bounds on solution quality for discretization of continuous action spaces in extensive-form games. For games where the error is Lipschitz-continuous in the distance of a continuous point to its nearest discrete point, we show that a uniform discretization of the space is optimal. When the error is monotonically increasing in distance to nearest discrete point, we develop an integer program for finding the optimal discretization when the error is described by piecewise linear functions. This result can further be used to approximate optimal solutions to general monotonic error functions. Finally we discuss how our theory applies to several practical problems for which no solution quality bounds could be derived before.