Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization
This addresses the challenge of scalable planning in large MDPs for reinforcement learning applications, though it appears incremental as it builds on existing assumptions like realizability and Bellman-closedness.
The paper tackles the problem of global planning in large Markov decision processes with linear function approximation by proposing a stochastic primal-dual optimization algorithm that outputs a near-optimal policy after a polynomial number of queries to the generative model, achieving computational efficiency without expensive runtime subroutines.
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.