mlsanityData to 14 Oct 2026

Adaptive Resolving Methods for Markov Decision Processes with Function Approximations

arXiv 2505.12037 ↗First posted 17 May 2025cs.LGcited by 0

Not on the map. Why?

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.

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

17 of 41 references.

References · 17

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 161
  4. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  5. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  6. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  7. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  8. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  9. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  10. 2019Online Linear Programming: Dual Convergence, New Algorithms, and Regret Boundscited by 32
  11. 2018A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Managementcited by 18
  12. 2013Primal Beats Dual on Online Packing LPs in the Random-Order Modelcited by 17
5 more
  1. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 14
  2. 2022Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributionscited by 13
  3. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  4. 2023Towards Instance-Optimality in Online PAC Reinforcement Learningcited by 7
  5. 2025Learning to Price with Resource Constraints: From Full Information to Machine-Learned Pricescited by 3

Built on by

Not cited yet.