Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization
Abstract
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.
Cite
Text
Neu and Okolo. "Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization." Proceedings of The 34th International Conference on Algorithmic Learning Theory, 2023.Markdown
[Neu and Okolo. "Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization." Proceedings of The 34th International Conference on Algorithmic Learning Theory, 2023.](https://mlanthology.org/alt/2023/neu2023alt-efficient/)BibTeX
@inproceedings{neu2023alt-efficient,
title = {{Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization}},
author = {Neu, Gergely and Okolo, Nneka},
booktitle = {Proceedings of The 34th International Conference on Algorithmic Learning Theory},
year = {2023},
pages = {1101-1123},
volume = {201},
url = {https://mlanthology.org/alt/2023/neu2023alt-efficient/}
}