Provably Efficient Reinforcement Learning with Aggregated States

2019/12/13 by Dong, Shi, Van Roy, Benjamin, Zhou, Zhengyuan · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1912.06366

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 O(√(H⁵ M K) + εHK), where H is the horizon, M is the number of aggregate states, K is the number of episodes, and ε 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 ε, 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.

Cited by

• Commit to the Bit: Reactive Reinforcement Learning Done Right

Related

• Optimistic Q-learning for average reward and episodic reinforcement learning
• Selecting Near-Optimal Approximate State Representations in Reinforcement Learning
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Regret Bounds for Reinforcement Learning via Markov Chain Concentration
• Tail Distribution of Regret in Optimistic Reinforcement Learning