# Adaptive Resolving Methods for Markov Decision Processes with Function Approximations

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 41 references that are in the map.
- First posted on arXiv 17 May 2025.

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

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient](https://mlsanity.com/paper/2210.06718/) (2022)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs](https://mlsanity.com/paper/2111.03289/) (2021)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design](https://mlsanity.com/paper/2207.02575/) (2022)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management](https://mlsanity.com/paper/1802.06192/) (2018)
- [Primal Beats Dual on Online Packing LPs in the Random-Order Model](https://mlsanity.com/paper/1311.2578/) (2013)
- [Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds](https://mlsanity.com/paper/2306.06836/) (2023)
- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards](https://mlsanity.com/paper/2303.05606/) (2023)
- [Towards Instance-Optimality in Online PAC Reinforcement Learning](https://mlsanity.com/paper/2311.05638/) (2023)
- [Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices](https://mlsanity.com/paper/2501.14155/) (2025)

## Abstract (arXiv)

Learning the optimal policy for Markov decision process problems (MDPs) from samples is a fundamental problem in online and data-driven decision-making. Function approximations are usually deployed to handle large or infinite state-action space. In our work, we consider the MDP problems with function approximation and we develop a new algorithm to solve it efficiently. Our algorithm is based on a linear programming (LP) reformulation and repeatedly resolves the identified reduced linear system as new transition samples arrive. After the optimal basis is identified, we show that, after N resolving rounds, the expected averaged iterate achieves an instance-dependent widetilde O(Cinst/N) objective shortfall and signed constraint residual. We separately account for the historical samples used for basis identification and the d2 transition queries used in each resolving round, which yields the corresponding total transition-query complexity. We further complement our result with a textitrobust O(1/√N) bound that is independent of Delta. In comparison to the guarantees established in the previous literature, our instance dependent guarantee is tighter when the underlying instance is favorable, and the numerical experiments also reveal the wide applications and efficient empirical performances of our algorithms.