  We propose a new stochastic primal-dual optimization algorithm for planning
in a large discounted Markov decision process with a generative model and
linear function approximation. Assuming that the feature map approximately
satisfies standard realizability and Bellman-closedness conditions and also
that the feature vectors of all state-action pairs are representable as convex
combinations of a small core set of state-action pairs, we show that our method
outputs a near-optimal policy after a polynomial number of queries to the
generative model. Our method is computationally efficient and comes with the
major advantage that it outputs a single softmax policy that is compactly
represented by a low-dimensional parameter vector, and does not need to execute
computationally expensive local planning subroutines in runtime.
