Single-partition adaptive Q-learning

Abstract

This paper introduces single-partition adaptive Q-learning (SPAQL), an algorithm for model-free episodic reinforcement learning (RL), which adaptively partitions the state-action space of a Markov decision process (MDP), while simultaneously learning a time-invariant policy (i. e., the mapping from states to actions does not depend explicitly on the episode time step) for maximizing the cumulative reward. The trade-off between exploration and exploitation is handled by using a mixture of upper confidence bounds (UCB) and Boltzmann exploration during training, with a temperature parameter that is automatically tuned as training progresses. The algorithm is an improvement over adaptive Q-learning (AQL). It converges faster to the optimal solution, while also using fewer arms. Tests on episodes with a large number of time steps show that SPAQL has no problems scaling, unlike AQL. Based on this empirical evidence, we claim that SPAQL may have a higher sample efficiency than AQL, thus being a relevant contribution to the field of efficient model-free RL methods.

34 pages, 15 figures

References in corpus (7)

• Trust Region Policy Optimization
• Dota 2 with Large Scale Deep Reinforcement Learning
• Algorithms for multi-armed bandit problems
• Cyclical Annealing Schedule: A Simple Approach to Mitigating KL Vanishing
• Snapshot Ensembles: Train 1, get M for free
• Efficient Model-free Reinforcement Learning in Metric Spaces
• Zooming for Efficient Model-Free Reinforcement Learning in Metric Spaces

Cited by in corpus (2)

• Adaptive Discretization in Online Reinforcement Learning
• Control with adaptive Q-learning