Provably Efficient Reinforcement Learning With Aggregated States

Abstract

We establish that an optimistic variant of Q-learning applied to a fixed-horizon episodic Markov decision process with an aggregated state representation incurs regret \(\tilde\{\mathcal\{O\}\}(\sqrt\{H^5 M K\} + \epsilon HK)\), where \(H\) is the horizon, \(M\) is the number of aggregate states, \(K\) is the number of episodes, and \(\epsilon\) is the largest difference between any pair of optimal state-action values associated with a common aggregate state. Notably, this regret bound does not depend on the number of states or actions and indicates that asymptotic per-period regret is no greater than \(\epsilon\), independent of horizon. To our knowledge, this is the first such result that applies to reinforcement learning with nontrivial value function approximation without any restrictions on transition probabilities.

Stats

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

Related papers

• Beyond Value-function Gaps: Improved Instance-dependent Regret Bounds For Episodic Reinforcement Learning (2021)0.00
• Logarithmic Regret For Episodic Continuous-time Linear-quadratic Reinforcement Learning Over A Finite-time Horizon (2020)7.81
• Provably Efficient And Agile Randomized Q-learning (2025)0.00
• Logarithmic Regret Of Exploration In Average Reward Markov Decision Processes (2025)0.00
• Online Learning In Unknown Markov Games (2020)0.00
• First-order Regret In Reinforcement Learning With Linear Function Approximation: A Robust Estimation Approach (2021)0.00
• Approximation Benefits Of Policy Gradient Methods With Aggregated States (2020)0.00
• Value Function Approximations Via Kernel Embeddings For No-regret Reinforcement Learning (2020)0.00