Adaptive Resolving Methods for Reinforcement Learning with Function Approximations

2025/05/17 by Jiashuo Jiang, Jiang, Jiashuo, Yiming Zong +3
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Age of Information Optimization #FOS: Computer and information sciences #Machine Learning (cs.LG) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2505.12037

openalex publication_date 2025/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Reinforcement learning (RL) problems are fundamental in online decision-making and have been instrumental in finding an optimal policy for Markov decision processes (MDPs). Function approximations are usually deployed to handle large or infinite state-action space. In our work, we consider the RL problems with function approximation and we develop a new algorithm to solve it efficiently. Our algorithm is based on the linear programming (LP) reformulation and it resolves the LP at each iteration improved with new data arrival. Such a resolving scheme enables our algorithm to achieve an instance-dependent sample complexity guarantee, more precisely, when we have N data, the output of our algorithm enjoys an instance-dependent O(1/N) suboptimality gap. In comparison to the O(1/√(N)) worst-case guarantee established in the previous literature, our instance-dependent guarantee is tighter when the underlying instance is favorable, and the numerical experiments also reveal the efficient empirical performances of our algorithms.

Related

• A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Online Model Selection for Reinforcement Learning with Function Approximation
• Computational-Statistical Gaps in Reinforcement Learning