PAC Learnability of Scenario Decision-Making Algorithms: Necessary Conditions and Sufficient Conditions
This work addresses the theoretical foundations of safety-critical decision-making algorithms, providing insights for algorithm designers and users in fields like robotics and control, though it is incremental in extending PAC theory to scenario-based methods.
The paper tackles the problem of determining necessary and sufficient conditions for scenario decision-making algorithms to be Probably Approximately Correct (PAC), showing through counterexamples that existing sufficient conditions like VC dimension finiteness are not necessary, and introduces a new dVC dimension as a necessary condition.
We investigate the Probably Approximately Correct (PAC) property of scenario decision algorithms, which refers to their ability to produce decisions with an arbitrarily low risk of violating unknown safety constraints, provided a sufficient number of realizations of these constraints are sampled. While several PAC sufficient conditions for such algorithms exist in the literature -- such as the finiteness of the VC dimension of their associated classifiers, or the existence of a compression scheme -- it remains unclear whether these conditions are also necessary. In this work, we demonstrate through counterexamples that these conditions are not necessary in general. These findings stand in contrast to binary classification learning, where analogous conditions are both sufficient and necessary for a family of classifiers to be PAC. Furthermore, we extend our analysis to stable scenario decision algorithms, a broad class that includes practical methods like scenario optimization. Even under this additional assumption, we show that the aforementioned conditions remain unnecessary. Furthermore, we introduce a novel quantity, called the dVC dimension, which serves as an analogue to the VC dimension for scenario decision algorithms. We prove that the finiteness of this dimension is a PAC necessary condition for scenario decision algorithms. This allows to (i) guide algorithm users and designers to recognize algorithms that are not PAC, and (ii) contribute to a comprehensive characterization of PAC scenario decision algorithms.