# Primal-dual regression approach for Markov decision processes with general state and action space

arXiv: https://arxiv.org/abs/2210.00258 · HTML: https://mlsanity.com/paper/2210.00258/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 29 references that are in the map.
- First posted on arXiv 1 Oct 2022.

## Builds on (most cited first, 4 of 4)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models](https://mlsanity.com/paper/1602.06346/) (2016)
- [Solving the Dual Problems of Dynamic Programs via Regression](https://mlsanity.com/paper/1610.07726/) (2016)

## Built on by (most cited first, 1 of 1)

- [Weighted mesh algorithms for general Markov decision processes: Convergence and tractability](https://mlsanity.com/paper/2407.00388/) (2024)

## Abstract (arXiv)

We develop a regression based primal-dual martingale approach for solving finite time horizon MDPs with general state and action space. As a result, our method allows for the construction of tight upper and lower biased approximations of the value functions, and, provides tight approximations to the optimal policy. In particular, we prove tight error bounds for the estimated duality gap featuring polynomial dependence on the time horizon, and sublinear dependence on the cardinality/dimension of the possibly infinite state and action space.From a computational point of view the proposed method is efficient since, in contrast to usual duality-based methods for optimal control problems in the literature, the Monte Carlo procedures here involved do not require nested simulations.