  Q-functions are widely used in discrete-time learning and control to model
future costs arising from a given control policy, when the initial state and
input are given. Although some of their properties are understood, Q-functions
generating optimal policies for continuous problems are usually hard to
compute. Even when a system model is available, optimal control is generally
difficult to achieve except in rare cases where an analytical solution happens
to exist, or an explicit exact solution can be computed. It is typically
necessary to discretize the state and action spaces, or parameterize the
Q-function with a basis that can be hard to select a priori. This paper
describes a model-based algorithm based on generalized Benders theory that
yields ever-tighter outer-approximations of the optimal Q-function. Under a
strong duality assumption, we prove that the algorithm yields an arbitrarily
small Bellman optimality error at any finite number of arbitrary points in the
state-input space, in finite iterations. Under additional assumptions, the same
guarantee holds when the inputs are determined online by the algorithm's
updating Q-function. We demonstrate these properties numerically on scalar and
8-dimensional systems.
