Non-stationary Reinforcement Learning Under General Function Approximation

Abstract

General function approximation is a powerful tool to handle large state and action spaces in a broad range of reinforcement learning (RL) scenarios. However, theoretical understanding of non-stationary MDPs with general function approximation is still limited. In this paper, we make the first such an attempt. We first propose a new complexity metric called dynamic Bellman Eluder (DBE) dimension for non-stationary MDPs, which subsumes majority of existing tractable RL problems in static MDPs as well as non-stationary MDPs. Based on the proposed complexity metric, we propose a novel confidence-set based model-free algorithm called SW-OPEA, which features a sliding window mechanism and a new confidence set design for non-stationary MDPs. We then establish an upper bound on the dynamic regret for the proposed algorithm, and show that SW-OPEA is provably efficient as long as the variation budget is not significantly large. We further demonstrate via examples of non-stationary linear and tab

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyfeng2023non

Related papers

• SBEED: Convergent Reinforcement Learning With Nonlinear Function Approximation (2017)0.00
• Prior-dependent Analysis Of Posterior Sampling Reinforcement Learning With Function Approximation (2024)0.00
• Nonstationary Reinforcement Learning With Linear Function Approximation (2020)0.00
• Provably Efficient Cooperative Multi-agent Reinforcement Learning With Function Approximation (2021)0.00
• Online Sub-sampling For Reinforcement Learning With General Function Approximation (2021)0.00
• Distributionally Robust Off-dynamics Reinforcement Learning: Provable Efficiency With Linear Function Approximation (2024)0.00
• Provably Efficient Reinforcement Learning With Linear Function Approximation (2019)11.76
• A Nearly Optimal And Low-switching Algorithm For Reinforcement Learning With General Function Approximation (2023)0.00