Classical model-free control treats the optimal action-value function Q* as the fixed point of the Bellman optimality operator and chases it by stochastic approximation. This talk develops a different view: Q* is the unique minimizer of an exact, unregularized linear program whose constraints are the Bellman inequalities, and a single agent–environment trajectory is a stream of sampled rows of that program. Learning Q* then becomes an instance of Constrained Online Convex Optimization (COCO), which we solve with a drift-plus-penalty algorithm that maintains one virtual queue of accumulated Bellman violations per state–action pair.
We show the time-averaged table converges to Q* from a single Markovian trajectory. The reduction is modular and any optimizer meeting a regret/violation/movement interface plugs in.
