Cloud elasticity, i.e., the dynamic allocation of resources to applications to meet fluctuating workload demands, has been one of
the greatest challenges in cloud computing. Approaches based on
reinforcement learning have been proposed but they require a large
number of states in order to model complex application behavior. In
this work we propose a novel reinforcement learning approach that
employs adaptive state space partitioning. The idea is to start from
one state that represents the entire environment and partition this
into finer-grained states adaptively to the observed workload and
system behavior following a decision-tree approach. We explore
novel statistical criteria and strategies that decide both the correct
parameters and the appropriate time to perform the partitioning.