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}MK}+\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.

References in corpus (8)

• (More) Efficient Reinforcement Learning via Posterior Sampling
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Deep Exploration via Randomized Value Functions
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• A Theoretical Analysis of Deep Q-Learning
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration

Cited by in corpus (6)

• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Randomized Value Functions via Posterior State-Abstraction Sampling
• Reinforcement Learning with Feedback Graphs
• Improved Algorithms for Misspecified Linear Markov Decision Processes